为什么要把地位变得不一样呢？
这是由于哈希表数组长度n会是偏小的数值 ， 那么进行(n - 1)--tt-darkmode-color: #FF5D6C;">h ^ (h >>> 16)加工后的hash值 ， 让hashCode高位的值也参与了哈希运算 ， 因此减少了碰撞的概率 。
(h ^ (h >>> 16))--tt-darkmode-color: #A3A3A3;">为何高位移到低位和原来低位做异或操作后 ， 还需要和HASH_BITS这个常量做--tt-darkmode-color: #FF5D6C;">HASH_BITS 这个常量的值为 0x7fffffff ， 转化为二进制为 0111 1111 1111 1111 1111 1111 1111 1111 。 这个操作后会把最高位转为 0 ， 其实就是消除了符号位 ， 得到的都是正数 。 这是因为负的 hashCode 在ConcurrentHashMap 中有特殊的含义 ， 因此我们需要得到一个正的 hashCode 。
扩容源码分析我们大致了解了ConcurrentHashMap 的存储结构 ， 那么我们思考一个问题 ， 当数组中保存的链表越来越多 ， 那么再存储进来的元素大概率会插入到现有的链表中 ， 而不是使用数组中剩下的空位 。 这样会造成数组中保存的链表越来越长 ， 由此导致哈希表查找速度下降 ， 从 O(1) 慢慢趋近于链表的时间复杂度 O(n/2) ， 这显然违背了哈希表的初衷 。
所以ConcurrentHashMap 会做一个操作 ， 称为扩容 。 也就是把数组长度变大 ， 增加更多的空位出来 ， 最终目的就是预防链表过长 ， 这样查找的时间复杂度才会趋向于 O(1) 。
扩容的操作并不会在数组没有空位时才进行 ， 因为在空位快满时 ， 新保存元素更大的概率会命中已经使用的位置 ， 那么可能最后几个桶位很难被使用 ， 而链表却越来越长了 。
另外 ConcurrentHashMap 还会有链表转红黑树的操作 ， 以提高查找的速度 ， 红黑树时间复杂度为 O(logn) ， 而链表是 O(n/2) ， 因此只在 O(logn) 接下来我们分析 treeifyBin 方法代码 ， 这个代码中会选择是把此时保存数据所在的链表转为红黑树 ， 还是对整个哈希表扩容
文章插图
我们再重点看一下 tryPresize ， 此方法中实现了对数组的扩容 ， 传入的参数 size 是原来哈希表大小的一倍 。 我们假定原来哈希表大小为 16 ， 那么传入的 size 值为 32
文章插图
ConcurrentHashMap 的扩容时机和 HashMap 相同 ， 都是在 put 方法的最后一步检查是否需要扩容 ， 如果需要则进行扩容 ， 但两者扩容的过程完全不同 ， ConcurrentHashMap 扩容的方法叫做 transfer ， 从 put 方法的 addCount 方法进去 ， 就能找到 transfer 方法 ， transfer 方法的主要思路是：
1.首先需要把老数组的值全部拷贝到扩容之后的新数组上 ， 先从数组的队尾开始拷贝；
2.拷贝数组的槽点时 ， 先把原数组槽点锁住 ， 保证原数组槽点不能操作 ， 成功拷贝到新数组时 ， 把原数组槽点赋值为转移节点；
3.这时如果有新数据正好需要 put 到此槽点时 ， 发现槽点为转移节点 ， 就会一直等待 ， 所以在扩容完成之前 ， 该槽点对应的数据是不会发生变化的；
4.从数组的尾部拷贝到头部 ， 每拷贝成功一次 ， 就把原数组中的节点设置成转移节点；
5.直到所有数组数据都拷贝到新数组时 ， 直接把新数组整个赋值给数组容器 ， 拷贝完成 。
扩容方法主要是通过在原数组上设置转移节点 ， put 时碰到转移节点时会等待扩容成功之后才能 put 的策略 ， 来保证了整个扩容过程中肯定是线程安全的 ， 因为数组的槽点一旦被设置成转移节点 ， 在没有扩容完成之前 ， 是无法进行操作的
文章插图
Get方法ConcurrentHashMap 读的话 ， 就比较简单 ， 先获取数组的下标 ， 然后通过判断数组下标的 key 是否和我们的 key 相等 ， 相等的话直接返回 ， 如果下标的槽点是链表或红黑树的话 ， 分别调用相应的查找数据的方法 ， 整体思路和 HashMap 很像
文章插图
构造函数源码public ConcurrentHashMap(int initialCapacity) {if (initialCapacity < 0)throw new IllegalArgumentException();//如果传入的初始化容量值超过最大容量的一半 ， 那么sizeCtl会被设置为最大容量 。//否则通过tableSizeFor方法就算出一个2的n次方数值作为sizeint cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?MAXIMUM_CAPACITY :tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));this.sizeCtl = cap;}复制代码