我发现以下代码用于计算 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 是素数)?
最佳答案
问题的完整答案需要咨询编写该代码的个人。所以我认为您不会得到完整的答案。
也就是说:
- 您所说的“通用散列法”几乎不是好的散列码的唯一可能实现方式。人们出于各种原因以各种方式实现哈希码计算。
不过更重要的是……
- 您提到的计算实际上并不是在计算哈希码。变量名称有点误导,因为虽然该值基于相关项的哈希码,但它实际上是类内部哈希表的实现细节。通过牺牲实际哈希码的最高位,可以使用该位将哈希表的
Entry
值标记为未使用。屏蔽该位,而不是例如仅对散列码值为-1
的元素进行特殊封装,保留原始散列码实现的分布质量(在Dictionary<TKey, TValue>
类之外确定)。
换句话说,您所询问的代码只是该代码的作者如何实现特定优化,其中他们通过存储其他目的所需的标志来减小 Entry
值的大小 - 即指示是否使用特定表 Entry
的目的 — 在存储部分元素哈希码的相同 32 位值中。
将哈希码存储在 Entry
值中也是一种优化。由于 Entry
值包含元素的 TKey key
值,因此实现可以实际上总是调用 key.GetHashCode()
方法来获取哈希码。这是承认 GetHashCode()
方法本身并不总是优化的权衡(实际上,大多数实现,包括 .NET 对 System.String
类的实现,总是从头开始重新计算哈希码),因此(显然)做出了选择在 Entry
值中缓存哈希码值,而不是在每次需要时都要求 TKey
值重新计算它。
不要将某些其他 对象的哈希码实现的缓存和后续使用与实际的哈希码实现混淆。后者不是您所询问的代码中发生的事情,前者是。
关于c# - 为什么使用除法而不是通用哈希法计算哈希码?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37927734/