从 Dictionary 开始

Dictionary 底层是什么？

标准答案

Dictionary<TKey, TValue> 底层是哈希表。它不是链表，也不是有序数组，核心思想是：

先根据 key 算出 hashCode，再通过 hash 定位到某个桶 bucket，桶里保存的是 entries 数组中的索引，真正的 key/value 数据存在 entries 里。

底层结构

它大概有两块核心数据：

buckets：桶数组，用来快速定位入口。 entries：元素数组，每个元素通常保存 hashCode、next、key、value。

如果两个不同的 key 算出来落到同一个 bucket，就发生哈希冲突。Dictionary 会通过 entries 里的 next 把冲突元素串起来，查找时沿着链继续比较。

查找流程

1. 对 key 调用 GetHashCode()。
2. 根据 hash 找到对应的 bucket。
3. 通过 bucket 找到 entries 中的第一个元素。
4. 先比 hash，再用 Equals 比 key 是否真正相等。
5. 如果不相等，就沿 next 找下一个冲突元素。

所以平均情况下查找、插入、删除接近 O(1)；但如果哈希函数很差，冲突特别多，性能会退化。

面试加分点

hashCode 相同，不代表两个 key 相等；但两个对象 Equals 为 true，它们的 GetHashCode() 必须相同。

自定义 key 时，最容易踩坑的是：重写了 Equals 却没重写 GetHashCode，或者把对象放进 Dictionary 后又修改了参与 hash 的字段，导致后面找不到这个 key。

在 Unity 项目里，Dictionary 常用于：id -> 配置、id -> 实例对象、事件表、对象缓存、资源句柄表。但要注意它默认不是线程安全的，遍历时修改会抛异常，大量插入前可以预设容量减少扩容成本。

哈希冲突怎么解决？

标准答案

哈希冲突就是：不同的 key 经过 hash 计算后，落到了同一个桶 bucket 里。 解决冲突的核心不是保证永远不冲突，而是：冲突后还能继续找到真正相等的 key。

常见解决方式

最常见有两类：

链地址法：同一个 bucket 下挂多个元素，冲突元素用链表或索引链串起来。C# 的 Dictionary<TKey, TValue> 常见实现思路就是这种：buckets 找入口，entries 里用 next 串冲突元素。

开放寻址法：如果当前位置被占了，就继续往后找空位置，比如线性探测、二次探测、双重哈希。手写哈希表时经常会提到它。

Dictionary 里大概怎么做

查找时先算：

hashCode -> bucketIndex

如果 bucket 里已经有元素，就进入 entries 数组比较：

先比较 hashCode，再用 Equals 判断 key 是否真的相等。 如果不相等，就沿着 next 找下一个冲突元素。

所以面试里要强调一句：hash 相同不代表 key 相同，最终还要 Equals 判断。

怎么减少冲突

可以通过扩容降低冲突概率。桶变多以后，元素重新分散，平均链会变短。 也可以优化 GetHashCode()，让 key 分布更均匀。

自定义 key 时一定要注意：Equals 和 GetHashCode 必须保持一致；插入 Dictionary 后，不要修改参与 hash 的字段。

为什么要重写 Equals？

标准答案

重写 Equals 的目的，是把“对象相等”的规则从默认规则改成业务规则。

比如两个 Item 对象：

A: itemId = 1001
B: itemId = 1001

它们虽然是两个 new 出来的不同对象，但在背包系统里，只要 itemId 一样，就可以认为是同一种物品。这时就应该重写 Equals。

底层原理

class 默认的 Equals 通常比较的是引用是否相同，也就是是不是同一个对象地址。

但很多集合会依赖 Equals 判断对象是否相等，比如：

Dictionary<TKey, TValue> 判断 key 是否相同。 HashSet<T> 判断元素是否重复。 List<T>.Contains 判断列表里有没有某个对象。 Distinct 判断是否去重。

所以如果不重写 Equals，两个字段一样的对象，可能仍然被认为“不相等”。

必须同时重写 GetHashCode

只要重写 Equals，通常就必须重写 GetHashCode。

规则是：

Equals 为 true 的两个对象，GetHashCode 必须相同。

否则 Dictionary、HashSet 这种哈希集合会出问题：明明业务上是同一个 key，但因为 hash 不一致，可能找不到。

示例代码

using System; // 引入 IEquatable<T> 接口所在命名空间

public sealed class ItemKey : IEquatable<ItemKey> // 定义一个物品 key，并实现强类型相等比较接口
{ // 类开始
    public int ItemId { get; } // 物品 ID，作为判断两个物品是否相同的核心字段

    public ItemKey(int itemId) // 构造函数，用来传入物品 ID
    { // 构造函数开始
        ItemId = itemId; // 保存物品 ID
    } // 构造函数结束

    public bool Equals(ItemKey other) // 实现强类型 Equals，避免不必要的类型转换
    { // Equals 方法开始
        return other != null && ItemId == other.ItemId; // 只要对方不为空，并且物品 ID 相同，就认为相等
    } // Equals 方法结束

    public override bool Equals(object obj) // 重写 object.Equals，让普通 Equals 调用也按业务规则比较
    { // object.Equals 方法开始
        return Equals(obj as ItemKey); // 把 object 转成 ItemKey，再复用强类型 Equals
    } // object.Equals 方法结束

    public override int GetHashCode() // 重写哈希值，保证和 Equals 使用同一套字段
    { // GetHashCode 方法开始
        return ItemId.GetHashCode(); // 物品 ID 相同，hash 就相同
    } // GetHashCode 方法结束
} // 类结束

Unity 项目场景

在 Unity 里，常见需要重写 Equals 的场景有：背包物品 key、格子坐标、技能 ID、配置表 key、地图节点、寻路节点。

比如 Dictionary<ItemKey, int> 用来记录物品数量，如果 ItemKey 不重写 Equals 和 GetHashCode，两个 itemId 一样的对象可能被当成两个不同 key。

常见坑

不要只重写 Equals，忘了重写 GetHashCode。 不要把可变字段作为 hash 字段后，又在放进 Dictionary 后修改它。 不要把 == 和 Equals 混为一谈，== 是运算符，Equals 是方法，集合主要依赖 Equals。

为什么要重写 GetHashCode？

标准答案

重写 GetHashCode 是为了让对象能在 Dictionary、HashSet 这种哈希集合里正常工作。

因为哈希集合不是一上来就调用 Equals，而是先调用 GetHashCode 找到对应的桶 bucket，然后才在这个桶里用 Equals 判断是不是同一个 key。

所以有一个非常重要的规则：

Equals 为 true 的两个对象，GetHashCode 必须相同。

反过来不要求成立：GetHashCode 相同，Equals 不一定为 true，因为可能只是哈希冲突。

底层原理

假设有两个物品 key：

A.ItemId = 1001
B.ItemId = 1001

业务上它们应该相等。

如果你重写了 Equals，认为 ItemId 相同就相等，但没有按 ItemId 重写 GetHashCode，那么 A 和 B 可能算出不同 hash，进入不同 bucket。

结果就是：Dictionary 查 B 时，只会去 B 对应的 bucket 找，不会跑到 A 的 bucket 里比较 Equals，于是可能出现“明明相等但找不到”的问题。

正确代码

using System; // 引入 IEquatable<T> 接口所在命名空间

public sealed class ItemKey : IEquatable<ItemKey> // 定义一个可作为 Dictionary key 的物品标识类
{ // 类开始
    public int ItemId { get; } // 物品 ID，作为业务相等和哈希计算的核心字段

    public ItemKey(int itemId) // 构造函数，用来创建物品 key
    { // 构造函数开始
        ItemId = itemId; // 保存传入的物品 ID
    } // 构造函数结束

    public bool Equals(ItemKey other) // 实现强类型 Equals，减少类型转换成本
    { // Equals 方法开始
        return other != null && ItemId == other.ItemId; // 只要对方不为空，并且 ItemId 相同，就认为业务上相等
    } // Equals 方法结束

    public override bool Equals(object obj) // 重写 object.Equals，让集合和普通调用都使用业务相等规则
    { // object.Equals 方法开始
        return Equals(obj as ItemKey); // 转成 ItemKey 后复用强类型 Equals
    } // object.Equals 方法结束

    public override int GetHashCode() // 重写 GetHashCode，保证和 Equals 使用同一套字段
    { // GetHashCode 方法开始
        return ItemId.GetHashCode(); // ItemId 相同的对象一定得到相同 hash
    } // GetHashCode 方法结束
} // 类结束

Unity 项目场景

比如背包系统、技能系统、配置表索引、地图格子坐标，经常会把自定义对象作为 Dictionary 的 key。 这时如果你定义了“两个对象怎么算相等”，就必须同步定义“相等对象怎么算 hash”。

常见坑

不要只重写 Equals，不重写 GetHashCode。 不要让 GetHashCode 返回随机数、时间戳这种不稳定值。 不要把会变化的字段放进 hash 计算里，否则对象放入 Dictionary 后字段变了，后面可能找不到它。

如果 key 变化了会怎样？

标准答案

如果 Dictionary 的 key 变化了，准确说是：参与 Equals / GetHashCode 的字段变化了，那这个 key 可能会出现“明明还在 Dictionary 里，但查不到、删不掉”的问题。

原因很核心：

Dictionary 插入时，会根据 key 当时的 GetHashCode() 算出 bucket，把元素挂到那个桶里。 如果后来 key 的字段变了，新的 GetHashCode() 也变了。 再查找时，Dictionary 会去新 bucket 找，但元素其实还挂在旧 bucket 里，所以可能找不到。

举个危险例子

using System.Collections.Generic; // 引入 Dictionary 类型

public sealed class ItemKey // 定义一个可作为 Dictionary key 的类
{ // 类开始
    public int ItemId; // 这个字段参与 Equals 和 GetHashCode

    public override bool Equals(object obj) // 重写 Equals，按 ItemId 判断业务相等
    { // Equals 方法开始
        return obj is ItemKey other && ItemId == other.ItemId; // ItemId 相同就认为是同一个 key
    } // Equals 方法结束

    public override int GetHashCode() // 重写 GetHashCode，按 ItemId 计算 hash
    { // GetHashCode 方法开始
        return ItemId.GetHashCode(); // ItemId 变了，hash 也会跟着变
    } // GetHashCode 方法结束
} // 类结束

var dict = new Dictionary<ItemKey, string>(); // 创建一个 Dictionary
var key = new ItemKey { ItemId = 1001 }; // 创建 key，此时 hash 基于 1001
dict[key] = "Potion"; // 插入时，元素被放到 hash(1001) 对应的桶里
key.ItemId = 2002; // 危险：修改了参与 hash 的字段
bool found = dict.ContainsKey(key); // 可能是 false，因为现在会去 hash(2002) 对应的桶里找

底层理解

插入时：

ItemId = 1001 -> hash(1001) -> bucket[2]

修改后：

ItemId = 2002 -> hash(2002) -> bucket[5]

但 Dictionary 不会自动把旧元素从 bucket[2] 移动到 bucket[5]。 所以它可能还在集合里，遍历能看到，但 ContainsKey、Remove、索引访问都可能失败。

哪些变化没事

如果修改的是不参与 Equals / GetHashCode 的字段，一般没事。 比如显示名、缓存文本、临时状态，只要不影响 hash 和相等判断，就不会破坏 Dictionary 结构。

正确做法

key 尽量设计成不可变，比如 readonly struct、只读属性、record。 更推荐用稳定 ID 当 key，比如 int itemId、long entityId、string guid。 如果必须改 key，正确流程是：先 Remove 旧 key，再修改，再 Add 新 key。

Unity 场景

背包物品 key、技能 key、配置表 key、地图格子坐标、寻路节点，如果要放进 Dictionary 或 HashSet，一定要保证参与 hash 的字段稳定。面试里可以直接说：哈希集合里的 key 应该尽量不可变。

扩容时为什么要重新分布？

标准答案

Dictionary 扩容时要重新分布，是因为元素属于哪个桶，不只取决于 hashCode，还取决于当前桶数组的长度。

核心公式可以理解成：

bucketIndex = hashCode % buckets.Length

扩容前 buckets.Length 可能是 4，扩容后变成 8、16 或更大。 长度一变，同一个 hashCode 算出来的 bucketIndex 就可能变，所以必须重新把元素分配到新的桶里。

举个例子

假设扩容前有 4 个桶：

hash = 1   -> 1 % 4 = 1
hash = 5   -> 5 % 4 = 1
hash = 9   -> 9 % 4 = 1

这三个元素都落在 bucket[1]，冲突比较多。

扩容后变成 8 个桶：

hash = 1   -> 1 % 8 = 1
hash = 5   -> 5 % 8 = 5
hash = 9   -> 9 % 8 = 1

原来挤在一起的元素，就有一部分被分散到了新的桶里，冲突减少，查找速度更稳定。

底层原理

Dictionary 里大概有两块结构：

buckets：保存每个桶的入口。 entries：保存真正的 key、value、hashCode、next。

扩容时，不能只把旧 buckets 数组复制到新数组里。因为旧 bucket 入口是按旧长度算出来的，新查找会按新长度计算 bucket。

所以扩容时通常要：

1. 分配更大的 buckets 和 entries。
2. 遍历已有 entries。
3. 用已有的 hashCode 按新桶数量重新算 bucket。
4. 重建每个 bucket 的入口和 next 链。

注意：很多情况下不一定重新调用 key.GetHashCode()，而是复用 entry 里保存的 hashCode，再根据新的桶数量重算下标。

为什么这么做

第一是为了保证查找正确。 如果不重新分布，新查找会去新 bucket 找，但元素还挂在旧 bucket 逻辑下，就会找不到。

第二是为了减少哈希冲突。 桶变多以后，平均每个桶里的元素变少，链更短，查找更接近 O(1)。

面试加分点

扩容本身是有代价的，单次扩容需要分配新数组，并遍历旧元素重建结构，所以那一次操作接近 O(n)。 但从整体看，扩容减少了后续冲突，让平均查询和插入保持接近 O(1)。

在 Unity 里，如果配置表、对象表、资源表数量能预估，最好创建 Dictionary 时提前设置容量，减少运行时扩容带来的 GC 和卡顿风险。

线程安全吗？

标准答案

普通 Dictionary<TKey, TValue> 不是线程安全的。

更准确地说：

多个线程只读：通常可以，前提是 Dictionary 已经构建完，并且之后没有任何线程修改。 多个线程同时写：不安全。 一个线程读，另一个线程写：也不安全。 遍历时另一个线程修改：很容易抛异常或读到不一致结果。

为什么不安全

Dictionary 内部有 buckets、entries、next 链。 当一个线程执行 Add、Remove、扩容时，内部结构可能正在变化。 另一个线程如果同时 TryGetValue 或 foreach，可能看到中间状态。

所以问题不是“它一定每次都会崩”，而是：结果不可预测。

典型坑

using System.Collections.Generic; // 引入 Dictionary 类型

private readonly object _lockObj = new object(); // 定义一把专门保护 Dictionary 的锁

private readonly Dictionary<int, string> _dict = new Dictionary<int, string>(); // 创建普通 Dictionary，它本身不是线程安全的

public void SetValue(int key, string value) // 定义写入方法
{ // 方法开始
    lock (_lockObj) // 所有写操作都进入同一把锁
    { // lock 代码块开始
        _dict[key] = value; // 在锁内修改 Dictionary，避免其他线程同时读写
    } // lock 代码块结束
} // 方法结束

public bool TryGetValue(int key, out string value) // 定义读取方法
{ // 方法开始
    lock (_lockObj) // 读操作也使用同一把锁，避免读写并发
    { // lock 代码块开始
        return _dict.TryGetValue(key, out value); // 在锁内读取 Dictionary
    } // lock 代码块结束
} // 方法结束

如果多线程频繁读写怎么办

可以用 ConcurrentDictionary<TKey, TValue>，它是专门为并发访问设计的。 比如 GetOrAdd、TryAdd、TryRemove 这类操作，比自己写 ContainsKey 再 Add 更安全。

因为这个写法不是原子的：

if (!dict.ContainsKey(key))
    dict.Add(key, value);

两个线程可能同时判断“不存在”，然后同时 Add，就出问题。

Unity 项目里怎么处理

Unity 里大多数游戏逻辑都在主线程，所以普通 Dictionary 很常见。 如果后台线程加载配置、解析数据、计算寻路结果，建议：

后台线程只处理自己的局部数据。 处理完以后把结果丢回主线程。 主线程统一写共享 Dictionary。

这样比到处加锁更清晰，也更符合 Unity 主线程模型。

面试一句话

普通 Dictionary 可以“只读共享”，但不能“并发写”或“读写并发”；如果共享读写，要加锁、用 ConcurrentDictionary，或者用主线程归并/不可变快照方案。

和 ConcurrentDictionary 区别？

标准答案

Dictionary<TKey, TValue> 和 ConcurrentDictionary<TKey, TValue> 都是哈希表思路，但核心区别是：

Dictionary 更轻、更快，适合单线程或构建完成后只读。 ConcurrentDictionary 支持多线程并发读写，内部做了并发控制，但有额外性能和内存开销。

底层区别

普通 Dictionary 内部有 buckets、entries、next 链。 如果一个线程正在 Add、Remove、扩容，另一个线程同时读，就可能读到中间状态，所以不安全。

ConcurrentDictionary 会通过细粒度锁、原子操作等机制保护内部结构，让多个线程可以安全地执行 TryAdd、TryRemove、GetOrAdd、AddOrUpdate 这类操作。

但要注意：它保证的是容器结构安全，不是说里面的 value 对象也自动线程安全。

典型区别

Dictionary：

ContainsKey + Add 不是原子操作

两个线程可能同时判断 key 不存在，然后同时 Add。

ConcurrentDictionary：

TryAdd / GetOrAdd / AddOrUpdate

这些是为并发场景设计的原子语义方法。

使用场景

Unity 主线程逻辑、配置表、对象表、技能表，通常用 Dictionary。 后台线程日志统计、下载状态、任务结果缓存、多线程数据归并，可以考虑 ConcurrentDictionary。

但不要误会：用了 ConcurrentDictionary 也不能在子线程操作 Unity API，比如 GameObject、Transform、Instantiate 这些仍然要回主线程。

常见坑

ConcurrentDictionary 不是永远更快。单线程场景下，普通 Dictionary 往往更快、更省内存。 ConcurrentDictionary 的遍历是安全的，但不一定是严格的瞬间快照。 GetOrAdd、AddOrUpdate 里的工厂委托可能被多次调用，所以不要在里面写有副作用的逻辑，比如扣金币、发奖励、写关键日志。

面试一句话

我会这样总结：Dictionary 追求轻量和速度，但需要外部保证线程安全；ConcurrentDictionary 追求并发安全，提供原子操作方法，但有额外开销。Unity 里主线程数据优先用 Dictionary，跨线程共享数据再考虑 ConcurrentDictionary 或主线程归并。

和 SortedDictionary 区别？

标准答案

Dictionary<TKey, TValue> 和 SortedDictionary<TKey, TValue> 的核心区别是：

Dictionary 底层是哈希表，追求快速查找，平均查找接近 O(1)，但不保证按 key 排序。 SortedDictionary 底层通常是平衡搜索树，会一直按 key 排序，查找、插入、删除都是 O(log n)。

底层原理

Dictionary 依赖：

GetHashCode() 决定去哪一个 bucket。 Equals() 判断是不是同一个 key。

所以它关心的是“这个 key 是不是同一个 key”，不关心 key 的大小顺序。

SortedDictionary 依赖：

IComparer<TKey> 或 key 自身的 IComparable<TKey>。

它通过比较 key 的大小，把元素放进一棵有序树里，所以遍历时天然就是按 key 从小到大。

怎么选择

如果只是：

根据 id 查配置
根据 entityId 查对象
根据 skillId 查技能数据

优先用 Dictionary，因为它更快、更轻。

如果你需要：

按时间点从小到大触发事件
按分数排序遍历排行榜区间
按 key 顺序输出数据

可以考虑 SortedDictionary。

复杂度对比

Dictionary：

查找平均 O(1)，最坏可能退化。 插入平均 O(1)。 遍历顺序不要作为业务依赖。

SortedDictionary：

查找 O(log n)。 插入 O(log n)。 删除 O(log n)。 遍历按 key 有序。

常见坑

不要因为名字里有 Sorted 就默认它更好。没有排序需求时，SortedDictionary 通常比 Dictionary 更重。 SortedDictionary 的 key 必须能比较大小，要么 key 实现 IComparable，要么传入 IComparer。 如果 key 是可变对象，修改参与排序比较的字段，也会破坏树的顺序，和 Dictionary 修改 hash 字段一样危险。

面试一句话

我会这么答：Dictionary 用 hash 换速度，适合快速查找；SortedDictionary 用平衡树维护 key 的有序性，适合需要按 key 有序遍历的场景。没有排序需求时，我不会为了“看起来高级”把 Dictionary 换成 SortedDictionary。

Unity 里哪些地方适合用 Dictionary？

标准答案

Unity 里适合用 Dictionary 的场景，本质都是一句话：

通过一个稳定 key，快速找到一个对象或一份数据。

比如：

配置表：configId -> ConfigData 运行时对象：entityId -> Entity 背包系统：itemId -> count / itemData 任务系统：questId -> QuestInstance 资源管理：assetPath -> loaded handle 对象池：prefabId -> ObjectPool UI 管理：windowName -> UIWindow 事件系统：eventType -> listener list 红点系统：redDotKey -> node state

为什么适合

如果不用 Dictionary，经常会写成遍历：

遍历所有配置，找 id == 1001 的那一行

数据少时没感觉，数据一多，每帧或高频调用就会很浪费。

用 Dictionary 后，可以变成：

dict.TryGetValue(id, out data)

平均查找接近 O(1)，非常适合游戏里高频查询。

简单代码例子

using System.Collections.Generic; // 引入 Dictionary 所在命名空间

public sealed class SkillConfig // 定义技能配置类
{ // 类开始
    public int SkillId; // 技能 ID，用来作为 Dictionary 的 key
    public string Name; // 技能名字，用来显示或调试
    public int Damage; // 技能伤害，用来战斗计算
} // 类结束

public sealed class SkillConfigTable // 定义技能配置表管理类
{ // 类开始
    private readonly Dictionary<int, SkillConfig> _configs = new Dictionary<int, SkillConfig>(); // 用 skillId 快速索引技能配置

    public void AddConfig(SkillConfig config) // 添加一条技能配置
    { // 方法开始
        _configs[config.SkillId] = config; // 用技能 ID 作为 key，把配置存进去
    } // 方法结束

    public bool TryGetConfig(int skillId, out SkillConfig config) // 尝试根据技能 ID 查配置
    { // 方法开始
        return _configs.TryGetValue(skillId, out config); // 平均 O(1) 查找，避免遍历整张表
    } // 方法结束
} // 类结束

Unity 工程里的判断标准

适合用 Dictionary：

key 稳定，比如 int id、string path、long entityId。 查找频繁，比如战斗目标查询、配置读取、资源缓存。 不关心顺序，比如只要查得到，不要求按 key 排序。

不适合用 Dictionary：

需要严格按顺序遍历，可以考虑 List、SortedDictionary。 key 会变化，容易破坏 hash。 数据量很小且只是顺序遍历，直接 List 更简单。

面试加分点

我会强调：Dictionary 是用空间换时间，适合做索引表和缓存表。 在 Unity 里大量数据可以提前设置容量，减少扩容。 不要每帧临时 new Dictionary，也不要用可变对象做 key。 如果跨线程共享，还要考虑线程安全，普通 Dictionary 不适合读写并发。