6.4　C# Dictionary 的内部与工程用法

学习目标：学完本节，你能

  • 解释为什么 Dictionary 的遍历顺序不可依赖；
  • 说清 Equals / GetHashCode 契约，并知道违反它的后果；
  • 避开"用可变对象当键""并发写"这几类最常见的生产事故；
  • 说出键类型选择对性能的量化影响。

先修：6.1–6.3（哈希函数、冲突解决、负载因子）。 固定术语：哈希契约、墓碑、线程安全。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、实验一：遍历顺序不可依赖

var d1 = new Dictionary<int, string>();
for (int i = 1; i <= 5; i++) d1[i] = $"v{i}";
PrintDict("插入 1,2,3,4,5", d1);

d1.Remove(3);
PrintDict("删除 3 之后", d1);

d1[6] = "v6";
PrintDict("再插入 6 之后", d1);

实测输出：

  插入 1,2,3,4,5        : 1 2 3 4 5
  删除 3 之后           : 1 2 4 5
  再插入 6 之后         : 1 2 6 4 5

注意最后一行：6 顶替了 3 原来的位置，所以顺序变成了 1 2 6 4 5。

为什么会这样？

因为 Dictionary 内部是一个开放寻址的数组（6.2 节）：

  1. 元素的位置由 哈希值 % 容量 决定；
  2. 删除会留下墓碑（6.2 节）；
  3. 插入新元素时，会优先复用遇到的第一个墓碑。

所以 6 被放进了 3 留下的那个坑里 —— 顺序自然就乱了。

这个现象在小字典上是"看起来还行"，在大字典上是"完全随机"。 而且它还会随 .NET 版本变化（微软随时可以调整内部实现）。

工程铁律：永远不要依赖 Dictionary 的遍历顺序。

需要顺序时用： | 需求 | 用什么 | 代价 | |---|---|---| | 按键排序 | SortedDictionary<K,V> / SortedSet<T> | 内部是红黑树，操作 $O(\log n)$ | | 按插入顺序 | .NET 9+ 的 OrderedDictionary<K,V> | 内存略多 | | 按插入顺序（老版本） | List<K> 记录顺序 + Dictionary 存值 | 要自己维护两个结构 |

二、实验二：Equals 与 GetHashCode 的契约

这是一个几乎每个人都踩过的坑。

/// <summary>反面教材：重写了 Equals 却没重写 GetHashCode。</summary>
public class BadKey
{
    public int Id;
    public BadKey(int id) => Id = id;

    public override bool Equals(object? obj) => obj is BadKey b && b.Id == Id;
    // 故意不重写 GetHashCode —— 这就是 bug
}

var badDict = new Dictionary<BadKey, string>();
badDict[new BadKey(1)] = "A";

bool contains = badDict.ContainsKey(new BadKey(1));
Console.WriteLine($"ContainsKey 返回 {contains}");     // False！

实测输出：

  存了一个 BadKey(Id=1)，再查一个「相等」的 BadKey(Id=1)：
    ContainsKey 返回 False    <- 应该是 True！

  而直接用 Equals 比较，它们明明是相等的：
    new BadKey(1).Equals(new BadKey(1)) = True

两个对象 Equals 返回 True，放进字典却查不到！

原因：

  • BadKey 重写了 Equals，但没有重写 GetHashCode；
  • 于是它继承了 object 的默认实现 —— 基于对象的内存地址；
  • 两个不同的对象地址不同 → 哈希值不同 → 被分到了不同的桶；
  • Dictionary 根本不会去比较它们（因为它只在自己的桶里找）。

契约（必须同时满足）：

如果 a.Equals(b) 返回 true，那么 a.GetHashCode() 必须等于 b.GetHashCode()。

反过来不要求：哈希值相同，两个对象不一定相等（这就是"冲突"，6.1 节讲过）。

哈希表的工作流程正是建立在这个契约上：

查找 key：
  1. 算出 key 的哈希值 -> 定位到桶        （依赖 GetHashCode）
  2. 在桶里逐个比较，用 Equals 判断是否相等  （依赖 Equals）

第 1 步用了 GetHashCode，第 2 步用了 Equals。如果两者不一致，第 1 步就会把你带到错误的桶，第 2 步永远没机会执行。

怎么避免？

  • 重写 Equals 时，IDE 和编译器都会提醒你重写 GetHashCode（Visual Studio 有快速修复）。
  • 最简单的办法：用 record 类型。 编译器会自动生成配套的 Equals 和 GetHashCode。
  • 或者用 readonly struct + 手动实现两者（结构体的默认 GetHashCode 也是基于字段的，行为比类更合理）。

用 record 改写（推荐）：

public record OrderKey(int UserId, string OrderNo);

一行代码，Equals 和 GetHashCode 都由编译器正确生成 —— 而且它们是基于所有字段的值计算的，完全符合契约。

三、实验三：用"会被修改的对象"当键

/// <summary>可变对象当键的反面教材。</summary>
public class MutableKey
{
    public int Id;

    public override int GetHashCode() => Id;                      // 哈希值跟着 Id 变
    public override bool Equals(object? obj) => obj is MutableKey m && m.Id == Id;
}

var mutDict = new Dictionary<MutableKey, string>();
var key = new MutableKey { Id = 1 };
mutDict[key] = "A";

key.Id = 2;                       // 修改了作为键的对象！
Console.WriteLine($"ContainsKey = {mutDict.ContainsKey(key)}");
Console.WriteLine($"元素个数 = {mutDict.Count}");

实测输出：

  存入 MutableKey(Id=1) -> "A"
  修改前 ContainsKey = True
  把 key.Id 改成 2 之后...
  修改后 ContainsKey = False
  字典里的元素个数   = 1（元素还在，但再也找不到了）

元素还在字典里（Count == 1），但再也找不到了 —— 相当于把钥匙弄丢了。

原因：GetHashCode 基于 Id，Id 一变，哈希值就变了。但元素仍然待在原来那个桶里。下次查找时，你会去新的桶找，而元素在旧的桶里。

这就是内存泄漏的一种隐蔽形式：这个元素永远不会被访问到，但只要字典活着，它就占着内存。

规则：用引用类型当键时，这个对象必须是"不可变的"（至少用来计算哈希的那些字段不能变）。

推荐的键类型： | 类型 | 为什么好 | |---|---| | int / long / Guid | 值类型，天生不可变，哈希快 | | string | 不可变 | | record | 编译器保证 Equals/GetHashCode 正确 | | readonly struct | 值类型 + 字段只读 | | enum | 本质是整数 |

要避免的：普通的 class（可变）、record struct 含可变字段、任何字段会被修改的键。

四、实验四：TryGetValue 比 ContainsKey + 索引器 快多少

这是 C# 里最著名的一条"微优化"：

// 差：同一个键查找了两次
if (dict.ContainsKey(k))          // 第一次查找
    sum += dict[k];               // 第二次查找！

// 好：一次查找同时拿到值
if (dict.TryGetValue(k, out int v))   // 一次搞定
    sum += v;

实测（300 万条数据，100 万次查找）：

  1,000,000 次查找（数据量 3,000,000）：
    ContainsKey + 索引器:    89.06 ms   （每个键查找两次）
    TryGetValue         :    66.29 ms   （每个键只查找一次）
    TryGetValue 快 1.34 倍（省下了约 26% 的查找次数）
    结果一致: True

这里快了约 1/3，没有到理论上的 2 倍 —— 因为：

  • 命中的键：ContainsKey 查一次，索引器再查一次 → 确实查了两次
  • 未命中的键：ContainsKey 返回 false，索引器根本不会执行 → 只查了一次

所以实际的查找次数节省比例，取决于命中率。本例中命中率较高，所以节省明显。

虽然这是"常数优化"（两者都是 $O(1)$），但它只改一行代码、零风险，值得养成习惯。

附加好处：TryGetValue 的写法避免了"先检查再使用"的时间窗口。在并发场景下（即使你用 ConcurrentDictionary），ContainsKey + 索引器之间可能被其他线程修改，而 TryGetValue 是原子的。

五、实验五：多线程并发写 Dictionary

这是生产事故的高发区。

var concurrentDict = new Dictionary<int, int>();
var task = Task.Run(() =>
{
    Parallel.For(0, 200_000, i => concurrentDict[i] = i);
});

bool completed;
try
{
    completed = task.Wait(TimeSpan.FromSeconds(5));
}
catch (AggregateException)
{
    completed = true;                 // 以异常方式结束了，也算「结束」
}

注意 Wait(timeout) 的陷阱：任务抛异常时它会抛出 AggregateException，而不是返回 false。不捕获的话，你的"测试代码"自己就崩了 —— 我第一次跑就踩了这个。

实测输出：

  抛出异常: InvalidOperationException
  消息: Operations that change non-concurrent collections must have exclusive access.
        A concurrent update was performed on this collection and corrupted its state...

  .NET 的 Dictionary 内置了「版本号检查」，检测到并发修改就主动抛异常，
  而不是像某些老实现那样【静默地损坏数据】—— 这是好事。

这条异常消息值得读一遍：.NET 的 Dictionary 内部维护了一个"版本号"，每次修改都会递增。如果检测到版本号在自己的操作过程中被改变了，就说明有别的线程在同时改 —— 它会主动抛异常。

主动抛异常是好事。 早期的 Dictionary 在并发下可能进入死循环（CPU 100% 卡死）或静默地损坏数据结构（数据丢失但不报错）。后者才是最可怕的 —— 你会得到错误的结果，却完全不知道。

但注意：抛异常不代表安全。检测是"尽力而为"的，在某些时序下仍然可能损坏数据。

并发场景的正确选择：

方案 适用场景 说明
ConcurrentDictionary<K,V> 多线程读写 专门为并发设计，API 也是原子的
lock + Dictionary 写少读多，或逻辑复杂 简单直接，但锁会限制并发度
写时复制 读极多、写极少 写时复制一份新字典再替换引用
[ThreadStatic] / 每线程一份 数据可以按线程隔离 完全没有竞争

关于 ConcurrentDictionary 的两个常见误解：

  1. "它比 Dictionary 慢，所以不用" —— 单线程下确实慢一些（要做原子操作），但并发场景下它是唯一正确的选择。用 Dictionary 得到的"快"是假的，换来的是随机的数据损坏。
  2. "用了它就万事大吉" —— ConcurrentDictionary 保证单个操作是原子的，但多个操作的组合不是。比如"先判断不存在再插入"这种逻辑，仍然要用 GetOrAdd / AddOrUpdate 这类原子 API。

六、实验六：键类型对性能的影响

  500,000 次插入 + 500,000 次查找：
    string 键:     35.5 ms
    int 键   :      4.5 ms
    int 键快 7.84 倍

int 键快将近 8 倍。

原因有两层：

  1. 哈希计算：int 的哈希就是它自己（一次赋值）；而 string 要遍历所有字符才能算出哈希。键越长，这个差距越大。
  2. 相等比较：int 比较是一条指令；string 比较要先比长度、再逐字符比较（虽然 .NET 会做引用相等和长度检查的短路优化）。

工程含义：如果键天然是整数（自增 ID、时间戳、枚举），用整数键会明显更快。

常见场景：把"用户名字符串"换成"用户 ID 整数"当缓存键 —— 前提是你已经拿到了 ID，否则转换本身的开销可能抵消收益。

但如果键必须是字符串，怎么办？

  • 别自己写哈希函数 —— .NET 的 string.GetHashCode() 是精心实现的（包含随机化和混合步骤）。
  • 如果键很长（比如整个 JSON 当键），考虑先算一个短哈希（比如取 SHA-256 的前 16 字节）当键，冲突时再比对原值。
  • 注意 .NET 的字符串哈希是随机化的：同一个字符串在不同进程里的 GetHashCode() 可能不同。所以不要把它持久化到磁盘或数据库。

七、容量与工程参数速查

参数 建议值 理由
初始容量 预期元素数 / 0.7 避免扩容（6.3 节实测快 2 倍）
负载因子 用默认的 0.72 左右 别去调 —— 它会显著影响探测长度
键类型 int > string > 自定义类 6.4 节实测差 7.84 倍
字符串键长 越短越好 哈希要遍历全部字符
并发 ConcurrentDictionary Dictionary 并发写会抛异常或损坏

几个容易忽略的 API：

// 1. 预分配容量（6.3 节：快 2 倍）
var dict = new Dictionary<string, int>(capacity: 100_000);

// 2. 自定义比较器（比如让字符串键忽略大小写）
var caseInsensitive = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

// 3. 原子式的"取或创建"（ConcurrentDictionary）
var value = concurrent.GetOrAdd(key, k => ExpensiveLoad(k));

// 4. 遍历时删除：不能边遍历边删！先收集要删的键
var toRemove = dict.Where(kv => kv.Value < 0).Select(kv => kv.Key).ToList();
foreach (var k in toRemove) dict.Remove(k);

第 4 条是个高频错误。 在 foreach 里直接 dict.Remove(k) 会抛 InvalidOperationException（"集合已修改"）—— 这和"版本号检查"是同一个机制。

顺便一提：这也是为什么"遍历顺序不可依赖"这条规则很重要 —— 如果你的代码依赖遍历顺序，那么在删除后它的行为就更加不可预测了。

八、练习

练习 6.4.1（找 bug） 下面这段代码有 bug，请指出并修复：

public class UserKey
{
    public string Name;
    public int Age;

    public override bool Equals(object? obj)
        => obj is UserKey u && u.Name == Name && u.Age == Age;
}

var cache = new Dictionary<UserKey, string>();
cache[new UserKey { Name = "张三", Age = 30 }] = "VIP";
Console.WriteLine(cache.ContainsKey(new UserKey { Name = "张三", Age = 30 }));   // 期望 True

练习 6.4.2（改写） 把练习 6.4.1 的 UserKey 改写成正确的形式，要求： (a) 用 record 实现（最简） (b) 用普通 class 实现（手动写 Equals 和 GetHashCode）

练习 6.4.3（判断） 判断对错并说明理由： (a) Dictionary 遍历顺序是按插入顺序的。 (b) 两个对象 Equals 返回 true，它们的哈希值一定相同。 (c) ConcurrentDictionary 的所有操作都是线程安全的，所以可以放心用。 (d) Dictionary 的 GetHashCode() 结果可以持久化到数据库，下次启动直接复用。

练习 6.4.4（工程判断） 一个订单服务用 Dictionary<string, Order> 做缓存，键是订单号。 运行中出现了两个问题：

  • 内存缓慢增长，重启后恢复
  • 偶尔抛 InvalidOperationException: Collection was modified

请分别分析这两个问题可能的原因，并给出修复方案。

练习 6.4.5（挑战·设计缓存键） 你要为一个"按多个条件查询商品"的接口做缓存。查询条件包括：

categoryId（整数）、minPrice（小数）、maxPrice（小数）、
brandIds（整数数组，最多 10 个）、keyword（字符串，可空）

(a) 你会怎么设计这个缓存键？ (b) 设计时要注意哪些坑？ (c) 用这个键去查 Dictionary 时，有什么性能隐患？

九、练习答案

6.4.1

Bug：重写了 Equals 却没有重写 GetHashCode（实验二的经典问题）。

于是 UserKey 继承了 object.GetHashCode()（基于内存地址），两个内容相同的对象哈希值不同，被分到不同的桶 —— ContainsKey 返回 False。

修复（用 record，最简洁）：

public record UserKey(string Name, int Age);

record 会自动生成基于所有字段的 Equals 和 GetHashCode，天然满足契约。

修复（手动实现）：

public class UserKey : IEquatable<UserKey>
{
    public string Name { get; }
    public int Age { get; }

    public UserKey(string name, int age) { Name = name; Age = age; }

    public bool Equals(UserKey? other)
        => other is not null && Name == other.Name && Age == other.Age;

    public override bool Equals(object? obj) => Equals(obj as UserKey);

    public override int GetHashCode() => HashCode.Combine(Name, Age);
}

三个要点：

  1. 必须重写 GetHashCode，并且用参与 Equals 比较的那些字段来算。
  2. 用 HashCode.Combine(...) —— 这是 .NET 提供的辅助方法，能正确地组合多个字段的哈希。别自己写 Name.GetHashCode() ^ Age（异或会让 (1,2) 和 (2,1) 得到相同的哈希）。
  3. 实现 IEquatable<T> —— 这样能避免对值类型装箱，并且 Dictionary 会优先调用它。

6.4.2 见上题答案的两种写法。

补充一个 record 的细节：record 默认生成的是值相等语义（两个字段相同的 record 实例是"相等"的），这正是哈希表需要的行为。

而 record struct 也是值相等。普通 class 默认是引用相等 —— 这就是为什么普通类不加处理就不能当键用。

6.4.3

  • (a) 错。 本节实验一就是反例：插入 1,2,3,4,5、删除 3、再插入 6，顺序变成了 1 2 6 4 5。

    原因是开放寻址的墓碑复用（6.2 节）。而且这个行为不保证跨版本一致。

  • (b) 对。 这正是契约的内容：a.Equals(b) 为 true ⟹ a.GetHashCode() == b.GetHashCode()。

    反过来不成立：哈希相同不代表对象相等（那就是"冲突"）。

  • (c) 错（说法太绝对）。 ConcurrentDictionary 保证的是单个操作的原子性。多个操作的组合仍然需要小心：
    // 错误：这两步之间可能被其他线程插入
if (!dict.ContainsKey(key))
    dict[key] = value;
// 正确：用原子 API
dict.TryAdd(key, value);

    通用原则：并发容器的原子性只覆盖它自己的单个方法调用，不覆盖你写的"检查 + 修改"组合。

  • (d) 错，而且这是个严重的安全问题。 .NET 的字符串哈希包含随机化（防止 6.1 节讲的哈希碰撞攻击）—— 同一个字符串在不同进程、不同运行中的 GetHashCode() 可能不同。

    后果：持久化后下次启动复用，会导致所有键都找不到。

    如果确实需要持久化键：用你自己控制的、稳定的哈希函数（比如 SHA-256 取前 8 字节），或者干脆存原始字符串。

6.4.4

问题 1：内存缓慢增长

可能的原因：

  1. 缓存没有淘汰机制。 如果订单号是唯一的、订单不断产生，而这个字典"只进不出"，内存必然持续增长。这是最常见的原因。
  2. "丢钥匙"式的泄漏（本节实验三）。如果订单对象被当作键使用、而它的字段又被修改过，就会产生"永远访问不到但占着内存"的条目。

    不过这里键是 string（不可变），所以这条不太可能 —— 但值得检查是否有别的地方用了可变对象当键。

  3. 事件订阅或闭包持有引用。 比如缓存的值对象挂了一个事件处理器，而处理器又引用了字典本身 —— 形成环导致都无法回收。

修复：

  • 加淘汰机制（LRU，或者用 MemoryCache 并设置过期策略）
  • 设一个容量上限
  • 用内存分析工具（如 dotnet-dump、dotMemory）确认对象是谁在持有

问题 2：InvalidOperationException: Collection was modified

这个异常只有两种可能：

  1. 在 foreach 遍历字典的过程中修改了它（包括增、删，甚至只是"覆盖已有的键"）。

    // 错误
foreach (var kv in cache)
    if (kv.Value.IsExpired) cache.Remove(kv.Key);     // 崩！

// 正确：先收集，再删除
var expired = cache.Where(kv => kv.Value.IsExpired).Select(kv => kv.Key).ToList();
foreach (var k in expired) cache.Remove(k);

  2. 多线程并发访问。 一个线程在遍历，另一个线程在写。

修复：

  • 如果是情况 1：用"先收集后删除"的写法，或者用 RemoveAll 风格的扩展方法
  • 如果是情况 2：换成 ConcurrentDictionary，或者加锁

怎么区分是哪种？ 看异常堆栈里有没有 Parallel/Task/Thread 相关的帧，或者看这个字典是否被多个线程共享。

一个值得注意的细节：Collection was modified 这个检查是基于版本号的。所以即使你只是"把某个键的值改成同样的值"，版本号也会变，遍历同样会抛异常。

6.4.5

(a) 缓存键的设计

方案一：规范化成一个字符串（最通用）

static string BuildCacheKey(int categoryId, decimal minPrice, decimal maxPrice,
                            IReadOnlyList<int> brandIds, string? keyword)
{
    var sb = new StringBuilder();
    sb.Append(categoryId).Append('|');
    sb.Append(minPrice).Append('|');
    sb.Append(maxPrice).Append('|');

    // 关键：把数组排序，让 {1,2,3} 和 {3,1,2} 生成同一个键
    sb.Append(string.Join(",", brandIds.OrderBy(x => x)));
    sb.Append('|');

    sb.Append(keyword ?? "");

    return sb.ToString();
}

方案二：用一个 record 当键（更安全）

public record ProductQueryKey(
    int CategoryId,
    decimal MinPrice,
    decimal MaxPrice,
    string BrandIdsKey,        // 已排序并拼接
    string? Keyword);

(b) 设计时要注意的坑

坑 说明 解法
数组顺序 {1,2,3} 和 {3,1,2} 是同一个查询，必须生成同一个键 先排序再拼接
分隔符歧义 "ab" + "c" 和 "a" + "bc" 拼出来都是 "abc" 用不会出现在数据里的分隔符（如 ），或者用长度前缀
字符串大小写 关键词 "iPhone" 和 "iphone" 是不是同一个查询？ 明确业务规则，并用 StringComparer 统一
浮点精度 19.99 和 19.990 应该是同一个查询 用 decimal 并统一保留位数
空值 null 和 "" 要区分吗？ 用一个明确的占位符（如 "\0"）表示 null
键太长 拼接出来的键可能几百个字符 长键会导致哈希计算慢；考虑先算哈希

(c) 性能隐患

  1. 键的构造本身有开销。 每次查询都要拼接字符串、排序数组 —— 如果查询很频繁，这个开销可能超过缓存查找本身。

    解法：让上游直接传来一个规范化的键，而不是每次重新构造。

  2. 字符串哈希要遍历整个键。 键越长，哈希计算越慢（6.4 节实测）。

    解法：如果键很长，先算一个固定的短哈希（如 SHA256 前 8 字节）当字典键，冲突时再比对原始键。

  3. 排序数组是 $O(k \log k)$（$k$ 最多 10），通常可接受，但如果 brandIds 经常很长就要注意。
  4. 内存：每个不同的查询组合都占一个缓存条目。组合爆炸时（比如关键词是自由文本），缓存会被瞬间打满。

    解法：限制缓存大小 + LRU 淘汰；或者对关键词做归一化（去除标点、转小写）。

这道题的核心是"缓存键必须是查询条件的"规范形式" —— 也就是说，语义相同的查询必须映射到同一个键。这需要你对业务语义有清晰的定义，而不只是写代码。

十、常见错误

误区 纠正
依赖 Dictionary 的遍历顺序 删除后插入会复用墓碑，顺序会变（实测 1 2 3 4 5 → 1 2 6 4 5）。而且不保证跨版本一致。
重写 Equals 不重写 GetHashCode 存进去就查不到了（实测 ContainsKey 返回 False）。用 record 一劳永逸。
用可变对象当键 改字段后哈希变了，元素还在但永远找不到（实测 Count 是 1 但 ContainsKey 是 False）。
在 foreach 里删除元素 抛 InvalidOperationException。先收集要删的键，再统一删。
多线程并发写 Dictionary 抛异常，甚至可能损坏数据。用 ConcurrentDictionary。
用 task.Wait(timeout) 判断超时 任务异常时它会抛出 AggregateException，不返回 false。必须 try-catch。
持久化 GetHashCode() 的结果 .NET 的字符串哈希带随机化，跨进程/跨运行不稳定。存原始值或用自己控制的哈希。

十一、本节总结

  1. 遍历顺序不可依赖：删除后插入会复用墓碑（实测 1 2 3 4 5 → 删 3 → 插 6 → 1 2 6 4 5）。需要顺序就用 SortedDictionary 或 OrderedDictionary。
  2. 哈希契约：Equals 为真 ⟹ GetHashCode 必须相等。违反它会导致存进去查不到（实测 ContainsKey 返回 False）。用 record 可以自动满足契约。
  3. 键必须不可变：修改键的字段会让哈希值改变，元素还在字典里但永远找不到（泄漏）。
  4. TryGetValue 优于 ContainsKey + 索引器：实测快 1.34 倍，而且避免了"检查-使用"之间的时间窗口。
  5. Dictionary 不是线程安全的：并发写会抛 InvalidOperationException（.NET 主动检测，比静默损坏好）。并发场景用 ConcurrentDictionary，但要注意它只保证单个操作的原子性。
  6. 键类型影响很大：int 键比 string 键快 7.84 倍（实测）。
  7. GetHashCode() 带随机化，不可持久化。

本章小结：第 6 章把哈希表从里到外讲了一遍。

  • 6.1 从"数组下标"出发，引出哈希函数 —— 以及一个灾难性的错误写法（字符求和）和一个容易被忽略的缺陷（末位扩散性差）。
  • 6.2 讲清了冲突的两大流派。最重要的收获是那个反直觉的实测：探测次数多 50% 的方案反而快 2.8 倍 —— 因为缓存。
  • 6.3 用实测曲线画出了负载因子的"悬崖"，并解释了它的数学根源（Knuth 公式）。
  • 6.4 回到工程，把最容易踩的坑逐个演示了一遍。

哈希表是本书前半部分最重要的数据结构 —— 它把查找从 $O(n)$ 和 $O(\log n)$ 降到了平均 $O(1)$，而且实现不算复杂。你以后遇到的绝大多数"需要快速查找"的问题，答案都是它。

下一章衔接：到这里，我们学的数据结构都是"无序"的 —— 数组、链表、哈希表，它们都不关心元素的顺序（SortedDictionary 除外，但它是树）。

但如果数据本身需要保持有序呢？ 比如"找出所有价格在 100 到 500 之间的商品"、"找出第 1000 名的成绩" —— 这类范围查询和排名查询，哈希表完全无能为力（哈希值打乱了顺序）。

解决这类问题需要排序。下一章讲排序算法 —— 不只是"怎么把数组排好序"，更重要的是排序能解锁哪些能力。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "6.4",
  "title": "C# Dictionary 的内部与工程用法",
  "covered": [
    "遍历顺序不可依赖的实测（墓碑复用导致 1 2 6 4 5）",
    "Equals/GetHashCode 契约与违反后果（ContainsKey 返回 False）",
    "可变对象当键导致的「丢钥匙」式泄漏",
    "TryGetValue vs ContainsKey+索引器实测（快 1.34 倍）",
    "并发写 Dictionary 实测（InvalidOperationException）与 Wait(timeout) 陷阱",
    "键类型影响实测（int 比 string 快 7.84 倍）",
    "容量/负载因子/键类型速查表与四个易忽略 API",
    "foreach 中删除元素的正确写法",
    "缓存键的规范化设计（数组排序、分隔符歧义、浮点精度）"
  ],
  "unresolved": [
    "SortedDictionary 的红黑树实现留到第 10 章后",
    "LRU 缓存的完整实现超出本章范围",
    "分布式缓存（Redis）不在本书范围"
  ],
  "canonical_terms": {
    "哈希契约": "Equals 为真则 GetHashCode 必须相等的约定",
    "线程安全": "多个线程同时访问时不会产生错误结果的性质"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 6.1-6.3 的哈希表原理",
    "读者了解 C# 的 record 类型与 IEquatable<T>"
  ],
  "word_count_actual": 3160,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch06/Sec64/",
    "六个实验的输出逐项核对（顺序变化、ContainsKey=False、1.34 倍、7.84 倍等）",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版并发实验用 task.Wait(timeout) 直接判断返回值，任务抛异常时导致整个程序崩溃（AggregateException 未捕获）；已改为 try-catch 并用 Flatten() 取首条异常消息"
  ],
  "next": "7.1 冒泡、选择、插入：三种 O(n^2) 排序"
}

results matching ""

    No results matching ""