HashMap的其他3个底层原理当你理解了以上三个有了这个原理之后，还需要掌握以下几个问题：如果计算出的哈希值相同，如何解决冲突？HashMap扩容后如何进行rehash？指定大小的HashMap的扩容阈值算法是什么？还是老规矩，见下图：如果计算的hash值相同，如何解决冲突？当hash值计算一致时，比如hash值为1100时，Key-Value对的Node节点也有一个next指针，它将冲突的节点挂在数组的相同位置，形式为单个链表。这就是数据结构中的内容。提到了hash的一种冲突解决方法：单链法。当然对detectionmethod+rehashmethod感兴趣的可以复习《数据结构和算法》相关书籍。但是当hash冲突严重的时候，单链的方式会导致principallink太长，导致HashMap的性能下降，因为链表需要一个一个遍历，性能很差.所以JDK1.8优化了哈希冲突算法。当链表节点数达到8时，会自动转为红黑树，一种自平衡二叉树，具有很多特点，比如区分红黑节点。详见小灰度算法图解。红黑树的遍历效率是O(logn)，肯定比单链表的O(n)好很多。总之，使用单链表法+红黑树解决hash冲突。HashMap扩容后如何进行rehash？上图中，核心上下文是四步，具体源码就不贴出来了。当放一个，map的大小达到12的扩容阈值时，就会触发rehash。具体思路可以看下：新数组的容量是原来的两倍，比如新的扩容阈值16-32也是原来的两倍，比如12->24为新数组newTab分配空间，原数组oldTab不为Empty，需要进行rehash操作rehash有3种情况，如果数组位置有值，则进行rehash。（这一步是rehash核心的核心）有以下三种情况：情况一：如果数组position只有一个值：使用新的容量进行rehash，即e.hash&(newCap-1)情况二：如果数组位置有为链表，根据e.hash&oldCap==0判断，如果结果为0，则使用原位置，否则使用索引+oldCap位置，将元素放入新链表。这里不会对case1的newcapacity进行rehash和操作，index+oldCap节省性能。情况3：如果数组位置有红黑树，按照split的方法，同样按照e.hash&oldCap==0统计树节点个数，如果个数小于6，则恢复树的result为普通Node，否则使用index+oldCap，调整红黑树的位置，这里不会对新容量进行rehash和操作，index+oldCap会节省性能。如果大家有兴趣，可以把这三种情况分别画出来。这里给大家上一张图，假设以上三种情况都启动了，结果如下：上图中，核心上下文是四步，源码就不贴出来了。当放一个，map的大小达到12的扩容阈值时，就会触发rehash。具体思路可以看下：新数组的容量是原来的两倍，比如新的扩容阈值16-32也是原来的两倍，比如12->24为新数组newTab分配空间，原数组oldTab不为Empty，需要进行rehash操作rehash有3种情况，如果数组位置有值，则进行rehash。（这一步是rehash核心的核心）有以下三种情况：情况一：如果数组position只有一个值：使用新的容量进行rehash，即e.hash&(newCap-1)情况二：如果数组位置有为链表，根据e.hash&oldCap==0判断，如果结果为0，则使用原位置，否则使用索引+oldCap位置，将元素放入新链表。这里不会对case1的newcapacity进行rehash和操作，index+oldCap节省性能。情况3：如果数组位置有红黑树，按照split的方法，同样按照e.hash&oldCap==0统计树节点个数，如果个数小于6，则恢复树的result为普通Node，否则使用index+oldCap，调整红黑树的位置，这里不会对新容量进行rehash和操作，index+oldCap会节省性能。如果大家有兴趣，可以把这三种情况分别画出来。这里给大家上一张图，假设以上三种情况都启动，结果如下：initialCapacity<0)thrownewIllegalArgumentException("非法初始容量："+initialCapacity);如果(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException"load+fllegloadFactor);this.loadFactor=loadFactor;this.threshold=tableSizeFor(initialCapacity);}上面源码的核心上下文，3个if主要是验证一堆，什么都不做，然后分配膨胀因子，不传默认值为0.75，膨胀阈值threshold是通过tableSizeFor(initialCapacity)计算的；注意这里只有膨胀阈值被计算，并且数组没有被初始化。代码如下：staticfinalinttableSizeFor(intcap){intn=cap-1;n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16；返回（n<0）？1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}不是size*expansionfactor吗？n|=n>>>1这句话在做什么？n|=n>>>1等同于n=n|n>>>1;和|表示位运算中的或，n>>>1表示无符号右移1位。在这种情况下，您应该已经学习过了。遇到复杂的逻辑和算法方法，要画图或举例说明。这里可以举个例子：假设指定容量为100，n=cap-1=99，那么计算过程应该是这样的：n是一个int类型，在java中一般是4字节32位。所以99在二进制中是：00000000000000000000000001100011。最后n+1=128，方法返回并赋值threshold=128。再次注意，这里只计算了扩展阈值，并没有对数组进行初始化。你为什么这么做？总之，为了提高哈希寻址和扩容计算的效率。因为扩展计算和寻址计算都是二进制位运算，所以效率非常快。另外大家还记得，在取余（%）运算中，如果除数是2的幂，就相当于AND（&）运算从除数减一。即hash%size=hash&(size-1)。这个前提条件是除数是2的幂。您可以再次查看调整大小代码，看看如果指定了地图容量，第一个put会发生什么。会设置扩容阈值threshold，这样newCap=oldThr会在第一次put的时候被调用；这样就会创建一个容量为threshold的数组，然后计算新的扩容阈值newThr为newCap*0.75=128*0.75=96。也就是说，当地图达到96个元素时，地图就会展开。JDK1.7HashMap死循环问题？