6

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

拥有唯一存储桶的 1 个优点是我可以在调用 equals() 方法时节省执行周期？

为什么设置桶的数量并尽可能均匀地分配对象很重要？

理想的对象与桶的比率应该是多少？

4

3 回答 3

8

为什么设置桶的数量并尽可能均匀地分配对象很重要？

AHashSet应该能够平均在 O(1) 时间内确定成员资格。从文档中：

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

Hashset用于实现此目的的算法是检索对象的哈希码并使用它来找到正确的存储桶。然后它遍历桶中的所有项目，直到找到一个相等的项目。如果桶中的项目数大于 O(1)，则查找将花费比 O(1) 更长的时间。

在最坏的情况下 - 如果所有项目散列到同一个桶 - 将花费 O(n) 时间来确定对象是否在集合中。

理想的对象与桶的比率应该是多少？

这里有一个时空权衡。增加桶的数量会减少碰撞的机会。然而，它也增加了内存需求。哈希集有两个参数initialCapacity，允许您调整应该创建loadFactor多少桶。HashSet默认负载系数为 0.75，这对于大多数用途来说都很好，但如果您有特殊要求，您可以选择其他值。

有关这些参数的更多信息可以在以下文档中找到HashMap：

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

HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子与当前容量的乘积时，通过调用rehash方法，容量大致翻倍。

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

于 2012-07-13T10:26:03.983 回答
1

每个元素大约一个桶对处理器来说更好，太多的桶对内存不利。Java 将从少量存储桶开始，一旦开始填满，就会自动增加 HashSet 的容量，因此除非您的应用程序出现性能问题并且您已确定原因是哈希集，否则您实际上不需要关心。

如果每个存储桶中有多个元素，则查找开始花费更长的时间。如果您有很多空桶，则您使用的内存超出了您的需要，并且迭代元素需要更长的时间。

不过，这似乎是一个等待发生的过早优化——默认构造函数在大多数情况下都很好。

于 2012-07-13T10:28:43.730 回答
1

Object.hashCode()是 type int，你只能有2^32 个不同的值，这就是你创建存储桶并在它们之间分配对象的原因。

编辑：如果您使用2^32存储桶来存储 2^32 对象，那么绝对的 get 操作会给您带来恒定的复杂性，但是当您一个一个地插入元素来存储2^32对象时，重新散列将比我们使用Object[]存储桶时执行的操作那么每次它超过它的长度array将创建更大大小的新数组并将元素复制到其中。这个过程会增加复杂性。这就是我们使用equalsand hashcodein ratio 的原因，这是Hashsets通过提供更好的hashing algorithm.

于 2012-07-13T10:29:13.620 回答