数据结构与算法 / 系统课时
哈希表性能陷阱
哈希表性能陷阱
相同的元素数和容量也可能出现不同的性能。一个表的键分散在多个桶中,另一个表却把许多键放进同一条链。判断原因时,先分开看哈希分布、冲突策略与查询分布。
学习目标
- 区分桶长度、槽探测次数、命中和未命中的成本。
- 观察输入模式与容量映射如何造成聚集。
- 为候选改进设计包含退化模式的实验。
聚集从哪里来
链地址法中,大量键落入同一桶时,链内查找可能随桶长度线性增长。线性探测中,相邻冲突会形成连续占用区域,未命中也必须探测到真正空槽才可停止。若删除用墓碑标记,还需统计墓碑数量和占用负载。清理墓碑可以缩短无效路径,但固定容量与输入步长造成的冲突可能仍然存在。 链地址和乘法散列 线性探测与占用

容量 16 时,key % 16 只按低 4 位分桶,所有 16 的倍数都从桶 0 开始。对同一负载,可分别记录最大桶长度、命中和未命中的键比较次数,以及查询延迟的高分位。桶统计不直接等于真实时延,生产还要考虑键长度、扩容、内存和并发。
Python 3.11 对照实验
本例固定 16 个桶,比较直接取余和固定 32 位乘法混合后取高位。该混合只用于演示输入低位为何可能不再直接决定下标,适合观察差异,也有明确的 32 位截断边界。每个实验记录成功查询的平均键比较次数和一个特定未命中查询的比较次数。 链地址和乘法散列
def low_bits(key: int) -> int:
return key % 16
def mixed_bits(key: int) -> int:
mixed = (key * 2654435761) & 0xFFFFFFFF
return mixed >> 28
def inspect(keys: list[int], miss: int, index_of) -> tuple[int, float, int]:
if not keys or len(set(keys)) != len(keys) or miss in keys:
raise ValueError("expected distinct keys and a missing query")
buckets = [[] for _ in range(16)]
for key in keys:
buckets[index_of(key)].append(key)
def compare_count(key: int) -> int:
chain = buckets[index_of(key)]
for count, stored in enumerate(chain, start=1):
if stored == key:
return count
return len(chain)
maximum = max(map(len, buckets))
hit_mean = sum(compare_count(key) for key in keys) / len(keys)
return maximum, hit_mean, compare_count(miss)
stride = [i * 16 for i in range(12)]
wide = [i << 32 for i in range(12)]
for name, keys, miss in [("stride", stride, 192), ("wide", wide, 12 << 32)]:
for index_of in (low_bits, mixed_bits):
longest, hit_mean, miss_cost = inspect(keys, miss, index_of)
print(f"{name}/{index_of.__name__}: max={longest}, hit={hit_mean:.2f}, miss={miss_cost}")stride/low_bits: max=12, hit=6.50, miss=12
stride/mixed_bits: max=2, hit=1.17, miss=1
wide/low_bits: max=12, hit=6.50, miss=12
wide/mixed_bits: max=12, hit=6.50, miss=12两个实验的负载完全相同。第二组键在 32 位截断后都一样,混合无法区分已被丢弃的高位。这组结果不能证明任意乘法混合都有效。实验还只选择了一个未命中键,评估整体失败查询应抽取有代表性的负样本。
定位与缓解
先核对有效负载和墓碑,再查看高成本桶或探测区。用实际键和固定步长、重复前缀、极端值等输入比较候选规则,并区分命中和失败负载。开放寻址的替代探测策略还要确认探测序列能覆盖必要槽位。对外部可控输入,选择适合该运行时的有种子哈希或可控制最坏成本的结构,并限制输入与处理预算。树化桶能否提供对数级搜索取决于键是否具有可用且一致的有序比较,不能只根据“树形结构”推断。 链地址与随机化假设 开放寻址实现
本课练习
分别使用连续整数和固定步长键,比较桶最大长度。再挑一个落在空桶的缺失键与一个落在长链的缺失键,对比同一张表上的失败成本。下一课介绍只回答“可能存在”的布隆过滤器。