哈希表(开放寻址法)
介绍
哈希表(Hash Table)是一种高效的数据结构,能够实现近乎 O(1) 时间复杂度的查找、插入和删除操作。开放寻址法(Open Addressing)是解决哈希冲突的一种重要方法,它不使用额外的数据结构(如链表),在哈希表本身的空间内寻找可用位置来存储冲突的元素,从而更加节省内存空间。
基本概念
哈希表(Hash Table)是一种基于哈希函数直接访问元素的数据结构,理解开放寻址法需要先掌握以下基础概念:
哈希函数(Hash Function):将输入数据映射到哈希表索引范围内的函数。理想的哈希函数应该计算快速且均匀分布元素。
哈希冲突(Hash Collision):当两个不同的键通过哈希函数得到相同的索引值时发生的情况。
开放寻址法(Open Addressing):解决哈希冲突的方法,其核心思想是:
- 当发生冲突时,通过特定的探测序列寻找表中的下一个可用位置
- 所有元素都直接存储在哈希表中,不使用额外的数据结构
- 每个桶只存储一个元素,表中的空间可分为三种状态:空闲、占用、删除
开放寻址法的主要探测技术包括:
- 线性探测(Linear Probing):
- 最简单的探测方法,冲突发生时,按顺序检查下一个位置
- 探测序列:h(k), (h(k) + 1) % m, (h(k) + 2) % m, ..., (h(k) + m-1) % m
- 优点:缓存友好;缺点:容易产生聚集
- 二次探测(Quadratic Probing):
- 通过平方级数增长的步长来寻找空位置
- 探测序列:h(k), (h(k) + 1²) % m, (h(k) + 2²) % m, (h(k) + 3²) % m, ...
- 优点:减少聚集;缺点:不保证能探测所有位置
- 双重哈希(Double Hashing):
- 使用第二个哈希函数确定探测步长
- 探测序列:h₁(k), (h₁(k) + h₂(k)) % m, (h₁(k) + 2h₂(k)) % m, ...
- 优点:减少聚集,增加探测路径多样性;缺点:需要计算两次哈希值
装载因子(Load Factor):表中已占用位置与表容量的比值,用 α 表示。当 α 增大时,冲突概率增加,性能下降。通常当 α 超过某个阈值(如 0.7)时进行扩容。
示例:
假设有一个大小为 7 的哈希表,使用简单的哈希函数 h(k) = k % 7 和线性探测。现在需要插入键:10, 21, 32, 17。
计算过程:
- h(10) = 10 % 7 = 3,将 10 存入索引 3
- h(21) = 21 % 7 = 0,将 21 存入索引 0
- h(32) = 32 % 7 = 4,将 32 存入索引 4
- h(17) = 17 % 7 = 3,但索引 3 已被 10 占用,按线性探测,尝试索引 4,已被 32 占用,继续尝试索引 5,可用,将 17 存入索引 5
最终哈希表结构为:[21, _, _, 10, 32, 17, _],其中 _ 表示空位置。
核心特性
- 空间效率:所有元素直接存储在表中,不需要额外指针,节省空间
- 缓存友好:特别是线性探测法,元素存储紧凑,有利于缓存局部性
- 灵活性:可以根据应用需求选择不同的探测策略
- 负载敏感:性能受装载因子影响显著,需要及时扩容维持性能
基本操作
- 插入(put):计算哈希值,如遇冲突则根据探测策略寻找下一个可用位置
- 查找(get):计算哈希值,在探测序列上查找,直到找到目标键或遇到空位置
- 删除(remove):计算哈希值,找到元素后不能直接标记为空闲,而是标记为已删除
- 扩容(resize):当装载因子超过阈值时,创建更大的表并重新哈希所有元素
基础实现
在大多数语言中都有哈希表的实现,比如 Java 中的 HashMap、Python 中的 dict 和 collections.defaultdict、JavaScript 中的 Object 和 Map、Go 中的 map 以及 C++ 中的 std::unordered_map,这些内置实现已经高度优化,能够有效处理哈希冲突并提供稳定的性能,所以这里不再提供自定义实现。
优缺点
优点:
- 内存效率高:不需要额外的链表结构和指针,节省空间
- 缓存友好:数据存储紧凑,有利于 CPU 缓存
- 实现简单:尤其是线性探测,实现逻辑相对简单
- 扩展性好:可以结合不同的探测策略适应不同的应用场景
缺点:
- 聚集问题:尤其是线性探测容易产生基本聚集(primary clustering)现象
- 装载因子限制:通常需要保持较低的装载因子(如 <0.7)才能维持性能
- 删除操作复杂:需要特殊处理删除操作,避免破坏探测链
- 全表重建:扩容时需要重新哈希所有元素,成本较高
应用场景
- 对内存使用敏感的环境:嵌入式系统或内存受限的应用
- 适合元素大小相对固定的场景
- 对缓存性能敏感的高性能计算
- 需要高效查找和简单实现的小型应用
- 适合装载因子可预测或可控制的场景
- 实现高性能的集合(Set)数据结构
扩展
常见的变种与改进
线性探测的改进
线性探测虽然简单,但存在严重的聚集问题。实践中常用以下技术改进:
- 带间隔的线性探测:不是每次加1,而是加一个质数(如7),减少聚集
- 伪随机序列:使用简单的伪随机数生成器创建探测序列,打破规则模式
混合策略
在实际应用中,经常采用混合策略结合多种方法的优点:
- 桶式开放寻址法:每个位置存储固定数量(如4个)的元素,减少冲突同时保持缓存友好
- 链接-开放混合:当冲突达到一定程度时,从开放寻址转为链式存储
实际应用中的考量
装载因子的选择
不同探测策略下的最佳装载因子不同:
- 线性探测:通常保持在0.5-0.7之间
- 二次探测:可以稍高,约0.7-0.8
- 双重哈希:可以更高,达到0.8-0.9
测验
- 在使用线性探测的开放寻址哈希表中,什么是"基本聚集"(primary clustering)?它如何影响哈希表性能?
- 开放寻址法中的删除操作为什么不能直接将位置标记为空(null)?这会导致什么问题?
- 在同样大小的哈希表中,假设装载因子为 0.8,开放寻址法和链地址法哪种方法的查找性能更好?为什么?
测验答案
- 基本聚集是指在线性探测中连续被占用的位置形成的"群集"现象。当一个位置发生冲突时,会占用下一个位置,导致对后续哈希到这些位置的键产生更多冲突,形成越来越长的连续占用区域。这会显著降低查找和插入操作的性能,因为探测长度增加。
- 不能直接标记为空,因为这会中断探测链。在开放寻址法中,探测序列遇到空位置时停止,表示元素不存在。如果删除操作简单地将位置标记为空,会导致原本能找到的后续插入的元素无法被找到。因此需要特殊的"已删除"标记。
- 通常情况下,在高装载因子(如0.8)时,链地址法的性能更好。因为开放寻址法在高装载因子时探测序列变长,查找性能下降明显;链地址法即使在高装载因子下,只要哈希函数分布均匀,每个链表的平均长度仍然可控。开放寻址法通常需要保持较低的装载因子(如<0.7)才能维持良好性能。
相关的 LeetCode 热门题目