在Hashmap中重新散列

Question

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

当一个项目被添加到该项目时HashMap,它将根据从其派生的值hashCode和该项目的桶大小分配给存储桶HashMap.要识别任何哈希映射的存储桶,请使用key.hashCode()并执行一些操作:

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

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

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

如果两个线程同时发现现在HashMap需要重新调整大小并且他们都试图重新调整大小可能会导致竞争条件HashMap.

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

我有以下问题:

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

Answer 1

这就是为什么我们有ConcurrentHashMap. 对于绝大多数情况下，如果没有同步，就不会在多个线程之间共享映射，普通旧的就HashMap足够了。

不能保证与n 个桶碰撞的两个物体仍然会与 2 n个桶碰撞。仅使用计数参数，任何两个物体发生碰撞的可能性应该只有一半左右。更少的冲突意味着更短的列表，这意味着检索时间更短。

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