bucketIndex = indexFor(hash, table.length);//indexFor的代码也很简单 ， 就是把散列值和数组长度做一个"与"操作 ， static int indexFor(int h, int length) {return h }顺便说一下 ， 这也正好解释了为什么 HashMap 的数组长度要取 2 的整次幂 。 因为这样（数组长度?1）正好相当于一个 “低位掩码” 。 “与” 操作的结果就是散列值的高位全部归零 ， 只保留低位值 ， 用来做数组下标访问 。 以初始长度 16 为例 ， 16?1=15 。 2 进制表示是 00000000 0000000000001111 。 和某散列值做 “与” 操作如下 ， 结果就是截取了最低的四位值 。
10100101 11000100 00100101 --tt-darkmode-color: #50616D;">但这时候问题就来了 ， 这样就算我的散列值分布再松散 ， 要是只取最后几位的话 ， 碰撞也会很严重 。 更要命的是如果散列本身做得不好 ， 分布上成等差数列的漏洞 ， 恰好使最后几个低位呈现规律性重复 ， 就无比蛋疼 。 这时候 “扰动函数” 的价值就出来了 ， 说到这大家应该都明白了 ， 看下图 。
文章插图
右位移 16 位 ， 正好是 32bit 的一半 ， 自己的高半区和低半区做异或 ， 就是为了混合原始哈希码的高位和低位 ， 以此来加大低位的随机性 。 而且混合后的低位掺杂了高位的部分特征 ， 这样高位的信息也被变相保留下来 。
putVal 方法HashMap 的 put 方法执行过程可以通过下图来理解 ， 自己有兴趣可以去对比源码更清楚地研究学习 。
文章插图
源码以及解释如下:
// 真正的put操作final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i;// 如果table没有初始化 ， 或者初始化的大小为0 ， 进行resize操作if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果hash值对应的桶内没有数据 ， 直接生成结点并且把结点放入桶中if ((p = tab[i = (n - 1)// 如果hash值对应的桶内有数据解决冲突 ， 再放入桶中else {Node e; K k;//判断put的元素和已经存在的元素是相同(hash一致 ， 并且equals返回true)if (p.hash == hash// put的元素和已经存在的元素是不相同(hash一致 ， 并且equals返回true)// 如果桶内元素的类型是TreeNode ， 也就是解决hash解决冲突用的树型结构 ， 把元素放入树种else if (p instanceof TreeNode)e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else {// 桶内元素的类型不是TreeNode ， 而是链表时 ， 把数据放入链表的最后一个元素上for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 如果链表的长度大于转换为树的阈值(TREEIFY_THRESHOLD) ， 将存储元素的数据结构变更为树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 如果查已经存在key ， 停止遍历if (e.hash == hashp = e;}}// 已经存在元素时if (e != null) { // existing mapping for keyV oldValue = http://kandian.youth.cn/index/e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 如果K-V数量大于阈值 ， 进行resize操作if (++size> threshold)resize();afterNodeInsertion(evict);return null;}扩容机制
HashMap 的扩容机制用的很巧妙 ， 以最小的性能来完成扩容 。 扩容后的容量就变成了变成了之前容量的 2 倍 ， 初始容量为 16 ， 所以经过 rehash 之后 ， 元素的位置要么是在原位置 ， 要么是在原位置再向高下标移动上次容量次数的位置 ， 也就是说如果上次容量是 16 ， 下次扩容后容量变成了 16+16 ， 如果一个元素在下标为 7 的位置 ， 下次扩容时 ， 要不还在 7 的位置 ， 要不在 7+16 的位置 。
我们下面来解释一下 Java8 的扩容机制是怎么做到的？n 为 table 的长度 ， 图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例 ， 图（b）表示扩容后 key1 和 key2 两种 key 确定索引位置的示例 ， 其中 hash1 是 key1 对应的哈希与高位运算结果 。
文章插图
元素在重新计算 hash 之后 ， 因为 n 变为 2 倍 ， 那么 n-1 的 mask 范围在高位多 1bit(红色) ， 因此新的 index 就会发生这样的变化：
文章插图
因此 ， 我们在扩充 HashMap 的时候 ， 不需要像 JDK1.7 的实现那样重新计算 hash ， 只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了 ， 是 0 的话索引没变 ， 是 1 的话索引变成 “原索引 + oldCap” ， 可以看看下图为 16 扩充为 32 的 resize 示意图：