HashMap底层数据结构是数组+链表，JDK1.8中还引入了红黑树，当链表长度超过8个时，会将链表转成红黑树，以提升其查找性能。
那么，给出一个<key, value>节点，HashMap是如何确定这个节点应该放在具体哪个位置呢？（以JDK1.8为例）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 该节点是链表节点
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();
afterNodeInsertion(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在元素达到负载因子对应数的时候就发生扩容。如果你看过源码就会发现，其实还有一种情况也可能会发生扩容：树形化的时候。
对象最终是如何放入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准备树形化但又发现数组太短，这两种情况均可能发生扩容。
以上这篇HashMap容量和负载因子使用说明就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持亿速云。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
