第 12 章 · 集合：列表、字典、集合与不可变集合

解决什么问题：一批数据怎么存、怎么按键查、怎么去重，遍历时顺序靠不靠得住，又怎么防止别人改掉它。

四种语言的态度：四种语言都内置动态数组和哈希表；Python 的 dict 和 JS 的 Map 保证插入顺序（JS 普通对象只部分保证），C# 不保证，Go 故意打乱；不可变集合 Python 有 tuple、frozenset，C# 有专门的库，JS 和 Go 只能靠约定或只读视图。

一个场景

仓库收到一串货品名：apple banana apple cherry banana apple。要做四件事：原样保存；去重但保留第一次出现的顺序；统计每种货品的数量；和另一批货 banana cherry durian 求交集。计数和交集一律先按名字排序再打印，不依赖字典或集合自己的遍历顺序，这样四种语言的输出才能逐字一致。

概念本身

几乎所有程序都离不开三种容器。列表（list）按位置存一串元素，最常见的实现是动态数组（dynamic array）：元素在内存里连续排放，按下标取值一步到位；空间用完时申请一块更大的内存，把旧元素整体搬过去。每次按比例（而不是固定几个）扩大，平均下来每次追加仍是常数时间。另一种实现是链表（linked list），插入删除不用搬动元素，但按下标取值要从头走，节点又分散在内存里，所以四种语言的默认列表都是动态数组。

字典（dictionary，也叫映射 map）按键存取，实现几乎都是哈希表（hash table）：对键算一个哈希值（hash），取模得到槽位（slot），把键值放进去；查找时重算一遍，直接跳到那个槽位。两个键落到同一个槽位叫冲突（collision），处理办法有两种：拉链法（separate chaining）在槽位上挂一条链，开放寻址（open addressing）按固定规则探测下一个空槽。集合（set）就是只有键、没有值的哈希表，所以判断“在不在”和求交集都很快。

上半张看 cherry 和 apple 撞在槽位 3 之后的两条出路；下半张看 Python 字典怎样把“按哈希找位置”和“按插入顺序存条目”拆成两张表。

哈希表本身不记录插入顺序：槽位由哈希值决定，按槽位遍历，顺序就取决于哈希函数和表的大小，表一扩容就可能全变。语言要承诺“按插入顺序遍历”，就得像图下半那样另存一份按顺序排列的条目。不可变集合（immutable collection）也有两种做法：只读视图（read-only view）只是不给你修改的方法，底下的集合别人照样能改；真正不可变则是建好后谁也改不了，“修改”会返回一个新集合。

Python 怎么做

Python 的 list、dict、set 是内置类型，有字面量语法；不可变的有 tuple 和 frozenset；collections 模块再补上 Counter、deque 等。

from collections import Counter

items = tuple("apple banana apple cherry banana apple".split())  # tuple：建好后不能改
other = frozenset("banana cherry durian".split())

unique = list(dict.fromkeys(items))  # dict 保证插入顺序，键又不重复
counts = Counter(items)  # dict 的子类，值是出现次数
common = set(items) & other

print("原始：" + " ".join(items))
print("去重（保留首次出现顺序）：" + " ".join(unique))
print("计数（按名字）：" + " ".join(f"{k}={counts[k]}" for k in sorted(counts)))
print("交集（按名字）：" + " ".join(sorted(common)))

# 输出：
# 原始：apple banana apple cherry banana apple
# 去重（保留首次出现顺序）：apple banana cherry
# 计数（按名字）：apple=3 banana=2 cherry=1
# 交集（按名字）：banana cherry

运行：python stock.py。dict.fromkeys 用元素做键建字典，重复的键只留第一次，取键就是保序去重。Counter 一步完成计数；&、|、- 是集合的交、并、差。

底层怎么实现。 list 是一个指针数组，每格指向一个对象；空间不够时按约八分之一的比例多申请一些。dict 从 CPython 3.6 起是紧凑字典（compact dict）：一张小的索引表（indices）只存条目的编号，用开放寻址解决冲突；条目（哈希值、键、值）按插入顺序追加在另一个数组里。遍历走条目数组，顺序自然就是插入顺序，而且比老式的稀疏大表省内存（3.6 的发布说明给的数字是少用 20%–25%）。set 仍是老式的一张大表，元素直接放在槽位里，所以集合不保证任何顺序。

• 一边遍历字典一边增删键，抛出 RuntimeError: dictionary changed size during iteration；要改就先 list(d) 拷一份键。
• [[0] * 3] * 3 得到的三行是同一个列表对象，改一格三行一起变，因为 * n 复制的是引用；要写成 [[0] * 3 for _ in range(3)]。
• tuple 只是自己不能改，里面装的列表照样能改；元素都可哈希（hashable）时它才能当字典的键。

JS/TS 怎么做

JavaScript 内置 Array、Map、Set；在 Map 出现（ES2015）之前，大家用普通对象当字典。没有内置的不可变集合，Object.freeze 是浅冻结，TS 另有只在编译期起作用的 readonly 类型。

/// <reference lib="esnext.collection" />
// 上一行打开 Set 新方法的类型声明；Node 22 运行时已经有这些方法

const items: readonly string[] = Object.freeze("apple banana apple cherry banana apple".split(" "));
const other = new Set("banana cherry durian".split(" "));

const unique = [...new Set(items)]; // Set 按插入顺序遍历
const counts = new Map<string, number>();
for (const item of items) counts.set(item, (counts.get(item) ?? 0) + 1);
const common = new Set(items).intersection(other);

const countText = [...counts.keys()].sort().map((k) => `${k}=${counts.get(k)}`);
console.log("原始：" + items.join(" "));
console.log("去重（保留首次出现顺序）：" + unique.join(" "));
console.log("计数（按名字）：" + countText.join(" "));
console.log("交集（按名字）：" + [...common].sort().join(" "));

// 输出：
// 原始：apple banana apple cherry banana apple
// 去重（保留首次出现顺序）：apple banana cherry
// 计数（按名字）：apple=3 banana=2 cherry=1
// 交集（按名字）：banana cherry

运行：tsx stock.ts。规范规定 Map 和 Set 按插入顺序遍历，所以 [...new Set(items)] 就是保序去重。intersection、union、difference、isSubsetOf 等七个集合方法进入了 ES2025，V8 12.2 起提供，Node 22 可以直接用；TS 5.5 起把它们的类型放在 esnext.collection 里，target 较低时要像第一行那样显式打开。readonly string[] 让编译器拒绝 push，Object.freeze 则让运行时的修改在严格模式下抛 TypeError。

底层怎么实现。 V8 的 Map 和 Set 用确定性哈希表（deterministic hash table）：条目按插入顺序存在一个数组里，另有一组桶（bucket）指向链头，冲突的条目靠“下一条”的编号串起来，删除只做标记，扩容时再压紧。数组在 V8 里按元素种类分别存储，全是小整数时存成连续的原始整数；容量不够时扩到约 1.5 倍。

• 普通对象当字典时，键都变成字符串：obj[1] 和 obj["1"] 是同一格；遍历时整数键（形如数组下标的键）先按数值升序，其余键再按插入顺序，所以 {b: 1, 2: 0, a: 1, 1: 0} 的键顺序是 1 2 b a。
• Map 用对象当键时按引用比较：两个内容相同的 {id: 1} 是两个键，查找时必须拿着同一个对象。

C# 怎么做

.NET 的 System.Collections.Generic 提供 List<T>、Dictionary<TKey, TValue>、HashSet<T>；System.Collections.Immutable 提供真正不可变的 ImmutableArray<T>、ImmutableList<T> 等；.NET 8 又加了为只读场景优化的 FrozenDictionary 和 FrozenSet。LINQ 负责分组、求交集这类运算。

using System;
using System.Collections.Frozen;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;

ImmutableArray<string> items = [.. "apple banana apple cherry banana apple".Split(' ')];
FrozenSet<string> other = "banana cherry durian".Split(' ').ToFrozenSet();

var seen = new HashSet<string>();
var unique = items.Where(seen.Add).ToList(); // Add 第一次见到时返回 true
var counts = items.CountBy(x => x).ToDictionary(); // .NET 9 起有 CountBy
var common = items.Intersect(other);

var countText = counts.Keys.Order(StringComparer.Ordinal).Select(k => $"{k}={counts[k]}");
Console.WriteLine("原始：" + string.Join(" ", items));
Console.WriteLine("去重（保留首次出现顺序）：" + string.Join(" ", unique));
Console.WriteLine("计数（按名字）：" + string.Join(" ", countText));
Console.WriteLine("交集（按名字）：" + string.Join(" ", common.Order(StringComparer.Ordinal)));

// 输出：
// 原始：apple banana apple cherry banana apple
// 去重（保留首次出现顺序）：apple banana cherry
// 计数（按名字）：apple=3 banana=2 cherry=1
// 交集（按名字）：banana cherry

运行：dotnet run stock.cs。HashSet.Add 返回“是否新加入”，配合 Where 正好是保序去重。计数在 .NET 9 之前惯用 GroupBy(x => x) 再 Count()。排序传 StringComparer.Ordinal，按字符编码比较，不受系统区域设置影响。

底层怎么实现。 List<T> 包着一个数组，满了就把容量翻倍。Dictionary 用两个数组：buckets 按哈希值存条目的编号，entries 依次存放条目，冲突的条目用 next 字段串成链。新条目先填删除留下的空位，没有空位才追加到末尾，所以只增不删时遍历恰好是插入顺序，一删一加顺序就乱了；文档明确说顺序未定义。ImmutableList<T> 是一棵平衡二叉树（AVL 树），“修改”只复制从根到改动处的一条路径，新旧版本共享其余节点；FrozenDictionary 在创建时多花时间，按实际的键挑选哈希和存储策略，换取更快的查找。

• 以为 Dictionary 有顺序：测试里只增不删，顺序一直对，上线后有了删除，输出顺序就变了。要顺序就排序，或用 .NET 9 新增的泛型 OrderedDictionary<TKey, TValue>。
• IReadOnlyList<T> 只是只读视图：拿到的人可以强转回 List<T> 去改，原列表变了它也跟着变；要防改就交出 ImmutableArray<T>。
• 在 foreach 里给 List 增删元素、给 Dictionary 加键，下一次取元素时抛 InvalidOperationException。

Go 怎么做

Go 内置切片（slice）和 map 两种容器，有字面量语法；没有集合类型，惯用 map[T]struct{} 代替，空结构体不占内存。1.21 起标准库有 slices 和 maps 两个包，1.23 起 maps.Keys 返回迭代器，可以直接交给 slices.Sorted 排序。没有不可变集合。

package main

import (
  "fmt"
  "maps"
  "slices"
  "strings"
)

func main() {
  items := strings.Fields("apple banana apple cherry banana apple")
  other := map[string]struct{}{}
  for _, s := range strings.Fields("banana cherry durian") {
    other[s] = struct{}{}
  }

  seen := map[string]struct{}{}
  var unique []string
  counts := map[string]int{}
  for _, s := range items {
    if _, ok := seen[s]; !ok {
      seen[s] = struct{}{}
      unique = append(unique, s)
    }
    counts[s]++ // 键不存在时读到零值 0
  }
  var common []string
  for s := range seen { // map 的遍历顺序每次不同，所以后面要排序
    if _, ok := other[s]; ok {
      common = append(common, s)
    }
  }
  slices.Sort(common)

  var countText []string
  for _, k := range slices.Sorted(maps.Keys(counts)) {
    countText = append(countText, fmt.Sprintf("%s=%d", k, counts[k]))
  }
  fmt.Println("原始：" + strings.Join(items, " "))
  fmt.Println("去重（保留首次出现顺序）：" + strings.Join(unique, " "))
  fmt.Println("计数（按名字）：" + strings.Join(countText, " "))
  fmt.Println("交集（按名字）：" + strings.Join(common, " "))
}

// 输出：
// 原始：apple banana apple cherry banana apple
// 去重（保留首次出现顺序）：apple banana cherry
// 计数（按名字）：apple=3 banana=2 cherry=1
// 交集（按名字）：banana cherry

运行：go run stock.go。保序去重要自己用切片记顺序、用 map 记见过的键；交集要自己写循环。读不存在的键得到零值，所以 counts[s]++ 不用先判断；需要区分“没有”和“值为零”时用 v, ok := m[k]。

底层怎么实现。 切片是一个三字段的头：指向底层数组的指针、长度、容量。append 超出容量时分配新数组，小切片容量翻倍，大了以后增长比例逐渐降到约 1.25 倍。map 是运行时实现的哈希表，Go 1.24 起改用瑞士表（Swiss table）：槽位八个一组，开放寻址。每次 range 一个 map，运行时都随机选一个起点，所以同一个 map 两次遍历的顺序也可能不同。

• 直接 range 一个 map 打印结果，本机跑几次看着稳定，换台机器或多跑几次就变；输出前一律排序。fmt.Println(m) 打印整个 map 时会按键排序，别因此以为遍历也有序。
• 多个 goroutine 同时读写同一个 map，运行时检测到后直接报 fatal error: concurrent map writes 终止进程，recover 救不回来；要加锁或用 sync.Map。

对比表

维度	Python	JS/TS	C#	Go
支持程度	原生	原生	标准库	原生（无集合类型）
实现机制	紧凑字典 + 开放寻址	确定性哈希表	桶数组 + 条目数组	瑞士表，遍历随机起点
动态数组	list	Array	List<T>	切片
字典的遍历顺序	插入顺序（3.7 起保证）	Map 插入顺序；对象整数键在前	未定义	故意随机
集合类型	set	Set	HashSet<T>	map[T]struct{}
不可变集合	tuple、frozenset	Object.freeze、readonly（浅）	ImmutableArray<T>、FrozenSet<T>	没有
计数的惯用写法	Counter(items)	m.set(k, (m.get(k) ?? 0) + 1)	items.CountBy(x => x)	counts[s]++

最大的差异在“字典的遍历顺序”一行：同样是哈希表，四种语言给出了保证、部分保证（JS 的 Map 保证，普通对象只部分保证）、不保证、故意打乱四种答案。

差异从哪来

Python 的有序字典起初是性能优化的副产品。2012 年 Raymond Hettinger 提出紧凑字典，为的是省内存、遍历更快；PyPy 先实现，CPython 3.6 跟进，插入顺序当时只算实现细节。用户很快开始依赖它，2017 年 Guido van Rossum 宣布从 3.7 起写进语言规范。后果是 Python 代码可以放心依赖字典顺序，其他 Python 实现也必须做到；set 没有做同样的承诺，保留了更紧凑的布局。

Go 走了相反的方向。早期的 map 遍历顺序看似固定，有的测试悄悄依赖了它，一换实现就坏。Go 1 起运行时随机化遍历起点，让依赖顺序的代码尽早失败，实现也因此保有自由：1.24 整个换成瑞士表，没有破坏任何合法程序。代价是凡要稳定输出都得自己排序；1.23 起可以写成 slices.Sorted(maps.Keys(m)) 一行。

JS 的普通对象既是记录又被当字典用，键的顺序规则是历史妥协：ES2015 先规定了对象自有属性键的顺序，ES2020 补齐了 for-in，整数键在前是把各引擎已有的做法写进规范。Map 和 Set 一开始就规定按插入顺序，V8 为此选了确定性哈希表。

C# 的 Dictionary 只承诺性能，不承诺顺序，实现可以随版本优化。.NET 另设不可变集合，服务多线程共享和“拿到的快照不会变”的需求；冻结集合（frozen collection）则针对建一次、此后只读无数次的配置表和路由表。代价是同一件事有好几种类型可选，选错了要么改不动，要么慢。

实践建议

• 要稳定输出就排序，不管语言保不保证顺序；Python 和 JS 的插入顺序只在“顺序本身有意义”时依赖。
• 判断“在不在”用集合：列表的 in、includes、Contains 都是逐个比较。
• 把集合交给别人时想清楚要的是只读视图还是快照：C# 交 ImmutableArray<T>，Python 交 tuple，JS 和 Go 交一份拷贝。
• Go 里跨 goroutine 共享 map 一律加锁；CPython 的字典单步操作是线程安全的，但“先查后改”两步之间仍可能被别的线程插进来。

练一练

用 Python 和 Go 各写一个词频统计：给定一段文字 the cat and the dog and the bird saw a cat，按出现次数降序排列，次数相同的按单词升序，打印前三个，每行形如 the 3。

提示：Python 的 Counter.most_common 对次数相同的词按什么顺序返回？它满足“按单词升序”吗？Go 的 slices.SortFunc 需要一个比较函数，次数和单词两个条件怎样组合？

小结

• 列表几乎都是动态数组，按比例扩容；字典和集合都是哈希表，集合是只有键的字典。
• 哈希表本身无序；Python 的 dict、JS 的 Map 和 Set 另存一份按插入顺序排列的条目，所以能保证顺序。
• C# 的 Dictionary 顺序未定义，Go 的 map 每次遍历随机起点；要稳定输出就先排序。
• 不可变有两种：只读视图挡住的只是你自己，真正不可变的集合谁也改不了，“修改”返回新集合。
• Go 没有集合类型，用 map[T]struct{}；并发读写 map 会直接让进程崩溃。