c# - 为什么使用除法而不是通用哈希法计算哈希码？

Question

我发现以下代码用于计算 hashcode :

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
int index = hashCode % buckets.Length;

为什么工程师没有选择通用的哈希方法:

int index = [(ak + b) mod p)mod buckets.Length]

a,b 是 0...p-1 之间的随机数(p 是素数)？

Answer 1

问题的完整答案需要咨询编写该代码的个人。所以我认为您不会得到完整的答案。

也就是说:

1. 您所说的“通用散列法”几乎不是好的散列码的唯一可能实现方式。人们出于各种原因以各种方式实现哈希码计算。

不过更重要的是……

1. 您提到的计算实际上并不是在计算哈希码。变量名称有点误导，因为虽然该值基于相关项的哈希码，但它实际上是类内部哈希表的实现细节。通过牺牲实际哈希码的最高位，可以使用该位将哈希表的 Entry 值标记为未使用。屏蔽该位，而不是例如仅对散列码值为 -1 的元素进行特殊封装，保留原始散列码实现的分布质量(在 Dictionary<TKey, TValue> 类之外确定)。

换句话说，您所询问的代码只是该代码的作者如何实现特定优化，其中他们通过存储其他目的所需的标志来减小 Entry 值的大小 - 即指示是否使用特定表 Entry 的目的 — 在存储部分元素哈希码的相同 32 位值中。

将哈希码存储在 Entry 值中也是一种优化。由于 Entry 值包含元素的 TKey key 值，因此实现可以实际上总是调用 key.GetHashCode() 方法来获取哈希码。这是承认 GetHashCode() 方法本身并不总是优化的权衡(实际上，大多数实现，包括 .NET 对 System.String 类的实现，总是从头开始重新计算哈希码)，因此(显然)做出了选择在 Entry 值中缓存哈希码值，而不是在每次需要时都要求 TKey 值重新计算它。

不要将某些其他 对象的哈希码实现的缓存和后续使用与实际的哈希码实现混淆。后者不是您所询问的代码中发生的事情，前者是。