在Hashmap中重新散列

初始容量和加载因子两个影响HashMap性能的参数。 默认负载系数（ .75 ）在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销，但会增加查找成本。

将项添加到HashMap ，会根据其hashCode派生的值和HashMap的桶大小将其分配给存储桶。 要识别任何哈希映射的桶，使用key.hashCode()并执行一些操作：

 Bucket (index) = HashMap.indexFor(HashMap.hash(key.hashCode()), entryArray.length) 

当哈希映射中的条目数超过加载因子和当前容量的乘积时，哈希映射将被重新哈希（内部数据结构被重建），因此哈希映射具有大约两倍的桶数。

当您重新散列并将所有内容移动到新位置（存储桶等）时，旧元素也会再次重新散列并根据新的哈希码存储在新存储桶中。 分配用于存储元素的旧空间被垃圾收集。

如果两个线程同时发现现在HashMap需要重新resize并且他们都尝试重新resize可能会导致HashMap竞争条件。

在重新调整HashMap大小的过程中，存储在链表中的存储桶中的元素在迁移到新存储桶时按顺序颠倒，因为java HashMap不会在尾部附加新元素，而是在头部附加新元素避免尾部穿越。 如果发生竞争条件，那么最终会出现无限循环。

我有以下问题：

1. 为什么在迁移到新存储桶期间按顺序颠倒每个存储桶的链接列表？
2. 竞争条件如何导致无限循环？
3. 如何增加桶的数量会减少查找等待时间？
4. 在重新划分后，同一个桶中的元素仍然会在同一个桶中？

Answer 1

这就是我们拥有ConcurrentHashMap的原因。 对于绝大多数没有同步而没有在多个线程上共享一个映射的情况，普通的HashMap就足够了。

无法保证与n个桶冲突的两个对象仍然会与2 个桶冲突。 只使用计数参数，它应该是任何两个对象碰撞的可能性的一半。 较少的碰撞意味着更短的列表，这意味着检索时间更短。

因为我们正在重复冲突并且冲突在不同数量的桶之间不一致，所以当您断言每个桶的列表作为流程的一部分被反转时，我怀疑您正在正确读取代码。

Answer 2

1. 实施细节 – 我不知道 – 可能是出于性能原因。
2. 我不知道它是否会导致无限循环，但由于HashMap中没有同步，因此它不是线程安全的，不管它如何中断并不是那么重要：它会以某种方式破坏……
3. 每个桶的最终产品数量减少 – 因此在给定存储桶中的项目搜索速度更快
4. 不，这是重新点火的重点。 想象一下，例如一个简单的哈希算法index = hash % numberOfBuckets 。