所以我需要创建一个字典，其中的键是具有自定义 Equals() 函数的对象。我发现我也需要覆盖 GetHashCode()。我听说为了获得最佳性能，您应该使用不冲突的哈希码，但这似乎违反直觉。我可能会误解它，但似乎使用哈希码的全部目的是将项目分组到桶中，如果哈希码从不冲突，每个桶将只有一个项目，这似乎违背了目的。
那么我应该故意让我的哈希码偶尔发生冲突吗？性能很重要。这将是一个可能会增长到数百万个项目的字典，我会经常进行查找。
问问题
291 次
3 回答
2
哈希码的目标是为您提供一个数组索引，每个数组都是一个可能包含零个、一个或多个项目的桶。查找的性能取决于桶中元素的数量。越少越好，因为一旦你在桶中，它就是一个 O(n) 搜索（其中 n 是桶中元素的数量）。因此，如果哈希码尽可能地防止冲突，那么它是理想的，尽可能地允许最佳 O(1) 时间。
于 2013-09-29T00:33:01.870 回答
1
字典将数据存储在桶中，但每个哈希码没有一个桶。桶的数量取决于容量。根据哈希码的模数和桶数将值放入桶中。
假设您有一个GetHashCode()方法可以为五个对象生成这些哈希码：
925
10641
14316
17213
28624
散列码应该散开。所以这些看起来分散了，对吧？如果我们有 7 个桶，那么我们最终会计算每个桶的模数，这给了我们：
1
1
1
0
1
所以我们最终得到了桶：
0 - 1 item
1 - 4 items
2 - 0 items
3 - 0 items
4 - 0 items
5 - 0 items
6 - 0 items
哎呀，现在散布得不太好。
这不是虚构的数据。这些是实际的哈希码。
这是如何从包含的数据生成哈希码的示例（不是用于上述哈希码的公式，一个更好的公式）。
于 2013-09-29T00:42:29.070 回答
0
您必须确保满足以下条件：
(GetHashCode(a) != GetHashCode(b)) => !Equals(a, b)
相反的含义在含义上是相同的：
Equals(a, b) => (GetHashCode(a) == GetHashCode(b))
除此之外，尽可能少地产生碰撞。碰撞定义为：
(GetHashCode(a) == GetHashCode(b)) && !Equals(a, b)
碰撞不会影响正确性，但会影响性能。GetHashCode例如，总是返回零是正确的，但速度很慢。
于 2013-09-29T17:11:00.323 回答