哈希表(链地址法)

算法

通过哈希函数将键映射到数组的索引,使用链表处理哈希冲突。提供近乎O(1)的查找、插入和删除操作。

空间复杂度:O(n)

算法讲解

哈希表(链地址法)

介绍

哈希表(Hash Table)是一种高效的数据结构,能够实现快速的插入、查找和删除操作。链地址法(Chaining)是解决哈希冲突的一种常用方法,它通过为每个哈希桶维护一个链表,将具有相同哈希值的元素存储在同一链表中,从而有效处理冲突问题。

基本概念

哈希表(Hash Table)是一种基于哈希函数直接访问元素的数据结构,理解它需要先掌握几个关键概念:

哈希函数(Hash Function):将输入数据(通常是无限范围)映射到有限范围(哈希表大小)的函数。一个好的哈希函数应该能够均匀分布元素,最小化冲突。

哈希值(Hash Value):哈希函数的输出结果,用作哈希表中的索引。

哈希桶(Bucket):哈希表中存储元素的位置,每个桶对应一个哈希值。

哈希冲突(Hash Collision):当两个不同的输入通过哈希函数产生相同的哈希值时发生冲突。由于哈希表空间有限而可能的输入数据无限,冲突不可避免。

链地址法(Chaining):解决哈希冲突的一种方法,其基本思想是:

  • 每个哈希桶维护一个链表
  • 当发生冲突时,将新元素添加到对应哈希桶的链表中
  • 查找元素时,先计算哈希值找到对应桶,然后在链表中搜索目标元素

哈希表的负载因子(Load Factor):表中元素数量与哈希表大小的比值。当负载因子增大时,链表长度可能增加,导致性能下降。

示例:
假设有一个大小为 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,将 (17, "葡萄") 存入索引 3 的链表,与 (10, "苹果") 在同一链表中

最终哈希表结构为:

▼
Plain
复制代码
0: → (21, "香蕉") → null 1: → null 2: → null 3: → (10, "苹果") → (17, "葡萄") → null 4: → (32, "橙子") → null 5: → null 6: → null

可以看到索引 3 处有两个元素,这是因为 10 和 17 发生了哈希冲突,它们通过链表连接在一起。

核心特性

  • 高效操作:平均情况下,插入、查找、删除操作的时间复杂度为 O(1)
  • 冲突处理:使用链表解决哈希冲突,适应性强
  • 动态扩容:当负载因子过高时,可以扩容哈希表以维持性能
  • 无序性:元素在哈希表中的位置由哈希函数决定,不保持插入顺序

基本操作

  • 插入(put):计算键的哈希值,将键值对插入对应桶的链表中
  • 查找(get):计算键的哈希值,在对应桶的链表中查找键值对
  • 删除(remove):计算键的哈希值,从对应桶的链表中移除键值对
  • 判断键是否存在(containsKey):计算键的哈希值,检查对应桶的链表中是否存在该键

基础实现

在大多数语言中都有哈希表的实现,比如 Java 中的 HashMap、Python 中的 dict 和 collections.defaultdict、JavaScript 中的 Object 和 Map、Go 中的 map 以及 C++ 中的 std::unordered_map,这些内置实现已经高度优化,能够有效处理哈希冲突并提供稳定的性能,所以这里不再提供自定义实现。

优缺点

优点:

  • 实现简单:链地址法概念明确,实现相对简单
  • 高效查找:平均情况下,查找操作的时间复杂度接近 O(1)
  • 适应性强:可以处理任意数量的冲突
  • 删除操作简单:不需要复杂的逻辑即可完成删除
  • 扩容策略灵活:可以根据负载因子动态调整哈希表大小

缺点:

  • 额外内存开销:每个节点需要额外的指针存储,增加了内存消耗
  • 不适合缓存局部性:链表中的元素可能散布在内存各处,不利于CPU缓存
  • 链表过长时性能下降:当哈希冲突严重时,操作可能退化为 O(n)
  • 哈希函数敏感:性能严重依赖于哈希函数的质量

应用场景

  • 实现关联数组或字典,如大多数语言的 HashMap/Dictionary 类
  • 数据库索引,特别是哈希索引
  • 缓存系统,如 LRU 缓存的底层结构
  • 符号表,用于编译器和解释器
  • 集合(Set)数据结构的实现
  • 用于快速去重和查找的场景

扩展

链地址法的优化与变体

改进链表结构

传统链地址法使用普通链表存储冲突元素,但可以通过替换链表结构提升性能:

  • 有序链表:保持链表元素有序,可以提前终止查找
  • 自调整链表:将频繁访问的元素移到链表前端,减少平均查找时间
  • 替换为平衡树:对于长链表,可以使用小型平衡树(如红黑树)替代,将最坏情况从O(n)改善为O(log n)

桶大小优化

  • 多元素桶:每个桶预先分配固定空间(如4个元素),当元素少时避免动态分配
  • 两级哈希:在冲突严重的桶中使用第二级哈希表

测验

  1. 在一个使用链地址法的哈希表中,如果负载因子(load factor)为 2,表示什么?这对哈希表性能有何影响?
  2. 如果哈希表的大小为 10,使用哈希函数 h(x) = x % 10,插入元素 {12, 22, 32, 42, 52},请描述哈希表的结构。
  3. 在哈希表中使用链地址法解决冲突时,查找不存在的元素的最坏时间复杂度是多少?为什么?

测验答案

  1. 负载因子为 2 表示哈希表中的元素数量是哈希表大小的两倍,平均每个桶包含 2 个元素。这意味着哈希冲突较多,查找时平均需要比较的元素变多。查找的期望时间复杂度为 O(1 + α),负载因子 α = 2 时仍是常数级,但比负载因子较小时慢,所以通常会在负载因子超过阈值时扩容。
  2. 哈希表结构如下:
    • 桶 2: → (12, value) → (22, value) → (32, value) → (42, value) → (52, value) → null
    • 其他桶 (0,1,3-9): → null
      所有元素都被映射到索引 2 上,形成了一个长链表。
  3. 最坏时间复杂度是 O(n),n 是哈希表中的元素总数。在最坏情况下,所有元素都被哈希到同一个桶中,形成一个长链表,需要遍历整个链表才能确定元素不存在。

相关的 LeetCode 热门题目