哈希表 (Hash Table)

哈希表 (Hash Table) / 散列表

概念：通过哈希函数将键 (Key) 映射到值 (Value) 的数据结构，实现快速查找

想象一下，你有一个巨大的图书馆，里面藏书无数。 如果你要找一本书，最笨的方法就是一本一本地找，这显然效率极低。但如果图书馆采用了 图书索引系统，比如按照书名的首字母分类，然后每个首字母下面再细分，你就可以根据书名快速定位到书籍所在的位置。

哈希表 (Hash Table) ，又叫 散列表，就类似于图书馆的图书索引系统。 它是一种非常高效的数据结构，用于实现 键值对 (Key-Value Pair) 的快速查找。你可以通过一个 键 (Key) 快速找到与之关联的 值 (Value) 。

哈希表数据结构示意图

哈希函数 (Hash Function)：将键转换为索引的函数

哈希函数 (Hash Function) 是哈希表的核心。 它的作用就像图书索引系统中的分类规则，将任意类型的键 (Key) 转换为一个固定范围内的整数，这个整数被称为哈希值或哈希码 (Hash Code) 。 这个哈希值通常被用作 哈希表数组的索引 (Index) ，从而确定键值对在哈希表中的存储位置。

  • 作用： 将键 (Key) 映射到哈希表中的索引位置。
  • 特性：
    • 确定性： 对于相同的输入键，哈希函数必须始终产生相同的哈希值。
    • 高效性： 计算哈希值的过程应该尽可能快速高效，不能成为性能瓶颈。
    • 均匀分布性 (理想情况)： 好的哈希函数应该尽可能将不同的键均匀地映射到哈希表的各个索引位置，减少 冲突 (Collision) 的发生（后面会讲到）。

简单的哈希函数示例 (将字符串键转换为索引 - 仅为演示概念，实际应用中可能不够好):

假设哈希表的大小为 10 (索引范围 0-9)，要将字符串键 “apple”, “banana”, “cherry” 映射到索引。 可以设计一个简单的哈希函数，将字符串的第一个字符的 ASCII 值对 10 取模：

  • hash("apple") = ASCII('a') % 10 = 97 % 10 = 7
  • hash("banana") = ASCII('b') % 10 = 98 % 10 = 8
  • hash("cherry") = ASCII('c') % 10 = 99 % 10 = 9

这样，”apple” 就被映射到索引 7，”banana” 映射到索引 8，”cherry” 映射到索引 9。

冲突 (Collision)：不同的键映射到相同的索引

由于哈希函数的输出范围是有限的（哈希表的大小是有限的），而输入键的范围可能是无限的，不同的键 (Key) 可能会被哈希函数映射到相同的索引位置，这种情况称为冲突 (Collision) 。

例如，如果哈希表大小仍然是 10，哈希函数仍然是取首字母 ASCII 值对 10 取模，这时如果再插入键 “apricot”：

  • hash("apricot") = ASCII('a') % 10 = 97 % 10 = 7

“apricot” 和 “apple” 的哈希值都是 7，发生了冲突，它们被映射到了相同的索引位置 7。

冲突是哈希表中不可避免的问题。 好的哈希函数可以尽可能减少冲突的发生，但无法完全避免。

解决冲突 是哈希表设计中非常重要的一个环节。

常见的冲突解决方法有两种： 链地址法 (Separate Chaining) 和 开放寻址法 (Open Addressing) 。

冲突解决方法 (Collision Resolution Methods)

  1. 链地址法 (Separate Chaining)：

    链地址法 是最常用的一种冲突解决方法。 它的思想是： 如果多个键被哈希到同一个索引位置，就在该索引位置创建一个链表 (Linked List)，将所有冲突的键值对都存储到这个链表中。

    • 工作原理：
      a. 当要插入一个新的键值对时，首先通过哈希函数计算键的索引位置。
      b. 如果该索引位置已经有元素（说明发生了冲突），就将新的键值对 添加到该索引位置的链表的末尾。
      c. 当要查找一个键时，首先计算键的索引位置。
      d. 然后在该索引位置的链表中 顺序查找 目标键，如果找到，则返回对应的值。

    • 优点：

      • 实现简单： 链地址法实现相对简单，只需要使用链表这种基本数据结构即可。

    • 处理冲突能力强： 即使冲突比较严重，链表也能容纳更多的冲突元素，哈希表的性能下降相对平缓。

      • 删除操作简单： 删除节点只需要在链表中进行删除操作，不会影响到其他索引位置的元素。

    • 缺点：

      • 空间开销： 链地址法需要额外的空间来存储链表节点，如果哈希表存储的元素较少，但哈希表本身的空间占用较多，空间利用率不高。

    • 查找效率可能下降： 如果某个索引位置的链表过长（冲突过多），在该链表中查找元素的时间复杂度会退化为 O(n) (n 为链表长度)，影响哈希表的整体查找效率。

  2. 开放寻址法 (Open Addressing)：

    开放寻址法 的核心思想是： 如果发生冲突，就继续在哈希表中寻找下一个可用的空闲位置，将冲突的键值对存储到这个空闲位置。 寻找下一个空闲位置的方法称为 探测 (Probing) 。

    • 探测方法 (Probing Techniques)： 常见的探测方法有：

      • 线性探测 (Linear Probing)： 如果索引 i 发生冲突，就依次检查 i+1, i+2, i+3… 等索引位置，直到找到空闲位置。 容易产生 聚集 (Clustering) 现象，即冲突元素会聚集在某些连续的索引位置，导致后续查找效率下降。

    • 二次探测 (Quadratic Probing)： 为了减少聚集现象，二次探测使用平方步长来寻找空闲位置。 例如，如果索引 i 冲突，就依次检查 i+1^2, i-1^2, i+2^2, i-2^2… 等索引位置。 可以一定程度上缓解聚集现象。

      • 双重哈希 (Double Hashing)： 使用 两个哈希函数。 第一个哈希函数 hash1(key) 用于计算初始索引位置。 如果发生冲突，使用 第二个哈希函数 hash2(key) 计算探测步长，例如，依次检查 i + hash2(key), i + 2*hash2(key), i + 3*hash2(key)… 等索引位置。 双重哈希可以更有效地避免聚集现象，散列性能更好。

    • 工作原理 (以线性探测为例)：
      a. 当要插入一个新的键值对时，首先通过哈希函数计算键的初始索引位置 i。
      b. 如果索引 i 为空闲位置，则将键值对存储到该位置。
      c. 如果索引 i 已被占用（发生冲突），则使用线性探测，检查 i+1, i+2, i+3… 等索引位置，直到找到第一个空闲位置，将键值对存储到该空闲位置。
      d. 当要查找一个键时，首先计算键的初始索引位置 i。
      e. 如果索引 i 位置的键与目标键相同，则查找成功。
      f. 如果索引 i 位置为空，则查找失败（目标键不存在）。
      g. 如果索引 i 位置的键与目标键不同（发生冲突），则使用相同的探测方法（线性探测），继续检查 i+1, i+2, i+3… 等索引位置，直到找到目标键或遇到空位置。

    • 优点：

      • 空间利用率高： 开放寻址法将所有键值对都直接存储在哈希表数组中，没有链表等额外的空间开销，空间利用率更高。

    • 缓存友好性： 由于键值对存储在连续的数组中，缓存命中率可能更高，对 CPU 缓存更友好，在某些情况下可以提升性能。

    • 缺点：

      • 删除操作复杂： 删除节点不能简单地将位置置为空，否则可能会中断后续查找的探测链，需要使用特殊的 标记 来处理删除操作，实现较为复杂。

    • 容易产生聚集现象： 线性探测等方法容易产生聚集现象，导致冲突元素扎堆，影响哈希表的性能，尤其是在哈希表 负载因子 (Load Factor) 较高时（即哈希表中已存储元素占总容量的比例较高时）。

      • 扩容代价高： 当哈希表需要扩容时，所有已存储的键值对都需要 重新哈希 并插入到新的哈希表中，开销较大。

哈希表简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include <list>

// 哈希表类
template <typename K, typename V> // 使用模板，使哈希表可以存储不同类型的数据
class HashTable {
private:
    std::vector<std::list<std::pair<K, V>>> table; // 哈希表，使用 vector 存储链表
    int size; // 哈希表大小

    // 哈希函数，将键转换为索引
    int hashFunction(const K& key) const {
        // 这里使用简单的取模法，将键的哈希值对表大小取模
        // 实际应用中，可以使用更复杂的哈希函数，以减少冲突
        return std::hash<K>{}(key) % size;
    }

public:
    // 构造函数，初始化哈希表
    HashTable(int size) : size(size), table(size) {}

    // 插入键值对
    void insert(const K& key, const V& value) {
        int index = hashFunction(key); // 计算索引
        // 在链表中查找是否已存在相同的键
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                // 如果存在，则更新值
                pair.second = value;
                return;
            }
        }
        // 如果不存在，则将键值对添加到链表的头部
        table[index].push_front({key, value});
    }

    // 获取值
    V get(const K& key) const {
        int index = hashFunction(key); // 计算索引
        // 在链表中查找键
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                // 如果找到，则返回值
                return pair.second;
            }
        }
        // 如果找不到，则抛出异常
        throw std::out_of_range("Key not found");
    }

    // 删除键值对
    void remove(const K& key) {
        int index = hashFunction(key); // 计算索引
        // 在链表中查找键
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                // 如果找到，则删除该键值对
                table[index].erase(it);
                return;
            }
        }
        // 如果找不到，则抛出异常
        throw std::out_of_range("Key not found");
    }

    // 打印哈希表
    void print() const {
        for (int i = 0; i < size; ++i) {
            std::cout << "Bucket " << i << ": ";
            for (const auto& pair : table[i]) {
                std::cout << "(" << pair.first << ", " << pair.second << ") ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    HashTable<std::string, int> ht(10); // 创建一个大小为 10 的哈希表

    ht.insert("apple", 1);
    ht.insert("banana", 2);
    ht.insert("orange", 3);

    ht.print(); // 打印哈希表

    std::cout << "Value of banana: " << ht.get("banana") << std::endl; // 输出：2

    ht.remove("banana");

    ht.print(); // 打印删除后的哈希表

    return 0;
}

适用场景 (Use Cases)

哈希表以其 平均常数时间 O(1) 的快速查找、插入、删除操作，在各种需要 高效键值对操作 的场景中得到广泛应用：

  1. 快速查找 (Fast Lookup)： 这是哈希表最核心的应用场景。 例如：

    • 字典 (Dictionary) / 映射 (Map)： 编程语言中的字典、映射数据结构，例如 Python 的 dict，Java 的 HashMap，C++ 的 unordered_map，底层通常都是基于哈希表实现的。 用于快速查找键对应的值。
    • 数据库索引： 数据库索引可以使用哈希表来加速记录的查找，例如在键值数据库 (Key-Value Database) 中，哈希表是核心数据结构。
    • 缓存 (Cache)： 缓存系统 (例如 Redis, Memcached) 可以使用哈希表来存储缓存数据，实现快速的缓存读取和写入。

  2. 缓存 (Caching)： 哈希表可以作为高效的缓存数据结构。 将经常访问的数据存储在哈希表中，可以大大提高数据访问速度。 例如：

    • Web 缓存： 浏览器缓存、CDN 缓存、服务器缓存等，可以使用哈希表来存储缓存的网页、图片、文件等资源。
    • 内存缓存： 应用程序可以使用哈希表作为内存缓存，缓存热点数据，减少对磁盘或数据库的访问。

  3. 索引 (Indexing)： 哈希表可以用于构建索引，加速数据检索。 例如：

    • 搜索引擎索引： 搜索引擎可以使用哈希表来构建倒排索引，快速查找包含特定关键词的文档。
    • DNS 解析： DNS 服务器可以使用哈希表来缓存域名和 IP 地址的映射关系，加速域名解析过程。

  4. 其他应用场景：

    • 集合 (Set)： 哈希集合 (Hash Set) 可以使用哈希表来存储元素，实现快速的元素查找和去重。 例如 Python 的 set，Java 的 HashSet，C++ 的 unordered_set。
    • 编译器的符号表： 编译器可以使用哈希表来存储程序中的变量名和其对应的内存地址等信息，方便快速查找和访问变量。
    • 数据校验 (Data Validation)： 哈希值可以用于数据校验，例如，计算文件的哈希值，可以用来验证文件在传输过程中是否被篡改。
    • 密码学应用： 哈希函数在密码学领域有广泛应用，例如，密码哈希、数字签名、消息认证码等。 但密码学哈希函数与数据结构哈希表使用的哈希函数有所不同，密码学哈希函数更注重安全性，例如抗碰撞性、抗原像攻击性等。

总结

哈希表是一种非常重要且实用的数据结构，它以其高效的平均查找、插入、删除性能，成为构建高性能系统的关键组件。 理解哈希表的原理、哈希函数的设计、冲突解决策略，以及各种应用场景，能够帮助你更好地选择和使用合适的数据结构，解决实际问题。 在后续的学习中，你会在更多高级数据结构和算法的应用中看到哈希表的身影。

计算机科学基础 > 数据结构 > 初学者入门 > 3.进阶数据结构
#数据结构 #哈希表
哈希表 (Hash Table)
https://god23bin.github.io/unreal-engine-blog/2025/01/01/cs/ds/ds-for-beginner/advanced-ds/哈希表/
作者
god23bin
发布于
2025年1月1日
许可协议