-
第13章 集合、映射与跳表 13.1 引言 集合（Set）和映射（Map）是两种常用的数据
第13章 集合、映射与跳表
13.1 引言
集合（Set）和映射（Map）是两种常用的数据结构，广泛应用于去重、查找、键值对存储等场景。集合的核心特性是元素唯一性（无重复元素），映射则是键值对（Key-Value）的集合（键唯一，值可重复）。跳表（Skip List）是一种有序数据结构，通过多级索引实现高效的查找、插入和删除操作，性能可与平衡树媲美，但实现更简单。本章将系统介绍集合、映射的基本概念与实现，以及跳表的结构与操作。
13.2 集合
13.2.1 基本概念
集合是由互不相同的元素组成的无序集合，其基本特性包括：
唯一性：集合中不存在重复元素；
无序性：元素之间没有固定顺序（与列表的有序性不同）。
基本操作：
add(e)：向集合中添加元素e（若e已存在，则不添加）；
remove(e)：从集合中删除元素e（若e不存在，抛出异常或返回False）；
contains(e)：判断集合是否包含元素e，返回bool值；
size()：返回集合中元素的个数；
is_empty()：判断集合是否为空，返回bool值。
13.2.2 集合的实现
集合的实现需高效支持上述操作，常见实现方式包括基于数组、链表、哈希表等。其中，哈希表实现因平均时间复杂度为O(1)，是实际应用中的首选。
哈希集合（HashSet）的实现
哈希集合通过哈希表存储元素，利用哈希函数将元素映射到表中的索引，通过链地址法处理冲突（同一索引的元素用链表存储）。
实现步骤：
1.初始化：创建哈希表（数组），初始容量为固定值（如16），负载因子阈值（如0.75，超过则扩容）；
2.添加元素：
o计算元素的哈希值，通过哈希函数（如hash(e) % capacity）得到索引；
o遍历该索引处的链表，若元素已存在则返回；否则将元素插入链表头部；
o若添加后元素个数超过capacity * 负载因子，则扩容（容量翻倍）并重新哈希所有元素；
3.删除元素：
o计算索引，遍历链表找到元素，删除该节点（修改链表指针）；
4.查找元素：
o计算索引，遍历链表判断元素是否存在。
代码实现（哈希集合）
python
class HashSet:
def __init__(self, capacity=16, load_factor=0.75):
self.capacity = capacity # 哈希表容量
self.load_factor = load_factor # 负载因子阈值
self.size = 0 # 元素个数
self.table = [[] for _ in range(capacity)] # 哈希表（桶数组，每个桶为链表）
def _hash(self, e):
"""哈希函数：计算元素e的索引"""
return hash(e) % self.capacity # 取模保证索引在[0, capacity-1]
def add(self, e):
"""添加元素e（若已存在则不添加）"""
idx = self._hash(e)
# 检查元素是否已存在
for elem in self.table[idx]:
if elem == e:
return # 已存在，直接返回
# 添加元素到链表头部
self.table[idx].append(e)
self.size += 1
# 检查是否需要扩容
if self.size / self.capacity > self.load_factor:
self._resize()
def remove(self, e):
"""删除元素e，成功返回True，失败返回False"""
idx = self._hash(e)
bucket = self.table[idx]
for i in range(len(bucket)):
if bucket[i] == e:
bucket.pop(i) # 删除元素
self.size -= 1
return True
return False # 元素不存在
def contains(self, e):
"""判断集合是否包含元素e"""
idx = self._hash(e)
for elem in self.table[idx]:
if elem == e:
return True
return False
def _resize(self):
"""扩容哈希表（容量翻倍）"""
old_table = self.table
self.capacity *= 2 # 容量翻倍
self.table = [[] for _ in range(self.capacity)] # 新哈希表
self.size = 0 # 重置size，后续重新添加元素
# 将旧表元素重新哈希到新表
for bucket in old_table:
for elem in bucket:
self.add(elem) # 调用add方法自动处理新索引
def __len__(self):
return self.size
def is_empty(self):
return self.size == 0
性能分析
时间复杂度：
oadd(e)、remove(e)、contains(e)：平均O(1)（哈希函数均匀分布时，链表长度接近1）；最坏O(n)（所有元素哈希冲突，链表长度为n）。
空间复杂度：O(n)（哈希表容量随元素个数动态增长）。
13.2.3 应用场景
集合常用于去重（如从列表中提取唯一元素）、** membership 测试**（判断元素是否存在）、集合运算（如交集、并集、差集）等场景。例如：
python
# 利用集合去重
nums = [1, 2, 2, 3, 3, 3]
unique_nums = list(HashSet(nums)) # [1, 2, 3]
13.3 映射
13.3.1 基本概念
映射（Map，又称字典）是键值对（Key-Value）的集合，其核心特性是键的唯一性（每个键对应唯一的值，值可重复）。
基本操作：
put(k, v)：插入键值对(k, v)（若k已存在，则更新值为v）；
remove(k)：删除键为k的键值对，返回对应的值（若k不存在，抛出异常或返回None）；
get(k)：返回键k对应的值（若k不存在，返回None或指定默认值）；
contains_key(k)：判断映射是否包含键k，返回bool值；
size()、is_empty()：同集合。
13.3.2 映射的实现
映射的实现与集合类似，核心是键的唯一性。常见实现方式包括基于哈希表（哈希映射）和平衡树（有序映射），其中哈希映射因高效性应用最广。
哈希映射（HashMap）的实现
哈希映射通过哈希表存储键值对，键通过哈希函数映射到索引，值与键关联存储。冲突处理仍采用链地址法（同一索引的键值对用链表存储）。
实现步骤：
1.键值对存储：每个链表节点存储键值对(key, value)；
2.哈希函数：基于键计算索引；
3.操作逻辑：put、remove、get等操作围绕键展开，与哈希集合类似，但需处理值的存储与更新。
代码实现（哈希映射）
python
class HashMap:
def __init__(self, capacity=16, load_factor=0.75):
self.capacity = capacity
self.load_factor = load_factor
self.size = 0
# 哈希表：每个桶为链表，存储键值对元组(key, value)
self.table = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
"""插入键值对(key, value)，若key存在则更新value"""
idx = self._hash(key)
bucket = self.table[idx]
# 检查key是否已存在，若存在则更新value
for i in range(len(bucket)):
k, v = bucket[i]
if k == key:
bucket[i] = (key, value) # 更新值
return
# key不存在，添加新键值对
bucket.append((key, value))
self.size += 1
# 检查扩容
if self.size / self.capacity > self.load_factor:
self._resize()
def remove(self, key):
"""删除键为key的键值对，返回value；若key不存在，返回None"""
idx = self._hash(key)
bucket = self.table[idx]
for i in range(len(bucket)):
k, v = bucket[i]
if k == key:
bucket.pop(i)
self.size -= 1
return v
return None
def get(self, key, default=None):
"""返回key对应的值，若不存在返回default"""
idx = self._hash(key)
for k, v in self.table[idx]:
if k == key:
return v
return default
def contains_key(self, key):
"""判断是否包含键key"""
idx = self._hash(key)
for k, _ in self.table[idx]:
if k == key:
return True
return False
def _resize(self):
"""扩容哈希表（容量翻倍）"""
old_table = self.table
self.capacity *= 2
self.table = [[] for _ in range(self.capacity)]
self.size = 0
# 重新哈希旧表键值对
for bucket in old_table:
for key, value in bucket:
self.put(key, value)
def __len__(self):
return self.size
def is_empty(self):
return self.size == 0
性能分析
时间复杂度：同哈希集合，put、remove、get平均O(1)，最坏O(n)。
空间复杂度：O(n)（存储键值对及哈希表结构）。
13.3.3 应用场景
映射常用于键值对存储与查询，如配置参数（键为参数名，值为参数值）、缓存系统（键为数据ID，值为数据内容）、索引（键为关键字，值为对应记录）等。
13.4 跳表
13.4.1 基本概念
跳表（Skip List）是一种有序数据结构，通过在原始链表（底层）之上添加多级索引，实现高效的查找、插入和删除操作。其核心思想是“空间换时间”——通过少量索引节点，减少查找时的比较次数，平均时间复杂度达到O(log n)。
结构特点：
多级索引：从底层链表（包含所有元素）开始，每向上一级，索引节点数量约为下一级的1/2（或其他比例），形成“金字塔”结构；
有序性：所有节点按关键字升序排列（底层链表和各级索引均有序）。
13.4.2 跳表的结构
以有序序列[3, 6, 7, 9, 12, 17]为例，跳表结构如下：
Level 2: 3 ----------------------> 12 ----------------------> None
Level 1: 3 --------> 6 --------> 9 --------> 12 --------> 17 --> None
Level 0: 3 --> 6 --> 7 --> 9 --> 12 --> 17 --> None （底层链表）
Level 0：底层链表，包含所有元素，节点间通过next指针连接；
Level 1：一级索引，每隔1个节点取一个索引（如3、6、9、12、17）；
Level 2：二级索引，每隔3个节点取一个索引（如3、12）；
索引层级越高，节点越稀疏，最高层级称为“跳表的高度”。
13.4.3 基本操作
-
查找操作
目标：在跳表中查找关键字为key的节点。
步骤：
1.从最高级索引的头节点开始，向右比较：
o若当前节点的下一个节点关键字<= key，则向右移动；
o否则，向下移动一级索引；
2.重复步骤1，直至到达底层链表（Level 0）；
3.在底层链表中向右查找，若找到关键字key的节点，返回该节点；否则返回None。
示例：查找key=9
从Level 2头节点开始：下一个节点为3（<=9）→ 无法向右（下一个是12>9）→ 下移至Level 1；
Level 1：当前节点3→下一个节点6（<=9）→ 下一个节点9（<=9）→ 下一个节点12（>9）→ 下移至Level 0；
Level 0：当前节点9→找到目标，返回节点9。 -
插入操作
目标：插入关键字为key的节点，维持跳表的有序性和索引结构。
步骤：
1.查找插入位置：类似查找操作，记录每一级索引中最后一个小于key的节点（“前驱节点”），用于后续插入索引；
2.生成随机层数：为新节点随机分配一个层数（level），决定该节点在哪些索引层出现（层数越高，被选中概率越低）；
3.插入节点：
o在底层链表（Level 0）中插入新节点；
o对于每一级索引（从1到level），若该级索引的前驱节点存在，将新节点插入到前驱节点之后；
4.更新跳表高度：若新节点的层数高于当前跳表高度，更新跳表高度。
随机层数生成：通过随机函数生成，通常以概率p（如0.5）决定是否增加层数，直至生成0或达到最大层数。例如：
python
def random_level(max_level=16, p=0.5):
level = 1
while random.random() < p and level < max_level:
level += 1
return level
-
删除操作
目标：删除关键字为key的节点，同时更新各级索引。
步骤：
1.查找节点及前驱：类似插入操作，查找目标节点，并记录每一级索引中该节点的前驱节点；
2.删除节点：
o从底层链表中删除目标节点；
o对于每一级索引，若该级索引中存在目标节点，通过前驱节点删除该索引节点；
3.更新跳表高度：若删除后最高级索引为空，降低跳表高度。
13.4.4 代码实现
python
import random
class SkipListNode:
def __init__(self, key=None, value=None, level=1):
self.key = key # 关键字
self.value = value # 值
self.next = [None] * level # 每级索引的next指针
class SkipList:
def __init__(self, max_level=16, p=0.5):
self.max_level = max_level # 最大层数
self.p = p # 层数增长概率
self.level = 1 # 当前跳表高度（初始为1）
self.head = SkipListNode(level=max_level) # 头节点（不存储数据）
def _random_level(self):
"""生成随机层数"""
level = 1
while random.random() < self.p and level < self.max_level:
level += 1
return level
def insert(self, key, value):
"""插入键值对(key, value)"""
update = [None] * self.max_level # 存储每级索引的前驱节点
current = self.head
# 1. 查找并记录各级索引的前驱节点
for i in range(self.level-1, -1, -1):
# 当前级索引向右查找，直至下一个节点key > 当前key
while current.next[i] and current.next[i].key < key:
current = current.next[i]
update[i] = current # 记录第i级索引的前驱节点
# 2. 检查key是否已存在（底层链表）
current = current.next[0]
if current and current.key == key:
current.value = value # 更新值
return
# 3. 生成随机层数
new_level = self._random_level()
# 4. 若新节点层数高于当前跳表高度，更新update和跳表高度
if new_level > self.level:
for i in range(self.level, new_level):
update[i] = self.head # 新层级的前驱节点为头节点
self.level = new_level
# 5. 创建新节点并插入各级索引
new_node = SkipListNode(key, value, new_level)
for i in range(new_level):
new_node.next[i] = update[i].next[i] # 新节点next指向原前驱节点的next
update[i].next[i] = new_node # 前驱节点next指向新节点
def search(self, key):
"""查找key对应的value，不存在返回None"""
current = self.head
# 从最高级索引向下查找
for i in range(self.level-1, -1, -1):
while current.next[i] and current.next[i].key < key:
current = current.next[i]
# 到达底层链表，检查是否找到
current = current.next[0]
return current.value if current and current.key == key else None
def delete(self, key):
"""删除key对应的节点，返回True，不存在返回False"""
update = [None] * self.max_level # 存储各级索引的前驱节点
current = self.head
# 1. 查找目标节点及前驱
for i in range(self.level-1, -1, -1):
while current.next[i] and current.next[i].key < key:
current = current.next[i]
update[i] = current
# 2. 检查key是否存在
current = current.next[0]
if not current or current.key != key:
return False # 不存在
# 3. 从各级索引中删除节点
for i in range(self.level):
if update[i].next[i] != current:
break # 该级索引中无此节点，无需删除
update[i].next[i] = current.next[i]
# 4. 更新跳表高度（若最高级索引为空）
while self.level > 1 and self.head.next[self.level-1] is None:
self.level -= 1
return True
13.4.5 性能分析
时间复杂度：
o查找、插入、删除：平均O(log n)（索引层数为O(log n)，每层查找O(1)）；最坏O(n)（极端情况下索引失效，退化为链表）。
空间复杂度：O(n log n)（存储各级索引节点，索引节点总数约为n/(1-p)，p为概率参数）。
13.4.6 应用场景
跳表因实现简单（无需像平衡树那样维护复杂的旋转操作）、性能稳定，被广泛应用于有序数据的高效操作场景，如Redis的有序集合（ZSet）、LevelDB等数据库的索引结构。
13.5 总结
本章介绍了集合、映射和跳表三种重要数据结构：
集合：基于哈希表实现，支持元素的唯一存储和高效增删查，平均时间复杂度O(1)，适用于去重和membership测试；
映射：基于哈希表实现的键值对存储，键唯一，支持高效的键值对操作，是缓存、索引等场景的核心数据结构；
跳表：通过多级索引实现有序数据的高效操作，平均时间复杂度O(log n)，实现简单，适用于有序集合和数据库索引。
实际应用中，需根据数据特性（有序性、唯一性、操作频率）选择合适的数据结构：无序唯一元素选集合，键值对存储选映射，有序数据且需高效操作选跳表或平衡树。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49279.html
