.NET字典,速度惊人,但它是如何工作的？

Question

好吧,我会承认我没有挖出反射器来看看这里发生了什么,但我希望有人可以告诉我.

Microsoft如何快速地添加和获取,我可以通过在数组中粘贴项目来快速添加,并且我可以通过对数组进行排序和使用二进制搜索来快速获取.但是,如果我每次添加一个项目以快速获取数据时都会进行快速排序,那么添加会大幅减慢速度,如果每次我尝试获取某些内容时都必须对数据进行排序,那么添加项目会大大减慢.

有谁知道字典的内部工作原理？它比数组更需要内存,所以除了聪明的算法之外,显然还有一些东西在幕后进行.

我正在努力理解魔法并从中学习!

Answer 1

该dictionary<T,T>在.net中被称为哈希表的数据结构:

在哈希表和.Net词典上:

http://en.wikipedia.org/wiki/Hash_table

http://msdn.microsoft.com/en-us/library/4yh14awz.aspx

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

关于二进制搜索:

http://en.wikipedia.org/wiki/Binary_search

你是对的,它使用更多的内存而不是数组来检索数据.这是你为更快的访问付出的代价.(在大多数情况下,当您开始考虑构建哈希表与阵列的设置时间时,情况确实如此,有时排序的数组可能会更快地进行设置时间和访问.通常,这是一个有效的假设.)

Answer 2

不久前，我发誓要对这个问题进行详细的回答，这花了我一段时间，因为某些细节和概念对我来说有点生锈，但是在这里：

.NET词典的长度（或种类）如何工作。

让我们从这个概念开始，就像指出的许多其他答案一样，它Dictionary<TKey, TValue>是哈希表的泛型（在C＃语言功能的意义上）实现。

哈希表只是一个关联数组，也就是说，当您传递一对（键，值）时，该键用于计算哈希码，这将有助于计算基础存储阵列中的位置（称为存储桶） （称为存储桶），该对和其他一些附加信息将保存在其中。这通常是通过计算所述模数实现%在阵列/桶的大小的哈希码的：hashCode % buckets.Length。

这种类型的关联数组的搜索，插入和删除操作的平均复杂度为O（1）（即恒定时间）……除非在某些情况下我们稍后会介绍。因此通常来说，在字典中查找内容要比在列表或数组中查找要快得多，因为您不必“正常”地遍历所有值。

如果您一直关注到现在为止所写的内容，那么您会注意到可能已经存在问题。如果根据我们的密钥计算出的哈希码与另一个密钥相同，或更糟的是一堆其他密钥，而我们最终位于同一位置怎么办？我们如何处理这些冲突？显然，人们早在数十年前就已经考虑过，并提出了解决冲突的两种主要方法：

• 单独链接：基本上，该对存储在与存储桶（通常称为条目）不同的存储中，例如，对于每个存储桶（计算每个索引），我们可以有一个条目列表，其中存储了相同存储的不同值“索引”（由于相同的哈希码），基本上在发生冲突的情况下，您必须遍历键（并找到除哈希码以外的另一种方法来区分它们）
• 开放式寻址：所有内容都存储在存储桶中，并根据我们接下来检查的第一个存储桶，它还以不同的方式来探查值（线性探测，二次探测，双重哈希等）。

两种冲突解决方案的实现有时可能会发生很大的变化。对于.NET词典，数据结构依赖于单独链接冲突解决方案，就像我们将看到的几分钟。

好了，现在让我们看看如何将内容插入.NET中Dictionary<TKey, TValue>，归结为下面的方法代码：

private void Insert(TKey key, TValue value, bool add)

注意：在阅读下面的插入步骤之后，您可以通过检查源代码中作为链接给出的代码，找出删除和查找操作背后的基本原理。

第1步：给我哈希码

有两种方法TKey可以计算密钥的哈希码：

• IEqualityComparer<TKey>如果TKey的类型不同于所有通常的东西（例如基元和字符串），则如果您不传递任何参数，则Dictionary<TKey, TValue>该参数将依赖于默认的实现比较器，该参数基本上是由EqualityComparer<TKey>.Default（通过此处的实现）生成的。自定义类型，IEqualityComparer<in TKey>将利用以下实现（包括override）：

  • bool Equals(object obj)
  • int GetHashCode()

• 好的，另一个依赖于IEqualityComparer<in TKey>您可以传递给Dictionary<TKey, TValue>构造函数的实现。

该界面IEqualityComparer<in T>如下所示：

// The generic IEqualityComparer interface implements methods to if check two objects are equal
// and generate Hashcode for an object.
// It is use in Dictionary class.  
public interface IEqualityComparer<in T>
{
    bool Equals(T x, T y);
    int GetHashCode(T obj);
}

无论哪种方式，字典都使用比较器最终具有第一个哈希码： comparer.GetHashCode()

步骤2：取得目标值区

从TKey密钥到密钥的哈希码IEqualityComparer<in T>有时可能是负数，如果我们想为数组获取正数索引，这实际上并没有帮助...

发生的事情是，为了消除负值，Int32将由所获得的哈希码comparer.GetHashCode()与Int32.MaxValue（即2147483647或0x7FFFFFFF）进行“与”操作（就布尔逻辑而言：位）：

var hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;

目标存储桶（索引）的获取方式如下：

var targetBucket = hashCode % buckets.Length

稍后还将看到如何buckets调整数组的大小。

的buckets（int[]）是一个private领域Dictionary<TKey, TValue>包含的在所述第一相关时隙的索引entries，其是字段Entry[]，具有Entry被定义为如下：

private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}

的key，value并且hashcode是不言自明的字段，关于next字段，它基本上表示一个索引，如果在该链的另一个项目（即，多个键具有相同的散列码），如果该条目是一个链的最后一个项目，则next场设置为-1。

注意：中的hashCode字段Entry struct是负值调整后的字段。

步骤3：检查是否已有条目

在此阶段，请注意，行为是不同的，具体取决于您是要更新（add = false）还是严格插入（add = true）新值。

现在，我们将检查targetBucket与从第一个条目开始的条目相关的条目，该条目可以通过以下方式给出：

var entryIndex = buckets[targetBucket];
var firstEntry = entries[entryIndex];

带有注释的实际（简化）源代码：

// Iterating through all the entries related to the targetBucket
for (var i = buckets[targetBucket]; i >= 0; i = entries[i].next)
{
    // Checked if all 
    if (entries[i].hashCode == hashCode && 
        comparer.Equals(entries[i].key, key)) 
    {
        // If update is not allowed
        if (add) 
        { 
            // Argument Exception:  
            // "Item with Same Key has already been added" thrown =]
            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
        }

        // We update the entry value
        entries[i].value = value;

        // Modification while iterating check field
        version++;

        return;
    } 
}

注意：该version字段也是在其他常见的.NET数据结构（例如List<T>）中使用的字段，该结构有助于在迭代时（在上MoveNext()）检测（并引发相关异常）。

步骤4：检查阵列是否需要调整大小

// The entries location in which the data will be inserted
var index = 0;

// The freeCount field indicates the number of holes / empty slotes available for insertions.
// Those available slots are the results of prior removal operations
if (freeCount > 0) 
{
    // The freeList field points to the first hole (ie. available slot) in the entries
    index = freeList;
    freeList = entries[index].next;
    // The hole is no longer available
    freeCount--;
}
else 
{
    // The entries array is full 
    // Need to resize it to make it bigger
    if (count == entries.Length)
    {
        Resize();
        targetBucket = hashCode % buckets.Length;
    }
    index = count;
    count++;
}

注意：关于Resize()电话：

• 像许多其他集合一样，它使基础数组（buckets和entries）的大小翻倍，从而通过在每次调整集合大小时提供足够的空间来避免过多的调整大小操作。
• Double->> ish <<，因为大小只能是来自Int32例如的预计算集的素数。 3，7，11，17，...，7199369因为使用的黄金可以减少冲突的数量（见上，这样的回答）

实际上在该Resize()方法的早期，新大小的计算如下：

public static int ExpandPrime(int oldSize)
{
    var min = 2 * oldSize;

    if ((uint) min > 2146435069U && 2146435069 > oldSize)
    {
        return 2146435069;
    }

    return HashHelpers.GetPrime(min);
}

步骤5：添加条目

因为字典做检查孔的大小，它可以再最后使用计算添加条目hashCode，key，value，右index刚刚计算并相应地调整目标斗：

entries[index].hashCode = hashCode;

// If the bucket already contained an item, it will be the next in the collision resolution chain.
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
// The bucket will point to this entry from now on.
buckets[targetBucket] = index;

// Again, modification while iterating check field
version++;

奖励：字符串特殊处理

引用下面列出的CodeProject源：

为了确保每个存储区的每个“获取”和“添加”操作不会超过100个项目，正在使用碰撞计数器。

如果在遍历数组以查找或添加项目时冲突计数器超过100（限制为硬编码）且IEqualityCompareris类型为EqualityComparer<string>.Default，IEqualityComparer<string>则正在生成新实例以用于替代字符串哈希算法。

如果找到了这样的提供程序，则字典将分配新的数组，并使用新的哈希码和相等提供程序将内容复制到新的数组。

此优化对于某些情况下可能有用，在这种情况下，您的字符串键不均匀地分布，但是也可能导致大量分配，并浪费了CPU时间来生成新的哈希码，而该​​哈希码可能是字典中的很多项。

用法

每当您使用自定义类型作为键时，别忘了拥有一个自定义类型IEqualityComparer或重写这两个Object方法（哈希码+相等），以防止自己在插入时感到意外。

您不仅可以避免一些意外，而且还可以控制所插入项目的分配。通过使哈希码分布均匀，您可以避免链接太多项目，从而避免在这些条目上进行迭代。

受访者/陪同人员的便条

我想强调一个事实，那就是知道采访的那些实现细节通常没什么大不了的（实际实现与某些版本的.NET（“ Regular”或Core ...）有所不同，并且可能仍会更改））。

如果有人问我这个问题，我会说：

• 您正在寻找的答案在StackOverflow上：）
• 您正在寻找的答案也可以
  • .NET参考
  • Github-.NET核心
• 您正在寻找的答案不需要实施细节和此处的官方文档，对于大多数使用情况而言，它们就足够了。

除非，除非...您应该在日常工作哈希表中实现自己，在这种情况下，这类知识（即，隐含细节）可能被认为是有帮助的，甚至是强制性的。

资料来源：

• .NET参考-源代码
• Github-.NET Core-源代码
• Reddit-Eli5：.NET词典中双哈希如何工作？
• 如此-在.NET词典中，双哈希如何工作？
• 代码项目-深入了解通用词典
• Mark Vincze的编码博客-返回基础：字典第1部分，哈希表
• Mark Vincze的编码博客-返回基础：字典第2部分，.NET实现

Answer 3

基本原则是:

1. 设置空数组.
2. 获取哈希码.
3. 重新散列哈希以适合数组的大小(例如,如果数组大小为31项,我们可以这样做hash % 31)并将其用作索引.

然后检索是以相同的方式查找索引,获取密钥(如果它在那里)并调用Equals该项.

这里显而易见的问题是,如果有两个属于同一索引的项目该怎么办.一种方法是在数组中存储列表或类似内容而不是键值对本身,另一种方法是"重新调用"到不同的索引中.这两种方法都有优点和缺点,Microsoft使用重新编写列表.

超过一定大小,重新调用的数量(或者如果采用该方法,存储列表的大小)会变得太大而且近O(1)行为会丢失,此时会调整表的大小以便改进这一点.

显然,一个非常差的哈希算法可以破坏它,你可以通过构建一个hashcode方法如下的对象字典来证明这一点:

public override int GetHashCode()
{
  return 0;
}

这是有效的,但很可怕,并将你的近O(1)行为变成O(n)(即使O(n)变为坏也是如此.

还有很多其他细节和优化,但以上是基本原则.

编辑:

顺便提一下,如果你有一个完美的哈希(你知道所有可能的值,并且有一个哈希方法,给每个这样的值在一个小范围内给出一个唯一的哈希值),那么就可以避免使用更通用的哈希值发生的重新引发问题 - 表,只是将哈希视为数组的索引.这给出了O(1)行为和最小内存使用,但仅在所有可能值都在较小范围内时适用.