HashMap中扩容时的问题

Question

老师好，这几天看HashMap的源码，1.7 1.8都看了，在扩容的时候有点疑问

比如说像上面那个图，有4个Key，都放在了一个桶里，扩容的时候，这4个key不应该还是在一个桶里吗，因为这4个key之前放在一个桶里说明他们hashCode是相同的，在1.7里有一个indexFor()的方法，求出应该存放在哪个桶里的下标，传入的是hash值和新的容量。。他们hash后都是相同的呀，求出的新下标不应该也是相同的吗，这里有点不理解。。。

Answer 1

Jimin 2018-04-18 11:58:41

你好，hash相同，不代表新下标也是相同的。你这里提到了1.7的indexFor()，我现在本地是jdk8，没法直接看源码，就不贴出来了，你具体看一下，他这里应该是有个取余操作。

我们假设长度由16变成32，16以内的下标确实没变化，但是16以后的就不一定了，比如 17%16=1，17%32=17，再比如33，33%16=1，33%32=1。

如果扩容之后元素对应下标都没变化，那就和容量没什么关系了，也可能导致扩容后的空间无法被使用到，你想想看是不是这个道理

• 提问者 深海鱼Q #1

  老师，我说的是同一个桶里链表上的结点，k1,k2,k3计算完hash再取余后放到了同一个桶，形成链表，扩大后，这个桶上的链表的所有点再重新分配也应该会分配在同一个桶里呀，直接移动整个链表就可以了，为什么还要每个结点重新计算桶的下标呢。。。这点我还是没弄懂。。还是我哪块理解有问题。。
  1.7里是indexFor(int h,int length)，return h&(length-1) .他们的h都相同，length再怎么变计算出来的下标也都是相同的呀。。1.8是找了个规律，挨个计算这条链上的每个节点，把这些结点按照条件放到两条链上，最后一条链放到原桶上，另一条链放在原索引+oldCap上。。。看了源码。。还是不懂啊

• Jimin 回复 提问者 深海鱼Q #2

  找了一篇详细介绍的文章，https://tech.meituan.com/java-hashmap.html  你具体看一下里面扩容的细节吧

• 余文乐 回复 Jimin #3

  这篇文章写的非常全面和具体，网上这么多讲HashMap源码的，就它讲的最正确了