深入理解泛型字典

引言

泛型字典是您工具箱中的一项强大工具。 

泛型部分确保了类型安全，有助于避免装箱/拆箱操作，而字典部分则允许我们管理键/值对并轻松访问它们。 
它还允许我们在常数时间内添加、删除和查找项目 复杂度 - O(1) - 即，前提是您知道如何正确使用它。  

让我们从向字典添加项目的简单示例开始，看看每种操作的时间复杂度：

Dictionary<int,string> myDictionary = new Dictionary<int,string>();
	
myDictionary.Add(1, "Item no'1"); // O(1)
myDictionary.Add(2, "Item no'2"); // O(1)
myDictionary.Add(3, "Item no'3"); // O(1)
myDictionary.Add(4, "Item no'4"); // O(N)
myDictionary.Add(5, "item no'5"); // O(1)
myDictionary.Add(6, "Item no'6"); // O(1)
myDictionary.Add(7, "item no'7"); // O(1) 
myDictionary.Add(8, "item no'8"); // O(N)
myDictionary.Add(9, "item no'9"); // O(1) 

我们可以看到，在前三个项目添加时，我们的时间复杂度为 O(1) - 这是我们所期望的。第四个和第八个项目的添加具有 O(N) 的时间复杂度（其中 N 代表字典中已存在的项目数量）。

要理解这里发生了什么，我们需要了解泛型字典是如何管理其项目的。

背景  

Object.GetHashCode 方法

System.Object 的一小组方法之一是名为 GetHashCode 的虚拟方法，其方法签名如下：

public virtual int GetHashCode()

由于 System.Object 是 .Net 中的最终基类，因此所有类型（包括值类型，它们也继承自 System.Object）都具有内置的哈希码生成功能，如果需要，子类也可以对其进行重写。

在将对象添加、删除或访问时，所有基于哈希的集合都会使用这个重要的方法。

在大多数情况下，System.Object 提供的默认 GetHashCode 实现应该足够了，但稍后在本文中，我们将讨论重写 GetHashCode 方法并创建自己的哈希算法何时是必需的。 

上图描述的是一个“简单”哈希表的原因是它不支持冲突。

.Net 中的哈希码（从对象的 GetHashCode 虚拟方法返回）是 Int32 类型 – 这意味着该方法可以返回 2^32 种可能的值。

这是否意味着我们的应用程序中不能有超过 2^32 个对象？当然不是。事实上，即使默认的 object.GetHashCode 也不保证为不同的对象返回唯一值。

此外，我们的桶数组可能比这个小得多。在上图中，桶数组设置为 30 个项目。

这里显而易见的问题是 – 是否有可能两个项目在桶数组中获得相同的索引？当然。鸽笼原理正是说明了这一点。

当两个对象在桶数组中获得相同的索引时，这意味着我们遇到了冲突 – 我们将在下一节中看到 .Net 字典如何处理冲突。

添加项目

Dictionary<int,string> myDictionary = new Dictionary<int,string>();

使用默认构造函数实例化字典时，会分配一个包含 3 个项目的数组。

然后，我们将前三个项目添加到字典中。

myDictionary.Add(1, "Item no'1"); // O(1)
myDictionary.Add(2, "Item no'2"); // O(1)
myDictionary.Add(3, "Item no'3"); // O(1)

注意 - 这意味着添加到字典中的项目总数等于数组的大小。这并不意味着桶数组的所有槽都已占用 – 正如我们上面所见，可能会发生冲突，即两个项目具有相同的索引（在哈希码调整为桶数组大小后 – 在这种情况下使用 MOD 运算符）。

让我们再添加一个项目。  

myDictionary.Add(4, "Item no'4"); // O(N)

在尝试添加第 4^个项时，字典会检查项目数量是否等于数组大小，在这种情况下是相等的，因此它会分配一个新的更大的数组。在这种情况下，新数组的大小将是 7，在添加了几个项目后，字典将再次调整大小为 17 个项目。

三？七？十七？正是如此。
字典实现包含一个内部预先计算的素数列表，将用于数组大小。

internal static readonly int[] primes = {3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};

需要调整数组大小时，新大小将是素数列表中大于旧容量乘以 2 的结果的下一个项。 

例如 

在前三次插入项目时，数组大小为 3 – 下一个项目将导致字典调整为 7，计算如下：
3 * 2 = 6 –> 列表中的下一个较大素数 – 7。   

添加几个项目后，当我们尝试插入第 8^个项时，字典将调整为：
7 * 2 = 14 –> 列表中的下一个较大素数 – 17。  

注意：如果添加的项目超过表格中的最大数量（即 7199369），resize 方法将手动搜索大于旧大小两倍的下一个素数。 

Dictionary<int,string> myDictionary = new Dictionary<int,string>(30); // The real size will be 37 – using the prime numbers table

myDictionary.Add(1, "Item no'1"); // O(1)
myDictionary.Add(2, "Item no'2"); // O(1)
myDictionary.Add(3, "Item no'3"); // O(1)
myDictionary.Add(4, "Item no'4"); // O(1)
myDictionary.Add(5, "item no'5"); // O(1)
myDictionary.Add(6, "Item no'6"); // O(1)
myDictionary.Add(7, "item no'7"); // O(1) 
myDictionary.Add(8, "item no'8"); // O(1)
myDictionary.Add(9, "item no'9"); // O(1)
//…	
myDictionary.Add(30, "item no'30"); // O(1)

注意：克隆字典时，首选使用接受源字典的相关构造函数，而不是简单地遍历旧集合并将其添加到新集合中。这样就不会有任何冗余的分配和数组复制。

处理冲突

处理冲突有几种方法。字典通过使用一种称为链式方法来处理。

字典实际上有两个长度相同的数组：

• 桶数组 – 存储对象在 entries 数组中存储的索引

• Entries 数组 – 在特殊的 O(1) 数据结构中存储实际项目（如果是引用类型 – 将存储对实际项目的引用）

 entries 数组中的每个项目都是一个具有以下字段的结构：

private struct Entry
{
    public int hashCode; // Entry (Key) hash code after being adjusted to the array size using MOD operator
    public int next; // Index of which the next item in the collision chain resides in the entries array - if there is no collision in that entry the value is -1
    public TKey key; // Entry generic Key
    public TValue value; // Entry generic Value
}

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

此优化可能适用于您的字符串键以某种方式未均匀分布的情况，但也可能导致大量分配和浪费 CPU 时间来生成可能是字典中许多项目的新的哈希码。