HashMap的扩容操作有什么作用

这篇文章主要介绍“HashMap的扩容操作有什么作用”，在日常操作中，相信很多人在HashMap的扩容操作有什么作用问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”HashMap的扩容操作有什么作用”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

还是先了解HashMap 的基础数据结构， 其实上图的描述并完整，因为TreeNode和TreeNode除了位于红黑树之中，其实TreeNode还有pre和next指针，即TreeNode 和 TreeNode 有先后顺序。

HashMap 的扩容操作将table的容量扩充一倍， 让后将Node重新分配到新的table中去。

 设定table的size为n，  则newTable的size为2n 。

table[j]  槽中的Node 一定满足  Node.hash % n = j .    重新计算位置  index =  Node.hash % 2n 。 

简单推测   Node.hash % 2n  = j 或者 n+j  。

证明：  设 hash = kn + j

       index =  hash % 2n = (kn +j) % 2n         

    当k为偶数时  index = j        此时Node应该位于  newTable[j] 槽位中

    当k为奇数时 index = n+j    此时Node应该位于 newTable[n+j]  槽位中。

又因为  n=0b000000001000000 ...    第m位为1 ， 其余位均为0 ，   

当k为偶数时 kn 一定表示为     n << a1 + n <<a2 + n <<a3  + ...  

即      kn = 0bxxxxxxxx00000000...   第m位为0      此时 (kn+j) & n = 0 .     

当k为奇数时 kn的第m位为1 ， 此时  (kn+j) & n = n

换句话说 可以根据 Node.hash & n 是否为0 能将冲突的节点分为两部分 .

当 Node.hash  & n ==0 时 Node 位于 newTable[j]  槽中， 否则Node 应该位于 newTable[n+j]  槽中。

以下将链表一拆为二的代码不难理解。

loHead 中的 lo 意为 lower

hiHead 中的 hi 意为 higher

Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {
    next = e.next;    if ((e.hash & oldCap) == 0) {if (loTail == null)
            loHead = e;        else            loTail.next = e;        loTail = e;    }else {if (hiTail == null)
            hiHead = e;        else            hiTail.next = e;        hiTail = e;    }
} while ((e = next) != null);if (loTail != null) {
    loTail.next = null;    newTab[j] = loHead;}if (hiTail != null) {
    hiTail.next = null;    newTab[j + oldCap] = hiHead;}

将红黑树一拆为二看不懂所以不分析， 红黑树绝对是最难的数据结构之一，所以不敢妄言。

到此，关于“HashMap的扩容操作有什么作用”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！