java - Java是如何实现哈希表的？

Question

有谁知道 Java 是如何实现其哈希表(HashSet 或 HashMap)的？考虑到人们可能希望将各种类型的对象放入哈希表中，似乎很难想出一个适用于所有情况的哈希函数。

Answer 1

HashMap 和HashSet 非常相似。事实上，第二个包含第一个的实例。

HashMap 包含一个桶数组以包含其条目。数组大小始终是 2 的幂。如果您不指定其他值，则最初有 16 个存储桶。

当您在其中放入一个条目(键和值)时，它会根据其键的哈希码(哈希码不是其内存地址，并且哈希不是模数)。不同的条目可能会在同一个桶中发生冲突，因此它们将被放入一个列表中。

条目将被插入，直到它们达到负载因子。此系数默认为 0.75，如果您不太确定自己在做什么，不建议更改它。 0.75 作为负载因子意味着 16 个桶的 HashMap 只能包含 12 个条目 (16*0.75)。然后，将创建一个桶数组，将前一个的大小加倍。所有条目将再次放入新数组中。此过程称为重新散列，并且可能代价高昂。

因此，如果您知道将插入多少条目，最佳做法是构造一个指定其最终大小的 HashMap:

new HashMap(finalSize);