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

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

改良的数据结构

当数据通过哈希函数运算后预备存储到哈希表的某个位置时，发现那个位置已经有数据存在了。

开放寻址

开放寻址会在目标位置后找个空位塞入新数据，而找空位的方式各有不同，此处以最简单的线性探测为例。

线性探测的开放寻址会在冲突的位置后遵循某个线性函数，将数据放到空位。

比如在冲突位置后遍历，直到遇到空位，而遍历的元素数量通常是固定的。

对于以下场景：

• 在放入元素时：发现哈希函数计算后的索引已存在数据，则往后遍历一段固定的步长，随后放入新数据。
• 在访问元素时：发现该索引存在哈希冲突，则同样地往后遍历一段固定的步长，返回数据。

这种方式显然存在两种不足：

• 冲突后的位置依然存在数据，处理有些麻烦
• 线性探测会导致一群元素挨在一块，空间利用率会下降

链式地址

如果把哈希表的元素变更为链表，那么出现哈希冲突后，只需要沿着目标索引的链表往后添加即可。

对于以下场景：

• 在放入元素时：借由哈希函数找到链表的头节点，然后将数据添加到链表。
• 在访问元素时：通过哈希函数找到链表的头节点，然后遍历链表并对比键以发现目标的键值对。

虽然这种方式相比于开放寻址提高了空间利用率，遇到冲突也能简单地解决。

但是由于是其元素是基于链表的，这也就意味着这种哈希表的占用空间大，且查询需要遍历，效率低。

哈希算法

哈希算法的优化目标应为将键值对均匀地分布到哈希表中，不要堆积。

在C#中，键值对会借助GetHashCode()并对当前哈希表容量取余得到索引，比如Dictionary.cs

1
2
3
4
5

uint hashCode = (uint)((typeof(TKey).IsValueType && comparer == null) ? key.GetHashCode() : comparer!.GetHashCode(key));
 
uint collisionCount = 0;
ref int bucket = ref GetBucket(hashCode);
int i = bucket - 1; // Value in _buckets is 1-based

和Java语言类似，C#对于冲突键值对少的情况下会基于链表存储，多了之后就会转换为红黑树。