11

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

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

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

当哈希图中的条目数超过负载因子和当前容量的乘积时，哈希图被重新哈希（内部数据结构被重建），使得哈希图大约有两倍的桶数。

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

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

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

我有以下问题：

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

2 回答 2

0

这就是为什么我们有ConcurrentHashMap. 对于绝大多数情况下，如果一个人没有在没有同步的情况下跨多个线程共享一个地图，那么简单的HashMap就足够了。

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

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

于 2013-09-26T07:27:19.557 回答
0
  1. 实施细节 - 我不知道 - 可能是出于性能原因。
  2. 我不知道它是否会导致无限循环，但由于 HashMap 中没有同步，所以无论如何它都不是线程安全的，它如何中断并不那么重要：它会以一种或另一种方式中断......
  3. 您最终每个存储桶的项目更少 - 因此在给定存储桶中的项目之间搜索会更快
  4. 不，这就是重新散列的重点。例如，想象一个简单的散列算法index = hash % numberOfBuckets。
于 2013-09-26T07:35:37.887 回答