04-01-哈希-Hash原理-期望O1查找与退化边界

Hash 原理：哈希表为什么能做到期望 O(1) 查找

系列：C# 与常用数据结构源码剖析 · 哈希与映射篇
阅读时间：约 60 分钟
前置知识：数组、链表、模运算、渐近复杂度
版本边界：前半部分讲数学与公共契约；.NET 例证固定为 dotnet/runtime 的 v8.0.0 tag。Dictionary<TKey,TValue> 的字段、容量、FastMod 快路径与字符串防御是该 tag 的实现事实，不是 C# 语言或 IDictionary 的永久契约。

一、O(1) 是期望成本，不是对每次调用的保证

字典要解决的问题是：给定键 k，找到与它关联的值。线性表从头扫到尾，最坏要比较 n 个键。哈希表先通过哈希函数将键投影为整数，再将整数映射到少量候选位置，从而把“全表查找”缩小为“查一个桶或一条探测序列”。

设键域为 K，32 位哈希函数为：

h: K -> {0, 1, …, 2^32 – 1}

当表有 m 个桶时，还需要一个缩减函数：

index: {0, …, 2^32 – 1} -> {0, …, m – 1}

如果键的哈希分布良好、桶数与元素数保持合理比例、冲突解决策略正确，那么单个桶中期望只有少量候选，查找的期望成本可视为 O(1)。这个结论依赖输入与哈希分布假设，不是最坏保证。

若所有键的哈希码都相同，链地址实现会在一条长冲突链上线性比较，开放寻址实现会沿很长的探测序列寻找。两者都可退化到 O(n)。所以标题中最准确的说法是“期望 O(1)”或“在良好分布下平均 O(1)”。

二、哈希与相等是一份不可拆分的契约

哈希值不是键的唯一 ID。字典先用哈希缩小候选集，最后仍需要相等比较确认键。对任意两个键 a、b，比较器必须满足：

Equals(a, b) == true => GetHashCode(a) == GetHashCode(b)

逆命题不成立：哈希相同的键可以不相等，这就是冲突。如果相等键产生不同哈希，它们会被定位到不同桶或不同探测路径，字典可能无法找到已存在的等价键。

public readonly struct Cell : IEquatable<Cell>
{
public Cell(int row, int column)
{
Row = row;
Column = column;
}

public int Row { get; }
public int Column { get; }

public bool Equals(Cell other) =>
Row == other.Row && Column == other.Column;

public override bool Equals(object? obj) =>
obj is Cell other && Equals(other);

public override int GetHashCode() =>
HashCode.Combine(Row, Column);
}

Equals 与 GetHashCode 应基于同一组稳定字段。不是说两个方法必须逐字读同样的代码，而是它们定义的等价类必须一致。若 Equals 忽略大小写，哈希也必须使用对应的忽略大小写规则，不能直接调用默认字符串哈希。

三、冲突不可避免

如果键域比 2^32 大，根据鸽巢原理，必然有不同键共享 32 位哈希。即使键总数少于 2^32，通用哈希函数也不可能对任意输入集保证无冲突。当 32 位哈希进一步压缩到 m 个桶时，不同哈希码也可能映射到同一桶。

“好哈希”的目标不是消灭冲突，而是在典型输入上使输出尽量均匀，同时保持计算快、等价契约正确。对不受信任输入，还要考虑攻击者能否预测并制造大量冲突。

不要在教程中写“某函数的冲突率为 0.001%”而不定义键分布、样本数、桶数、比较函数和置信范围。冲突率不是脱离数据集的算法常数。

四、从哈希码到桶索引

最直接的映射是 hash % bucketCount。若桶数是 2 的幂，可用 hash & (bucketCount – 1) 取低位。若桶数使用素数系列，则使用对应模运算。这些是容量策略，不是“二的幂必差”或“素数必快”。

二的幂映射更依赖低位混合质量，但可以配合高质量哈希与位混合使用；素数模可以减少一些周期模式与桶长的不利共振，但仍无法修复“所有键哈希相同”的坏比较器。完整设计需要同时考虑哈希函数、桶数、冲突策略、扩容成本和 CPU 除法成本。

在 .NET 8 v8.0.0 的 Dictionary<TKey,TValue> 中，容量选择与 HashHelpers 的素数工具相关。某些 64 位路径可以预计算乘法器，用 FastMod 类技术将反复模运算降为乘法、移位和少量校正。这是固定架构与 tag 的私有优化，不改变“同一哈希必须映射到同一桶”的数学语义，也不能推广到所有 .NET、CPU 或 Unity 实现。

五、冲突策略一：链地址

链地址（separate chaining）为每个桶保存一组冲突条目。教材常画成每桶一条对象链表，但工程实现不必为每个节点分配独立对象。.NET 8 Dictionary<TKey,TValue> 使用桶数组保存冲突链入口，用连续 Entry 数组保存哈希/链接、键和值。

buckets[0] -> none
buckets[1] -> entry 6 -> entry 2 -> none
buckets[2] -> entry 9 -> none

entries:
index | next | key | value
2 | -1 | K1 | V1
6 | 2 | K2 | V2
9 | -1 | K3 | V3

这是教学布局，索引基数、空值哨兵和字段形式必须以 v8.0.0 源码为准。核心不变式是：桶只定位第一个候选 Entry，每个 Entry 的 next 又是下一个冲突 Entry 的数组索引。链上节点在 Entry 数组中不保证物理相邻。

因此“.NET 8 Dictionary 用 Vector256 连续扫描一条冲突链”是错误模型。冲突链需要通过 next 索引追踪，不能假设可将若干链节点当成连续 SIMD 块。某些哈希类型或运行时辅助函数可以使用向量化，不等于 Dictionary 冲突链使用该算法。

5.1 查找伪代码

// 结构化伪代码，非 .NET 8 逐字源码。
bool TryFind(TKey key, out TValue value)
{
int hash = comparer.GetHashCode(key);
int index = buckets[MapToBucket(hash)];

while (index is a valid entry index)
{
ref Entry entry = ref entries[index];
if (entry.HashMatches(hash) && comparer.Equals(entry.Key, key))
{
value = entry.Value;
return true;
}

index = entry.Next;
}

value = default;
return false;
}

真实实现还需要空键规则、默认比较器特化、冲突计数安全检查、移除后的自由链、引用清理和异常契约。伪代码只解释“哈希缩小候选集，相等完成确认”。

六、冲突策略二：开放寻址和墓碑

开放寻址（open addressing）将条目直接放在槽位数组中。起始位置被占用时，按某个探测函数尝试下一槽位。常见策略包括线性探测、二次探测与双重哈希，它们对缓存局部性、主聚集和覆盖所有槽位的条件不同。

home(key) = hash1(key) mod m
probe(key, i) = (home(key) + i * step(key)) mod m

删除时不能把槽位直接恢复成“从未使用”。假设 A 和 B 的主位置相同，B 因 A 存在而被放到后面；删除 A 后，若查找 B 在 A 的位置看到“从未使用”就停止，会错误返回未找到。实现需要墓碑（deleted marker）或等价状态，表示“该位置现在空，但探测不能在此停止”。

从未使用：查找可停止，插入可使用
正在使用：比较哈希与键
已删除/墓碑：查找继续，插入可在合适时复用

.NET 8 v8.0.0 中的非泛型 Hashtable 与 Dictionary<TKey,TValue> 不是同一冲突结构。Hashtable 使用开放寻址/双重哈希模型及兼容所需的 bucket 状态；Dictionary 使用桶入口加 Entry 冲突链。不应从类名都是哈希映射，就在它们之间复制字段和删除模型。

七、负载因子与扩容

负载因子通常表示元素数 n 与桶/槽位数 m 的比率：

alpha = n / m

对链地址，alpha 可以大于 1，但平均冲突链会增长；对开放寻址，槽位接近填满时探测成本会迅速增加，实现必须在真正满表前扩容。两种结构不能共享一个脱离实现的“最佳负载因子”常数。

扩容通常分配更大的桶/槽位数组，然后重建索引。因为桶映射依赖 m，容量变化后不能只将旧桶数组的整个内存复制到新数组。链地址需重建桶入口和 next 链；开放寻址需按新槽位数重新探测。

某一次触发扩容的插入可以是 O(n)，但如果容量按几何方式增长，连续插入序列的扩容复制总量可摊薄，因此插入常表述为均摊 O(1)。“均摊”不会消灤某次操作的尖峰，实时系统仍应使用容量上界、EnsureCapacity 或批处理阶段控制扩容时机，并按目标版本验证 API。

八、平均、最坏和均摊是三种不同语句

一次字典查找的实际时间还包括键哈希、比较、桶定位、链/探测访存和分支。如果键是一个很长的字符串，计算哈希本身与键长度有关；如果自定义 Equals 深度遍历对象图，候选少也不代表比较廉价。复杂度必须说明把哈希和比较视为什么成本。

九、HashCode 的版本与算法边界

System.HashCode 在 .NET Core 2.1 时代就已提供，不是“.NET 6 首次引入”。它为将多个字段的哈希组合成一个 int 提供统一 API：

public override int GetHashCode() =>
HashCode.Combine(Id, Region, Version);

public int ComputeManyFields()
{
var hash = new HashCode();
hash.Add(Id);
hash.Add(Region, StringComparer.Ordinal);
hash.Add(Version);
return hash.ToHashCode();
}

在 dotnet/runtime v8.0.0 的 System.HashCode 实现中，混合设计源自 xxHash32 类算法思路，并使用每进程随机种子及针对少量值的 Combine 路径。不应把它写成 xxHash3，也不应伪造一组 64 位 _v1…_v4 字段当成 .NET 8 源码。私有常量和混合步骤可在后续版本改变，公共契约只是生成与所加值/比较器相关的哈希码。

HashCode 结果不适合持久化或网络协议。它可包含进程随机化，其余列化格式不是公共契约。若需要稳定内容指纹、文件去重或密码学完整性，应选择具有明确算法名称、版本、字节编码和安全性契约的专用哈希，而不是 GetHashCode。

十、值类型默认哈希不应被概括为“反射 + XOR”

ValueType.GetHashCode 的具体快路径、JIT 内部化与字段处理会随运行时和类型形状变化。不能用一段“遍历反射字段再 XOR”的 C# 伪代码充当 .NET 8 真实实现，更不能由此给出“显式实现固定快 10–50 倍”。

工程上仍然建议领域键显式定义相等与哈希，原因首先是语义清晰：哪些字段构成身份，大小写和空值如何处理，哈希是否保持等价契约。性能收益要对具体 TKey、运行时和工作负载测量。

readonly record struct 可以让编译器合成值相等与哈希，但合成契约会包含其定义的成员。若某些字段不应影响业务身份，就不能仅为省代码依赖默认合成。类型设计应先定义等价关系，再选自动生成或手写实现。

十一、字符串哈希和随机化边界

在现代 .NET/CoreCLR 中，默认字符串哈希可使用每进程随机化的种子，使攻击者更难在事前为所有进程准备同一组冲突键。这意味着不应持久 string.GetHashCode() 的结果，也不应用它作为跨进程分区、网络协议 ID 或文件校验值。

不能把“字符串哈希随机化”推广为所有 .NET Framework、Mono、Unity、所有比较器和所有配置下的永久行为。旧 .NET Framework 有历史开关和不同算法，不同运行时可使用不同实现。需要产品级结论时，固定 runtime 版本并用两个独立进程实测，不要只在一次运行内重复调用。

.NET 8 v8.0.0 的 NonRandomizedStringEqualityComparer 是 CoreLib/Dictionary 可使用的内部实现细节，不是应用可直接 new 或访问 .Default 的公共 API。它与字符串冲突防御和比较器切换路径的具体关系要按 tag 阅读，不能给用户写出无法编译的：

// 错误示例：内部比较器不是公共 API。
// new Dictionary<string, int>(NonRandomizedStringEqualityComparer.Default);

// 公共业务语义应选明确的公共比较器。
var ids = new Dictionary<string, int>(StringComparer.Ordinal);

StringComparer.Ordinal、OrdinalIgnoreCase 和文化相关比较器定义的首先是相等语义。不要只为了想象的性能更换比较器，导致用户名、路径、资源 ID 或协议键的大小写契约改变。

十二、可变键是正确性故障

键进入哈希表后，任何参与相等与哈希的状态都必须保持稳定。字典不会监听键对象变化并自动迁移 Entry。

public sealed class MutableKey
{
public string Id { get; set; } = "";

public override bool Equals(object? obj) =>
obj is MutableKey other && Id == other.Id;

public override int GetHashCode() => Id.GetHashCode();
}

var key = new MutableKey { Id = "A" };
var map = new Dictionary<MutableKey, string> { [key] = "value" };
key.Id = "B";

// 此后查找/删除行为已被调用者破坏，不是 Dictionary 自动 rehash 的时机。

键对象仍存在于旧哈希对应的冲突链中，但新查找从新哈希对应的桶开始，可能根本不访问该 Entry。即使新旧哈希恰好映射到同一桶，这也只是偶然，不能恢复契约。

优先使用不可变值作键：整型 ID、不可变字符串、readonly struct 或明确值对象。若业务身份需要更改，应以旧键移除、再以新键添加，并在必要时用锁或事务边界保证中间状态不可见。

十三、比较器将业务语义与类型实现分离

Dictionary<TKey,TValue> 接受 IEqualityComparer<TKey>，使同一键类型可以在不同字典中使用不同等价语义。例如资源代码可以大小写敏感，用户登录名可以按规范化后忽略大小写。不要为了某一容器的局部需求修改键类型的全局 Equals/GetHashCode。

public sealed class AssetIdComparer : IEqualityComparer<AssetId>
{
public bool Equals(AssetId x, AssetId y) =>
StringComparer.Ordinal.Equals(x.Namespace, y.Namespace) &&
StringComparer.OrdinalIgnoreCase.Equals(x.Name, y.Name);

public int GetHashCode(AssetId value)
{
var hash = new HashCode();
hash.Add(value.Namespace, StringComparer.Ordinal);
hash.Add(value.Name, StringComparer.OrdinalIgnoreCase);
return hash.ToHashCode();
}
}

自定义比较器应当无副作用、线程使用方式清晰，不读取会在键存活期改变的文化或配置。对字符串、数组、浮点、路径与 Unity 对象等特殊键，先定义领域中的相等，再写哈希。

十四、哈希碰撞是性能与安全攻击面

如果攻击者能提交大量键，并能预测哈希/桶映射，就可能刻意制造长冲突链或探测群，把每次操作从期望 O(1) 推向 O(n)。一次插入很多攻击键的总成本可接近二次量级，造成 CPU 拒绝服务。

每进程字符串哈希随机化使预计算攻击更难，但它不是通用资源上限。攻击者还可通过提交超多唯一键、超长字符串、昂贵规范化或自定义类型的坏哈希消耗资源。输入边界应限制键数、键长度、请求体和并发度，并对异常冲突/延迟监控。

非字符串自定义键不会自动获得同样的密钥化防御。若系统接受不受信任的复合键，不应直接把对方提供的哈希码作为字典哈希。需要时在服务边界使用受控规范化、密钥化哈希或改用具有最坏时间保证的树结构，并衡量密码学成本。

十五、容量不是逻辑计数，预分配也不是越大越好

Count 是有效键值对数，容量是内部存储在下次增长前可支持的尺寸概念，具体与桶和 Entry 数组长度相关。删除可能将 Entry 放入自由链供后续插入复用，不必立即缩小内部数组。

已知要插入的数量时，构造容量或 EnsureCapacity 可以减少中途增长和重建桶链。但容量高估会增加桶/Entry 数组驻留内存和 GC 扫描成本，一次峰值后长期复用字典可以保留过大容量。TrimExcess 类操作可能分配、重建并使枚举/引用失效，不应每次删除后调用。

对游戏帧循环或低延迟服务，预分配应基于典型值、历史高分位和业务上限，而不是用“内存换性能”一句话无限放大。空间成本与扩容尖峰必须同时测量。

十六、Unity 中要分开语义、类库实现和后端优化

Unity 项目中的 Dictionary<TKey,TValue> 公共语义与 C# 键契约仍然适用：相等键必须哈希相同，键存活期不得改变哈希/相等状态，字符串比较必须按业务语义选择。但 Unity 所带的类库可能来自自己的 Mono/BCL 分支，不能用 CoreCLR .NET 8 v8.0.0 的私有字段、FastMod 或字符串防御路径解释所有 Unity 版本。

Editor Mono、Mono Player 和 IL2CPP 也可产生不同机器码、泛型共享、内联与分配行为。某个 CoreCLR 基准的纳秒数、哈希快路径或比较器特化不能直接复制到 Unity Player 结论。每份报告应记录 Editor 完整版本、API Compatibility Level、脚本后端、目标平台、CPU、Development/Release 和裁剪设置。

对 Burst/Jobs，不应将托管 Dictionary 作为 Job 容器。Unity Collections 的原生哈希容器有独立的元素约束、Allocator、安全句柄、并行写协议和私有布局，不能从名称将 CoreLib Dictionary 的链地址结构推导过去。按对应 Collections 包 tag 阅读源码，在目标设备上分别基准。

十七、故障注入：主动把坏情况变成测试

正常随机 ID 很难覆盖长冲突链。可以写一个故意返回常量哈希的比较器，验证不同键即使全部冲突仍能正确添加、查找和删除：

public sealed class ConstantHashComparer<T> : IEqualityComparer<T>
{
private readonly IEqualityComparer<T> _equals =
EqualityComparer<T>.Default;

public bool Equals(T? x, T? y) => _equals.Equals(x!, y!);
public int GetHashCode(T value) => 0;
}

测试应包含空表、单元素、大量冲突键、删除链首/中间/链尾、删除后插入、触发扩容、不存在键和值恰好为 default。对 Hashtable 模型，还要验证墓碑之后的键仍能找到，以及重新插入可在不破坏探测链的情况下复用删除槽位。

另一个故障注入是可变键：先加入，修改参与哈希的字段，再记录 ContainsKey/Remove 失败。这个测试的目的不是要求 Dictionary 支持可变键，而是让团队看到违反调用契约的后果，并通过不可变键/API 封装阻止误用进入生产。

十八、相等与哈希的性质测试

对自定义键和比较器，少量示例很难覆盖组合。可以生成大量业务键 a、b、c，验证：

• 自反性：Equals(a,a) 为真。
• 对称性：Equals(a,b) 与 Equals(b,a) 一致。
• 传递性：若 a==b 且 b==c，则 a==c。
• 哈希一致：若 Equals(a,b)，则两者哈希相同。
• 稳定性：键未发生合法状态变化时，重复计算相等与哈希结果不变。
• 字典往返：添加后用任意等价键都能查到，删除后都查不到。

对字符串比较器，要专门生成大小写、Unicode 等价外观、组合字符、空字符串与文化边界。比较器不会自动做 Unicode 规范化；如果业务需要 NFC/NFD 等价，应先定义规范化边界，再保证相等和哈希使用同一规则。

十九、哈希分布实验

分布实验的输入必须来自真实键域或有代表性生成器，而不是只用随机 GUID 证明随机数据哈希得还可以。对坐标键，测网格线、对角线、分块边界与常见零值；对 ID，测递增、固定前缀、低位为零和旧数据迁移格式。

给定候选桶数 m，可将每个键的哈希映射到计数数组，记录：

• 非空桶数与空桶数。
• 最大桶占用、分位数与直方图。
• 实际相等键数和不等键冲突数。
• 不同容量映射下的结果，防止某一个 m 恰好遮住模式。
• comparer 的 GetHashCode/Equals 调用次数与耗时分布。

可以使用卡方、方差或其他统计量帮助比较分布，但统计显著不自动等于业务上的灾难，“未显著”也不证明对抗恶意输入。报告要保存键数据集版本、生成器、随机种子、桶数、映射函数与原始直方图，不只写一个“冲突率”。

二十、性能实验应同时测哈希、比较与容量

微基准至少区分成功查找、失败查找、新键插入、已有键更新、删除和枚举。成功查找还应分顶部命中与长冲突链后部命中，失败查找需要遍历所有候选才能确认不存在。预分配与从空表增长应分开，否则扩容会与稳态查找成本混在一起。

自定义比较器实验可用包装器计数 GetHashCode 和 Equals 次数，这比只看总时间更容易解释。若坏哈希导致 Equals 次数增加，就能将症状与冲突链建立因果；若次数不变但时间增大，需要检查键长度、缓存局部性或其他因素。

报告固定 SDK/runtime 完整版本、dotnet/runtime v8.0.0 源码基线、CPU、OS、GC、键类型与宽度、比较器、数据规模、命中率、初始容量和输入种子。保存 BenchmarkDotNet 或同等框架的原始报告，不发布无代码、无环境的“快若干倍”。

二十一、代码审查清单

结语

哈希表的速度来自“先用哈希缩小候选集”，而不是哈希值消除了相等比较。相等键必须产生相同哈希，不同键可以冲突；冲突不可避免，只能用良好分布、合理负载和正确链地址/开放寻址协议控制。

期望 O(1)、最坏 O(n) 与扩容均摊 O(1) 是三个同时为真的句子。只写“O(1)”会隐藏坏比较器、攻击键、长冲突链和扩容尖峰。哈希的安全性也不能只依赖字符串随机化，还要有输入上限与资源治理。

源码研究应固定运行时 tag，并与公共契约、Unity 版本边界分开；再用性质测试、坏哈希注入和真实键分布实验验证结论。

下一篇：Dictionary<TKey,TValue>（上）：桶、Entry 与容量演化