C# 常用集合(二):Dictionary 与 HashSet 的哈希表原理
哈希表的基本思路
数组能 O(1) 访问,是因为可以根据下标直接算出位置。哈希表把这个能力扩展到任意类型的 key:
key ──哈希函数──▶ 哈希值(一个整数)──对数组长度取模──▶ 数组下标"sword" → 98213 → 98213 % 7 = 1 → 存在位置 1只要哈希函数足够快、结果足够分散,查找、插入、删除平均都是 O(1)。
哈希冲突
不同的 key 可能算出相同的下标,这就是哈希冲突。冲突不可避免,只能处理:
| 方式 | 做法 | 代表 |
|---|---|---|
| 链地址法(拉链法) | 每个位置挂一个链表,冲突的元素都放在同一个链上 | .NET Dictionary、Java HashMap |
| 开放寻址法 | 位置被占了,就按规则找下一个空位置(比如往后一个个找) | Python dict、很多 C++ 实现 |
冲突越多,链越长,查找就越接近 O(n)。所以哈希表的性能取决于两点:哈希值分布是否均匀,以及数组是否足够大(装载因子不能太高)。
.NET Dictionary 的实现
两个数组
.NET 的 Dictionary<TKey, TValue> 用的是链地址法,但它没有用真正的链表节点,而是用两个数组模拟,避免为每个元素分配一个对象:
// 简化后的结构int[] buckets; // 桶:每个位置存这个桶中第一个元素在 entries 中的下标Entry[] entries; // 所有元素,紧凑地存放在一个数组里
struct Entry{ public int hashCode; // 缓存的哈希值 public int next; // 同一个桶中下一个元素在 entries 中的下标,-1 表示没有了 public TKey key; public TValue value;}buckets: [ 0 ][ - ][ 2 ][ - ][ - ] ← "-" 表示空桶 │ │ ▼ ▼entries: [0] key=A, next=1 ──▶ [1] key=C, next=-1 A 和 C 冲突,在同一个桶 [2] key=B, next=-1Entry 是结构体,所有元素连续存放在 entries 数组中,添加元素不会产生额外的堆分配(扩容除外),遍历时缓存也友好。
查找流程
dict[key] 或 TryGetValue(key, out value) 的过程:
- 计算
hash = comparer.GetHashCode(key) & 0x7FFFFFFF(去掉符号位,保证非负)。 - 计算桶下标
bucket = hash % buckets.Length。 - 从
buckets[bucket]拿到第一个元素的下标,沿着next一个个往下找。 - 对每个元素,先比较缓存的
hashCode,相等时再调用Equals比较 key。 - 找到就返回,走到
-1还没找到就说明不存在。
先比哈希值是一个优化:整数比较很快,哈希值不同的 key 肯定不相等,可以跳过开销更大的 Equals。
删除与空闲链表
删除元素时,entries 中的那个位置不会被移走,而是被串到一个空闲链表里。之后再添加元素时,优先复用这些空位。
这带来一个结论:Dictionary 的遍历顺序是不确定的。没有删除过元素时,遍历顺序恰好是插入顺序;一旦删除后再添加,新元素会填进旧的空位,顺序就乱了。不要依赖 Dictionary 的遍历顺序。
扩容
Dictionary在元素个数达到entries的长度时扩容,也就是装载因子达到 1 才扩容。用链地址法,冲突了也只是链变长,所以可以容忍较高的装载因子。- 新的大小是大于当前两倍的最小质数(比如 3 → 7 → 17 → 37 → …)。
- 扩容时要新建两个数组,并把所有元素重新计算桶位置(rehash),是 O(n) 的操作。
为什么用质数? 桶下标是 hash % 长度。如果长度是 2 的幂、而哈希值的低位分布不均匀(比如都是偶数),取模后就会集中在少数桶里。长度取质数,能让取模的结果更分散。
Java 的
HashMap选择了另一条路:长度用 2 的幂,用位运算代替取模(更快),再对哈希值做一次扰动(把高位混进低位)来弥补分布问题。
实践:和 List 一样,能预估数量时指定初始容量:
var map = new Dictionary<int, Enemy>(1000);GetHashCode 与 Equals
必须遵守的约定
作为 key 的类型,GetHashCode 和 Equals 必须满足:
Equals相等的两个对象,GetHashCode必须相等。 反过来不要求:哈希值相等的对象不一定相等(那就是冲突)。- 对象作为 key 存在字典中期间,它的哈希值不能变。
违反第 1 条:重写了 Equals 却没重写 GetHashCode,两个”相等”的 key 落到不同的桶里,字典里就会出现”重复”的 key,也查不到本该存在的值。所以重写 Equals 时必须同时重写 GetHashCode,编译器也会给出警告。
违反第 2 条:
var pos = new MutableKey { X = 1 };dict[pos] = "A";pos.X = 2; // 修改了参与哈希计算的字段dict[pos]; // 找不到了:按新哈希值去了另一个桶所以用作 key 的类型最好是不可变的。string、int、枚举都是不可变的,最适合做 key。
默认实现
| 类型 | 默认的 Equals / GetHashCode |
|---|---|
| 引用类型(class) | 基于引用:同一个对象才相等 |
| 值类型(struct) | ValueType 的实现:逐字段比较,可能用到反射,慢;默认的哈希值可能只用到部分字段,分布差 |
string | 基于内容 |
结构体作 key:会装箱
Dictionary 通过 EqualityComparer<TKey>.Default 比较 key:
- 如果
TKey实现了IEquatable<TKey>,会使用泛型版本的Equals(TKey),不装箱。 - 否则只能调用
Equals(object),每次比较都要把 key 装箱。
所以自定义结构体作 key 时,要这样写:
public readonly struct GridPos : IEquatable<GridPos>{ public readonly int X, Y; public GridPos(int x, int y) { X = x; Y = y; }
public bool Equals(GridPos other) => X == other.X && Y == other.Y; public override bool Equals(object obj) => obj is GridPos p && Equals(p); public override int GetHashCode() => (X * 397) ^ Y; // 或 HashCode.Combine(X, Y)}在旧版本的 Unity(旧版 Mono)中,枚举作 key 也会因为比较器的实现问题而装箱,当时的常见做法是自己实现一个
IEqualityComparer<TEnum>传给字典。新版本已经没有这个问题。
也可以不修改 key 的类型,而是在创建字典时传入一个自定义的 IEqualityComparer<TKey>,比如忽略大小写的字符串比较:
var map = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);Unity 对象作 key:为什么慢
用 GameObject、Transform 或组件作为 Dictionary 的 key,比用普通的 class 慢。原因在 UnityEngine.Object 重写的相等判断上。
以 Unity 公开的 C# 源码为例,UnityEngine.Object 的 Equals 大致是这样的:
public override bool Equals(object other){ Object otherAsObject = other as Object; // 1. 类型转换 if (otherAsObject == null && other != null && !(other is Object)) // 2. 这里的 == 是 Unity 重载的 return false; return CompareBaseObjects(this, otherAsObject);}
public static bool operator ==(Object x, Object y) => CompareBaseObjects(x, y);
static bool CompareBaseObjects(Object lhs, Object rhs){ // 一方为 null 时,要检查另一方的原生对象是否还存在:IsNativeObjectAlive // 都不为 null 时,比较两者的对象 ID}Dictionary 每次比较 key 时都会调用这个 Equals:
- 先做一次
as类型转换; - 再用重载的
==和 null 比较,这一步会调用IsNativeObjectAlive,到原生层查找 C++ 对象是否还存在; - 最后才比较对象 ID。
而普通 class 的默认 Equals 只是比较引用,一条指令就完成了。GetHashCode 倒是不慢,只是对对象 ID 做一次哈希。
具体实现在不同 Unity 版本中有差异(比如新版本用 EntityId 代替了 InstanceID),但”相等判断要额外检查原生对象”这一点是一致的。实际开销以 Profiler 测量为准。
另一个问题:已销毁的对象
对象被 Destroy 后,它的 C# 壳仍然作为 key 留在字典里:key == null 判断为 true,但字典不会自动删除它,C# 壳也因为被字典引用而无法回收(见 Unity 内存构成)。对象销毁时要记得从字典中移除。
解决方法
// 方法一:用整数 ID 作 keyvar map = new Dictionary<int, EnemyData>();map[go.GetInstanceID()] = data;
// 方法二:传入按引用比较的比较器,绕过 Unity 重写的 Equalspublic sealed class ReferenceComparer<T> : IEqualityComparer<T> where T : class{ public static readonly ReferenceComparer<T> Instance = new(); public bool Equals(T x, T y) => ReferenceEquals(x, y); public int GetHashCode(T obj) => RuntimeHelpers.GetHashCode(obj);}var map2 = new Dictionary<GameObject, EnemyData>(ReferenceComparer<GameObject>.Instance);更根本的做法是不用 Unity 对象去查数据:让组件自己持有它的数据引用,或者在实体创建时分配一个自己的 ID。
使用注意
-
查找用
TryGetValue,不要先ContainsKey再取值,那样会查两次:if (dict.TryGetValue(id, out var enemy)) { ... } -
dict[key]读取不存在的 key 会抛出KeyNotFoundException;dict[key] = value写入时,不存在就添加,存在就覆盖。Add遇到已存在的 key 会抛异常。 -
遍历时不能增删,否则抛出
InvalidOperationException。可以先把要删除的 key 收集起来,遍历结束后再删。(新版 .NET 允许在遍历中Remove,但为了兼容性不要依赖。) -
不是线程安全的。多线程读写要加锁,或使用
ConcurrentDictionary。 -
foreach遍历Dictionary不产生 GC,枚举器是结构体。
HashSet<T>
HashSet<T> 的内部结构和 Dictionary 基本一样,只是每个元素只有 key 没有 value。
Add、Remove、Contains平均 O(1)。Add重复元素时返回false,不抛异常。- 用于去重和快速判断是否存在。在大量数据中判断”是否包含”,不要用
List.Contains(O(n)),用HashSet。 - 支持集合运算:
UnionWith(并集)、IntersectWith(交集)、ExceptWith(差集)、IsSubsetOf等。
有序的替代:SortedDictionary 与 SortedList
哈希表是无序的。需要按 key 排序遍历时,用这两个:
Dictionary | SortedDictionary | SortedList | |
|---|---|---|---|
| 底层 | 哈希表 | 红黑树(自平衡二叉搜索树) | 两个有序数组(keys、values) |
| 查找 | O(1) | O(log n) | O(log n),二分查找 |
| 插入 / 删除 | O(1) | O(log n) | O(n),要挪动数组元素 |
| 按下标访问 | 不支持 | 不支持 | 支持 |
| 内存 | 中 | 多(每个节点一个对象) | 少 |
| 遍历顺序 | 不确定 | 按 key 排序 | 按 key 排序 |
- 数据量大、插入删除频繁、需要有序:
SortedDictionary。 - 数据量小、基本只读、需要有序或按下标访问:
SortedList。 - 不需要有序:
Dictionary。
常见追问
Dictionary 的底层是怎么实现的?
哈希表,链地址法解决冲突。用 buckets 数组记录每个桶的第一个元素,用 entries 结构体数组存放所有元素,元素之间通过 next 下标串成链,不需要为每个元素分配节点对象。
Dictionary 查找的过程是怎样的?
计算 key 的哈希值,对桶数组长度取模得到桶,沿着链逐个比较:先比哈希值,再调 Equals。
哈希冲突怎么解决? 链地址法:冲突的元素放在同一个桶的链上。开放寻址法:被占了就按规则找下一个空位。.NET 的 Dictionary 用前者。
Dictionary 什么时候扩容?为什么扩容到质数? 元素个数达到容量时扩容到大于两倍的最小质数,并重新计算所有元素的位置。质数能让取模后的结果更分散,减少冲突。
为什么重写 Equals 必须重写 GetHashCode? Dictionary 先用哈希值找桶,再用 Equals 比较。相等的对象如果哈希值不同,会被放进不同的桶,导致查不到或出现重复 key。
结构体作为 Dictionary 的 key 要注意什么?
实现 IEquatable<T> 并重写 GetHashCode,否则比较时会装箱,默认实现还可能用到反射、哈希分布也差。key 最好不可变。
为什么用 GameObject 作 Dictionary 的 key 会慢?
Unity 对象重写了 Equals,比较时要做类型转换,并通过重载的 == 到原生层检查对象是否还存在,比普通引用比较慢得多。可以改用 GetInstanceID() 作 key,或者传入按引用比较的比较器;另外要注意对象销毁后从字典中移除。
Dictionary 的遍历顺序是插入顺序吗? 不保证。没删除过元素时碰巧是,删除后新元素会复用空位,顺序就变了。
Dictionary、SortedDictionary、SortedList 怎么选? 不需要有序用 Dictionary;需要有序且插入频繁用 SortedDictionary(红黑树);数据少、基本只读、需要按下标访问用 SortedList(有序数组)。
判断一个元素是否存在,用 List 还是 HashSet? 数据量大时用 HashSet,O(1);List.Contains 是 O(n)。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!