哈希表（字典等）与整数键

Question

我已经思考了几天...欢迎打破我的任何假设。

我们正在使用整数键的字典。我认为在这种情况下，键的值直接用作哈希值。如果键分组在一个小范围内，这是否意味着键哈希（与键本身相同，对吗？）的分布将在类似的小范围内，因此不适合用作哈希表的选择？

提供一个IEqualityComparer是否更好，它可以使用质数和模数数学来计算更好的分布式哈希？

- spender

---

这取决于你的整数键的分布情况。在计算哈希桶时，键已经取模为素数。 - Mitch Wheat

为什么要假设哈希码与整数值相同？来测试一下吧！ - SteveD

哈希码与整数值相同。 - spender

Answer 1

它并没有直接使用，因为字典仍会要求键提供其哈希值 - 但是Int32的哈希值恰好是其值，所以你的问题是相关的。

我认为.NET字典的工作方式不依赖于哈希值均匀分布。它采用hash％bucketCount，其中bucketCount始终是质数。（尽管这是从记忆中得出的 - 我可能是错的。）

当然，你仍然可能遇到一组效率低下的键，如果它们碰巧被桶计数间隔开。不过这种情况总是存在的 - 只有当所有键都具有唯一的哈希值且该表维护了每个可能的哈希的桶集时，哈希表才会真正地对于所有键都是O（1）的。实际上往往不是个问题。如果你知道它将成为一个问题，那么是的，自定义的IEqualityComparer<T>可以帮助解决。

- Jon Skeet

---

刚刚用反射检查了一下...你对哈希%桶计数是正确的。知道了这一点，一切都水到渠成了。谢谢Jon。 - spender

Answer 2

在进行一些聪明的操作之前，我会测试现有代码的速度，看它是否适合你。如果不适合，那么再去尝试那些聪明的东西。但是我认为最好的方法是将其保持原样；更重要的是哈希值不发生冲突，只要这个条件得到满足，就可以放心使用了。

- Noon Silk

Answer 3

假设您正在使用标准库哈希表实现，即使键是整数，也很有可能键不是哈希值，正如您指出的那样。

因此，尽管您关于哈希分布的逻辑是正确的，但您最初的假设即整数键意味着哈希=键可能不正确。

如果我对.NET错误了，那么好吧；这更多是一个概括性的答案。 :)

- Amber

---

我认为对于数字类型的哈希值而言，如果它适合哈希范围，那么哈希值就是其本身的值，这是相当普遍的做法。 - Jon Skeet

你可能会遇到的一个潜在问题是，数字序列中的模式——如果你的模式宽度恰好是 bucketCount 的倍数，那么就会遇到问题。 - Amber

正如我的帖子所提到的那样...但是，如果你运气不好，任何哈希算法都可能遇到这个问题。 - Jon Skeet

当然可以。但是由于数据的本质，模式往往在标准输入中出现得比专门设计用于混合数据的哈希函数的输出中更频繁。 - Amber