哈希算法会占用大量的内存吗？

Question

GetHashCode()得到的是一个32位的整数
难道要分配这么多个存储桶？

Answer 1

Hashtable 的加载因子确定元素与存储桶的最大比率。加载因子越小，平均查找速度越快，但消耗的内存也增加。默认的加载因子 1.0 通常提供速度和大小之间的最佳平衡。当创建 Hashtable 时，也可以指定其他加载因子。摘自<MSDN>

Answer 2

HashTable是把（HashCode & int.MaxValue(保证是个正数)）% 某一个质数

Answer 3

我的意思是，即使 Dictionary<TKey,TValue>或者Hashtable里的元素很少（例如只有几个），也会占用大量内存吗？因为存储桶很多啊

Answer 4

囧你看msdn了吗?
当向 Hashtable 添加元素时，Hashtable 的实际加载因子将增加。当实际加载因子达到指定的加载因子时，Hashtable 中存储桶的数目自动增加到大于当前 Hashtable 存储桶数两倍的最小质数。

Answer 5

囧你看msdn了吗?
当向 Hashtable 添加元素时，Hashtable 的实际加载因子将增加。当实际加载因子达到指定的加载因子时，Hashtable 中存储桶的数目自动增加到大于当前 Hashtable 存储桶数两倍的最小质数。

Answer 6

你的意思是存储桶的数目并不是uint.MaxValue+1？
那如果两个元素的HashCode不同，也可能存在同一个存储桶中？

Answer 7

那如果两个元素的HashCode不同，也可能存在同一个存储桶中？
怎么可能

Answer 8

GetHashCode返回的是一个32位整数如果存储桶没有2的32次方这么多，怎么能保证Hash代码不同的元素存在于不同的存储桶？

Answer 9

我看了一下源码，大概知道怎么回事了。“兄弟，你是怎么理解的，为什么存储桶要2的32次方这么多”
>>这是你自己的理解能力有问题
你既然说如果两个元素的Hash代码不同，它们就存在于不同的存储桶，而每个元素的Hash代码是32位整数，也就是有2的32次方种可能，那要能唯一识别不能的元素，必然至少需要2的32次方个桶。这就像汉字超过了256个，要使得每个汉字的编码不同，一个字节就不够用，所以要用两个或更多。这是很简单的道理。根据我刚才对源码的初步分析，的确没那么多桶，但前提是Hash代码不同的元素，是可能存在于相同的桶的private uint InitHash(object key, int hashsize, out uint seed, out uint incr)
{
    uint num = (uint) (this.GetHash(key) & 0x7fffffff);
    seed = num;
    incr = 1 + ((uint) (((seed >> 5) + 1) % (hashsize - 1)));
    return num;
}
其中GetHash的实现为：
protected virtual int GetHash(object key)
{
    if (this._keycomparer != null)
    {
        return this._keycomparer.GetHashCode(key);
    }
    return key.GetHashCode();
}也就是说：Hash代码并非是桶的代号，而只是用于计算桶的代号所以桶的数量我可以自定，比如我设为7，那么我可以把7,14,21放置于0号桶，把8,15,22放于1号桶,
所以如果有3个元素，它们的Hash代码分别是8,15,22的话，虽然各不相同，但是都被放于1号桶。
但是你居然认为既要让不同Hash代码的元素放于不同的桶，又要求桶的数目小于Hash可能的取值范围，你也把计算机看得太神秘了吧？ 
 

Answer 10

Hashtable里的元素很少（例如只有几个），存储桶不会太多，