C# 中 Dictionary 的用法和内部实现

推荐答案

// www.javascriptcn.com code example
// 创建一个Dictionary
Dictionary<string, int> dictionary = new Dictionary<string, int>();

// 添加元素
dictionary.Add("apple", 1);
dictionary.Add("banana", 2);

// 访问元素
int value = dictionary["apple"]; // 输出: 1

// 修改元素
dictionary["banana"] = 3;

// 删除元素
dictionary.Remove("apple");

// 检查键是否存在
bool containsKey = dictionary.ContainsKey("banana"); // 输出: true

// 遍历Dictionary
foreach (var kvp in dictionary)
{
    Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value}");
}

本题详细解读

Dictionary 的用法

Dictionary<TKey, TValue> 是 C# 中常用的集合类型，用于存储键值对。它提供了快速的查找、插入和删除操作。以下是一些常见的操作：

1. 创建 Dictionary：使用 new 关键字创建一个 Dictionary 实例。
2. 添加元素：使用 Add 方法或索引器添加键值对。
3. 访问元素：通过键访问对应的值。
4. 修改元素：通过键修改对应的值。
5. 删除元素：使用 Remove 方法删除指定的键值对。
6. 检查键是否存在：使用 ContainsKey 方法检查字典中是否包含指定的键。
7. 遍历 Dictionary：使用 foreach 循环遍历字典中的所有键值对。

Dictionary 的内部实现

Dictionary<TKey, TValue> 的内部实现基于哈希表（Hash Table），它通过哈希函数将键映射到存储桶（bucket）中。哈希表的主要优点是提供了接近 O(1) 的平均时间复杂度来进行查找、插入和删除操作。

1. 哈希函数：Dictionary 使用键的哈希码来确定存储桶的位置。哈希码通过 GetHashCode 方法获取。
2. 冲突处理：当两个不同的键产生相同的哈希码时，会发生哈希冲突。Dictionary 使用链地址法（Chaining）来处理冲突，即在同一个存储桶中使用链表存储多个键值对。
3. 扩容机制：当 Dictionary 中的元素数量超过当前容量的阈值时，会自动进行扩容。扩容操作会重新计算所有键的哈希码，并将它们重新分配到新的存储桶中。

通过这种实现方式，Dictionary 能够在大多数情况下提供高效的查找和操作性能。