Dictionary.cs 中的 FindEntry 函数

Question

我一直在查看字典的 .NET 实现，因为我想了解是什么使字典 ContainsKey 和查找快速：http : //referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,15debc34d286fdb3

containsKey 函数基本上会导致下面列出的 FindEntry：

buckets 是一个整数数组，entries 是一个 Entry 对象数组，它们是包含 HashCode、TKey 和 TValue 的结构。

所以我知道这个查找很快，因为它是一个简单的数组查找。

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

但是我试图理解这两行：

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)

1）如果我理解正确，0x7FFFFFFF 是否可以确保我们不会得到负值。那么第一行返回什么呢？它是一个简单的整数还是一个素数？

2）在第二行中，为什么我们将 i 初始化为 buckets[hashCode % buckets.Length]？

Answer 1

第一行返回哈希码，其中高位关闭以使数字为正。它不一定是素数。丢弃任何哈希中的数据是完全有效的。哈希值0（常量为零）始终是有效的哈希值。这就是为什么这个操作是安全的。

在第二行中，我们需要将哈希码映射到存储桶索引。任何确定性映射都可以。因此，我们再次通过减少可能值的数量来丢弃哈希中的信息。模运算符实现了相当统一的映射。其他映射也是可能的，例如（再次）简单地屏蔽位。

在 .NETDictionary类中，每个存储桶逻辑上都是链表的开始。包含存储在 内的链表开头的int[] buckets索引。entriesentries

由于性能原因，它很复杂。从逻辑上讲，buckets可能是一个new LinkedList<Entry>[capacity]. 这会做同样的事情，但分配更多。

网上有一些关于Dictionary内部结构的文章。我发现这个算法非常好而且聪明。它不需要负载因子。桌子可以满载。