.NET C# Dictionary Hashtable

.NET C# Dictionary & Hashtable

1 Dictionary

1.1 底层实现

• 哈希表：Dictionary 底层实现是一个哈希表。它使用键的哈希值来快速定位值。
• 泛型支持：Dictionary<TKey, TValue> 是泛型的，可以存储任何类型的键和值，这增加了类型安全性。
• 存储结构：内部使用一个数组来存储键值对，并通过哈希函数计算每个键的哈希值，将其映射到数组中的一个索引位置。

1.2 优点

• 类型安全：由于是泛型，编译时可以检查类型，避免了类型转换错误。
• 性能：查找、插入和删除操作的平均时间复杂度为 O(1)，非常高效。
• 灵活性：可以存储任何类型的键和值，使用方便。

1.3 缺点

• 内存消耗：由于使用泛型和哈希表，内存消耗相对较大。
• 初始化时间：初始化和重新调整大小时可能会有较大的时间开销。

2 Hashtable

2.1 底层实现

• 哈希表：Hashtable 也使用哈希表来实现。
• 非泛型：Hashtable 是非泛型的，键和值都是 object 类型，需要进行装箱和拆箱操作。

2.2 优点

• 灵活性：可以存储任何类型的键和值，但需要进行类型转换。
• 历史悠久：在 .NET 1.0 中就存在，兼容旧版本代码。

2.3 缺点

• 类型不安全：由于键和值都是 object 类型，编译时无法检查类型，容易出错。
• 性能较差：由于需要装箱和拆箱，性能不如 Dictionary。
• 过时：随着泛型集合的引入，Hashtable 已经不再推荐使用。

3 对比总结

1. 类型安全性：Dictionary 是泛型的，更加类型安全，而 Hashtable 是非泛型的，需要进行类型转换。
2. 性能：Dictionary 性能优于 Hashtable，特别是在涉及大量数据操作时。
3. 内存消耗：Dictionary 由于泛型和哈希表的实现，内存消耗较大，而 Hashtable 相对较小，但性能不如前者。
4. 历史兼容性：Hashtable 由于存在时间较长，在一些旧项目中仍然可以见到，但新的项目一般推荐使用 Dictionary。

4 遍历方式，与耗时对比

foreach遍历

foreach (DictionaryEntry entry in hashtable)
{var key = entry.Key;var value = entry.Value;
}foreach (KeyValuePair<int,int> entry in dictionary)
{var key = entry.Key;var value = entry.Value;
}

Keys遍历

foreach (var key in hashtable.Keys)
{var value = hashtable[key];
}foreach (var key in dictionary.Keys)
{var value = dictionary[key];
}

IDictionaryEnumerator遍历

IDictionaryEnumerator enumeratorHt = hashtable.GetEnumerator();
while (enumeratorHt.MoveNext())
{var key = enumeratorHt.Key;var value = enumeratorHt.Value;
}IDictionaryEnumerator enumeratorDic = dictionary.GetEnumerator();
while (enumeratorDic.MoveNext())
{var key = enumeratorDic.Key;var value = enumeratorDic.Value;
}

耗时对比

static void Main(string[] args)
{// 创建并填充HashtableHashtable hashtable = new Hashtable();Dictionary<int,int> dictionary = new Dictionary<int,int>();for (int i = 0; i < 10000000; i++){hashtable[i] = i;dictionary[i] = i;}// 基准测试Stopwatch stopwatch = new Stopwatch();// 测试foreach遍历stopwatch.Start();foreach (DictionaryEntry entry in hashtable){var key = entry.Key;var value = entry.Value;}stopwatch.Stop();Console.WriteLine($"Hashtable - foreach遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");stopwatch.Restart();stopwatch.Start();foreach (KeyValuePair<int,int> entry in dictionary){var key = entry.Key;var value = entry.Value;}stopwatch.Stop();Console.WriteLine($"Dictionary - foreach遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");// 测试Keys遍历stopwatch.Restart();foreach (var key in hashtable.Keys){var value = hashtable[key];}stopwatch.Stop();Console.WriteLine($"Hashtable - Keys遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");stopwatch.Restart();foreach (var key in dictionary.Keys){var value = dictionary[key];}stopwatch.Stop();Console.WriteLine($"Dictionary - Keys遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");// 测试IDictionaryEnumerator遍历stopwatch.Restart();IDictionaryEnumerator enumeratorHt = hashtable.GetEnumerator();while (enumeratorHt.MoveNext()){var key = enumeratorHt.Key;var value = enumeratorHt.Value;}stopwatch.Stop();Console.WriteLine($"Hashtable - IDictionaryEnumerator遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");stopwatch.Restart();IDictionaryEnumerator enumeratorDic = dictionary.GetEnumerator();while (enumeratorDic.MoveNext()){var key = enumeratorDic.Key;var value = enumeratorDic.Value;}stopwatch.Stop();Console.WriteLine($"Dictionary - IDictionaryEnumerator遍历耗时: {stopwatch.ElapsedMilliseconds} 毫秒");
}

输出：

Hashtable - foreach遍历耗时: 576 毫秒
Dictionary - foreach遍历耗时: 93 毫秒
Hashtable - Keys遍历耗时: 279 毫秒
Dictionary - Keys遍历耗时: 112 毫秒
Hashtable - IDictionaryEnumerator遍历耗时: 147 毫秒
Hashtable - foreach遍历耗时: 576 毫秒
Dictionary - foreach遍历耗时: 93 毫秒
Hashtable - Keys遍历耗时: 279 毫秒
Dictionary - Keys遍历耗时: 112 毫秒
Hashtable - IDictionaryEnumerator遍历耗时: 147 毫秒
Dictionary - IDictionaryEnumerator遍历耗时: 169 毫秒