第14章 布隆过滤器与区间数据结构
14.1 布隆过滤器
14.1.1 基本概念
布隆过滤器（Bloom Filter）是一种空间高效的概率型数据结构，用于判断一个元素是否属于一个集合。它的核心特性是：
高效性：插入和查询的时间复杂度均为O(k)（k为哈希函数个数），空间复杂度远低于哈希表；
概率性：存在假阳性（False Positive）（误判元素存在），但无假阴性（False Negative）（不会误判元素不存在）。
布隆过滤器适用于“允许一定误判率，但对空间和时间效率要求极高”的场景，如缓存穿透防护、海量数据去重等。
14.1.2 基本原理
布隆过滤器由一个位数组（Bit Array） 和k个独立的哈希函数组成。
核心结构
位数组：长度为m的二进制数组，初始所有位均为0；
哈希函数：k个不同的哈希函数，每个函数将元素映射到位数组的一个索引（范围[0, m-1]）。
插入操作
对于元素x，插入步骤如下：
1.对x应用k个哈希函数，得到k个索引h₁(x), h₂(x), ..., hₖ(x)；
2.将位数组中这k个索引对应的位均设为1。
查询操作
判断元素x是否存在，步骤如下：
1.对x应用k个哈希函数，得到k个索引h₁(x), h₂(x), ..., hₖ(x)；
2.检查位数组中这k个索引对应的位是否均为1：
o若有任意一位为0，则x一定不存在于集合中（无假阴性）；
o若所有位均为1，则x可能存在（存在假阳性，因不同元素的哈希索引可能重叠）。
14.1.3 实现
以下用Python实现一个基础布隆过滤器，使用bitarray模块（高效存储位数组），若未安装可通过pip install bitarray获取。
python

import bitarray 
	import mmh3 # 非加密哈希函数库（MurmurHash3），可通过pip install mmh3安装 
	
	class BloomFilter: 
	def __init__(self, capacity, false_positive_rate=0.01): 
	""" 
	初始化布隆过滤器 
	:param capacity: 预期存储元素个数n 
	:param false_positive_rate: 期望假阳性率p 
	""" 
	self.n = capacity # 预期元素个数 
	self.p = false_positive_rate # 期望假阳性率 
	
	# 计算位数组长度m和哈希函数个数k（基于概率模型推导） 
	self.m = int(- (self.n * np.log(self.p)) / (np.log(2) ** 2)) # m = -n ln p / (ln 2)² 
	self.k = int((self.m / self.n) * np.log(2)) # k = (m/n) ln 2 
	
	self.bit_array = bitarray.bitarray(self.m) 
	self.bit_array.setall(0) # 初始化位数组为全0 
	
	def add(self, item): 
	"""插入元素item""" 
	for seed in range(self.k): 
	# 使用不同seed的mmh3哈希函数生成索引 
	idx = mmh3.hash(item, seed) % self.m 
	self.bit_array[idx] = 1 
	
	def contains(self, item): 
	"""判断元素item是否存在（可能假阳性）""" 
	for seed in range(self.k): 
	idx = mmh3.hash(item, seed) % self.m 
	if not self.bit_array[idx]: 
	return False # 至少一位为0，元素一定不存在 
	return True # 所有位为1，元素可能存在 
	
	def __len__(self): 
	"""返回当前位数组中1的个数（近似元素数量，非精确值）""" 
	return self.bit_array.count(1)

注：若无法使用mmh3，可替换为Python内置hash函数（但需注意vb.net教程C#教程python教程SQL教程access 2010教程内置hash的随机性，可能影响稳定性）。
14.1.4 性能分析
假阳性率
布隆过滤器的假阳性率p与位数组长度m、哈希函数个数k、元素个数n的关系为：
p≈(1−e−kn/m)k p pprox left(1 - e^{{-kn/m} ight)}k p≈(1−e−kn/m)k
当k = (m/n)ln2时，假阳性率最低，此时p ≈ (0.6185)^(m/n)。
时间复杂度
插入与查询：O(k)（k为哈希函数个数，通常k=3~10，可视为常数级）。
空间复杂度
O(m)（m为位数组长度，通常m = -n ln p / (ln2)²，当n=10⁶，p=0.01时，m≈9.5×10⁶位≈1.1MB，空间效率极高）。
14.1.5 优缺点
优点
空间效率：相比哈希表，无需存储元素本身，仅需位数组，空间成本极低；
时间高效：插入和查询均为O(k)，常数级时间；
支持海量数据：适用于内存受限场景（如判断一个URL是否已爬取，无需存储所有URL）。
缺点
假阳性：存在误判（无法区分“元素存在”和“哈希碰撞导致所有位为1”）；
不支持删除：删除元素会将对应位设为0，但可能影响其他元素（多个元素共享位）；
哈希函数依赖：哈希函数的独立性和均匀性直接影响假阳性率。
14.1.6 应用场景
缓存穿透防护：数据库查询前，用布隆过滤器判断key是否存在，避免对不存在key的无效查询；
海量数据去重：如爬虫URL去重、邮件黑名单过滤（无需存储所有URL/邮箱，仅需判断是否存在）；
集合 membership 测试：如判断一个用户是否为VIP（允许少量误判）。
14.2 区间树
14.2.1 基本概念
区间树（Interval Tree）是一种动态数据结构，用于高效查询“与给定区间重叠的所有区间”。其核心目标是解决“区间重叠查询”问题：给定一组区间，快速找出所有与查询区间[q_low, q_high]重叠的区间。
区间树的查询时间复杂度为O(log n + k)（n为区间总数，k为重叠区间个数），支持动态插入和删除区间。
14.2.2 结构定义
区间树的节点结构包含以下信息：
mid：区间中点（用于划分左右子树的依据）；
left/right：左/右子树（左子树区间均≤mid，右子树区间均≥mid）；
intervals：存储包含mid的区间（按区间左端点排序的列表）；
max_right：当前子树中所有区间的最大右端点（用于剪枝，若max_right < q_low，则无需查询该子树）。
结构示例：
节点:

{ 
	mid: 5, 
	max_right: 10, 
	intervals: [(2, 7), (3, 9)], # 包含mid=5的区间，按左端点排序 
	left: 左子树（区间≤5）, 
	right: 右子树（区间≥5） 
	}

14.2.3 基本操作

1. 插入操作
   插入区间[low, high]的步骤：
   1.若当前节点为空，创建新节点，mid设为区间中点（如(low+high)/2）；
   2.若区间包含当前节点mid（low ≤ mid ≤ high），将区间加入当前节点的intervals列表（按左端点排序）；
   3.否则，若high ≤ mid，递归插入左子树；若low ≥ mid，递归插入右子树；
   4.更新当前节点的max_right（取当前max_right与区间high的最大值）。
2. 查询重叠区间
   查询与[q_low, q_high]重叠的所有区间的步骤：
   1.初始化结果列表；
   2.遍历当前节点的intervals列表，判断每个区间是否与[q_low, q_high]重叠（low ≤ q_high且high ≥ q_low），若重叠则加入结果；
   3.若左子树非空且左子树max_right ≥ q_low，递归查询左子树；
   4.若右子树非空且右子树min_left ≤ q_high（或右子树存在区间low ≤ q_high），递归查询右子树；
   5.返回结果列表。
   14.2.4 实现
   以下为区间树的Python实现（简化版，仅包含核心操作）：
   python

	class Interval: 
	"""区间类，存储左右端点""" 
	def __init__(self, low, high): 
	self.low = low 
	self.high = high 
	
	def __repr__(self): 
	return f"[{self.low}, {self.high}]" 
	
	class IntervalTreeNode: 
	"""区间树节点""" 
	def __init__(self, mid): 
	self.mid = mid # 区间中点 
	self.intervals = [] # 包含mid的区间（按low排序） 
	self.left = None # 左子树（区间high ≤ mid） 
	self.right = None # 右子树（区间low ≥ mid） 
	self.max_right = -float('inf') # 当前子树最大右端点 
	
	class IntervalTree: 
	def __init__(self): 
	self.root = None 
	
	def _insert(self, node, interval): 
	"""递归插入区间（辅助函数）""" 
	if not node: 
	# 新节点mid设为区间中点（简化处理，实际可优化为所有区间的中位数） 
	mid = (interval.low + interval.high) // 2 
	node = IntervalTreeNode(mid) 
	
	# 若区间包含当前节点mid，加入intervals列表并排序 
	if interval.low <= node.mid <= interval.high: 
	node.intervals.append(interval) 
	node.intervals.sort(key=lambda x: x.low) # 按low排序，便于查询 
	# 否则插入左/右子树 
	elif interval.high <= node.mid: 
	node.left = self._insert(node.left, interval) 
	else: 
	node.right = self._insert(node.right, interval) 
	
	# 更新max_right 
	node.max_right = max(node.max_right, interval.high) 
	return node 
	
	def insert(self, low, high): 
	"""插入区间[low, high]""" 
	interval = Interval(low, high) 
	self.root = self._insert(self.root, interval) 
	
	def _query_overlapping(self, node, q_interval, result): 
	"""递归查询重叠区间（辅助函数）""" 
	if not node: 
	return 
	q_low, q_high = q_interval.low, q_interval.high 
	
	# 检查当前节点intervals中与q_interval重叠的区间 
	for interval in node.intervals: 
	if interval.low <= q_high and interval.high >= q_low: 
	result.append(interval) 
	
	# 递归查询左子树（若左子树max_right >= q_low，可能存在重叠） 
	if node.left and node.left.max_right >= q_low: 
	self._query_overlapping(node.left, q_interval, result) 
	
	# 递归查询右子树（若右子树存在区间low <= q_high，可能存在重叠） 
	# 简化处理：假设右子树存在区间，实际可维护min_left 
	if node.right: 
	self._query_overlapping(node.right, q_interval, result) 
	
	def query_overlapping(self, q_low, q_high): 
	"""查询与[q_low, q_high]重叠的所有区间""" 
	result = [] 
	q_interval = Interval(q_low, q_high) 
	self._query_overlapping(self.root, q_interval, result) 
	return result

14.2.5 性能分析
插入时间：O(log n)（递归深度为log n，每次插入需维护intervals排序，简化版为O(k log k)，k为节点intervals个数，通常k较小）；
查询时间：O(log n + k)（log n为递归深度，k为重叠区间个数）；
空间复杂度：O(n)（每个区间存储在O(1)个节点中）。
14.2.6 应用场景
区间调度：如会议室预订系统，查询与指定时间段重叠的所有预订；
地理信息系统：查询地图上与指定区域重叠的所有区域（如行政边界、兴趣点）；
数据库索引：对区间类型字段（如时间范围、数值范围）建立索引，加速区间重叠查询。
14.3 线段树
14.3.1 基本概念
线段树（Segment Tree）是一种静态/动态数据结构，用于高效查询和更新“区间信息”（如区间最值、区间和、区间乘积等）。它将一个完整区间划分为多个不重叠的子区间，每个节点代表一个子区间，存储该区间的聚合信息（如最大值、和）。
线段树的核心特性是：区间分解（将任意区间查询分解为O(log n)个节点区间的查询），支持O(log n)时间的单点更新和区间查询。
14.3.2 结构定义
线段树通常表示为完全二叉树（可用数组存储），其中：
根节点代表整个区间[0, n-1]（n为区间长度）；
叶节点代表单个元素区间[i, i]；
非叶节点代表区间[l, r]，左子树为[l, mid]，右子树为[mid+1, r]，mid = (l + r) // 2；
每个节点存储区间[l, r]的聚合信息（如max、sum等）。
结构示例（区间[0, 7]的最大值线段树）：
根节点:

[0,7], max=10 
	├─ 左子树: [0,3], max=8 
	│ ├─ [0,1], max=5 
	│ │ ├─ [0,0], max=3 
	│ │ └─ [1,1], max=5 
	│ └─ [2,3], max=8 
	│ ├─ [2,2], max=2 
	│ └─ [3,3], max=8 
	└─ 右子树: [4,7], max=10 
	├─ [4,5], max=9 
	│ ├─ [4,4], max=9 
	│ └─ [5,5], max=6 
	└─ [6,7], max=10 
	├─ [6,6], max=10 
	└─ [7,7], max=4

14.3.3 基本操作

1. 构建线段树
   以区间最大值线段树为例，构建步骤：
   1.若当前节点为叶节点（l = r），存储arr[l]；
   2.否则，递归构建左子树（[l, mid]）和右子树（[mid+1, r]）；
   3.当前节点的max值为左子树max和右子树max的最大值。
2. 单点更新
   更新位置i的值为val，步骤：
   1.若当前节点为叶节点（l = r = i），更新值为val；
   2.否则，若i ≤ mid，递归更新左子树；若i > mid，递归更新右子树；
   3.更新当前节点的max值（左子树max和右子树max的最大值）。
3. 区间查询
   查询区间[ql, qr]的最大值，步骤：
   1.若当前节点区间[l, r]与[ql, qr]无重叠，返回-∞；
   2.若当前节点区间完全包含于[ql, qr]，返回当前节点的max值；
   3.否则，递归查询左子树和右子树，返回两者的最大值。
   14.3.4 实现
   以下为区间最大值线段树的Python实现（数组存储）：
   python

	class SegmentTree: 
	def __init__(self, data): 
	"""初始化线段树（区间最大值）""" 
	self.n = len(data) # 区间长度 
	self.size = 1 # 线段树数组大小（下一个2的幂，简化实现） 
	while self.size < self.n: 
	self.size <<= 1 # 确保size为2的幂 
	self.tree = [-float('inf')] * (2 * self.size) # 线段树数组（大小2*size） 
	
	# 填充叶节点 
	for i in range(self.n): 
	self.tree[self.size + i] = data[i] 
	# 构建非叶节点（从size-1向下更新） 
	for i in range(self.size - 1, 0, -1): 
	self.tree[i] = max(self.tree[2*i], self.tree[2*i+1]) 
	
	def update(self, idx, val): 
	"""更新位置idx的值为val（idx从0开始）""" 
	idx += self.size # 叶节点索引 
	self.tree[idx] = val 
	# 向上更新父节点 
	idx >>= 1 # 移动到父节点 
	while idx >= 1: 
	new_val = max(self.tree[2*idx], self.tree[2*idx+1]) 
	if self.tree[idx] == new_val: 
	break # 无变化，停止更新 
	self.tree[idx] = new_val 
	idx >>= 1 
	
	def query_max(self, l, r): 
	"""查询区间[l, r]的最大值（闭区间，0<=l<=r<n）""" 
	res = -float('inf') 
	l += self.size # 叶节点左边界 
	r += self.size # 叶节点右边界 
	while l <= r: 
	if l % 2 == 1: # 左节点为右孩子，加入结果并右移 
	res = max(res, self.tree[l]) 
	l += 1 
	if r % 2 == 0: # 右节点为左孩子，加入结果并左移 
	res = max(res, self.tree[r]) 
	r -= 1 
	l >>= 1 # 上移到父节点 
	r >>= 1 
	return res

注：上述实现采用“大小为2的幂”的数组存储，简化了节点索引计算；实际也可采用动态二叉树结构，但数组实现更高效。
14.3.5 性能分析
构建时间：O(n)（n为区间长度，需初始化n个叶节点和n-1个非叶节点）；
单点更新：O(log n)（从叶节点到根节点，路径长度为log n）；
区间查询：O(log n)（分解为O(log n)个节点区间的查询）；
空间复杂度：O(n)（数组实现需2n空间，n为区间长度的下一个2的幂）。
14.3.6 应用场景
区间最值查询：如股票价格区间最大值查询、温度区间最高值查询；
区间和查询：如数组区间和、前缀和动态更新；
范围更新：如区间加法（需扩展为懒惰标记线段树）、区间赋值；
事件检测：如检测区间内是否存在超过阈值的元素（如传感器数据异常检测）。
14.4 总结
14.4.1 核心数据结构对比

14.4.2 选择建议
元素存在性判断（允许误判）：选择布隆过滤器（空间效率优先）；
区间重叠查询（动态数据）：选择区间树（支持插入删除，查询重叠区间）；
区间聚合信息（如最值、和）：选择线段树（高效查询与更新，静态/动态数据均适用）。
实际应用中，需根据数据特性（是否动态、查询类型、空间限制）选择合适的数据结构，或结合多种结构（如布隆过滤器+哈希表，线段树+懒惰标记）以优化性能。

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