c# - 在内部，哈希如何查找键来获取值？

Question

在内部，哈希如何查找键来获取值？

会不会是bin排序？

Answer 1

字典使用哈希码来计算存储条目的桶的编号。桶的数量被选择为质数，并且特定键的桶号被计算为键的散列码对桶的数量取模。因为多个对象可以具有相同的哈希码，并且多个哈希码可以落在同一个桶中，所以当在桶中找到一个键时，还必须比较它是否相等以确保它是正确的键。如果在桶中发现不正确的 key ，则使用错误条目的 next 成员查找下一个位置以搜索所需的 key 。

该算法的结果是，当没有碰撞时，可以非常快地找到正确的桶 - O(1)，但在最坏的情况下，它可能需要与字典中存储的条目数成线性关系的时间。我在这里假设一个对象的哈希码可以在常数时间内计算出来。

.NET实现中的实际代码可以通过下载引用实现源，或者使用.NET Reflector查看:

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;
}