几天来我一直对此感到困惑……请随时否定我的任何假设。
我们正在使用带有整数键的字典。我假设在这种情况下键的值直接用作散列。这是否意味着（如果键被分组在一个小范围内）键散列的分布（与键本身相同，对吗？）将在一个类似的小范围内，因此对于散列表来说是一个糟糕的选择？
提供一个 IEqualityComparer 会更好地使用素数和模数学来计算更好的分布式哈希吗？
问问题
2380 次
3 回答
8
它不是直接使用的，因为字典仍然会向键询问其哈希值 - 但 an 的哈希值Int32 只是值，所以你的问题的重点是相关的，是的。
我相信 .NET 字典的工作方式并不依赖于均匀分布的哈希值。它总是占据首要hash % bucketCount位置。bucketCount（不过那是凭记忆——我可能是错的。）
当然，如果它们碰巧被桶数隔开，你仍然可能最终得到一组效率低下的键。但情况总是如此 -如果所有键具有唯一的散列值并且表为每个可能的散列维护一组存储桶，散列表将永远是真正的 O(1) :) 实际上它往往不是一个问题。如果您碰巧知道这将是一个问题，那么是的，定制可能会有所帮助。IEqualityComparer<T>
于 2009-09-07T08:57:55.770 回答
1
在做一些聪明的事情之前，我会按原样测试它的速度，看看它是否适合你。如果不是，那么尝试聪明的事情。但我希望最好不要管它。更重要的是哈希不会发生冲突，只要发生这种情况，生活就会很好。
于 2009-09-07T09:02:15.113 回答
0
假设您使用的是标准库哈希表实现，那么键可能不是哈希，即使键是整数，这正是您指出的原因。
因此，虽然您关于哈希分布的逻辑是正确的，但您最初假设整数键意味着 hashes = keys 可能不是。
如果我错了：.NET 那么好吧；这更像是一个笼统的答案。:)
于 2009-09-07T08:58:25.957 回答