哈希表（字典等）整数键 [英] Hashtables (Dictionary etc) with integer keys

问题描述

我一直琢磨不透这几天......随意拍下来我的任何假设。

I've been puzzling over this for a few days... feel free to shoot down any of my assumptions.

我们正在使用词典整数键。我认为在这种情况下，键的值被直接用作散列。这是否意味着（如果密钥是在一个小范围的分组）的密钥散列分布（相同密钥本身，对不对？）将在一个类似的小范围内，因此对Hashtable的一个不错的选择？

We're using a Dictionary with integer keys. I assume that the value of the key in this case is used directly as the hash. Does this mean (if the keys are grouped over a small range) that the distribution of the key hash (same as the key itself, right?) will be in a similarly small range, and therefore a bad choice for a hashtable?

它会更好，以提供的IEqualityComparer是做了与素数一些聪明和模数学计算更好的分布式哈希？

Would it be better to provide an IEqualityComparer that did something clever with primes and modulo mathematics to calculate a better distributed hash?

推荐答案

，不作为的直接的在字典中仍然会要求其散列的关键 - 但一个的Int32的哈希值的是的只是价值，所以你的问题的重点是相关的，是的。

It's not used directly in that the dictionary will still ask the key for its hash - but the hash value of an Int32 is just the value, so the thrust of your question is relevant, yes.

我相信，这样的.NET字典的作品并不依赖于哈希值均匀分布。它采用散％bucketCount ，其中 bucketCount 始终是首要。 （这从内存是虽然 - 我可能是错的）

I believe that the way the .NET dictionary works doesn't rely on hash values being uniformly distributed. It takes hash % bucketCount where bucketCount is always prime. (That's from memory though - I could be wrong.)

您仍然可以结束了一个低效率的一套，当然键，如果他们碰巧被斗被间隔计数。这将永远是这样，但 - 哈希表将永远只能是的真正的O（1），如果他们有独特的哈希值的和所有键的表保持一套水桶每个可能的哈希:)在现实中它往往不是一个问题。如果你碰巧知道它的 的将是一个问题，那么，一个自定义的的IEqualityComparer< T> 可以帮助

You could still end up with an inefficient set of keys of course, if they happen to be spaced by the bucket count. That will always be the case though - a hash table would only ever be genuinely O(1) for all keys if they had unique hash values and the table maintained a set of buckets for every possible hash :) In reality it tends not to be a problem. If you happen to know that it will be a problem, then yes, a custom IEqualityComparer<T> could help.

这篇关于哈希表（字典等）整数键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！