哈希表（Hash Table）是一种用于存储键值对的数据结构，可以通过哈希函数快速地根据键找到对应的值。哈希表的查找、插入和删除操作在平均情况下具有 O(1) 的时间复杂度，非常高效。

1. 哈希表的基本概念

哈希表的核心思想是将键通过一个哈希函数（Hash Function）映射到一个哈希表的索引位置上。若两个键映射到同一位置（即出现哈希冲突），则需要解决冲突以保证数据存储的正确性。

哈希表的术语

  • 哈希函数：将键映射到表中某个位置的函数。
  • 哈希冲突：两个不同的键被映射到同一个位置。
  • 装载因子：表中已填充元素的数量与哈希表大小的比值。较高的装载因子会增加冲突发生的可能性。

2. 哈希表的实现方式

哈希表的常用实现方式主要有两种：

  1. 开放寻址法：在发生冲突时，通过寻找其他空闲位置来存储元素。常见的开放寻址方法包括线性探测、二次探测和双重哈希。
  2. 链地址法（拉链法）：在每个哈希表位置存储一个链表，在发生冲突时将新元素插入到链表中。

3. 哈希表的 C++ 实现

使用链地址法（拉链法）的 C++ 实现

我们可以使用一个数组加链表的结构来实现哈希表。每个数组元素是一个链表，用于解决哈希冲突。

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
#include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
private:
    vector<list<int>> table;  // 哈希表的数组，每个位置是一个链表
    int size;                 // 哈希表的大小

    // 哈希函数：简单取模法
    int hashFunction(int key) {
        return key % size;
    }

public:
    HashTable(int s) : size(s) {
        table.resize(size);
    }

    // 插入操作
    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    // 删除操作
    void remove(int key) {
        int index = hashFunction(key);
        table[index].remove(key);
    }

    // 查找操作
    bool search(int key) {
        int index = hashFunction(key);
        for (auto& element : table[index]) {
            if (element == key) return true;
        }
        return false;
    }

    // 显示哈希表
    void display() {
        for (int i = 0; i < size; ++i) {
            cout << "Index " << i << ": ";
            for (auto& element : table[i]) {
                cout << element << " -> ";
            }
            cout << "NULL" << endl;
        }
    }
};

int main() {
    HashTable hashTable(7); // 创建大小为 7 的哈希表
    hashTable.insert(10);
    hashTable.insert(20);
    hashTable.insert(15);
    hashTable.insert(7);
    hashTable.insert(14);

    cout << "Hash Table:" << endl;
    hashTable.display();

    cout << "Searching for 15: " << (hashTable.search(15) ? "Found" : "Not Found") << endl;
    hashTable.remove(15);
    cout << "After removing 15:" << endl;
    hashTable.display();

    return 0;
}

解释

  • 哈希函数：这里我们用简单的取模方法，将键值对映射到表中的某个位置。hashFunction(int key) 通过 key % size 计算索引。
  • 插入操作：将元素插入到哈希表中指定索引的链表中。
  • 删除操作：从哈希表中指定索引的链表中删除目标元素。
  • 查找操作：检查目标元素是否在哈希表的某个位置的链表中。

开放寻址法的几种探测方法

  1. 线性探测（Linear Probing）：冲突时按固定步长（通常为 1）查找下一个空位。
  2. 二次探测（Quadratic Probing）：冲突时按二次方步长查找下一个空位，步长逐渐增加以避免簇现象。
  3. 双重哈希（Double Hashing）：使用两个哈希函数，当冲突发生时，通过第二个哈希函数计算步长。

下面我们以线性探测法为例，展示开放寻址法的实现。

使用开放寻址法的哈希表 C++ 实现

基本思想

  • 使用一个数组保存元素，初始值为 -1 或 nullptr 表示该位置空闲。
  • 插入元素时，如果计算出的索引位置被占用，则按探测策略查找下一个位置。
  • 删除元素时，采用标记（例如 -2）表示“删除状态”，这样在查找时不会打断探测链。
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
96
97
#include <iostream>
#include <vector>
using namespace std;

class OpenAddressHashTable {
private:
    vector<int> table; // 哈希表数组
    int size;

    // 哈希函数：简单取模
    int hashFunction(int key) {
        return key % size;
    }

public:
    OpenAddressHashTable(int s) : size(s) {
        table.resize(size, -1); // -1 表示空闲位置
    }

    // 插入操作
    bool insert(int key) {
        int index = hashFunction(key);

        // 线性探测
        for (int i = 0; i < size; ++i) {
            int probeIndex = (index + i) % size;  // 线性探测
            if (table[probeIndex] == -1 || table[probeIndex] == -2) { // 找到空闲或已删除位置
                table[probeIndex] = key;
                return true;
            }
        }
        return false; // 哈希表已满
    }

    // 删除操作
    bool remove(int key) {
        int index = hashFunction(key);

        // 线性探测
        for (int i = 0; i < size; ++i) {
            int probeIndex = (index + i) % size;
            if (table[probeIndex] == key) {  // 找到目标元素
                table[probeIndex] = -2; // -2 标记删除状态
                return true;
            }
            if (table[probeIndex] == -1) {  // 没找到且遇到空闲位置，停止查找
                return false;
            }
        }
        return false;
    }

    // 查找操作
    bool search(int key) {
        int index = hashFunction(key);

        // 线性探测
        for (int i = 0; i < size; ++i) {
            int probeIndex = (index + i) % size;
            if (table[probeIndex] == key) return true;   // 找到目标元素
            if (table[probeIndex] == -1) return false;   // 找到空闲位置，停止查找
        }
        return false;
    }

    // 显示哈希表
    void display() {
        for (int i = 0; i < size; ++i) {
            if (table[i] >= 0)
                cout << "Index " << i << ": " << table[i] << endl;
            else if (table[i] == -2)
                cout << "Index " << i << ": [Deleted]" << endl;
            else
                cout << "Index " << i << ": [Empty]" << endl;
        }
    }
};

int main() {
    OpenAddressHashTable hashTable(7); // 创建大小为 7 的哈希表

    hashTable.insert(10);
    hashTable.insert(20);
    hashTable.insert(15);
    hashTable.insert(7);
    hashTable.insert(14);

    cout << "Hash Table:" << endl;
    hashTable.display();

    cout << "Searching for 15: " << (hashTable.search(15) ? "Found" : "Not Found") << endl;
    hashTable.remove(15);
    cout << "After removing 15:" << endl;
    hashTable.display();

    return 0;
}

解释

  • 哈希函数：使用 key % size 计算元素的初始索引位置。
  • 线性探测：在发生冲突时，通过逐次递增索引来查找下一个空闲位置，直到找到空位或返回失败。
  • 删除标记：删除元素时，将该位置标记为 -2（表示已删除），防止探测链的中断。-1 表示空闲位置。
  • 查找与删除：查找元素时遇到 -1 即可停止查找，遇到 -2 则继续探测链。

其他探测方法简述

  1. 二次探测：冲突时探测间隔为 $( i^2 )$ （如 index + i^2）。这样可以避免线性探测中的“主簇”问题，但可能引入新的探测区域。
  2. 双重哈希：冲突时通过第二个哈希函数计算步长，跳跃性地寻找位置，减少了探测链的聚集现象。

开放寻址法通常比链地址法更节省空间，但当装载因子过高时，开放寻址法的性能下降更明显。