C# 常用集合(二):Dictionary 与 HashSet 的哈希表原理

3026 字
15 分钟
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=-1

Entry 是结构体,所有元素连续存放在 entries 数组中,添加元素不会产生额外的堆分配(扩容除外),遍历时缓存也友好。

查找流程#

dict[key] 或 TryGetValue(key, out value) 的过程:

  1. 计算 hash = comparer.GetHashCode(key) & 0x7FFFFFFF(去掉符号位,保证非负)。
  2. 计算桶下标 bucket = hash % buckets.Length。
  3. 从 buckets[bucket] 拿到第一个元素的下标,沿着 next 一个个往下找。
  4. 对每个元素,先比较缓存的 hashCode,相等时再调用 Equals 比较 key。
  5. 找到就返回,走到 -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 必须满足:

  1. Equals 相等的两个对象,GetHashCode 必须相等。 反过来不要求:哈希值相等的对象不一定相等(那就是冲突)。
  2. 对象作为 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 作 key
var map = new Dictionary<int, EnemyData>();
map[go.GetInstanceID()] = data;
// 方法二:传入按引用比较的比较器,绕过 Unity 重写的 Equals
public 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 排序遍历时,用这两个:

DictionarySortedDictionarySortedList
底层哈希表红黑树(自平衡二叉搜索树)两个有序数组(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)。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

C# 常用集合(二):Dictionary 与 HashSet 的哈希表原理
https://xslab.cloud/posts/csharp/collections/hash-collections/
作者
LuxFire
发布于
2026-10-10
许可协议
CC BY-NC-SA 4.0
相关文章 智能推荐
1
C# 常用集合(一):数组、List、LinkedList、Stack、Queue
C#底层/数据结构 数组为什么能 O(1) 访问;List 的扩容机制与各操作的复杂度;LinkedList 为什么实际很少更快;Stack 与 Queue(环形数组)的实现;以及所有常用集合的选型对比表。
2
C# 迭代器与 async/await 原理:编译器生成的状态机
C#底层/关键字 yield return 和 async/await 编译后分别变成了什么;状态机如何保存局部变量、如何从中断处继续;awaiter 模式;async 状态机什么时候会分配堆内存;SynchronizationContext 决定 await 之后在哪个线程继续;以及"异步不等于多线程"。
3
C# 关键字速查
C#底层/关键字 按类别整理 C# 常用关键字,每个一两句话说明用途和要点,复杂的关键字链接到专题文章。适合复习时快速过一遍。
4
C# 访问修饰符与类型修饰符
C#底层/关键字 六种访问级别的可见范围对比,protected internal 与 private protected 的区别,各种成员的默认访问级别;以及 static、sealed、abstract、partial 修饰类型时的含义和限制,附 Unity 中 asmdef 与静态字段的注意点。
5
C# 委托、事件与 Lambda:原理、区别与闭包陷阱
C#底层/关键字 委托的本质是什么,多播委托的调用顺序、返回值与异常;事件在委托之上加了哪些限制,委托与事件的对比;Lambda 与闭包编译后的样子,循环中捕获变量的经典陷阱;以及委托在 Unity 中的 GC 开销、事件导致的内存泄漏和 UnityEvent。
随机文章 随机推荐
Profile Image of the Author
LuxFire
Hello, I'm LuxFire.
公告
欢迎来到我的博客!这是一则示例公告。
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
60
分类
6
标签
164
总字数
171,869
运行时长
0 天
最后活动
0 天前

文章目录