C#面试常考随笔11：Dictionary＜K, V＞、Hashtable的内部实现原理是什么？效率如何？

Dictionary<K, V>

• 底层数据结构：使用哈希表（Hash Table），由一个数组和链表（或在.NET Core 2.1 及之后版本中，当链表长度达到一定阈值时转换为红黑树）组成。数组中的每个元素称为一个桶（Bucket），用于存储键值对。
• 工作原理：添加键值对时，先计算键（Key）的哈希码，通过哈希码对数组长度取模，得到对应的桶索引。若该桶为空，直接将键值对存入；若不为空（即发生哈希冲突），则以链表（或红黑树）的形式将新的键值对添加到该桶的链表（或红黑树）中。查找元素时，先计算键的哈希码定位到桶，然后在桶内的链表（或红黑树）中通过键的比较（调用Equals方法）找到对应的值。

Hashtable

• 底层数据结构：同样基于哈希表实现，由数组和链表构成。数组中的每个元素是一个桶，用于存储键值对。
• 工作原理：添加键值对时，计算键的哈希码，对数组长度取模确定桶索引。若桶为空，直接存入键值对；若桶已有元素（哈希冲突），则将新键值对添加到该桶的链表中。查找元素时，先计算键的哈希码定位桶，再在桶内链表中通过键的比较（调用Equals方法）获取对应的值。与Dictionary<K, V>不同的是，Hashtable是线程安全的，因为其方法实现中添加了synchronized关键字（在多线程环境下可确保线程同步，但性能相对Dictionary<K, V>较低），并且Hashtable的键和值都是object类型，存储和获取时可能需要类型转换，存在装箱和拆箱操作。

查找效率

• 理想情况：二者在理想情况下查找效率都较高。它们内部都基于哈希表结构，通过计算键的哈希码来定位存储位置。在没有哈希冲突（即不同键计算出的哈希码对应到哈希表中的不同位置）时，查找操作可以在接近常数时间（O (1)）内完成，即能快速定位到目标键值对。
• 存在哈希冲突时：
  • Hashtable：当发生哈希冲突，同一桶中存在多个键值对（以链表形式存储）时，查找时需要在链表中顺序比较键。如果哈希冲突严重，链表较长，查找效率会降低，时间复杂度可能退化为 O (n)，n 为链表长度。不过，由于其内部实现对哈希函数等进行了优化，在一般情况下能较好地分散哈希值，减少冲突。
  • Dictionary<K, V> ：在.NET Core 2.1 之前，处理哈希冲突与Hashtable类似，通过链表存储冲突的键值对，冲突严重时查找效率受链表长度影响。在.NET Core 2.1 及之后版本中，当链表长度达到一定阈值（通常为 8 ）时，会将链表转换为红黑树。红黑树是一种自平衡的二叉搜索树，查找操作的时间复杂度为 O (log n)，相比于长链表的 O (n)，在冲突较多时能提供更稳定和高效的查找性能。