哈希表入门

哈希表入门

哈希表（Hash Table）也叫散列表，是一种非常常用的数据结构。我们先从一个简单的例子入手：

假设你有很多学生的名字和对应的学号，你想通过名字快速查到学号。最直接的做法是：

  1. 用一个很长的数组 arr，数组下标是名字的第一个字母的 ASCII 码。
  2. 写一个函数 f，把名字转成下标。

比如：

1
2
3
func f(key string) int {
    return int(key[0])
}

这样 arr[f(“Alice”)] 就能存 Alice 对应的学号。

这就是哈希表的雏形。我们可以继续改进：
其中 arr就是 hash表，f就是hash函数

哈希冲突

但这样有个问题：如果两个名字的首字母一样，比如 “Alice” 和 “Amy”，它们会被放到同一个位置，后面的会覆盖前面的。

用更复杂的哈希函数，比如把所有字符都参与进来：

1
2
3
4
5
6
7
8
//合适的哈希函数可以减少哈希冲突
func f(key string) int {
    sum := 0
    for i := 0; i < len(key); i++ {
        sum += int(key[i])
    }
    return sum % 256
}

但是任何哈希函数都无法完全避免哈希冲突，当发生冲突时，需要想办法解决

拉链法

拉链法（Separate Chaining）是解决哈希冲突最常用的方法之一。它的做法是：

  • 哈希表的每个位置不再是一个单独的元素，而是一个链表（或其他结构，如动态数组）。
  • 当多个 key 经过哈希函数映射到同一个位置时，这些 key 对应的元素就被插入到该位置的链表中。

示意图：

哈希表下标 链表内容
0 [key1, key2]
1 [key3]
2 [key4, key5, key6]

查找时，先通过哈希函数定位到下标，再在链表中顺序查找。

优点：实现简单，负载高时性能下降不明显。
缺点：需要额外的链表存储空间。

开放地址法

开放地址法（Open Addressing）是另一种常见的哈希冲突解决方法。

  • 当发生冲突时，不是用链表存储冲突元素，而是在哈希表内寻找下一个空位。
  • 常见的探查方式有：
    • 线性探查（Linear Probing）：依次往后找空位。
    • 二次探查（Quadratic Probing）：按照二次函数间隔找空位。
    • 双重哈希（Double Hashing）：用第二个哈希函数计算步长。

示例（线性探查）：
假设 key1 和 key2 都映射到下标 5，key1 占了 5，key2 就去找 6，如果 6 也被占了，就找 7，直到找到空位。

优点：不需要链表，节省空间。
缺点：负载高时容易出现“堆积”现象，查找效率下降。

哈希表的常见应用

哈希表能够实现的大多数功能，基于树状结构的 map（如红黑树、AVL 树等）同样可以完成。但哈希表（HashMap）在查找和插入操作上通常更高效，平均时间复杂度为 $O(1)$，而树状结构 map 的查找和插入为 $O(\log n)$。不过，哈希表在空间利用率和内存消耗上通常不如树状结构 map，因此在实际应用中需要根据性能和内存需求进行权衡选择。

  1. 快速查找与去重

    • 原理：哈希表通过哈希函数将元素映射到唯一的下标位置，插入和查找的平均时间复杂度为 $O(1)$。判断元素是否存在时，只需查找对应下标即可，无需遍历所有元素。
    • 应用：如判重、统计唯一元素个数。例如，判断一个数组中是否有重复元素时，将每个元素插入哈希表，若发现已存在则说明有重复。

  2. 计数统计

    • 原理：哈希表的 value 可以存储计数信息。每遇到一个元素，就以该元素为 key，计数为 value，若已存在则自增。
    • 应用：如统计单词出现频率、字符计数等。遍历数据时，利用哈希表高效更新和查询计数。

  3. 映射关系存储

    • 原理：哈希表天生适合存储 key-value 关系。通过哈希函数定位 key 的存储位置，查找和插入都非常高效。
    • 应用：如用户名到用户信息、商品编号到商品详情等映射。只需通过 key 即可快速获取对应 value。

  4. 缓存（如 LRU 缓存）

    • 原理：哈希表用于缓存系统时，可以实现对缓存项的快速定位和更新。结合链表等结构可实现 LRU（最近最少使用）缓存淘汰策略。
    • 应用：如浏览器缓存、数据库缓存等。哈希表保证了缓存命中的高效率。

  5. 哈希加密/摘要

    • 原理：哈希函数可将任意长度的数据映射为定长的哈希值，用于数据摘要、签名、密码存储等安全场景。哈希表本身不是加密算法，但其底层依赖哈希函数。
    • 应用：如密码校验、文件完整性校验、数字签名等。

  6. 集合与映射类数据结构的底层实现

    • 原理：许多高级语言的 set、map、dict、unordered_map 等集合和映射类数据结构，底层都用哈希表实现，利用其高效的查找和插入特性。
    • 应用：如 Python 的 dict/set，C++ 的 unordered_map/unordered_set，Java 的 HashMap/HashSet 等。

  7. 负载均衡与分布式一致性哈希

    • 原理：分布式系统中，哈希表可用于将数据均匀分布到不同节点，实现负载均衡。通过一致性哈希算法，可以在节点变动时减少数据迁移量。
    • 应用：如分布式缓存、分布式存储、分布式数据库等场景。

哈希表的复杂度分析

  • 插入、查找、删除的平均时间复杂度都是 $O(1)$。
  • 最坏情况下（所有元素都冲突），时间复杂度为 $O(n)$，但实际应用中只要哈希函数设计合理、负载因子控制得当，性能非常优秀。

总结

哈希表是一种高效、实用的数据结构，广泛应用于各种需要快速查找、插入、删除的场景。理解哈希函数和冲突解决方法，是掌握哈希表的关键。