Java如何实现哈希表？

Question

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

Answer 1

HashMap和HashSet非常相似.实际上,第二个包含第一个实例.

HashMap包含一个桶数组以包含其条目.数组大小始终为2的幂.如果未指定其他值,则最初有16个桶.

当你在其中放入一个条目(键和值)时,它决定插入条目的存储区,从其键的哈希码计算它(哈希码不是它的内存地址,哈希不是模数).不同的条目可能会在同一个桶中发生冲突,因此它们将被放入列表中.

将插入条目,直到它们达到负载系数.默认情况下,此因子为0.75,如果您不确定自己在做什么,建议不要更改它.0.75作为加载因子意味着16个桶的HashMap 只能包含12个条目(16*0.75).然后,将创建一个桶阵列,使之前的大小加倍.所有条目将再次放入新数组中.这个过程称为rehashing,可能很昂贵.

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

new HashMap(finalSize);

Answer 2

HashMap例如,您可以查看来源.

Answer 3

Java依赖于每个类的hashCode()方法的实现来均匀地分布对象.显然,糟糕的hashCode()方法会导致大型哈希表的性能问题.如果类没有提供hashCode()方法,则当前实现中的默认值是返回内存中对象地址的某些函数(即散列).引用API文档:

尽可能合理,Object类定义的hashCode方法确实为不同的对象返回不同的整数.(这通常通过将对象的内部地址转换为整数来实现,但JavaTM编程语言不需要此实现技术.)