第11章 集合与映射
11.1 引言
在日常数据处理中，我们经常需要两种基础操作：存储不重复的元素（如班级学生名单，避免重复）和建立键与值的关联（如字典中“单词-释义”的对应关系）。这两种需求催生了两种重要的抽象数据类型——集合（Set） 和映射（Map）。
集合：存储一组互不相同的元素，支持添加、删除元素和判断元素是否存在等操作；
映射：存储一组键值对（Key-Value Pair），键唯一，支持根据键快速查找、添加、删除值的操作。
集合与映射本身不依赖特定的底层实现，但结合前一章学习的哈希表，可以实现高效的集合与映射（平均时间复杂度O(1)）。本章将从实际需求出发，先定义集合与映射的抽象接口，再基于哈希表实现哈希集合（HashSet）和哈希映射（HashMap），通过Python代码展示核心操作原理，并结合去重、索引构建等工程案例，说明集合与映射在实际问题中的应用价值。
11.2 集合（Set）
11.2.1 集合的定义与基本操作
定义11.1 集合（Set）：一种不包含重复元素的无序数据结构，支持以下核心操作：
添加元素（add）：将元素加入集合，若元素已存在则不操作；
删除元素（remove）：从集合中删除指定元素，若元素不存在则抛出异常（或返回False）；
判断存在（contains）：判断元素是否在集合中，返回布尔值；
集合大小（size）：返回集合中元素的个数；
清空集合（clear）：删除集合中所有元素。
示例：班级学生集合{"Alice", "Bob", "Charlie"}，添加“Bob”时集合不变，判断“Alice”是否存在返回True，删除“Charlie”后集合变为{"Alice", "Bob"}。
11.2.2 集合的实现方式
集合的实现依赖底层数据结构，常见方式有两种：

1. 基于数组的实现
   原理：用数组存储元素，添加时遍历数组检查是否重复（O(n)），删除时遍历找到元素后移动后续元素（O(n)）。
   缺点：添加和删除效率低，不适合大数据量场景。
2. 基于哈希表的实现（哈希集合，HashSet）
   原理：利用哈希表的键唯一特性，将集合元素作为哈希表的键，值存储为占位符（如None）。
   优点：添加、删除、判断存在的平均时间复杂度均为O(1)，是实际应用的首选（如Python的set、Java的HashSet）。
   11.2.3 哈希集合的Python实现
   基于第10章的哈希表实现，哈希集合可简化为“只存键、不存值”的哈希表。以下是核心代码：
   python

	class HashSet: 
	def __init__(self): 
	"""初始化哈希集合（基于哈希表，键为集合元素，值为占位符）""" 
	self.hash_table = [[] for _ in range(16)] # 底层数组+链表 
	self.size = 0 # 元素个数 
	self.load_factor = 0.7 # 装填因子阈值 
	
	def _hash(self, key): 
	"""哈希函数：计算元素的哈希地址""" 
	return hash(key) % len(self.hash_table) 
	
	def add(self, key): 
	"""添加元素到集合（若已存在则不操作）""" 
	index = self._hash(key) 
	# 检查元素是否已存在 
	for k in self.hash_table[index]: 
	if k == key: 
	return # 元素已存在，直接返回 
	# 添加元素到链表头部 
	self.hash_table[index].append(key) 
	self.size += 1 
	# 扩容：若装填因子超过阈值，数组容量翻倍 
	if self.size / len(self.hash_table) > self.load_factor: 
	self._resize(len(self.hash_table) * 2) 
	
	def remove(self, key): 
	"""删除集合中的元素（若不存在则返回False）""" 
	index = self._hash(key) 
	# 遍历链表查找元素 
	for i, k in enumerate(self.hash_table[index]): 
	if k == key: 
	del self.hash_table[index][i] 
	self.size -= 1 
	# 缩容：若装填因子小于0.2且容量>16，数组容量减半 
	if self.size > 0 and self.size / len(self.hash_table) < 0.2 and len(self.hash_table) > 16: 
	self._resize(len(self.hash_table) // 2) 
	return True 
	return False 
	
	def contains(self, key): 
	"""判断元素是否在集合中""" 
	index = self._hash(key) 
	for k in self.hash_table[index]: 
	if k == key: 
	return True 
	return False 
	
	def _resize(self, new_capacity): 
	"""扩容/缩容：重新哈希所有元素""" 
	old_table = self.hash_table 
	self.hash_table = [[] for _ in range(new_capacity)] 
	self.size = 0 
	# 重新插入所有元素 
	for bucket in old_table: 
	for key in bucket: 
	self.add(key) 
	
	def __len__(self): 
	"""返回集合大小""" 
	return self.size 
	
	def __str__(self): 
	"""打印集合元素""" 
	elements = [] 
	for bucket in self.hash_table: 
	elements.extend(bucket) 
	return f"Set({elements})"

使用示例：
python

	s = HashSet() 
	s.add("Alice") 
	s.add("Bob") 
	s.add("Alice") # 重复添加，无效果 
	print(s) # 输出：Set(['Alice', 'Bob']) 
	print(s.contains("Bob")) # 输出：True 
	s.remove("Bob") 
	print(s.contains("Bob")) # 输出：False

11.2.4 集合的运算
集合支持三种基本数学运算：
并集（Union）：两个集合中所有元素组成的新集合（去重）；
交集（Intersection）：两个集合中共同元素组成的新集合；
差集（Difference）：属于第一个集合但不属于第二个集合的元素组成的新集合。
基于哈希集合的实现：
python

	def set_union(s1, s2): 
	"""计算集合s1和s2的并集""" 
	result = HashSet() 
	# 添加s1所有元素 
	for bucket in s1.hash_table: 
	for key in bucket: 
	result.add(key) 
	# 添加s2所有元素 
	for bucket in s2.hash_table: 
	for key in bucket: 
	result.add(key) 
	return result 
	
	def set_intersection(s1, s2): 
	"""计算集合s1和s2的交集""" 
	result = HashSet() 
	for bucket in s1.hash_table: 
	for key in bucket: 
	if s2.contains(key): 
	result.add(key) 
	return result

11.2.5 集合的应用场景
数据去重：如统计网站独立访客（UV），使用集合存储用户ID，自动去重；
元素存在性判断：如判断某个单词是否在词典中，集合的contains操作高效；
数学运算：如计算两个班级的共同学生（交集）、所有学生（并集）等。
11.3 映射（Map）
11.3.1 映射的定义与基本操作
定义11.2 映射（Map）：一种存储键值对（Key-Value Pair）的无序数据结构，键（Key）唯一，每个键对应一个值（Value）。核心操作包括：
添加/更新键值对（put）：若键存在则更新值，否则添加新键值对；
获取值（get）：根据键获取对应值，若键不存在返回默认值（如None）；
删除键值对（remove）：根据键删除对应的键值对；
判断键存在（contains_key）：判断键是否在映射中；
遍历操作：遍历所有键、所有值或所有键值对。
示例：学生成绩映射{"Alice": 90, "Bob": 85, "Charlie": 95}，获取“Bob”的值为85，更新“Alice”的值为92，删除“Charlie”后映射变为{"Alice": 92, "Bob": 85}。
11.3.2 映射的实现方式
与集合类似，映射的实现也依赖底层数据结构：

1. 基于哈希表的实现（哈希映射，HashMap）
   原理：将键值对存储在哈希表中，键作为哈希函数的输入，值随键存储在链表中。
   优点：添加、删除、查找的平均时间复杂度O(1)，是实际应用的主流选择（如Python的dict、Java的HashMap）。
2. 基于树结构的实现（有序映射，TreeMap）
   原理：基于红黑树或平衡二叉搜索树，键按顺序存储，支持按键排序遍历。
   优点：有序性，适合需要按键范围查询的场景（如“查找所有键大于100的键值对”）；
   缺点：操作时间复杂度O(log n)，略低于哈希映射。
   11.3.3 哈希映射的Python实现
   哈希映射的实现与哈希集合类似，区别在于链表中存储的是键值对（(key, value)）而非单个键。以下是核心代码：
   python

	class HashMap: 
	def __init__(self): 
	"""初始化哈希映射（底层数组+链表存储键值对）""" 
	self.hash_table = [[] for _ in range(16)] # 桶数组 
	self.size = 0 
	self.load_factor = 0.7 
	
	def _hash(self, key): 
	"""哈希函数：计算键的哈希地址""" 
	return hash(key) % len(self.hash_table) 
	
	def put(self, key, value): 
	"""添加/更新键值对（键存在则更新值）""" 
	index = self._hash(key) 
	# 遍历链表，检查键是否存在 
	for i, (k, v) in enumerate(self.hash_table[index]): 
	if k == key: 
	self.hash_table[index][i] = (key, value) # 更新值 
	return 
	# 键不存在，添加新键值对 
	self.hash_table[index].append((key, value)) 
	self.size += 1 
	# 扩容 
	if self.size / len(self.hash_table) > self.load_factor: 
	self._resize(len(self.hash_table) * 2) 
	
	def get(self, key, default=None): 
	"""根据键获取值（键不存在返回default）""" 
	index = self._hash(key) 
	for k, v in self.hash_table[index]: 
	if k == key: 
	return v 
	return default 
	
	def remove(self, key): 
	"""删除键值对（键不存在返回False）""" 
	index = self._hash(key) 
	for i, (k, v) in enumerate(self.hash_table[index]): 
	if k == key: 
	del self.hash_table[index][i] 
	self.size -= 1 
	# 缩容 
	if self.size > 0 and self.size / len(self.hash_table) < 0.2 and len(self.hash_table) > 16: 
	self._resize(len(self.hash_table) // 2) 
	return True 
	return False 
	
	def contains_key(self, key): 
	"""判断键是否存在""" 
	index = self._hash(key) 
	for k, _ in self.hash_table[index]: 
	if k == key: 
	return True 
	return False 
	
	def keys(self): 
	"""返回所有键的列表""" 
	keys = [] 
	for bucket in self.hash_table: 
	for k, _ in bucket: 
	keys.append(k) 
	return keys 
	
	def values(self): 
	"""返回所有值的列表""" 
	values = [] 
	for bucket in self.hash_table: 
	for _, v in bucket: 
	values.append(v) 
	return values 
	
	def items(self): 
	"""返回所有键值对的列表""" 
	items = [] 
	for bucket in self.hash_table: 
	items.extend(bucket) 
	return items 
	
	def _resize(self, new_capacity): 
	"""扩容/缩容：重新哈希所有键值对""" 
	old_table = self.hash_table 
	self.hash_table = [[] for _ in range(new_capacity)] 
	self.size = 0 
	for bucket in old_table: 
	for key, value in bucket: 
	self.put(key, value) 
	
	def __str__(self): 
	"""打印映射的键值对""" 
	items = self.items() 
	return f"Map({', '.join([f'{k}: {v}' for k, v in items])})"

使用示例：
python

	score_map = HashMap() 
	score_map.put("Alice", 90) 
	score_map.put("Bob", 85) 
	score_map.put("Alice", 92) # 更新Alice的分数 
	print(score_map.get("Bob")) # 输出：85 
	print(score_map.keys()) # 输出：['Alice', 'Bob'] 
	print(score_map.items()) # 输出：[('Alice', 92), ('Bob', 85)] 
	score_map.remove("Bob") 
	print(score_map) # 输出：Map(Alice: 92)

11.3.4 映射的应用场景
缓存系统：如Web缓存中，用URL作为键，页面内容作为值，快速读取缓存数据；
索引存储：如数据库索引，用主键作为键，记录地址作为值，加速查询；
配置管理：如程序配置文件，用配置项名称作为键，配置值作为值，方便读取配置；
词频统计：如统计文本中单词出现的次数，用单词作为键，次数作为值。
11.4 集合与映射的对比

11.5 本章总结
集合和映射的核心价值：集合提供高效的元素去重与存在性判断，映射提供键值对的快速关联存储，两者均基于哈希表实现平均O(1)的操作效率，是编程中处理关联数据的基础工具。
实现关键：
o集合可视为“只存键不存值”的映射，底层依赖哈希表的冲突解决机制（链地址法等）；
o映射通过键的哈希地址定位键值对，需保证键的唯一性和哈希函数的均匀性。
实际应用：集合用于去重、交集/并集运算；映射用于缓存、索引、配置存储等场景，是数据库、缓存系统、搜索引擎的底层核心组件。
理解集合与映射的本质，关键在于掌握“键”的唯一性和哈希表的高效性，它们的设计思想体现了“用空间换时间”的权衡，也是解决实际问题中“关联”与“去重”需求的首选方案。
11.6 思考题
1.基于红黑树实现一个有序集合（TreeSet），支持按元素大小顺序遍历（提示：键按中序遍历有序）。
2.设计一个映射的迭代器，支持按插入顺序遍历键值对（提示：用链表记录插入顺序）。
3.用哈希集合实现两个字符串的交集（如“abc”和“acd”的交集为“ac”）。
4.用哈希映射实现一个简单的LRU缓存（最近最少使用缓存），支持get(key)和put(key, value)操作（提示：映射存储键值对，双向链表记录访问顺序）。
5.对比哈希映射和有序映射（TreeMap）的适用场景，分析在什么情况下选择有序映射更合适。
第11章 集合与映射
11.1 引言
在数据处理与算法设计中，我们经常面临两类基础需求：存储不重复元素与建立键值关联。例如：
统计网站独立访客时，需存储不重复的用户ID；
实现英汉词典时，需建立“单词-释义”的对应关系；
配置文件解析时，需通过配置项名称快速获取配置值。
为满足这类需求，抽象数据类型集合（Set） 与映射（Map） 应运而生。集合专注于“元素唯一性”管理，映射则专注于“键值对关联”存储。两者的底层实现可基于数组、链表或树结构，但结合第10章的哈希表，能将核心操作的平均时间复杂度优化至O(1)，成为工程实践中的首选方案。
本章将从集合与映射的抽象定义出发，详细讲解基于哈希表的实现原理，通过Python代码实现可复用的哈希集合与哈希映射，并结合去重、索引构建等实际案例，展示其在解决实际问题中的价值。
11.2 集合（Set）
11.2.1 集合的定义与核心操作
定义11.1 集合（Set）：由互不相同的元素组成的无序数据结构，其核心操作如下：

示例：对于集合{1, 2, 3}，执行add(2)后集合不变；执行remove(3)后集合变为{1, 2}；执行contains(4)返回False。
11.2.2 基于哈希表的实现：哈希集合（HashSet）
集合的高效实现依赖哈希表的“键唯一性”特性——将集合元素作为哈希表的键，值存储为占位符（如None）。这种实现称为哈希集合（HashSet），其核心思想如下：
1.底层存储：采用“数组+链表”的链地址法哈希表（见第10章），数组每个位置（桶）存储哈希地址相同的元素链表；
2.哈希函数：通过hash(e) % capacity计算元素e的哈希地址，其中capacity为数组容量；
3.冲突处理：哈希地址相同的元素存储在同一桶的链表中；
4.扩容/缩容：通过控制装填因子（元素个数/数组容量）在0.5~0.7，保证操作效率。
哈希集合的Python实现
python

	class HashSet: 
	def __init__(self, capacity: int = 16): 
	"""初始化哈希集合，默认数组容量为16""" 
	self._capacity = capacity # 数组容量 
	self._size = 0 # 元素个数 
	self._table = [[] for _ in range(self._capacity)] # 桶数组（每个桶为链表） 
	self._load_factor_threshold = 0.7 # 扩容阈值（装填因子>0.7时扩容） 
	self._shrink_factor_threshold = 0.2 # 缩容阈值（装填因子<0.2时缩容） 
	
	def add(self, e) -> None: 
	"""添加元素e到集合""" 
	if self.contains(e): # 元素已存在，直接返回 
	return 
	# 计算哈希地址 
	bucket_idx = hash(e) % self._capacity 
	# 添加元素到对应桶的链表尾部 
	self._table[bucket_idx].append(e) 
	self._size += 1 
	# 检查是否需要扩容 
	if self._size / self._capacity > self._load_factor_threshold: 
	self._resize(self._capacity * 2) 
	
	def remove(self, e) -> None: 
	"""删除元素e，若不存在则抛出KeyError""" 
	bucket_idx = hash(e) % self._capacity 
	bucket = self._table[bucket_idx] 
	for i in range(len(bucket)): 
	if bucket[i] == e: 
	del bucket[i] 
	self._size -= 1 
	# 检查是否需要缩容（容量需大于16，避免过小） 
	if (self._size > 0 and self._size / self._capacity < self._shrink_factor_threshold and 
	self._capacity > 16): 
	self._resize(self._capacity // 2) 
	return 
	raise KeyError(f"Element {e} not in set") 
	
	def discard(self, e) -> None: 
	"""删除元素e，若不存在则不执行""" 
	try: 
	self.remove(e) 
	except KeyError: 
	pass 
	
	def contains(self, e) -> bool: 
	"""判断元素e是否在集合中""" 
	bucket_idx = hash(e) % self._capacity 
	return e in self._table[bucket_idx] # 利用Python列表的in操作遍历链表 
	
	def size(self) -> int: 
	"""返回集合元素个数""" 
	return self._size 
	
	def clear(self) -> None: 
	"""清空集合""" 
	self._capacity = 16 
	self._size = 0 
	self._table = [[] for _ in range(self._capacity)] 
	
	def _resize(self, new_capacity: int) -> None: 
	"""扩容/缩容：创建新桶数组，重新哈希所有元素""" 
	old_table = self._table 
	self._capacity = new_capacity 
	self._table = [[] for _ in range(new_capacity)] # 初始化新桶数组 
	self._size = 0 # 重置size，后续add时重新计数 
	# 遍历旧桶数组，将所有元素重新插入新桶 
	for bucket in old_table: 
	for e in bucket: 
	self.add(e) 
	
	def __str__(self) -> str: 
	"""返回集合的字符串表示（无序）""" 
	elements = [] 
	for bucket in self._table: 
	elements.extend(bucket) 
	return f"{{{', '.join(map(str, elements))}}}" 
	
	def __len__(self) -> int: 
	"""支持len()操作""" 
	return self._size

代码解析
哈希地址计算：通过hash(e) % self._capacity将元素映射到桶数组索引，利用Python内置hash()函数处理不同类型元素（如整数、字符串、元组等可哈希类型）；
元素去重：add操作前通过contains检查元素是否已存在，避免重复插入；
扩容逻辑：当装填因子超过0.7时，数组容量翻倍，重新哈希所有元素，保证桶链表长度较浅（平均0.7个元素）；
缩容逻辑：当装填因子低于0.2且容量大于16时，数组容量减半，节省内存空间。
使用示例
python

	# 创建哈希集合 
	s = HashSet() 
	# 添加元素 
	s.add(10) 
	s.add(20) 
	s.add(10) # 重复添加，无效果 
	print(s) # 输出：{10, 20}（顺序可能因哈希地址不同而变化） 
	# 判断元素是否存在 
	print(s.contains(20)) # 输出：True 
	# 删除元素 
	s.remove(10) 
	print(s) # 输出：{20} 
	# 清空集合 
	s.clear() 
	print(len(s)) # 输出：0

11.2.3 集合的常用运算
集合支持三种基本数学运算，基于哈希集合可高效实现：

1. 并集（Union）
   定义：两个集合A、B的并集是包含A或B中所有元素的集合（去重），记为A∪B。
   实现思路：创建新集合，添加A中所有元素，再添加B中所有元素（利用集合的去重特性）。
   python

	def set_union(a: HashSet, b: HashSet) -> HashSet: 
	"""计算集合a和b的并集""" 
	result = HashSet() 
	# 添加a中所有元素 
	for bucket in a._table: 
	for e in bucket: 
	result.add(e) 
	# 添加b中所有元素（自动去重） 
	for bucket in b._table: 
	for e in bucket: 
	result.add(e) 
	return result

2. 交集（Intersection）
   定义：两个集合A、B的交集是包含A和B中共同元素的集合，记为A∩B。
   实现思路：遍历集合A的元素，若元素同时存在于集合B，则添加到结果集合。
   python

	def set_intersection(a: HashSet, b: HashSet) -> HashSet: 
	"""计算集合a和b的交集""" 
	result = HashSet() 
	for bucket in a._table: 
	for e in bucket: 
	if b.contains(e): 
	result.add(e) 
	return result

3. 差集（Difference）
   定义：集合A对B的差集是包含A中所有不属于B的元素的集合，记为A-B。
   实现思路：遍历集合A的元素，若元素不存在于集合B，则添加到结果集合。
   python

	def set_difference(a: HashSet, b: HashSet) -> HashSet: 
	"""计算集合a对b的差集""" 
	result = HashSet() 
	for bucket in a._table: 
	for e in bucket: 
	if not b.contains(e): 
	result.add(e) 
	return result

11.2.4 集合的应用场景

1. 数据去重
   问题：给定一个列表，去除重复元素。
   解法：将列表元素依次加入集合，再转换回列表。
   python

	def remove_duplicates(lst: list) -> list: 
	s = HashSet() 
	for e in lst: 
	s.add(e) 
	return [e for bucket in s._table for e in bucket] # 遍历集合元素 
	
	# 示例 
	print(remove_duplicates([1, 2, 2, 3, 3, 3])) # 输出：[1, 2, 3]（顺序可能不同）

2. 元素存在性快速判断
   问题：判断一个元素是否在海量数据中（如判断用户是否为VIP会员）。
   解法：将VIP用户ID存入哈希集合，通过contains操作O(1)判断。
   python

	# 模拟VIP会员集合 
	vip_users = HashSet() 
	for uid in [1001, 1002, 1003]: 
	vip_users.add(uid) 
	
	# 判断用户是否为VIP 
	def is_vip(uid: int) -> bool: 
	return vip_users.contains(uid) 
	
	print(is_vip(1002)) # 输出：True 
	print(is_vip(2000)) # 输出：False

11.3 映射（Map）
11.3.1 映射的定义与核心操作
定义11.2 映射（Map）：由互不相同的键（Key）和对应值（Value）组成的无序数据结构，键唯一，每个键关联一个值。核心操作如下：

示例：对于映射{"name": "Alice", "age": 20}，执行put("age", 21)后映射变为{"name": "Alice", "age": 21}；执行get("name")返回"Alice"；执行remove("age")后映射变为{"name": "Alice"}。
11.3.2 基于哈希表的实现：哈希映射（HashMap）
映射的高效实现同样依赖哈希表，将键值对(k, v)存储在桶数组中，键k作为哈希函数的输入，值v随键存储。这种实现称为哈希映射（HashMap），其核心思想与哈希集合类似，但需存储键值对而非单个元素。
哈希映射的Python实现
python

	class HashMap: 
	def __init__(self, capacity: int = 16): 
	"""初始化哈希映射，默认数组容量为16""" 
	self._capacity = capacity # 数组容量 
	self._size = 0 # 键值对个数 
	self._table = [[] for _ in range(self._capacity)] # 桶数组（每个桶存储键值对元组） 
	self._load_factor_threshold = 0.7 # 扩容阈值 
	self._shrink_factor_threshold = 0.2 # 缩容阈值 
	
	def put(self, k, v) -> None: 
	"""添加/更新键值对(k, v)""" 
	bucket_idx = hash(k) % self._capacity 
	bucket = self._table[bucket_idx] 
	# 遍历桶，若键已存在则更新值 
	for i in range(len(bucket)): 
	key, val = bucket[i] 
	if key == k: 
	bucket[i] = (k, v) 
	return 
	# 键不存在，添加新键值对到桶尾部 
	bucket.append((k, v)) 
	self._size += 1 
	# 检查扩容 
	if self._size / self._capacity > self._load_factor_threshold: 
	self._resize(self._capacity * 2) 
	
	def get(self, k, default=None): 
	"""获取键k对应的值，不存在则返回default""" 
	bucket_idx = hash(k) % self._capacity 
	for key, val in self._table[bucket_idx]: 
	if key == k: 
	return val 
	return default 
	
	def remove(self, k): 
	"""删除键k对应的键值对，返回被删除的值""" 
	bucket_idx = hash(k) % self._capacity 
	bucket = self._table[bucket_idx] 
	for i in range(len(bucket)): 
	key, val = bucket[i] 
	if key == k: 
	del bucket[i] 
	self._size -= 1 
	# 检查缩容 
	if (self._size > 0 and self._size / self._capacity < self._shrink_factor_threshold and 
	self._capacity > 16): 
	self._resize(self._capacity // 2) 
	return val 
	raise KeyError(f"Key {k} not in map") 
	
	def contains_key(self, k) -> bool: 
	"""判断键k是否存在""" 
	bucket_idx = hash(k) % self._capacity 
	for key, _ in self._table[bucket_idx]: 
	if key == k: 
	return True 
	return False 
	
	def keys(self) -> list: 
	"""返回所有键的列表（无序）""" 
	keys = [] 
	for bucket in self._table: 
	for key, _ in bucket: 
	keys.append(key) 
	return keys 
	
	def values(self) -> list: 
	"""返回所有值的列表（无序）""" 
	values = [] 
	for bucket in self._table: 
	for _, val in bucket: 
	values.append(val) 
	return values 
	
	def items(self) -> list: 
	"""返回所有键值对的列表（元组形式，无序）""" 
	items = [] 
	for bucket in self._table: 
	items.extend(bucket) 
	return items 
	
	def size(self) -> int: 
	"""返回键值对个数""" 
	return self._size 
	
	def clear(self) -> None: 
	"""清空映射""" 
	self._capacity = 16 
	self._size = 0 
	self._table = [[] for _ in range(self._capacity)] 
	
	def _resize(self, new_capacity: int) -> None: 
	"""扩容/缩容：重新哈希所有键值对""" 
	old_table = self._table 
	self._capacity = new_capacity 
	self._table = [[] for _ in range(new_capacity)] 
	self._size = 0 
	for bucket in old_table: 
	for k, v in bucket: 
	self.put(k, v) 
	
	def __str__(self) -> str: 
	"""返回映射的字符串表示""" 
	items = [f"{k}: {v}" for k, v in self.items()] 
	return f"{{{', '.join(items)}}}" 
	
	def __len__(self) -> int: 
	"""支持len()操作""" 
	return self._size

代码解析
键值对存储：桶数组中的每个链表存储哈希地址相同的键值对元组(k, v)；
值更新：put操作遍历桶中键值对，若键已存在则更新对应值，保证键的唯一性；
遍历操作：keys()、values()、items()通过遍历桶数组和链表，收集所有键、值、键值对；
哈希冲突处理：与哈希集合一致，通过链地址法存储冲突的键值对，依赖哈希函数均匀性保证操作效率。
使用示例
python

	# 创建哈希映射（学生-成绩） 
	score_map = HashMap() 
	score_map.put("Alice", 90) 
	score_map.put("Bob", 85) 
	score_map.put("Alice", 92) # 更新Alice的成绩 
	print(score_map) # 输出：{Alice: 92, Bob: 85}（顺序可能不同） 
	
	# 获取值 
	print(score_map.get("Bob")) # 输出：85 
	print(score_map.get("Charlie", 0)) # 输出：0（键不存在，返回默认值） 
	
	# 遍历键值对 
	print(score_map.keys()) # 输出：['Alice', 'Bob'] 
	print(score_map.items()) # 输出：[('Alice', 92), ('Bob', 85)] 
	
	# 删除键值对 
	score_map.remove("Bob") 
	print(score_map) # 输出：{Alice: 92}

11.3.3 映射的应用场景

1. 词频统计
   问题：统计一段文本中每个单词出现的次数。
   解法：用映射的键存储单词，值存储出现次数，遍历文本时更新次数。
   python

	def count_word_frequency(text: str) -> HashMap: 
	word_map = HashMap() 
	for word in text.lower().split(): 
	# 去除标点符号（简化处理） 
	cleaned_word = word.strip(".,!?") 
	# 更新次数：若单词已存在则+1，否则初始化为1 
	current_count = word_map.get(cleaned_word, 0) 
	word_map.put(cleaned_word, current_count + 1) 
	return word_map 
	
	# 示例 
	text = "Hello world! Hello Python, Python is great." 
	freq_map = count_word_frequency(text) 
	print(freq_map) # 输出：{hello: 2, world: 1, python: 2, is: 1, great: 1}

2. 缓存系统（简易版）
   问题：实现一个缓存，存储频繁访问的数据，避免重复计算或查询。
   解法：用映射存储键值对（如URL-页面内容），通过键快速获取缓存数据。
   python

	# 模拟数据库查询（耗时操作） 
	def query_database(user_id: int) -> str: 
	print(f"Querying database for user {user_id}...") 
	return f"User {user_id}'s profile" 
	
	# 缓存系统 
	cache = HashMap() 
	
	def get_user_profile(user_id: int) -> str: 
	# 先查缓存 
	if cache.contains_key(user_id): 
	return cache.get(user_id) 
	# 缓存未命中，查数据库并写入缓存 
	profile = query_database(user_id) 
	cache.put(user_id, profile) 
	return profile 
	
	# 第一次查询（缓存未命中） 
	print(get_user_profile(1001)) # 输出：Querying database for user 1001... User 1001's profile 
	# 第二次查询（缓存命中） 
	print(get_user_profile(1001)) # 输出：User 1001's profile（无数据库查询）

11.4 集合与映射的对比

11.5 本章总结
集合与映射的本质：集合专注于“元素唯一性”管理，映射专注于“键值关联”存储，两者均基于哈希表实现平均O(1)的核心操作效率，是解决“去重”与“关联”问题的基础工具。
哈希表的核心作用：通过哈希函数将键映射到桶数组地址，结合链地址法处理冲突，通过扩容/缩容维持低装填因子，保证集合与映射的高效性。
工程实践价值：集合广泛用于数据去重、存在性判断；映射广泛用于缓存、索引、统计计数等场景，是数据库、搜索引擎、配置系统的底层核心组件。
理解集合与映射的关键在于掌握“键”的唯一性与哈希表的工作原理，它们的设计思想体现了“用空间换时间”的权衡，也是后续学习更复杂数据结构（如LRU缓存、图）的基础。
11.6 思考题
1.基于红黑树实现一个有序集合（TreeSet），支持按元素大小顺序遍历（提示：键按中序遍历有序）。
2.设计一个哈希映射的迭代器，支持按插入顺序遍历键值对（提示：用双向链表记录插入顺序，映射存储键到链表节点的引用）。
3.用哈希集合实现两个字符串的交集（如输入"abc"和"acd"，输出"ac"）。
4.用哈希映射实现一个简化版LRU缓存（最近最少使用缓存），支持get(key)和put(key, value)操作，当缓存满时删除最久未使用的键值对（提示：用双向链表记录访问顺序，映射存储键到链表节点的引用）。
5.对比哈希映射与有序映射（如Python的collections.OrderedDict）的适用场景，分析何时需要有序性，何时优先考虑哈希映射的高效性。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49301.html