HashSetT独立实现的哈希集合而不是“无值 Dictionary”系列C# 与常用数据结构源码剖析 · 数据结构—哈希与映射篇源码基线dotnet/runtime v8.0.0 / 5535e31a... 的 HashSet.cs公共语义基线.NET 8 的HashSetT、ISetT与IReadOnlySetT公开契约阅读约定本文把固定 tag 的私有字段称为“实现事实”带“结构化节选”的代码为保留控制流的改写不是可替换运行时源码“伪代码”只用于解释算法。Unity、Mono 和未来 .NET 版本必须以项目实际运行时核验。一、先纠正标题留下的误导把HashSetT叫作“基于 Dictionary 的无值哈希集合”可以帮助初学者联想到“只存键、不存关联值”却不是准确的对象模型描述。在 .NET 8 中HashSetT没有包一层DictionaryT, bool也没有与某个 Dictionary 实例共享桶数组。它有自己的_buckets、_entries、_count、空闲链、比较器和枚举器条目只保存HashCode、Next与Value。源码注释所说的“uses the same array-based implementation as Dictionary”应理解为两者采用相同家族的数组哈希表设计维护方式和若干优化彼此对齐。它不等于“HashSet 继承 Dictionary”也不等于“所有私有实现完全共用”。本文保留原文件名以免破坏专栏链接但正文使用更准确的说法独立实现、架构同源、集合语义不同。HashSetT解决的不是键到值的映射而是一个等价关系下的有限集合。若比较器认为x与y相等容器里至多保留一个等价代表Add是否成功、Contains查找谁、Remove删除谁以及并集、交集、子集判断全都由同一个IEqualityComparerT决定。因此理解 HashSet 的第一关键词不是“没有 value 的 Dictionary”而是唯一性由比较器定义。var names new HashSetstring(StringComparer.OrdinalIgnoreCase); Console.WriteLine(names.Add(PlayerOne)); // true Console.WriteLine(names.Add(playerone)); // false Console.WriteLine(names.Count); // 1这里没有发生字符串规范化也没有先转小写再保存。第二次添加失败是因为比较器把两个字符串放进同一个等价类。集合仍保留第一次插入的那个实例如果调用者需要取回容器中的等价代表可使用TryGetValue。二、公开契约集合承诺什么不承诺什么2.1 唯一、无序、可变HashSetT实现ICollectionT、ISetT、IReadOnlyCollectionT和IReadOnlySetT。它提供三组能力单元素的Add、Contains、Remove原地集合运算集合关系判断。所谓“无序”不是说每次枚举都随机而是公开契约没有把某种顺序承诺给调用者。当前实现常呈现与条目槽位有关的稳定表象但删除、空闲槽复用、扩容、运行时升级或序列化往返都不应被当成业务排序规则。若系统需要“唯一且按插入顺序输出”应显式维护顺序结构与成员索引或选用契约真正承诺顺序的类型不要对 HashSet 当前的枚举现象编写持久化协议、联网协议或回放校验。2.2null、默认比较器与自定义比较器对于允许为null的引用类型默认集合可以保存一个null。在 .NET 8 固定实现中空引用的哈希码按零处理最终相等判断仍由比较器完成。值类型使用默认比较器时JIT 有机会将EqualityComparerT.Default的路径去虚调用引用类型会在字段里保留比较器实例以避免共享泛型代码反复获取默认比较器。这是私有性能策略不改变公共等价语义。比较器必须满足等价关系与哈希一致性自反、对称、传递而且Equals(x, y)为真时必须有相同哈希码。哈希相同不要求对象相等碰撞会由第二阶段的Equals区分。sealed class PlayerIdComparer : IEqualityComparerPlayer { public bool Equals(Player? x, Player? y) x?.Id y?.Id; public int GetHashCode(Player obj) obj.Id; }还要守住“入集合后哈希身份不可变”的约束。下面的代码能够编译却破坏了桶定位不变式对象仍留在旧哈希码对应的桶链中修改Id后再按新哈希查找可能失败。var p new Player { Id 7, Name A }; var set new HashSetPlayer(new PlayerIdComparer()) { p }; p.Id 99; // 错误修改了参与哈希和相等判断的字段 Console.WriteLine(set.Contains(p)); // 结果不再可靠地表达业务意图正确方案通常是使用不可变标识、只把Id放入集合或在改变身份前先按旧身份删除、改变后重新添加。不要指望 Resize 自动“治愈”已变异的元素。2.3 集合关系按集合语义处理重复项SetEquals、IsSubsetOf等 API 接受IEnumerableT而参数不一定是集合。参数中的重复元素不应被重复计数。例如{1,2}与序列1,1,2,2在集合意义下相等“proper subset”比较的是不同等价类而不是枚举产生了多少次值。源码因此需要记录“已经命中过的本集合槽位”不能简单比较other的遍历次数与Count。两个 HashSet 只有在元素类型相同且比较器相等时才能安全使用“对方已经去重”的快速假设。比较器不同意味着对“唯一元素”的划分不同。例如大小写敏感集合中的A与a是两个元素在忽略大小写集合中却属于一个等价类此时直接比较 Count 或仅调用对方的Contains都可能错误。三、.NET 8 的存储模型与不变式固定到v8.0.0核心字段可以抽象为// 结构化节选字段名对应 v8.0.0省略序列化与 64 位取模辅助字段。 private int[]? _buckets; private Entry[]? _entries; private int _count; private int _freeList; private int _freeCount; private int _version; private IEqualityComparerT? _comparer; private struct Entry { public int HashCode; public int Next; public T Value; }不要据此写死“每个 Entry 必然多少字节”。结构体大小受T、目标架构、字段对齐和运行时布局影响整个集合还包含对象头、桶数组、条目数组的数组头、未使用容量和比较器对象。DictionaryT,bool多一个值字段也不代表它在所有T上固定多出某个字节数对齐可能吞掉或扩大差异。要回答具体项目的内存问题应在目标架构上用诊断工具测量并把容量与活跃元素数同时记录。3.1 桶采用一基索引冲突链采用零基索引_buckets[b]保存“条目索引加一”零表示空桶取出后减一才是_entries下标。这样新数组依赖 CLR 的零初始化即可表达所有空桶。有效条目的Next保存同一桶中下一个条目的零基下标-1表示链尾。buckets[b] 5 减一 entries[4] - entries[1] - -1同一个Next字段还承担空闲链编码。删除槽的Next使用小于-1的特殊负数配合StartOfFreeList -3可逆地编码下一个空闲下标。于是枚举器能用entry.Next -1判断槽位是否有效无需额外的布尔字段。3.2_count不是公开 Count_count是已经启用过的条目区间上界删除一个元素不会把末端之前的_count递减而是增加_freeCount并把槽位接入_freeList。所以公开 Count _count - _freeCount下一次插入先复用空闲槽只有没有空闲槽且_count _entries.Length时才扩容。由此可见“删掉很多元素以后 Count 很小”不意味着数组自动缩小。若长期峰值造成明显闲置调用者需要在合适的非热点阶段考虑TrimExcess。3.3 三组必须同时成立的不变式第一任意有效条目必须位于其当前哈希码对应的桶链上。第二一条合法冲突链访问的节点数不应超过条目数组长度源码以碰撞计数发现无锁并发写导致的环并抛出异常避免死循环但这不是线程安全承诺。第三有效链与 free list 不得把同一槽位同时视为活跃和空闲。普通 HashSet 不支持多个线程并发写。即便源码有“concurrent operations not supported”的损坏检测也不能提供原子性、内存可见性或丢失更新保护。安全模型通常是构造完成后安全发布并只读或者所有访问遵守同一把锁或者重新选择适合并发与快照语义的方案。四、查询与插入平均常数时间从何而来4.1FindItemIndex的真实工作Contains最终定位条目索引。算法先由同一比较器计算哈希码通过取模映射桶再沿冲突链逐项检查。先比缓存哈希码命中后才执行可能更昂贵的相等比较。// 结构化节选合并值类型默认比较器与自定义比较器两套快路径。 private int FindItemIndex(T item) { if (_buckets is null) return -1; int hashCode ComputeHashCode(item); int i GetBucketRef(hashCode) - 1; uint collisionCount 0; while (i 0) { ref Entry entry ref _entries![i]; if (entry.HashCode hashCode ItemsEqual(entry.Value, item)) return i; i entry.Next; if (collisionCount (uint)_entries.Length) throw new InvalidOperationException(Concurrent update or corrupted chain.); } return -1; }平均O(1)的前提不是语法而是容量与分布哈希应把元素较均匀地散到桶中相等比较成本应可控容器也没有被并发破坏。最坏情况下大量元素进入同一桶查找退化为沿链线性扫描即O(n)。字符串路径在满足固定实现的比较器与碰撞条件时存在随机化重哈希防御但不能把它泛化成对任意恶意T的复杂度保证。4.2AddIfNotPresent先证明不存在再选择槽位Add返回布尔值找到等价元素时不修改集合并返回false未找到时写入新条目并返回true。显式接口ICollectionT.Add没有返回值但仍汇入同一内部逻辑。// 结构化节选保留插入位置选择不是逐字源码。 private bool AddIfNotPresent(T value, out int location) { EnsureInitialized(); int hashCode ComputeHashCode(value); ref int bucket ref GetBucketRef(hashCode); if (FindEquivalentInChain(bucket, hashCode, value, out location)) return false; int index; if (_freeCount 0) { index _freeList; _freeList DecodeNextFree(_entries![index].Next); _freeCount--; } else { if (_count _entries!.Length) { Resize(); bucket ref GetBucketRef(hashCode); // 旧数组元素引用已经失效 } index _count; } _entries![index] new Entry { HashCode hashCode, Next bucket - 1, Value value }; bucket index 1; _version; location index; return true; }扩容后必须重新取得bucket的引用因为旧引用指向旧桶数组。新节点采用头插法加入原链头之前。扩容本身需要分配新数组并重建桶链接因此单次可能是O(n)把一系列插入摊开分析在哈希良好且容量增长策略正常时才称均摊O(1)。如果能预估元素上限构造函数容量或EnsureCapacity可减少中途扩容和数组垃圾但预估过大也会保留大量闲置槽。容量优化的目标不是“越大越快”而是在扩容次数、常驻内存与峰值之间取得可测量的平衡。4.3TryGetValue取回集合中的规范代表TryGetValue(equalValue, out actualValue)与Contains的查找条件相同但命中后返回集合里实际保存的值。它适合字符串驻留式复用、按 ID 比较但希望拿回完整对象等场景。var canonical new HashSetstring(StringComparer.OrdinalIgnoreCase) { MainMenu }; if (canonical.TryGetValue(mainmenu, out string? stored)) { Console.WriteLine(stored); // MainMenu返回已存代表不是查询参数 }这比“先 Contains再自己猜测保存的是哪个对象”准确也避免重复查询。不过若调用者随后修改了stored中参与比较的状态仍会破坏哈希不变式。五、删除、清理、容量与枚举失效5.1 Remove 如何同时维护两条链删除要记住当前节点的前驱。命中链头时改桶命中链中节点时改前驱的Next。随后把被删槽接入 free list。若T是引用类型或内部包含引用.NET 8 会把Value清成默认值避免已删除对象因条目数组继续存活而被无意保留。// 伪代码解释摘链和回收不表示所有版本的字段细节。 if (previous 0) bucket removed.Next 1; else entries[previous].Next removed.Next; removed.Next EncodeFreeList(_freeList); if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) removed.Value default!; _freeList removedIndex; _freeCount;RemoveWhere(predicate)会扫描有效槽并删除满足条件的元素时间下界就是查看当前条目区域不能按“每次 Remove 平均 O(1)”误写成整个操作 O(1)。谓词也不应重入修改同一个集合把结构修改藏在 predicate 中会使推理和版本检查变得脆弱。5.2 .NET 8 中删除与枚举的特殊版本边界很多教程机械地说“集合任何修改都会让枚举器失效”。固定到本文的 .NET 8 源码新增元素会推进_version枚举器在MoveNext时发现版本不同并抛异常而Remove和Clear的实现没有推进版本。这使运行时能够支持某些枚举期间的删除/清空行为也让内部交集算法可以按槽扫描并删除。但这不应被扩写成跨版本永久承诺更不代表可以并发修改。若库需要覆盖 .NET Framework、Unity Mono 和不同 CoreCLR 版本应以目标 API 文档和实测为准。最可移植、最易审查的写法仍是先收集待删除项或使用RemoveWhere而不是依赖某一代运行时的枚举器细节。5.3Clear、EnsureCapacity与TrimExcessClear把逻辑元素全部移除并清理先前启用过的条目范围它通常保留已经分配的数组适合下一轮复用同等规模集合。若目标是释放长期不用的大数组仅 Clear 不够需要丢弃集合引用或在适当时机 Trim。EnsureCapacity(k)保证至少能容纳请求数量可能分配并重排桶TrimExcess()按当前 Count 选择更紧凑容量也可能分配和重建。它们应放在加载阶段、关卡切换或其他可接受尖峰的位置而不是每帧调用。池化一个 HashSet 也不是无条件收益池会延长大数组生命周期并可能把一次峰值容量永久带入常驻池。六、集合运算路径取决于参数类型和比较器6.1UnionWith与ExceptWith并集遍历other并逐个 Add。若other枚举m个元素在平均哈希条件下主要成本是m次插入/查找加上可能的扩容不能只写结果 Count。ExceptWith遍历other并逐个 Remove参数中的重复项只会让后续删除返回 false不会改变集合语义。自操作有明确代数结果set.UnionWith(set)不改变集合set.ExceptWith(set)清空集合。实现可以针对自引用提前返回或 Clear从而避免一边枚举同一对象一边修改的陷阱。自己实现扩展方法时也应先处理ReferenceEquals(this, other)。6.2IntersectWith为什么需要两种算法若other是比较器相同的HashSetT实现可以扫描当前条目数组用other.Contains判断不存在就 Remove。注意它不是用公开foreach再删除的天真写法而是按内部槽位扫描因此不会落入“枚举器被结构修改”的通用陷阱。若other只是任意IEnumerableT则不能假设无重复也不能安全地“看见一个就保留、没看见就立即删”。.NET 8 的策略是建立与原条目索引对应的位图枚举 other凡是在 this 中找到的槽位就标记最后扫描原条目区域删除未标记项。小位图使用栈上空间超过阈值后分配托管int[]。原集合槽 [A] [已删] [B] [C] 标记位 1 0 1 other 枚举A, A, C 最终删除B因此一般路径的时间可概括为“枚举 other 扫描当前原条目区域 每次哈希查询”平均情形接近O(mn)并可能有O(n)位图空间同 comparer HashSet 路径则主要扫描当前集合并查询对方。最坏碰撞条件会把每次查询放大不能声称所有路径都有无条件O(nm)上界。6.3 对称差必须消除 other 中重复项的影响对称差保留“恰好属于两集合之一”的元素。若 other 是同 comparer 的 HashSet它已经保证唯一逐项执行“存在则删不存在则加”即可。若 other 是普通序列直接切换会出错一个原本不存在的元素出现两次会先加入再删除但在集合语义中它应只算一个参数元素。.NET 8 的一般路径用位图区分“原集合中待删除的槽”和“本轮由 other 新增的槽”让重复输入不重复切换。这个例子说明集合 API 接受IEnumerableT时算法复杂度和辅助空间不能仅从方法名字推断。6.4 关系判断为什么记录 unique foundSetEquals、子集和超集判断的一般路径会统计 other 中有多少个唯一的本集合元素被找到以及有多少枚举值没有找到。位图保证重复命中同一槽只计一次。调用者再结合 Count 判定集合相等没有未找到项且唯一命中数等于 this.Count this 是子集唯一命中数等于 this.Count this 是真子集还必须存在 this 之外的参数元素 this 是真超集参数没有未知元素且唯一命中数小于 this.Count同 comparer HashSet 可以通过 Count 提前排除并直接 Contains不同 comparer 或普通序列不能套用这个捷径。Overlaps更容易短路找到第一个共同元素即可返回 true最好情况只需一次命中最坏才枚举完整个 other。七、复杂度、分配与 GC用前提约束结论操作平均条件下的主要成本退化或额外成本Contains/TryGetValue定位桶并遍历短链常称平均O(1)碰撞链最坏O(n)比较器本身也可能昂贵Add平均/均摊O(1)扩容需新数组与重建坏碰撞需线性扫描Remove平均O(1)坏碰撞为O(n)引用值需要清引用枚举扫描到_count约O(_count)删除留下的洞会被跳过成本不严格等于公开 CountUnionWith/ExceptWith主要与 other 的枚举次数相关插入可能扩容重复项仍有查询成本一般IntersectWith枚举 other 再扫描原条目区域位图可能产生托管分配坏碰撞放大查询关系判断可短路一般路径跟双方规模有关普通序列为去重计数可能需要位图GC 方面需要区分三件事。第一集合增长会分配新的桶数组和条目数组旧数组等待回收预容量能减少次数。第二条目数组直接保存T引用类型保存引用值类型内联保存字段包含引用的值类型仍会被 GC 按布局扫描。第三使用具体类型枚举器的普通foreach通常走结构体枚举器路径但把它转成IEnumerableT/IEnumeratorT、使用某些 LINQ 组合或闭包谓词可能产生装箱、迭代器或委托分配。不能把“foreach HashSet 永远零分配”当作语言定律。也不要把 HashSet 和 Dictionary 的性能差写成固定倍数。HashSet 少一个关联值字段且直接表达集合运算但实际缓存占用受T与容量影响Dictionary 在需要关联数据时避免了第二次查找或平行容器。选择首先由语义决定再由目标设备上的剖析证据决定。八、游戏开发中的正确用法与失败模式8.1 合适场景已加载资源 ID、已触发一次性事件、脏实体 ID 等只需要成员关系的数据两组玩家、标签、技能或可见对象之间的并、交、差构建阶段去重随后转换为排序数组或紧凑只读结构通过Add返回值把“查重”和“加入”合并成一次哈希查找。if (_playedCueIds.Add(cueId)) { PlayCue(cueId); // 仅首次加入时播放 }8.2 不合适场景每帧只有几十个元素时小数组的连续扫描可能比哈希、间接寻址和较大常数更合适需要稳定顺序、范围查询、最小值或按排名访问时应考虑排序数组、树或专门索引需要高并发原子更新时普通 HashSet 也不是现成答案。ECS、Jobs 或 Burst 环境还可能要求原生容器和显式生命周期而不是托管HashSetT。以下写法尤其危险// 错误 1依赖枚举顺序生成确定性网络包 foreach (int id in visibleIds) writer.Write(id); // 错误 2每帧为临时交集复制两个大集合 var visibleEnemies new HashSetint(visible); visibleEnemies.IntersectWith(enemies); // 错误 3比较器读入会随时间变化的外部状态 var set new HashSetEntity(new DistanceComparer(playerTransform));第一种应排序或使用有序契约第二种应测量并考虑复用缓冲、遍历较小集合执行 Contains或改变数据布局第三种比较器甚至可能在元素未修改时改变等价关系完全破坏容器不变式。8.3 Unity、Mono、IL2CPP 与 Burst 边界Unity 项目不能因为编辑器能使用某个 .NET API就推断所有目标平台实现与 .NET 8 CoreCLR 相同。Unity 版本、API Compatibility Level、所用类库 profile、Mono 或 IL2CPP 后端共同决定 API 是否存在以及私有布局。EnsureCapacity、TryGetValue、IReadOnlySetT等能力应在项目的最低 Unity 版本和所有目标后端编译验证。IL2CPP 会把托管代码转换为原生代码但HashSetT的托管对象语义、数组分配、比较器调用和 GC 生命周期不会因此消失。AOT 还可能改变泛型代码生成和比较器调用成本。Burst 编译代码通常不能任意使用托管 HashSetJob 场景应根据包版本选择NativeHashSetT等原生容器并遵守 allocator、Dispose、安全句柄和并行写入器契约。名字相似不代表实现、线程模型或集合运算 API 相同。九、可复现实验验证假设而不是背诵倍数9.1 正确性与契约实验先写不依赖性能环境的测试覆盖比较器、重复项和自操作[Fact] public void SetOperationsRespectComparerAndDuplicates() { var set new HashSetstring(StringComparer.OrdinalIgnoreCase) { A, B }; Assert.True(set.SetEquals(new[] { a, a, b })); set.SymmetricExceptWith(new[] { b, b, c, c }); Assert.True(set.SetEquals(new[] { A, c })); }再增加空集合、null、比较器不同的两个集合、ExceptWith(this)、IntersectWith(this)、先删后加的槽复用以及可变键反例。测试应断言集合语义不断言私有数组长度或枚举顺序除非目标就是固定 tag 的源码研究。9.2 容量与分配实验性能实验至少比较“无预容量”和“合理预容量”并记录runtime 完整版本、CPU、架构、Release、是否调试器附加、元素类型、比较器、输入分布、命中率、初始容量与最终 Count。使用 BenchmarkDotNet 时让结果由当前机器产生不在文章里虚构固定纳秒或倍数。[MemoryDiagnoser] public class HashSetCapacityBench { [Params(128, 4096)] public int N; [Benchmark(Baseline true)] public int GrowNaturally() { var set new HashSetint(); for (int i 0; i N; i) set.Add(i); return set.Count; } [Benchmark] public int PreSized() { var set new HashSetint(N); for (int i 0; i N; i) set.Add(i); return set.Count; } }为了观察碰撞而不是测试随机噪声可以提供一个恒定哈希比较器作为故障注入。它只用于展示链退化绝不能用于生产sealed class CollisionComparer : IEqualityComparerint { public bool Equals(int x, int y) x y; public int GetHashCode(int value) 0; }分别测量均匀默认比较器与该比较器的命中、未命中查询就能看到“平均 O(1)”依赖哈希分布。结果应报告分布和误差而不是把某台机器一次结果升级成语言保证。9.3 源码复核步骤切换到dotnet/runtime的v8.0.0tag而不是浏览会继续变化的 main在HashSet.cs定位Entry、FindItemIndex、AddIfNotPresent、Remove与Enumerator沿IntersectWith、SymmetricExceptWith、CheckUniqueAndUnfoundElements查看 comparer 快路径和位图路径对照HashHelpers核验素数容量、快取模与碰撞阈值不把常量推广到其他 tag在 Unity 项目中再以实际安装的参考程序集、后端生成结果和设备 profiler 复核不用 CoreCLR 私有字段替代 Unity 证据。十、选型与审查清单只需要唯一性与成员测试时HashSetT通常比DictionaryT,bool更清楚需要元素关联数据时直接使用 Dictionary需要排序或范围查询时选择有序结构需要确定性输出时显式排序或使用承诺顺序的数据结构。语义正确是第一层容量、分配和缓存行为是第二层。提交代码前可以逐项检查唯一性到底由哪些字段定义比较器是否满足等价关系与哈希一致性元素进入集合后参与哈希的字段会不会变化比较器会不会读取时变外部状态是否错误依赖了枚举顺序、私有容量、Entry 固定大小或某个运行时的删除枚举行为是否能预估容量Clear 后的大数组是需要复用还是应该释放/Trim集合运算的 other 是同 comparer HashSet还是含重复项的任意序列辅助位图分配是否处于热点是否存在无锁并发读写或把碰撞环检测误当成线程安全接口转换、LINQ、闭包、复制集合是否带来实际可见的每帧分配Unity 的最低版本、Mono/IL2CPP、目标平台和 Burst 环境是否分别编译与测量性能结论是否写明 runtime、硬件、输入分布和测量方法而非传播固定倍数HashSetT的精髓可以归纳为三句话比较器定义集合里的“同一个”桶数组与条目数组让良好分布下的成员操作达到平均常数成本集合运算会根据参数类型、比较器兼容性和重复项语义选择不同路径。掌握这三层比记住“它就是没有 value 的 Dictionary”更接近源码也更能指导真实游戏工程。下一篇OrderedDictionaryTKey,TValue当映射还必须保留可观察顺序时数据结构需要付出什么代价。