在内部,哈希如何查找密钥以获取值？

Question

在内部,哈希如何查找密钥以获取值？

它会被bin排序吗？

Answer 1

字典使用哈希码来计算存储条目的存储桶的编号.桶的数量被选择为素数,并且特定密钥的桶号被计算为以桶的数量为模的密钥的哈希码.因为多个对象可以具有相同的哈希码,并且多个哈希码可以位于同一个桶中,所以当在桶中找到密钥时,还必须对其进行比较以确保它是正确的密钥.如果在存储桶中找到错误的密钥,next则使用错误条目的成员查找下一个搜索所需密钥的位置.

该算法的结果是,当没有冲突时,可以非常快速地找到正确的桶 - O(1),但在最坏的情况下,它可以花费在字典中存储的条目数量的线性时间.我假设在这里可以在恒定时间内计算对象的哈希码.

通过下载参考实现源或使用.NET Reflector可以看到.NET实现中的实际代码:

private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (this.buckets != null)
    {
        int num = this.comparer.GetHashCode(key) & 0x7fffffff;
        for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
        {
            if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
            {
                return i;
            }
        }
    }
    return -1;
}