在Hashmap中重新散列 [英] Rehashing in Hashmap

问题描述

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

The initial capacity and load factor two parameters that affect the HashMap performance. The default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost.

当项目添加到 HashMap 时，根据从 hashCode 派生的值和 HashMap 的桶大小分配给存储桶。
要识别任何桶，Hash地图使用 key.hashCode（）并执行一些操作：

When an item is added to the HashMap, it is assigned to a buckets based on a value derived of its hashCode and the bucket size of the HashMap. To identify the bucket for any , Hash map use key.hashCode() and perform some operation:

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

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

When the number of entries in the hash map exceeds the product of the load factor and the current capacity, the hash map is rehashed (internal data structures are rebuilt), so that the hash map has approximately twice the number of buckets.

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

When you rehash and move everything to a new location (bucket, etc.) then the older elements are also rehashed again and stored in the new bucket according to their new hash codes. The old space which was allocated to store the elements is garbage collected.

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

If two thread at the same time found that now HashMap needs re-sizing and they both try to re-size may cause race condition in HashMap.

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

On the process of re-sizing of HashMap, the element in bucket which is stored in linked list get reversed in order during their migration to new bucket because java HashMap doesn't append the new element at tail instead it append new element at head to avoid tail traversing. If race condition happens then you will end up with an infinite loop.

我有以下问题：

1. 为什么每个桶的链表在
   迁移到新桶期间按顺序颠倒？


2. 竞争条件如何导致无限循环？


3. 如何增加桶数减少查找等待
   时间？


4. 同一个桶中的元素仍然在一起rehashing后
   桶？

1. Why is the linked list for each bucket be reversed in order during migration to new bucket?
2. How race condition can lead to infinite loop?
3. How can increasing the number of buckets diminish the lookup waiting time?
4. Elements which are in the same bucket will still be together in same bucket after rehashing?

推荐答案

1. 实施细节 - 我不知道 - 可能是出于性能原因。


2. 我不知道它是否会导致无限循环，但由于HashMap中没有同步，因此无论如何都不是线程安全的如何打破它并不是那么重要：它会以某种方式打破......


3. 你最终每桶的物品更少 - 所以在给定桶中的物品搜索更快


4. 不，这就是重复的重点。想象一个简单的哈希算法 index = hash％numberOfBuckets 例如。

1. Implementation detail - I don't know - probably for performance reasons.
2. I don't know if it could result in an infinite loop but since there is no synchronisation in HashMap it is not thread safe anyway do how it break is not so important: it will break one way or another...
3. You end up with less items per bucket - so searching among items in a given bucket is quicker
4. No, that's the point of rehashing. Imagine a simple hashing algo index = hash % numberOfBuckets for example.

这篇关于在Hashmap中重新散列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！