HashMap容量和负载因子使用说明

HashMap容量和负载因子使用说明

HashMap底层数据结构是数组+链表，JDK1.8中还引入了红黑树，当链表长度超过8个时，会将链表转成红黑树，以提升其查找性能。

那么，给出一个节点，HashMap是如何确定这个节点应该放在具体哪个位置呢？（以JDK1.8为例）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node[] tab; Node p; int n, i;

// HashMap没有被初始化，则先进行初始化

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// 节点所在index = (n - 1) & hash，该位置没有数据，则直接将新节点放在数组的index位置上

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else { // index上已经有节点了

Node e; K k;

// 如果新key与原来的key一样，则e指向原节点p（后面会用新value替换e所指向的value）

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

// 如果该节点是树节点，则采用树的插入算法，插入新节点

else if (p instanceof HashMap.TreeNode)

e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

else { // 该节点HHFiJZ是链表节点

for (int binCount = 0; ; ++binCount) {

// 将新节点插入到index所在链表的末端

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

// 链表节点超过8个，则进行链表转树处理

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

// 同样的，如果key已经存在的话，则不进行插入操作，而是后面进行value替换

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

}

// e != null的情况，就是key已经存在了，这里统一进行了新值value，替换旧值e.value的操作

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

// 插入后数组size 大于阈值的话，需要进行扩容

if (++size > threshold)

resize();

afterNohttp://deInsertion(evict);

return null;

}

看源码，节点落在数组中的index = （数组长度 - 1） & key的hashcode，如果该index上没有数据，则直接插到该index上，如果节点已经有数据了，则把新节点插入该index对应的链表中（如果链表节点大于8个，会进行链表转树，之后的插入算法就变成了树的插入算法）。

每次put之后，会检测一下是否需要扩容，size超过了 总容量 * 负载因子，则会扩容。默认情况下，16 * 0.75 = 12个。

1、为什么初始容量是16

当容量为2的幂时，上述n -1 对应的二进制数全为1，这样才能保证它和key的hashcode做&运算后，能够均匀分布，这样才能减少hash碰撞的次数。至于默认值为什么是16，而不是2 、4、8，或者32、64、1024等，我想应该就是个折中处理，过小会导致放不下几个元素，就要进行扩容了，而扩容是一个很消耗性能的操作。取值过大的话，无疑会浪费更多的内存空间。因此在日常开发中，如果可以预估HashMap会存入节点的数量，则应该在初始化时，指定其容量。

2、为什么负载因子是0.75

也是一个综合考虑，如果设置过小，HashMap每put少量的数据，都要进行一次扩容，而扩容操作会消耗大量的性能。如果设置过大的话，如果设成1，容量还是16，假设现在数组上已经占用的15个，再要put数据进来，计算数组index时，发生hash碰撞的概率将达到15/16，这违背的HashMap减少hash碰撞的原则。

补充知识：HashMap只有容量达到阀值才发生扩容吗？大错特错！

看了网上很多文章，说HashMap在元素达到负载因子对应数的时候就发生扩容。如果你看过源码就会发现，其实还有一种情况也可http://能会发生扩容：树形化的时候。

对象最终是如何放入HashMap中的?

HashMap底层是由数组+链表组成的，为了方便不懂的人更容易理解，那我们就先假设HashMap底层就是数组，先不管链表。

当一个对象add到HashMap中，此时HashMap的add方法是如何来确定这个对象是放在数组中的哪个位置的呢？

拿JDK1.8来说（其他JDK版本稍有不同，但大同小异）,大家应该知道每一个对象天生都继承了或程序员自己覆盖了Object类的 hashCode（）方法，此方法返回对象的hashcode值。

HashMap会有一个方法，先拿到要add进HashMap中的对象的hashCode，再将这个hashCode异或上对象自身hashCode右移16位（是不是感觉说的不是人话？这个步骤叫扰乱，这样做的目的是为了让hashCode每一位都尽可能用到，如果不理解没关系并不影响接下来的阅读），hashCode经过上述步骤之后再&（数组长度-1），计算的结果就是这个对象在数组中的位置了。我自己都觉得说的不是人话，下面举个例子，便于理解：

这里有一个Student对象的hashCode是：a

先把这个a右移16位 ， b=a>>>16;

然后a=a&b;

数组中的位置等于: a&(数组长度-1)；

上述源码如下：

h=key.hashCode();

h = key.hashCode()) ^ (h >>> 16）

数组位置=h&(数组长度-1)；

好了， 我们已经知道元素是如何在hashMap中的数组上如何定位了，现在假设一个极端情况（不可能发生，但是我用这个举例子）:

假设数组长度为1，根据源码：

数组位置=h&（数组长度-1）

那么有：

数组位置=h&（1-1）=0 ，无论什么对象，都定位到数组的第0个位置。

这个很好理解吧。无论元素是否一样，由于数组长度为1，所以元素通通定位到数组中第0个位置。大家都知道一个数组只能放一个元素啊？那怎么办呢？我们用链表来解决这个问题，把定位到这个位置的元素通过链表连接。这就是我一开始说的：hashMap是数组+链表。

那树形化又是什么东东呢？

想一下我们为什么要用HashMap，是因为通过Hash算法在理想情况下时间复杂度O(1)就能找到元素，特别快，但是我都说了是理想情况，如果遇到上述发生hash碰撞（谁jb取的名字，就是上面我才说的，两个元素定位到数组中同一个位置），且hash碰撞比较频繁的话，那么当我们get一个元素的时候，定位到了这个数组，还需要在数组中遍历一次链表最终才能找到要get的元素，是不是已经失去一部分使用HashMap的初心了？（因为需要遍历链表，所以时间复杂度就比之前高了）

所以JDK1.8使用红黑树这种数据结构来解决链表过长的问题（可以简单理解为用红黑树遍历比链表遍历速度快，时间复杂度低，不懂红黑树的可以去搜搜看），默认链表长度达到8就将链表树形化（变为红黑树）。

回到最最开始我提到的，那为什么树形化的时候可能会发生扩容呢？

想想刚刚的例子数组长度为1，所有元素全部在数组的第0个位置形成一条链表，这例子是一种极端情况，数组长度过小，那自然就会经常发生hash碰撞，那形成长链表是肯定的，这个时候树形化其实是治标不治本，因为引起链表过长的根本原因是数组过短，所以在JDK1.8源码中，执行树形化之前，会先检查数组长度，如果长度小于64，则对数组进行扩容，而不是进行树形化。

所以发生扩容的时候有两种情况，一种是元素达到阀值了，一种是HashMap准备树形化但又发现数组太短，这两种情况均可能发生扩容。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。