.NET 数据结构：哈希冲突与算法

为了解决哈希表中可能出现的数据冲突，需要对哈希表的数据结构和哈希算法进行改进。

解决哈希冲突的策略

当不同的键（Key）通过哈希函数计算出相同的索引时，就发生了哈希冲突 (Hash Collision)。
常见的解决策略主要有两种：开放寻址法和链式地址法。

开放寻址法 (Open Addressing)

开放寻址的核心思想是：当目标位置 bucket[i] 被占用时，按照某种规则寻找下一个空闲位置 bucket[j]。所有数据都存储在同一个哈希表数组中。

最简单的探测方式是线性探测 (Linear Probing)：

存入：如果位置 i 被占用，则检查 i+1，直到找到空位。
查找：计算位置 i，如果该位置不是目标 Key，则检查 i+1，直到找到目标或遇到空位（说明不存在）。

这种方式的优点是内存数据连续，对 CPU 缓存友好。但缺点也很明显：

聚集现象 (Clustering)：冲突的数据容易连成一片，导致后续插入和查找效率急剧下降。
删除困难：直接删除元素会“断链”，导致后续元素无法被查找。通常需要使用特殊的标记（如 Deleted）来代替物理删除。

链式地址法 (Chaining)

链式地址法将哈希表的每个 bucket 视为一个链表的头节点。当发生冲突时，将新元素添加到该 bucket 对应的链表中。

存入：计算哈希值定位 bucket，遍历链表检查 Key 是否已存在。若不存在，将新节点追加到链表末尾（或头部）。
查找：定位 bucket，遍历链表寻找匹配的 Key。

这种方式的优点是：

容忍度高：不像开放寻址法那样受限于数组长度，理论上链表可以无限延伸（只要内存足够）。
删除简单：只需从链表中移除节点即可。

缺点则是链表节点需要额外的内存存储指针，且分散的内存节点对 CPU 缓存不友好。

.NET 的哈希实现

优秀的哈希函数

哈希算法的优化目标是将键值对均匀地分布到哈希表中，避免为了减少冲突而导致数据在某些 buckets 中堆积。

在 .NET 中，Dictionary<TKey, TValue> 的核心逻辑依赖于 GetHashCode() 方法。当插入元素时，它会计算 Key 的哈希值，并通过取模运算（或者位运算）映射到 buckets 数组的索引。

参考源代码 Dictionary.cs：

// 1. 获取哈希值
uint hashCode = (uint)((typeof(TKey).IsValueType && comparer == null) 
    ? key.GetHashCode() 
    : comparer!.GetHashCode(key));

// 2. 定位 bucket（.NET Core 优化了取模运算）
ref int bucket = ref GetBucket(hashCode);

冲突处理机制

值得注意的是，早期版本的 .NET Framework 和 .NET Core 中，Dictionary<TKey, TValue> 仅使用链式地址法（通过 next 数组模拟链表）来解决冲突。

与 Java 的 HashMap 不同（Java 8+ 会在链表过长时转换为红黑树），.NET 的标准 Dictionary 不会将链表转换为红黑树。如果发生大量哈希冲突（例如哈希洪水攻击 Hash Flooding），性能会退化为 O(n)。

不过，为了应对这种攻击，.NET 在检测到频繁冲突时，可能会动态切换哈希种子（Seed）并重组哈希表。