字典中的查找条目函数.cs

本文关键字：函数 cs 查找 字典 | 更新日期: 2023-09-27 17:56:01

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

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

buckets 是一个整数数组，条目是 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;
    }

但是，我试图理解这 2 行： 

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

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

2）在第二行为什么我们将i初始化为桶[hashCode %桶。长度]？

字典中的查找条目函数.cs

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

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

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

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

网络上有关于Dictionary内部的文章。我发现算法非常好，也很聪明。它不需要负载系数。表可以完全加载。

相关文章：