java中HashMap的扩容机制怎么实现?实例展示

BSO 2020-11-30 15:18:04 java常见问答 7784

想要学好java编程语言,就需要花费大量的时间和精力,去了解相关的基础知识。java中关于HashMap的内容是非常多的,不知道你都了解了吗?一起来巩固一下吧。

首先说一下,扩容机制的实现

一、扩容(resize)就是重新计算容量。当向HashMap对象里不停的添加元素,而HashMap对象内部的桶数组无法装载更多的元素时,HashMap对象就需要扩大桶数组的长度,以便能装入更多的元素。

二、capacity就是数组的长度/大小,loadFactor是这个数组填满程度的最大比比例。

三、size表示当前HashMap中已经储存的Node的数量,包括桶数组和链表/红黑树中的的Node

四、threshold表示扩容的临界值,如果size大于这个值,则必需调用resize()方法进行扩容。

五、在jdk1.7及以前,threshold=capacity * loadFactor,其中capacity为桶数组的长度。 这里需要说明一点,默认负载因子0.75是是对空间和时间(纵向横向)效率的一个平衡选择,建议大家不要修改。 jdk1.8对threshold值进行了改进,通过一系列位移操作算法最后得到一个power of two size的值

什么时候扩容?

另外,当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值—即当前数组的长度乘以加载因子的值的时候,就要自动扩容啦。

还有就是,扩容必须满足两个条件:

一、存放新值的时候 当前已有元素的个数(size)必须大于等于阈值

二、存放新值的时候当前存放数据发生hash碰撞(当前key计算的hash值换算出来的数组下标位置已经存在值)

如果计算的哈希位置有值(及hash冲突),且key值一样,则覆盖原值value,并返回原值value,实例代码如下所示:

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
{
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
}

resize()方法: 该函数有2种使用情况1.初始化哈希表 2.当前数组容量过小,需扩容

过程:

HashMap是先插入数据再进行扩容的,但是如果是刚刚初始化容器的时候是先扩容再插入数据。

插入键值对时发现容量不足,调用resize()方法方法,

1.首先进行异常情况的判断,如是否需要初始化,二是若当前容量最大值则不扩容,

2.然后根据新容量(是就容量的2倍、)新建数组,将旧数组上的数据(键值对)转移到新的数组中,这里包括:(遍历旧数组的每个元素,重新计算每个数据在数组中的存放位置。(原位置或者原位置+旧容量),将旧数组上的每个数据逐个转移到新数组中,这里采用的是尾插法。)

3.新数组table引用到HashMap的table属性上

4.最后重新设置扩容阙值。

关于实现java中HashMap的扩容机制方法还是有一点复杂的,需要大家实际操作看看。大家平时也可以多积累一些相关知识。想要了解更多java实例,敬请关注奇Q工具网。

推荐阅读:

hashmap面试题汇总

hashmap的实现原理和hashset的实现原理是什么?

hashmap和hashtable区别是什么?有什么区别?