01-数据容器进阶

难度：⭐⭐ 进阶 预计时间：60分钟 前置知识：列表、字典、元组基础操作 引入版本：Python 2.4+ (collections 模块)

原生的 list, dict, tuple 虽然好用，但在某些特定场景下（如计数、去重、复杂配置合并），原生数据结构会显得笨重且低效。collections 模块提供了高性能的替代方案，底层由 C 语言实现，是进阶 Python 开发的必修课。

概念铺垫

┌─────────────────────────────────────────────────────────────┐
│          collections 核心组件概览                            │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. Counter：计数器                                         │
│  ─────────────────────────────────────────────              │
│  • 用途：统计元素出现频率                                    │
│  • 特点：自动计数、支持数学运算、Top K 查询                  │
│  • 生活类比：计票员（自动统计票数）                          │
│                                                             │
│  2. defaultdict：带默认值的字典                              │
│  ─────────────────────────────────────────────              │
│  • 用途：避免 KeyError，自动初始化值                         │
│  • 特点：指定工厂函数，缺失键自动创建默认值                  │
│  • 生活类比：自动售货机（按键必出商品）                      │
│                                                             │
│  3. namedtuple：命名元组                                     │
│  ─────────────────────────────────────────────              │
│  • 用途：创建带字段名的不可变数据结构                        │
│  • 特点：内存占用小、可读性强、支持索引访问                  │
│  • 生活类比：带标签的快递包裹（姓名、地址、电话）            │
│                                                             │
│  4. deque：双向队列                                          │
│  ─────────────────────────────────────────────              │
│  • 用途：高效的两端操作队列                                  │
│  • 特点：两端添加/删除均为 O(1)，支持 maxlen 限制            │
│  • 生活类比：传送带（两端都可以放取物品）                    │
│                                                             │
│  5. ChainMap：链式映射                                       │
│  ─────────────────────────────────────────────              │
│  • 用途：合并多个字典，优先级查找                            │
│  • 特点：不复制数据，动态合并，写入影响第一个映射            │
│  • 生活类比：法律优先级（地方法 > 州法律 > 联邦法律）        │
│                                                             │
│  6. 组件对比                                                 │
│  ─────────────────────────────────────────────              │
│  组件          基础类型替代    核心优势                      │
│  Counter       dict           自动计数 + 数学运算            │
│  defaultdict   dict           自动初始化缺失键               │
│  namedtuple    tuple          字段名访问 + 可读性            │
│  deque         list           两端 O(1) 操作                │
│  ChainMap      dict合并       不复制的动态合并               │
│                                                             │
└─────────────────────────────────────────────────────────────┘

L1 理解层：会用

Counter：计数器

语法结构

┌─────────────────────────────────────────────────────────────┐
│  Counter 核心语法                                            │
│                                                             │
│  创建计数器：                                                │
│  Counter(iterable)          # 从可迭代对象创建              │
│  Counter(a=3, b=2)          # 从关键字参数创建              │
│  Counter({'a': 3, 'b': 2})  # 从字典创建                    │
│                                                             │
│  常用方法：                                                  │
│  c.most_common(n)           # 返回前 n 个最常见的元素       │
│  c.elements()               # 返回所有元素的迭代器          │
│  c.update(iterable)         # 增加计数                      │
│  c.subtract(iterable)       # 减少计数                      │
│                                                             │
│  数学运算：                                                  │
│  c1 + c2                    # 合并计数（相加）              │
│  c1 - c2                    # 计数相减（只保留正数）          │
│  c1 & c2                    # 交集（取最小计数）            │
│  c1 | c2                    # 并集（取最大计数）            │
│                                                             │
└─────────────────────────────────────────────────────────────┘

最简示例

python

from collections import Counter

words = ["apple", "banana", "apple", "orange", "banana", "apple"]
c = Counter(words)

print(c)  # Counter({'apple': 3, 'banana': 2, 'orange': 1})

详细示例

python

from collections import Counter

# 创建方式
c1 = Counter("abracadabra")        # 从字符串
c2 = Counter([1, 2, 2, 3, 3, 3])   # 从列表
c3 = Counter(a=3, b=2, c=1)        # 从关键字参数

# 获取最常见元素
print(c3.most_common(2))  # [('a', 3), ('b', 2)]

# 访问计数
print(c3['a'])   # 3（存在）
print(c3['z'])   # 0（不存在不报错）

# 数学运算
c_a = Counter(a=3, b=1)
c_b = Counter(a=1, b=2)

print(c_a + c_b)  # Counter({'a': 4, 'b': 3}) - 相加
print(c_a - c_b)  # Counter({'a': 2})          - 相减（只保留正数）
print(c_a & c_b)  # Counter({'a': 1, 'b': 1})  - 交集（最小值）
print(c_a | c_b)  # Counter({'a': 3, 'b': 2})  - 并集（最大值）

关键代码说明

代码片段	含义	为什么这样写
`Counter(words)`	从列表创建计数器	自动统计每个元素出现次数
`c.most_common(2)`	获取前 2 个最常见元素	快速实现 Top K 查询
`c['z']`	访问不存在的键	Counter 返回 0 而非 KeyError
`c1 + c2`	合并两个计数器	比手动遍历合并更简洁

defaultdict：带默认值的字典

语法结构

┌─────────────────────────────────────────────────────────────┐
│  defaultdict 核心语法                                        │
│                                                             │
│  创建：                                                      │
│  from collections import defaultdict                        │
│  dd = defaultdict(factory)        # factory 是可调用对象    │
│                                                             │
│  常用工厂函数：                                              │
│  defaultdict(list)          # 默认值 []                     │
│  defaultdict(dict)          # 默认值 {}                     │
│  defaultdict(int)           # 默认值 0                      │
│  defaultdict(set)           # 默认值 set()                  │
│  defaultdict(lambda: 'N/A') # 自定义默认值                   │
│                                                             │
│  行为：                                                      │
│  dd[key]                    # 存在则返回，不存在则创建默认值  │
│                                                             │
└─────────────────────────────────────────────────────────────┘

最简示例

python

from collections import defaultdict

dd = defaultdict(list)
dd['fruits'].append('apple')

print(dd)  # defaultdict(<class 'list'>, {'fruits': ['apple']})

详细示例

python

from collections import defaultdict

# 分组聚合
users = [("Alice", "HR"), ("Bob", "IT"), ("Alice", "IT")]
dept_map = defaultdict(list)

for name, dept in users:
    dept_map[name].append(dept)

print(dict(dept_map))  # {'Alice': ['HR', 'IT'], 'Bob': ['IT']}

# 计数器替代方案
counter = defaultdict(int)
for char in "hello":
    counter[char] += 1

print(dict(counter))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

# 嵌套字典
tree = defaultdict(dict)
tree['root']['child'] = 'value'

print(dict(tree))  # {'root': {'child': 'value'}}

# 自定义默认值
config = defaultdict(lambda: 'Unknown')
print(config['name'])  # 'Unknown'

关键代码说明

代码片段	含义	为什么这样写
`defaultdict(list)`	创建默认值为空列表的字典	自动初始化，无需 if 检查
`dd[key].append(x)`	直接追加，无需判断 key 存在	defaultdict 自动创建空列表
`defaultdict(int)`	创建默认值为 0 的字典	适合计数场景
`lambda: 'N/A'`	自定义默认值	灵活指定任意默认值

namedtuple：命名元组

语法结构

┌─────────────────────────────────────────────────────────────┐
│  namedtuple 核心语法                                         │
│                                                             │
│  创建类型：                                                  │
│  from collections import namedtuple                         │
│  Point = namedtuple('Point', ['x', 'y'])                    │
│  Point = namedtuple('Point', 'x y')          # 空格分隔      │
│  Point = namedtuple('Point', 'x, y')         # 逗号分隔      │
│                                                             │
│  创建实例：                                                  │
│  p = Point(1, 2)              # 位置参数                    │
│  p = Point(x=1, y=2)          # 关键字参数                  │
│                                                             │
│  访问字段：                                                  │
│  p.x                          # 属性访问                    │
│  p[0]                         # 索引访问                    │
│                                                             │
│  常用方法：                                                  │
│  p._asdict()                  # 转为字典                    │
│  p._replace(x=10)             # 创建新实例，替换字段        │
│  p._fields                    # 获取字段名元组              │
│                                                             │
└─────────────────────────────────────────────────────────────┘

最简示例

python

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)

print(p.x, p.y)  # 1 2
print(p[0], p[1])  # 1 2

详细示例

python

from collections import namedtuple

# 创建命名元组类型
Person = namedtuple('Person', ['name', 'age', 'city'])

# 创建实例
alice = Person('Alice', 30, 'Beijing')
bob = Person(name='Bob', age=25, city='Shanghai')

# 访问字段
print(alice.name)   # 'Alice'（属性访问）
print(alice[0])      # 'Alice'（索引访问）

# 解包
name, age, city = alice

# 常用方法
print(alice._asdict())  # {'name': 'Alice', 'age': 30, 'city': 'Beijing'}
print(alice._fields)    # ('name', 'age', 'city')

# 创建新实例（替换字段）
alice_new = alice._replace(age=31)
print(alice_new)  # Person(name='Alice', age=31, city='Beijing')

关键代码说明

代码片段	含义	为什么这样写
`namedtuple('Point', ['x', 'y'])`	定义命名元组类型	第一个参数是类型名，第二个是字段列表
`p.x`	属性访问	比索引更可读
`p[0]`	索引访问	兼容普通元组接口
`p._asdict()`	转为字典	便于序列化和打印
`p._replace(x=10)`	创建新实例	元组不可变，需创建新对象

deque：双向队列

语法结构

┌─────────────────────────────────────────────────────────────┐
│  deque 核心语法                                              │
│                                                             │
│  创建：                                                      │
│  from collections import deque                              │
│  d = deque()                 # 空队列                        │
│  d = deque([1, 2, 3])        # 从可迭代对象创建              │
│  d = deque(maxlen=5)         # 固定长度队列                  │
│                                                             │
│  两端操作：                                                  │
│  d.append(x)                 # 右端添加                     │
│  d.appendleft(x)             # 左端添加                     │
│  d.pop()                     # 右端弹出                     │
│  d.popleft()                 # 左端弹出                     │
│                                                             │
│  其他操作：                                                  │
│  d.rotate(n)                 # 旋转 n 步                   │
│  d.extend(iterable)          # 右端扩展                     │
│  d.extendleft(iterable)      # 左端扩展（注意顺序反转）     │
│                                                             │
└─────────────────────────────────────────────────────────────┘

最简示例

python

from collections import deque

d = deque([1, 2, 3])
d.appendleft(0)
d.append(4)

print(d)  # deque([0, 1, 2, 3, 4])
print(d.popleft())  # 0

详细示例

python

from collections import deque

# 基础操作
d = deque([1, 2, 3])
d.append(4)        # deque([1, 2, 3, 4])
d.appendleft(0)    # deque([0, 1, 2, 3, 4])
d.pop()            # 返回 4，deque([0, 1, 2, 3])
d.popleft()        # 返回 0，deque([1, 2, 3])

# 固定长度（ maxlen）
cache = deque(maxlen=3)
cache.append(1)
cache.append(2)
cache.append(3)
cache.append(4)    # 1 被挤出
print(cache)       # deque([2, 3, 4], maxlen=3)

# 旋转
d = deque([1, 2, 3, 4, 5])
d.rotate(2)        # 向右旋转 2 步
print(d)           # deque([4, 5, 1, 2, 3])
d.rotate(-2)       # 向左旋转 2 步
print(d)           # deque([1, 2, 3, 4, 5])

# 扩展
d = deque([1, 2])
d.extend([3, 4])        # deque([1, 2, 3, 4])
d.extendleft([0, -1])   # deque([-1, 0, 1, 2, 3, 4])，注意顺序

关键代码说明

代码片段	含义	为什么这样写
`deque([1, 2, 3])`	从列表创建双向队列	初始化队列
`d.appendleft(0)`	左端添加	O(1) 操作，比 list.insert(0) 高效
`d.popleft()`	左端弹出	O(1) 操作，比 list.pop(0) 高效
`deque(maxlen=5)`	固定长度队列	满时自动挤出最老元素
`d.rotate(2)`	旋转队列	实现循环移位

ChainMap：链式映射

语法结构

┌─────────────────────────────────────────────────────────────┐
│  ChainMap 核心语法                                           │
│                                                             │
│  创建：                                                      │
│  from collections import ChainMap                           │
│  cm = ChainMap(dict1, dict2, dict3)  # 多个字典，优先级递减  │
│                                                             │
│  查找：                                                      │
│  cm[key]                     # 按顺序查找第一个匹配          │
│  cm.get(key, default)        # 同 dict.get                  │
│                                                             │
│  写入：                                                      │
│  cm[key] = value             # 写入第一个字典                │
│  cm.new_child()              # 添加新字典到最前面            │
│  cm.parents                  # 返回去掉第一个字典的 ChainMap │
│                                                             │
│  其他：                                                      │
│  cm.maps                     # 返回所有字典列表              │
│                                                             │
└─────────────────────────────────────────────────────────────┘

最简示例

python

from collections import ChainMap

defaults = {'theme': 'light', 'font': 'Arial'}
user = {'theme': 'dark'}

config = ChainMap(user, defaults)
print(config['theme'])  # 'dark'（优先级：user > defaults）
print(config['font'])    # 'Arial'（user 没有，查 defaults）

详细示例

python

from collections import ChainMap

# 多层配置
defaults = {'debug': False, 'port': 8080, 'host': 'localhost'}
env_config = {'port': 3000}
user_config = {'debug': True}

# 优先级：user_config > env_config > defaults
config = ChainMap(user_config, env_config, defaults)

print(config['debug'])  # True（来自 user_config）
print(config['port'])   # 3000（来自 env_config）
print(config['host'])   # 'localhost'（来自 defaults）

# 写入影响第一个字典
config['new_key'] = 'value'
print(user_config)  # {'debug': True, 'new_key': 'value'}

# new_child 添加新层
new_config = config.new_child({'level': 'test'})
print(new_config['level'])  # 'test'

# parents 去掉第一层
print(config.parents)  # ChainMap(env_config, defaults)

关键代码说明

代码片段	含义	为什么这样写
`ChainMap(d1, d2, d3)`	链式合并字典	不复制，动态查找
`cm['key']`	按优先级查找	返回第一个匹配
`cm['key'] = value`	写入第一个字典	不影响其他字典
`cm.new_child(d)`	添加新字典到最前	创建新作用域
`cm.parents`	返回父级 ChainMap	回退到上层作用域

L2 实践层：用好

Counter 推荐做法

做法	原因	示例
用 Counter 统计频率	比手动计数更简洁高效	`Counter(text.split())`
用 most_common 取 Top K	内置排序，代码清晰	`c.most_common(10)`
用 & 取交集计数	快速找出共同元素的最小出现次数	`c1 & c2`
用 elements() 展开	获取所有元素的迭代器	`list(c.elements())`

Counter 反模式

python

# ❌ 错误做法：手动计数
words = ["apple", "banana", "apple"]
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1

# 问题：
# 1. 代码冗长，容易出错
# 2. 缺少 most_common 等便捷方法
# 3. 不支持数学运算

python

from collections import Counter

# ✅ 正确做法：使用 Counter
words = ["apple", "banana", "apple"]
counts = Counter(words)

# 简洁且功能丰富
top_2 = counts.most_common(2)

python

# ❌ 错误做法：用 Counter 存储需要频繁修改的数据
c = Counter()
c['x'] = -1  # 计数为负，但 Counter 设计用于非负计数

python

# ✅ 正确做法：Counter 适用于非负计数场景
c = Counter(items)
if c['x'] > 0:
    print(f"x 出现了 {c['x']} 次")

Counter 适用场景

场景	是否推荐 Counter	原因
词频统计	✅ 推荐	核心场景，一行代码搞定
Top K 问题	✅ 推荐	most_common 内置排序
投票计数	✅ 推荐	自动累加，支持合并
配置存储	❌ 不推荐	用普通 dict，Counter 返回 0 掩盖缺失
需要负数计数	❌ 不推荐	用普通 dict 手动管理

defaultdict 推荐做法

做法	原因	示例
分组聚合用 defaultdict(list)	避免手动初始化列表	`group_by[key].append(item)`
计数用 defaultdict(int)	自动从 0 开始计数	`counter[key] += 1`
图结构用 defaultdict(set)	自动处理新节点	`graph[node].add(neighbor)`
自定义默认值用 lambda	灵活指定任意值	`defaultdict(lambda: 'N/A')`

defaultdict 反模式

python

# ❌ 错误做法：手动初始化检查
groups = {}
for item in items:
    if item.category not in groups:
        groups[item.category] = []
    groups[item.category].append(item)

# 问题：
# 1. 代码冗长
# 2. 每次都要判断 key 是否存在
# 3. 容易遗漏初始化

python

from collections import defaultdict

# ✅ 正确做法：使用 defaultdict
groups = defaultdict(list)
for item in items:
    groups[item.category].append(item)

python

from collections import defaultdict

# ❌ 错误做法：对复杂对象使用不合适的工厂
dd = defaultdict(dict)
dd['a']['b'] = 1  # 每次访问 'a' 都创建新字典？
# 问题：理解混乱，可能不是预期行为

python

from collections import defaultdict

# ✅ 正确做法：理解工厂函数何时被调用
dd = defaultdict(dict)
# 只在 key 不存在时调用 dict() 创建默认值
dd['a']['b'] = 1
dd['a']['c'] = 2  # 第二次访问 'a'，字典已存在

defaultdict 适用场景

场景	是否推荐 defaultdict	原因
分组聚合	✅ 推荐	自动初始化列表
图结构存储	✅ 推荐	自动处理新节点
计数统计	✅ 推荐	自动从 0 开始
配置读取	❌ 不推荐	需要 KeyError 提示缺失配置
JSON 解析	❌ 不推荐	需要严格区分 null 和缺失

namedtuple 推荐做法

做法	原因	示例
替代只读数据类	更轻量，内存更小	`Point = namedtuple('Point', 'x y')`
用于函数返回多值	比元组更可读	`return Point(x, y)`
使用 _asdict 序列化	转为字典便于 JSON	`json.dumps(p._asdict())`
使用 _replace 更新字段	不可变对象的标准更新方式	`p._replace(x=10)`

namedtuple 反模式

python

# ❌ 错误做法：尝试修改 namedtuple 字段
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)
p.x = 10  # AttributeError: can't set attribute

# 问题：namedtuple 是不可变的

python

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)

# ✅ 正确做法：使用 _replace 创建新实例
p_new = p._replace(x=10)
print(p_new)  # Point(x=10, y=2)

python

from collections import namedtuple

# ❌ 错误做法：字段名与内置方法冲突
Person = namedtuple('Person', ['name', 'class'])  # class 是关键字

# 问题：字段名必须是合法标识符，不能是关键字

python

from collections import namedtuple

# ✅ 正确做法：使用 rename=True 自动重命名冲突字段
Person = namedtuple('Person', ['name', 'class'], rename=True)
print(Person._fields)  # ('name', '_1')  # 'class' 被重命名为 '_1'

namedtuple 适用场景

场景	是否推荐 namedtuple	原因
简单数据记录	✅ 推荐	轻量、可读、不可变
函数返回多值	✅ 推荐	比元组更清晰
数据库行映射	✅ 推荐	内存占用小
需要可变对象	❌ 不推荐	用 dataclass 或普通类
需要继承扩展	❌ 不推荐	用 dataclass 或普通类
Python 3.7+	❓ 考虑 dataclass	dataclass 功能更强大

deque 推荐做法

做法	原因	示例
频繁两端操作用 deque	两端操作都是 O(1)	`d.appendleft(x)`
固定长度缓存用 maxlen	自动挤出，无需手动管理	`deque(maxlen=100)`
队列用 append + popleft	标准队列操作（FIFO）	`d.append(x); d.popleft()`
栈用 append + pop	标准栈操作（LIFO）	`d.append(x); d.pop()`

deque 反模式

python

# ❌ 错误做法：用 list 实现队列
queue = []
queue.insert(0, item)  # O(n) 操作！
queue.pop()             # O(1)

# 问题：insert(0) 需要移动所有元素，效率低下

python

from collections import deque

# ✅ 正确做法：用 deque 实现队列
queue = deque()
queue.appendleft(item)   # O(1) 操作
queue.pop()              # O(1) 操作
# 或者标准 FIFO
queue.append(item)       # O(1)
queue.popleft()          # O(1)

python

from collections import deque

# ❌ 错误做法：在 deque 中间操作
d = deque([1, 2, 3, 4, 5])
d[2] = 10  # 可以，但性能差

# 问题：deque 随机访问是 O(n)，list 是 O(1)

python

# ✅ 正确做法：中间操作用 list
lst = [1, 2, 3, 4, 5]
lst[2] = 10  # O(1)

deque 适用场景

场景	是否推荐 deque	原因
队列（FIFO）	✅ 推荐	两端 O(1) 操作
栈（LIFO）	✅ 推荐	但 list 也可以
滑动窗口	✅ 推荐	maxlen 自动管理
最近使用缓存	✅ 推荐	maxlen 实现简单
随机访问频繁	❌ 不推荐	用 list，O(1) vs O(n)
中间插入频繁	❌ 不推荐	用 list

ChainMap 推荐做法

做法	原因	示例
配置合并用 ChainMap	不复制，动态更新	`ChainMap(user, defaults)`
作用域查找用 ChainMap	模拟嵌套作用域	`ChainMap(local, global)`
用 new_child 创建新作用域	简洁直观	`cm.new_child()`
优先级高的放前面	从前向后查找	`ChainMap(high, medium, low)`

ChainMap 反模式

python

# ❌ 错误做法：多次 update 合并配置
defaults = {'theme': 'light', 'font': 'Arial'}
env = {'theme': 'dark'}
user = {'font': 'Times'}

config = {}
config.update(defaults)
config.update(env)
config.update(user)

# 问题：
# 1. 创建了新字典，内存浪费
# 2. 更新后原配置变化不会反映
# 3. 不知道值来自哪一层

python

from collections import ChainMap

# ✅ 正确做法：使用 ChainMap
defaults = {'theme': 'light', 'font': 'Arial'}
env = {'theme': 'dark'}
user = {'font': 'Times'}

config = ChainMap(user, env, defaults)

# 优点：
# 1. 不复制数据
# 2. 原配置变化自动反映
# 3. 可追踪值来源
print(config['theme'])  # 'dark'（来自 env）

python

from collections import ChainMap

# ❌ 错误做法：删除中间层元素
cm = ChainMap({'a': 1}, {'b': 2})
del cm['b']  # KeyError（只能删除第一层）

# 问题：删除操作只作用于第一个字典

python

from collections import ChainMap

# ✅ 正确做法：理解写入和删除的作用范围
cm = ChainMap({'a': 1}, {'b': 2})

# 删除只能删除第一层
if 'a' in cm.maps[0]:
    del cm['a']

# 或者直接操作原字典
del cm.maps[1]['b']

ChainMap 适用场景

场景	是否推荐 ChainMap	原因
多层配置合并	✅ 推荐	不复制，动态更新
作用域模拟	✅ 推荐	模拟嵌套命名空间
只读配置合并	✅ 推荐	性能优于 update
频繁写入合并	❌ 不推荐	写入只影响第一层
需要独立副本	❌ 不推荐	用 `{d1, d2}`

L3 专家层：深入

Counter 原理

Counter 内部实现

┌─────────────────────────────────────────────────────────────┐
│          Counter 内部实现                                    │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 继承关系                                                 │
│  ─────────────────────────────────────────────              │
│  Counter 是 dict 的子类                                      │
│  • 拥有 dict 所有方法                                        │
│  • 额外添加计数相关方法                                      │
│                                                             │
│  2. 计数存储                                                 │
│  ─────────────────────────────────────────────              │
│  • 键：元素                                                  │
│  • 值：计数（可以为负数或零）                                │
│  • __missing__ 返回 0 而非 KeyError                         │
│                                                             │
│  3. most_common 实现                                        │
│  ─────────────────────────────────────────────              │
│  • 使用 heapq.nlargest                                      │
│  • 时间复杂度：O(n log k)                                    │
│                                                             │
│  4. 数学运算                                                 │
│  ─────────────────────────────────────────────              │
│  + : 计数相加                                               │
│  - : 计数相减，负数和零被删除                                │
│  & : 取最小值（交集）                                        │
│  | : 取最大值（并集）                                        │
│                                                             │
└─────────────────────────────────────────────────────────────┘

python

from collections import Counter

# 验证 Counter 是 dict 子类
print(issubclass(Counter, dict))  # True

# __missing__ 行为
c = Counter(['a', 'b'])
print(c['x'])  # 0（普通 dict 会抛出 KeyError）

# elements() 返回迭代器
c = Counter(a=2, b=1)
print(list(c.elements()))  # ['a', 'a', 'b']

Counter 性能考量

操作	时间复杂度	说明
创建 Counter	O(n)	遍历一次可迭代对象
访问计数 `c[key]`	O(1)	哈希表查找
most_common(k)	O(n log k)	使用堆排序
elements()	O(n)	生成所有元素
数学运算 +	O(n)	合并两个字典

内存影响：

Counter 比普通 dict 略大（额外方法）
存储整数计数，内存占用与元素数量成正比

Counter 设计动机

设计选择	原因
继承 dict	复用字典功能，兼容性好
missing 返回 0	计数场景天然需求
支持数学运算	集合运算在计数场景常见
most_common 使用堆	比 sorted 更高效

Counter 知识关联

Counter 知识关联：
┌───────────────┐     ┌───────────────┐
│    dict       │────→│   Counter     │
│   基础字典    │     │   计数字典    │
└───────────────┘     └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   heapq        │
                      │   堆排序       │
                      └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   defaultdict │
                      │   带默认值字典 │
                      └───────────────┘

defaultdict 原理

defaultdict 内部实现

┌─────────────────────────────────────────────────────────────┐
│          defaultdict 内部实现                                │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 继承关系                                                 │
│  ─────────────────────────────────────────────              │
│  defaultdict 是 dict 的子类                                  │
│  • 拥有 dict 所有方法                                        │
│  • 重写 __missing__ 方法                                    │
│                                                             │
│  2. __missing__ 机制                                        │
│  ─────────────────────────────────────────────              │
│  当 key 不存在时：                                          │
│  • dict 抛出 KeyError                                       │
│  • defaultdict 调用 factory() 创建默认值                     │
│  • 创建的值自动存入字典                                      │
│                                                             │
│  3. 工厂函数                                                 │
│  ─────────────────────────────────────────────              │
│  • list, dict, set, int 等类型都是可调用对象                │
│  • 调用时返回该类型的"空"实例                                │
│  • lambda 可以返回任意值                                    │
│                                                             │
│  4. 与 dict.get() 的区别                                    │
│  ─────────────────────────────────────────────              │
│  d.get(key, default)：返回默认值，但不存储                  │
│  dd[key]：返回默认值，并存储到字典中                         │
│                                                             │
└─────────────────────────────────────────────────────────────┘

python

from collections import defaultdict

# 验证 __missing__ 行为
dd = defaultdict(list)
print('x' in dd)  # False
print(dd['x'])    # []（自动创建）
print('x' in dd)  # True（已存储）

# 与 dict.get 的区别
d = {}
print(d.get('x', []))  # []（返回但不存储）
print('x' in d)         # False

# 验证 defaultdict 存储行为
dd = defaultdict(list)
value = dd['new_key']
print(dd)  # defaultdict(<class 'list'>, {'new_key': []})

defaultdict 性能考量

操作	时间复杂度	说明
创建 defaultdict	O(1)	仅存储工厂函数
访问存在的键	O(1)	同普通字典
访问不存在的键	O(1)	调用工厂函数 + 存储
工厂函数调用	取决于工厂	list()、dict() 都是 O(1)

内存影响：

比 dict 多存储一个工厂函数引用
创建的默认值会占用内存

defaultdict 设计动机

设计选择	原因
重写 missing	自动处理缺失键
存储工厂函数	延迟创建默认值
继承 dict	兼容现有代码

defaultdict 知识关联

defaultdict 知识关联：
┌───────────────┐     ┌───────────────┐
│    dict       │────→│  defaultdict  │
│   __missing__ │     │   自动初始化  │
└───────────────┘     └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   Counter      │
                      │   计数字典     │
                      └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   setdefault   │
                      │   字典方法     │
                      └───────────────┘

namedtuple 原理

namedtuple 内部实现

┌─────────────────────────────────────────────────────────────┐
│          namedtuple 内部实现                                 │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 动态创建类                                               │
│  ─────────────────────────────────────────────              │
│  namedtuple() 返回一个新类（不是实例）                       │
│  • 类继承自 tuple                                            │
│  • 动态添加属性访问器                                         │
│  • 使用 __slots__ 节省内存                                   │
│                                                             │
│  2. 内存优势                                                 │
│  ─────────────────────────────────────────────              │
│  • 与普通 tuple 相同大小                                     │
│  • 比普通类对象小很多                                         │
│  • 没有 __dict__ 字典开销                                    │
│                                                             │
│  3. 不可变性                                                 │
│  ─────────────────────────────────────────────              │
│  • 继承 tuple 的不可变性                                    │
│  • _replace 创建新实例而非修改                               │
│                                                             │
│  4. 方法来源                                                 │
│  ─────────────────────────────────────────────              │
│  • _fields: 类属性，存储字段名                               │
│  • _asdict: 实例方法，返回 OrderedDict                       │
│  • _replace: 实例方法，创建新实例                            │
│  • _make: 类方法，从可迭代对象创建实例                        │
│                                                             │
└─────────────────────────────────────────────────────────────┘

python

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])

# 验证继承关系
print(issubclass(Point, tuple))  # True

# 验证内存占用
import sys
p = Point(1, 2)
t = (1, 2)
print(sys.getsizeof(p))  # 与 tuple 相同

# 验证不可变性
p.x = 10  # AttributeError

# _make 从可迭代对象创建
data = [3, 4]
p = Point._make(data)
print(p)  # Point(x=3, y=4)

namedtuple 性能考量

操作	时间复杂度	说明
创建 namedtuple 类型	O(n)	n 是字段数，一次性开销
创建实例	O(n)	与普通 tuple 相同
属性访问	O(1)	直接属性查找
索引访问	O(1)	继承自 tuple

内存影响：

与普通 tuple 相同
比普通类小 5-10 倍
无 dict 开销

namedtuple 设计动机

设计选择	原因
继承 tuple	复用 tuple 的不可变性和内存效率
动态创建类	字段名在运行时确定
使用 slots	节省内存
提供 _asdict/_replace	支持常见操作模式

namedtuple vs dataclass

python

from collections import namedtuple
from dataclasses import dataclass

# namedtuple
Point = namedtuple('Point', ['x', 'y'])
p1 = Point(1, 2)

# dataclass (Python 3.7+)
@dataclass
class PointClass:
    x: int
    y: int

p2 = PointClass(1, 2)

# 对比
# namedtuple: 不可变、内存小、无默认值
# dataclass: 可变（默认）、类型注解、默认值支持

namedtuple 知识关联

namedtuple 知识关联：
┌───────────────┐     ┌───────────────┐
│    tuple      │────→│  namedtuple   │
│   不可变序列  │     │   命名元组    │
└───────────────┘     └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │  __slots__    │
                      │   内存优化    │
                      └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │  dataclass    │
                      │   数据类      │
                      └───────────────┘

deque 原理

deque 内部实现

┌─────────────────────────────────────────────────────────────┐
│          deque 内部实现                                      │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 数据结构                                                 │
│  ─────────────────────────────────────────────              │
│  deque 是双向链表（C 实现）                                   │
│  • 内存不连续，但缓存友好                                    │
│  • 每个节点存储多个元素（块）                                │
│                                                             │
│  2. 与 list 的区别                                           │
│  ─────────────────────────────────────────────              │
│  list:                                                      │
│  • 基于动态数组                                              │
│  • 随机访问 O(1)                                            │
│  • 头部操作 O(n)（需要移动所有元素）                         │
│                                                             │
│  deque:                                                     │
│  • 基于双向链表                                              │
│  • 随机访问 O(n)                                            │
│  • 两端操作 O(1)                                            │
│                                                             │
│  3. maxlen 行为                                             │
│  ─────────────────────────────────────────────              │
│  • 队列满时，新元素挤掉最老的元素                            │
│  • append 时挤掉 popleft                                    │
│  • appendleft 时挤掉 pop                                    │
│                                                             │
│  4. 线程安全                                                │
│  ─────────────────────────────────────────────              │
│  • append/appendleft/pop/popleft 是原子操作                 │
│  • 多线程安全使用两端操作                                    │
│                                                             │
└─────────────────────────────────────────────────────────────┘

python

from collections import deque

# 验证两端操作性能
import timeit

# list 头部操作
list_time = timeit.timeit('lst.insert(0, 1)', 
                          setup='lst = []', 
                          number=10000)

# deque 头部操作
deque_time = timeit.timeit('d.appendleft(1)', 
                           setup='from collections import deque; d = deque()', 
                           number=10000)

print(f"list insert(0): {list_time:.4f}s")
print(f"deque appendleft: {deque_time:.4f}s")
# deque 快得多

deque 性能考量

操作	list	deque	说明
`append()` 右端添加	O(1)	O(1)	相同
`pop()` 右端弹出	O(1)	O(1)	相同
`insert(0)` 左端添加	O(n)	O(1)	deque 快
`pop(0)` 左端弹出	O(n)	O(1)	deque 快
`d[i]` 随机访问	O(1)	O(n)	list 快

内存影响：

deque 内存略大于 list（链表开销）
但两端操作无内存重新分配

deque 设计动机

设计选择	原因
双向链表	两端 O(1) 操作
块式存储	缓存友好
maxlen	简化 LRU 缓存实现
线程安全操作	多线程队列场景

deque 知识关联

deque 知识关联：
┌───────────────┐     ┌───────────────┐
│    list       │────→│    deque      │
│   动态数组    │     │   双向链表    │
└───────────────┘     └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   queue.Queue  │
                      │   线程安全队列 │
                      └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │   heapq        │
                      │   优先队列     │
                      └───────────────┘

ChainMap 原理

ChainMap 内部实现

┌─────────────────────────────────────────────────────────────┐
│          ChainMap 内部实现                                    │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  1. 数据结构                                                 │
│  ─────────────────────────────────────────────              │
│  ChainMap 存储字典列表（maps 属性）                          │
│  • 不复制原字典                                              │
│  • 查找时按顺序遍历                                          │
│  • 写入时修改第一个字典                                      │
│                                                             │
│  2. 查找机制                                                 │
│  ─────────────────────────────────────────────              │
│  cm['key'] 的查找过程：                                      │
│  1. 查找 cm.maps[0]['key']                                  │
│  2. 不存在则查找 cm.maps[1]['key']                          │
│  3. 以此类推，直到找到或全部查完                             │
│                                                             │
│  3. 写入机制                                                 │
│  ─────────────────────────────────────────────              │
│  cm['key'] = value：                                        │
│  • 只写入 cm.maps[0]（第一个字典）                          │
│  • 不影响其他字典                                            │
│                                                             │
│  4. new_child 原理                                          │
│  ─────────────────────────────────────────────              │
│  new_child(d) 创建新 ChainMap：                              │
│  • d 放在最前面                                              │
│  • 原 ChainMap 作为 parents                                 │
│                                                             │
│  5. 与 {**d1, **d2} 的区别                                  │
│  ─────────────────────────────────────────────              │
│  ChainMap：                                                 │
│  • 不复制数据                                                │
│  • 原字典变化自动反映                                        │
│  • 查找慢（遍历）                                            │
│                                                             │
│  {**d1, **d2}：                                             │
│  • 创建新字典                                                │
│  • 原字典变化不反映                                          │
│  • 查找快（O(1)）                                            │
│                                                             │
└─────────────────────────────────────────────────────────────┘

python

from collections import ChainMap

d1 = {'a': 1}
d2 = {'b': 2}
cm = ChainMap(d1, d2)

# 查看内部结构
print(cm.maps)  # [{'a': 1}, {'b': 2}]

# 修改原字典
d1['a'] = 100
print(cm['a'])  # 100（变化自动反映）

# 写入只影响第一个字典
cm['c'] = 3
print(d1)  # {'a': 100, 'c': 3}
print(d2)  # {'b': 2}

# new_child 示例
new_cm = cm.new_child({'d': 4})
print(new_cm.maps)  # [{'d': 4}, {'a': 100, 'c': 3}, {'b': 2}]
print(new_cm.parents.maps)  # [{'a': 100, 'c': 3}, {'b': 2}]

ChainMap 性能考量

操作	时间复杂度	说明
创建 ChainMap	O(1)	只存储引用
查找 `cm[key]`	O(n)	n 是字典数量
写入 `cm[key] = v`	O(1)	写入第一个字典
删除 `del cm[key]`	O(1)	只能删第一个字典
new_child	O(1)	创建新 ChainMap

与字典合并对比：

python

import timeit

# ChainMap
setup_cm = '''
from collections import ChainMap
d1 = {i: i for i in range(1000)}
d2 = {i: i for i in range(1000, 2000)}
'''
time_cm = timeit.timeit('ChainMap(d1, d2)', setup=setup_cm, number=10000)

# 字典合并
setup_merge = '''
d1 = {i: i for i in range(1000)}
d2 = {i: i for i in range(1000, 2000)}
'''
time_merge = timeit.timeit('{**d1, **d2}', setup=setup_merge, number=10000)

print(f"ChainMap 创建: {time_cm:.4f}s")
print(f"字典合并创建: {time_merge:.4f}s")
# ChainMap 创建快得多（不复制数据）

ChainMap 设计动机

设计选择	原因
存储字典列表	不复制，动态反映变化
查找按顺序	模拟作用域优先级
写入第一层	模拟局部变量覆盖
new_child	简化作用域创建

ChainMap 知识关联

ChainMap 知识关联：
┌───────────────┐     ┌───────────────┐
│    dict       │────→│   ChainMap    │
│   字典合并    │     │   链式映射    │
└───────────────┘     └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │  作用域链     │
                      │  变量查找     │
                      └───────────────┘
                             │
                             ↓
                      ┌───────────────┐
                      │  配置优先级   │
                      │  层叠配置     │
                      └───────────────┘

本章小结

┌─────────────────────────────────────────────────────────────┐
│                 collections 核心功能回顾                     │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  组件          核心场景              替代原生方式            │
│  ────────────  ──────────────────    ──────────────────     │
│  Counter       词频统计、Top K        dict 手动计数          │
│  defaultdict   分组聚合、避免错误    if key not in dict      │
│  namedtuple    简单数据模型          tuple 或普通类          │
│  deque         队列、滑动窗口        list 头部操作           │
│  ChainMap      多层配置合并          多次 dict.update()      │
│                                                             │
│  选择指南：                                                  │
│  ─────────────────────────────────────────────              │
│  需要统计频率？           → Counter                          │
│  需要 KeyError 安全？     → defaultdict                      │
│  需要不可变数据模型？     → namedtuple                        │
│  需要高效两端操作？       → deque                             │
│  需要合并多层配置？       → ChainMap                          │
│                                                             │
│  记忆口诀：                                                  │
│  ─────────────────────────────────────────────              │
│  计数用 Counter，默认值用 defaultdict                        │
│  命名用 namedtuple，两端用 deque                             │
│  合并用 ChainMap，性能优于手写代码                            │
│                                                             │
└─────────────────────────────────────────────────────────────┘

自检清单

回答以下问题，检查你是否掌握了核心概念：

Counter 如何实现 Top K 查询？

答案

使用 most_common(k) 方法，内部使用堆排序，时间复杂度 O(n log k)。

python

from collections import Counter
words = ["a", "b", "a", "c", "a", "b"]
c = Counter(words)
print(c.most_common(2))  # [('a', 3), ('b', 2)]

defaultdict 与 dict.get(key, default) 的区别？

答案

dict.get(key, default)：返回默认值但不存储
defaultdict[key]：返回默认值并存储到字典中

python

d = {}
print(d.get('x', []))  # []（不存储）
print('x' in d)         # False

from collections import defaultdict
dd = defaultdict(list)
print(dd['x'])          # []（已存储）
print('x' in dd)        # True

namedtuple 与 dataclass 如何选择？
答案
特性 namedtuple dataclass
可变性不可变默认可变
内存占用小较大
类型注解不支持支持
默认值不支持支持
Python 版本 2.4+ 3.7+
选择：需要不可变、轻量 → namedtuple；需要类型注解、默认值 → dataclass
deque 与 list 的性能差异在哪里？
答案
操作 list deque
append/pop 右端 O(1) O(1)
append/pop 左端 O(n) O(1)
随机访问 O(1) O(n)
频繁左端操作用 deque，频繁随机访问用 list。

特性	namedtuple	dataclass
可变性	不可变	默认可变
内存占用	小	较大
类型注解	不支持	支持
默认值	不支持	支持
Python 版本	2.4+	3.7+

操作	list	deque
append/pop 右端	O(1)	O(1)
append/pop 左端	O(n)	O(1)
随机访问	O(1)	O(n)

ChainMap 写入操作会影响哪些字典？

答案

写入只影响第一个字典（优先级最高的）。

python

from collections import ChainMap
d1 = {'a': 1}
d2 = {'b': 2}
cm = ChainMap(d1, d2)

cm['c'] = 3    # 写入 d1
print(d1)      # {'a': 1, 'c': 3}
print(d2)      # {'b': 2}（未受影响）

本章术语表

术语	定义	本章位置
Counter	计数器字典，自动统计元素频率	Counter 章节
defaultdict	带默认值字典，自动初始化缺失键	defaultdict 章节
namedtuple	命名元组，支持属性访问的不可变序列	namedtuple 章节
deque	双向队列，两端操作均为 O(1)	deque 章节
ChainMap	链式映射，按优先级查找多个字典	ChainMap 章节
factory	工厂函数，创建默认值的可调用对象	defaultdict 章节
maxlen	deque 最大长度，满时自动挤出	deque 章节
most_common	Counter 方法，返回前 K 个最常见元素	Counter 章节
_asdict	namedtuple 方法，转为字典	namedtuple 章节
new_child	ChainMap 方法，添加新字典到最前	ChainMap 章节

扩展阅读

Python 官方文档：collections 模块
《流畅的Python》第3章：字典和集合
PEP 3119：Introducing Abstract Base Classes
Python 源码：Modules/_collectionsmodule.c

01-数据容器进阶 ​

概念铺垫 ​

L1 理解层：会用 ​

Counter：计数器 ​

语法结构 ​

最简示例 ​

详细示例 ​

关键代码说明 ​

defaultdict：带默认值的字典 ​

语法结构 ​

最简示例 ​

详细示例 ​

关键代码说明 ​

namedtuple：命名元组 ​

语法结构 ​

最简示例 ​

详细示例 ​

关键代码说明 ​

deque：双向队列 ​

语法结构 ​

最简示例 ​

详细示例 ​

关键代码说明 ​

ChainMap：链式映射 ​

语法结构 ​

最简示例 ​

详细示例 ​

关键代码说明 ​

L2 实践层：用好 ​

Counter 推荐做法 ​

Counter 反模式 ​

Counter 适用场景 ​

defaultdict 推荐做法 ​

defaultdict 反模式 ​

defaultdict 适用场景 ​

namedtuple 推荐做法 ​

namedtuple 反模式 ​

namedtuple 适用场景 ​

deque 推荐做法 ​

deque 反模式 ​

deque 适用场景 ​

ChainMap 推荐做法 ​

ChainMap 反模式 ​

ChainMap 适用场景 ​

L3 专家层：深入 ​

Counter 原理 ​

Counter 内部实现 ​

Counter 性能考量 ​

Counter 设计动机 ​

Counter 知识关联 ​

defaultdict 原理 ​

defaultdict 内部实现 ​

defaultdict 性能考量 ​

defaultdict 设计动机 ​

defaultdict 知识关联 ​

namedtuple 原理 ​

namedtuple 内部实现 ​

namedtuple 性能考量 ​

namedtuple 设计动机 ​

namedtuple vs dataclass ​

namedtuple 知识关联 ​

deque 原理 ​

deque 内部实现 ​

deque 性能考量 ​

deque 设计动机 ​

deque 知识关联 ​

ChainMap 原理 ​

ChainMap 内部实现 ​

ChainMap 性能考量 ​

ChainMap 设计动机 ​

ChainMap 知识关联 ​

本章小结 ​

自检清单 ​

本章术语表 ​

扩展阅读 ​

01-数据容器进阶

概念铺垫

L1 理解层：会用

Counter：计数器

语法结构

最简示例

详细示例

关键代码说明

defaultdict：带默认值的字典

语法结构

最简示例

详细示例

关键代码说明

namedtuple：命名元组

语法结构

最简示例

详细示例

关键代码说明

deque：双向队列

语法结构

最简示例

详细示例

关键代码说明

ChainMap：链式映射

语法结构

最简示例

详细示例

关键代码说明

L2 实践层：用好

Counter 推荐做法

Counter 反模式

Counter 适用场景

defaultdict 推荐做法

defaultdict 反模式

defaultdict 适用场景

namedtuple 推荐做法

namedtuple 反模式

namedtuple 适用场景

deque 推荐做法

deque 反模式

deque 适用场景

ChainMap 推荐做法

ChainMap 反模式

ChainMap 适用场景

L3 专家层：深入

Counter 原理

Counter 内部实现

Counter 性能考量

Counter 设计动机

Counter 知识关联

defaultdict 原理

defaultdict 内部实现

defaultdict 性能考量

defaultdict 设计动机

defaultdict 知识关联

namedtuple 原理

namedtuple 内部实现

namedtuple 性能考量

namedtuple 设计动机

namedtuple vs dataclass

namedtuple 知识关联

deque 原理

deque 内部实现

deque 性能考量

deque 设计动机

deque 知识关联

ChainMap 原理

ChainMap 内部实现

ChainMap 性能考量

ChainMap 设计动机

ChainMap 知识关联

本章小结

自检清单

本章术语表

扩展阅读