哈希表(开放寻址法)

算法

通过哈希函数将键映射到数组的索引,使用开放寻址法(线性探测)处理哈希冲突,提供近乎O(1)的查找、插入和删除操作。

空间复杂度:O(n)

算法讲解

哈希表(开放寻址法)

介绍

哈希表(Hash Table)是一种高效的数据结构,能够实现近乎 O(1) 时间复杂度的查找、插入和删除操作。开放寻址法(Open Addressing)是解决哈希冲突的一种重要方法,它不使用额外的数据结构(如链表),在哈希表本身的空间内寻找可用位置来存储冲突的元素,从而更加节省内存空间。

基本概念

哈希表(Hash Table)是一种基于哈希函数直接访问元素的数据结构,理解开放寻址法需要先掌握以下基础概念:

哈希函数(Hash Function):将输入数据映射到哈希表索引范围内的函数。理想的哈希函数应该计算快速且均匀分布元素。

哈希冲突(Hash Collision):当两个不同的键通过哈希函数得到相同的索引值时发生的情况。

开放寻址法(Open Addressing):解决哈希冲突的方法,其核心思想是:

  • 当发生冲突时,通过特定的探测序列寻找表中的下一个可用位置
  • 所有元素都直接存储在哈希表中,不使用额外的数据结构
  • 每个桶只存储一个元素,表中的空间可分为三种状态:空闲、占用、删除

开放寻址法的主要探测技术包括:

  1. 线性探测(Linear Probing):
    • 最简单的探测方法,冲突发生时,按顺序检查下一个位置
    • 探测序列:h(k), (h(k) + 1) % m, (h(k) + 2) % m, ..., (h(k) + m-1) % m
    • 优点:缓存友好;缺点:容易产生聚集
  2. 二次探测(Quadratic Probing):
    • 通过平方级数增长的步长来寻找空位置
    • 探测序列:h(k), (h(k) + 1²) % m, (h(k) + 2²) % m, (h(k) + 3²) % m, ...
    • 优点:减少聚集;缺点:不保证能探测所有位置
  3. 双重哈希(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

测验

  1. 在使用线性探测的开放寻址哈希表中,什么是"基本聚集"(primary clustering)?它如何影响哈希表性能?
  2. 开放寻址法中的删除操作为什么不能直接将位置标记为空(null)?这会导致什么问题?
  3. 在同样大小的哈希表中,假设装载因子为 0.8,开放寻址法和链地址法哪种方法的查找性能更好?为什么?

测验答案

  1. 基本聚集是指在线性探测中连续被占用的位置形成的"群集"现象。当一个位置发生冲突时,会占用下一个位置,导致对后续哈希到这些位置的键产生更多冲突,形成越来越长的连续占用区域。这会显著降低查找和插入操作的性能,因为探测长度增加。
  2. 不能直接标记为空,因为这会中断探测链。在开放寻址法中,探测序列遇到空位置时停止,表示元素不存在。如果删除操作简单地将位置标记为空,会导致原本能找到的后续插入的元素无法被找到。因此需要特殊的"已删除"标记。
  3. 通常情况下,在高装载因子(如0.8)时,链地址法的性能更好。因为开放寻址法在高装载因子时探测序列变长,查找性能下降明显;链地址法即使在高装载因子下,只要哈希函数分布均匀,每个链表的平均长度仍然可控。开放寻址法通常需要保持较低的装载因子(如<0.7)才能维持良好性能。

相关的 LeetCode 热门题目