Java中的哈希码存储桶分布

Question

假设我需要在Hashset中存储1000个对象，最好是让1000个包含每个对象的存储桶（通过为每个对象生成哈希码的唯一值）还是让10个存储桶大致包含100个对象？

具有唯一存储桶的一个优点是，我可以节省调用equals（）方法的执行周期？

为什么一定要设置数量的桶并尽可能均匀地分布在它们之间的物体很重要？

理想的物斗比应该是多少？

Answer 1

为什么一定要设置数量的桶并尽可能均匀地分布在它们之间的物体很重要？

A
HashSet应该能够平均确定O（1）时间的成员资格。从文档中：

该类为基本操作（添加，删除，包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在存储桶中。

Hashhtml" target="_blank">set用于实现此目标的算法是检索对象的哈希码，并使用此算法找到正确的存储桶。然后，对存储桶中的所有项目进行迭代，直到找到相等的项目为止。如果存储桶中的项目数大于O（1），则查找将花费比O（1）时间更长的时间。

在最坏的情况下-如果所有项目都散列到同一个存储桶-则需要O（n）时间来确定对象是否在集合中。

理想的物斗比应该是多少？

这里有一个时空权衡。增加铲斗数量会减少发生碰撞的机会。但是，这也增加了内存需求。该哈希集合有两个参数initialCapacity，并loadFactor允许您调整多少桶HashSet应该创建。默认的负载系数是0.75，在大多数情况下都可以使用，但是如果您有特殊要求，则可以选择另一个值。

有关这些参数的更多信息，请参见以下文档HashMap：

假设哈希函数将元素正确分散在存储桶中，则此实现为基本操作（获取和放置）提供恒定时间的性能。集合视图上的迭代所需的时间与HashMap实例的“容量”（存储桶数）及其大小（键-值映射数）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得过高（或负载因子过低），这一点非常重要。

HashMap的实例具有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中存储桶的数量，初始容量只是创建哈希表时的容量。负载因子是散列表的容量自动增加之前允许其填充的完整程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，通过调用rehash方法，容量大约增加了一倍。

通常，默认负载因子（.75）在时间和空间成本之间提供了很好的折衷。较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括get和put）。设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以最大程度地减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则将不会进行任何哈希操作。