哈希表#

哈希表的简介#

哈希表（Hash Table），又称为散列表，是一种基于 键值对（Key-Value Pair） 存储的数据结构。它通过哈希函数将键（Key）映射为数组索引，从而实现高效的插入、查找和删除操作。

哈希表的数学描述#

数学语言上，可以将其看做一种映射，即：

\begin{aligned} f &: X \rightarrow Y \\ &: x_i \mapsto y_i \end{aligned}

其中 X为输入数据的集合，Y为桶下标集合，f为哈希函数。
描述的是一个key经过哈希函数f映射后，得到的一个桶下标。然后将所要的数据存到该桶中，方便后续查询。

当然这是简化版，详细的：(看不懂没关系，不用硬看)

设有有序键序列：

\mathbf{x} = (x_1, x_2, \dots, x_n)， x \in X

定义每个元素的基础哈希函数：

h_i = H_i(x_i), \quad h_i \in \mathbb{N}

定义状态递推的混合函数：

\operatorname{mix}(S, h) = S \;\oplus\; \big( h + C + (S \ll a) + (S \gg b) \big)

其中 $C$ 为常数， $a,b>0$ 为位移参数。

设初始状态：

S_0 = 0

则组合哈希状态按顺序递推为：

S_k = \operatorname{mix}(S_{k-1}, h_k), \quad k = 1, \dots, n

最终组合哈希值为：

S = S_n

若哈希表具有 $m$ 个桶，则键 $\mathbf{x}$ 映射到桶索引 $t$ 的完整映射为：

\boxed{ \begin{aligned} t &= \operatorname{index}(\mathbf{x}) \\ &= S \bmod m \\ &= \Big( \operatorname{foldl} ( \operatorname{mix}, 0, (H_1(x_1), \dots, H_n(x_n)) \Big) \Big) \bmod m \end{aligned} }

哈希表的性能特性#

时间复杂度#

一般为O(1),但这一般要满足没有哈希冲突
这往往意味着桶的数量多但数据较少，且没有人为根据哈希函数去构造的冲突键值对

一旦有冲突，那就需要根据哈希表解决哈希冲突时的方案具体来看了。

空间复杂度#

设：
存储的元素个数：n
桶（bucket）数量：m
负载因子（load factor）：

α = \frac{n}{m}

理论空间复杂度

Space = O(n+m)

O(n)：实际存储的键值对
O(m)：哈希桶数组（哪怕是空桶，也占空间）

在“理想 O(1)”假设下

为了保持 期望时间复杂度 O(1)，必须满足：

α=\frac{n}{m}=O(1) ⇒ Space = O(n)

这里明确说明，有写教学会说哈希表在使用时，是只为出现过的键付空间，显然在底层上可以这么去实现哈希表，但效率往往会非常低，这在后期会提到哈希表的实现为了高效率，会像动态数组那样申请大空间：

哈希表的在哈希冲突上的解决方案#

一般有两个大类：

分离存储（Separate Chaining）
开放定址（Open Addressing）

分离存储（拉链法 / Separate Chaining）#

大意是对桶内多个数据串成链表，然后查找时先通过哈希函数计算得到的桶下标，查找对应桶内链表上是否存在该元素。

开放定址（Open Addressing）#

大意是对一个元素，经过映射后发现桶下标对应的桶内已经有元素，那么就将该元素放到下一个桶，当下一个桶也有元素，则继续查找下一个桶，直到找到一个空桶并放入。

还有一些方法可以在这个视频查看：

哈希表的代码实现(统一c++写)#

tip: 如果要实现一个纯正的哈希表，最好还是了解前面的数学公式哦

1. 先来个简单的，字母到数字的映射：
#

这个很简单，因为用个数组就成功了，哈希函数就是ASCII编码转换而已

1
namespace my{
2
int hash[26] = {0};
3
}
4
void insert(char input) {
5
    if(isupper(input))  ++my::hash[input - 'A'];
6
    if(islower(input))  ++my::hash[input - 'a'];
7
}
8
int find(char input) {
9
    if(isupper(input))  return my::hash[input - 'A'];
10
    if(islower(input))  return my::hash[input - 'a'];
11
}

2. 然后写一个int->int的哈希表，但是这次要求数据和桶下标是不能一样的，不然又是创建一个数组记录就解决的事了#

1
#include <iostream>
2
#include <vector>
3
#include <list>
4

5
class IntHashMap {
6
private:
7
    // 桶的数量
8
    size_t bucket_count;
9
    // 每个桶是一个 list<pair<key,value>>
10
    std::vector<std::list<std::pair<int,int>>> buckets;
11
    // 哈希函数：简单取模
12
    size_t hash(int key) const {
13
        return key % bucket_count;
14
    }
15

16
public:
17
    // 构造函数
18
    IntHashMap(size_t buckets_num = 16) : bucket_count(buckets_num), buckets(buckets_num) {}
19
    // 插入或更新
20
    void put(int key, int value) {
21
        size_t idx = hash(key);
22
        for (auto &p : buckets[idx]) {
23
            if (p.first == key) {
24
                p.second = value; // 更新
25
                return;
26
            }
27
        }
28
        buckets[idx].push_back({key, value}); // 插入
29
    }
30
    // 查询，找不到返回 false
31
    bool get(int key, int &value) const {
32
        size_t idx = hash(key);
33
        for (const auto &p : buckets[idx]) {
34
            if (p.first == key) {
35
                value = p.second;
36
                return true;
37
            }
38
        }
39
        return false;
40
    }
41
    // 删除
42
    bool remove(int key) {
43
        size_t idx = hash(key);
44
        for (auto it = buckets[idx].begin(); it != buckets[idx].end(); ++it) {
45
            if (it->first == key) {
46
                buckets[idx].erase(it);
47
                return true;
48
            }
49
        }
50
        return false;
51
    }
52
    // 打印整个表（调试用）
53
    void print() const {
54
        for (size_t i = 0; i < bucket_count; ++i) {
55
            std::cout << "Bucket " << i << ": ";
56
            for (const auto &p : buckets[i]) {
57
                std::cout << "(" << p.first << "->" << p.second << ") ";
58
            }
59
            std::cout << "\n";
60
        }
61
    }
62
};

测试：

1
int main() {
2
    IntHashMap map(8);
3

4
    map.put(1, 10);
5
    map.put(2, 20);
6
    map.put(10, 100); // 冲突到 bucket 2（10 % 8 = 2）
7

8
    map.print();
9

10
    int value;
11
    if (map.get(2, value)) {
12
        std::cout << "Key 2 -> " << value << "\n";
13
    }
14

15
    map.remove(1);
16
    map.print();
17

18
    return 0;
19
}

输出：

1
Bucket 0:
2
Bucket 1: (1->10)
3
Bucket 2: (2->20) (10->100)
4
Bucket 3:
5
Bucket 4:
6
Bucket 5:
7
Bucket 6:
8
Bucket 7:
9
Key 2 -> 20
10
Bucket 0:
11
Bucket 1:
12
Bucket 2: (2->20) (10->100)
13
Bucket 3:
14
Bucket 4:
15
Bucket 5:
16
Bucket 6:
17
Bucket 7:

可见哈希函数是给元素分配到桶的关键函数。现在这个例子将会侧重于哈希函数的编写,具体的插入等操作交给unordered_map：

3. tuple->int的哈希函数写法#

1
#include <bits/stdc++.h>
2

3
struct TupleHash {
4
    template <typename... Ts>
5
    size_t operator()(const std::tuple<Ts...>& t) const noexcept {
6
        size_t seed = 0;
7
        std::apply([&seed](const Ts&... args) {
8
            ((seed ^= std::hash<Ts>{}(args)
9
              + 0x9e3779b9
10
              + (seed << 6)
11
              + (seed >> 2)), ...);
12
        }, t);
13
        return seed;
14
    }
15
};
16

17
int main() {
18
    std::unordered_map<std::tuple<int,int>, int, TupleHash> mp;
19
    ++mp[{3,5}];
20
    std::cout << mp[{3,5}];
21
}

这里主要讲解

1
std::apply([&seed](const Ts&... args) {
2
            ((seed ^= std::hash<Ts>{}(args)
3
              + 0x9e3779b9
4
              + (seed << 6)
5
              + (seed >> 2)), ...);
6
        }, t);

显然，这里的哈希函数是先得到tuple的各个元素，在根据各个元素的哈希函数变换混合后得到的seed,也就是桶下标

根据前面讲到的数学公式，在这里有：

设 tuple 为：

\mathbf{x} = (x_1, x_2, \dots, x_n)

每个元素的基础哈希：

h_i = H(x_i), \quad i = 1,\dots,n

定义递推组合哈希函数：

S_0 = 0

S_k = S_{k-1} \;\oplus\; \big( h_k + 0x9e3779b9 + (S_{k-1} \ll 6) + (S_{k-1} \gg 2) \big), \quad k = 1,\dots,n

最终组合哈希值：

S = S_n

映射到桶索引：

t = S \bmod m

综上，便是：

\boxed{ \begin{aligned} S_0 &= 0, \\ S_k &= S_{k-1} \;\oplus\; \big(h_k + 0x9e3779b9 + (S_{k-1} \ll 6) + (S_{k-1} \gg 2)\big), \quad k = 1,\dots,n, \\ t &= S_n \bmod m \end{aligned} }

或者

\boxed{ t = \Bigg( \bigoplus_{k=1}^{n} \big( h_k + 0x9e3779b9 + (S_{k-1} \ll 6) + (S_{k-1} \gg 2) \big) \Bigg) \bmod m }

这里的 ⊕ 表示“按顺序的累积 XOR + 位移混合”，可以注释说明：

⊕：按顺序累积状态
h_k：元素哈希
位移 + 常数：信息扩散

最后，说明0x9e3779b9是什么：
它是数学常数 $(\sqrt{5}-1)/2$ 对应的 32 位整数形式
它的存在有利于减少哈希冲突，提高哈希表性能

4. 最后，不用unordered_map实现一次哈希表#

1
#include <iostream>
2
#include <vector>
3
#include <list>
4
#include <tuple>
5

6
// -------------------- 组合哈希函数 --------------------
7

8
// 单元素哈希（使用 std::hash）
9
template <typename T>
10
size_t hash_val(const T &v) {
11
    return std::hash<T>{}(v);
12
}
13
// 递归折叠 tuple
14
template <typename Tuple, size_t Index = 0>
15
struct TupleHasher {
16
    static size_t apply(const Tuple &t) {
17
        size_t seed = TupleHasher<Tuple, Index + 1>::apply(t);
18
        size_t h = hash_val(std::get<Index>(t));
19
        // 对应公式 S_k = S_{k-1} ⊕ (h_k + 0x9e3779b9 + (S_{k-1} << 6) + (S_{k-1} >> 2))
20
        seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
21
        return seed;
22
    }
23
};
24
// 递归终止
25
template <typename Tuple>
26
struct TupleHasher<Tuple, std::tuple_size<Tuple>::value> {
27
    static size_t apply(const Tuple &) { return 0; }
28
};
29
// 外部接口
30
template <typename... Ts>
31
size_t hash_tuple(const std::tuple<Ts...> &t) {
32
    return TupleHasher<std::tuple<Ts...>>::apply(t);
33
}
34

35
// -------------------- 哈希表定义 --------------------
36

37
template <typename... Ts>
38
class TupleHashMap {
39
private:
40
    using Key = std::tuple<Ts...>;
41
    using Pair = std::pair<Key, int>;
42

43
    size_t bucket_count;
44
    std::vector<std::list<Pair>> buckets;
45

46
    size_t hash(const Key &key) const {
47
        return hash_tuple(key) % bucket_count;
48
    }
49

50
public:
51
    TupleHashMap(size_t buckets_num = 16) : bucket_count(buckets_num), buckets(buckets_num) {}
52
    // 插入或更新
53
    void put(const Key &key, int value) {
54
        size_t idx = hash(key);
55
        for (auto &p : buckets[idx]) {
56
            if (p.first == key) {
57
                p.second = value; // 更新
58
                return;
59
            }
60
        }
61
        buckets[idx].push_back({key, value}); // 插入
62
    }
63
    // 查询
64
    bool get(const Key &key, int &value) const {
65
        size_t idx = hash(key);
66
        for (const auto &p : buckets[idx]) {
67
            if (p.first == key) {
68
                value = p.second;
69
                return true;
70
            }
71
        }
72
        return false;
73
    }
74
    // 删除
75
    bool remove(const Key &key) {
76
        size_t idx = hash(key);
77
        for (auto it = buckets[idx].begin(); it != buckets[idx].end(); ++it) {
78
            if (it->first == key) {
79
                buckets[idx].erase(it);
80
                return true;
81
            }
82
        }
83
        return false;
84
    }
85
    // 打印所有桶
86
    void print() const {
87
        for (size_t i = 0; i < bucket_count; ++i) {
88
            std::cout << "Bucket " << i << ": ";
89
            for (const auto &p : buckets[i]) {
90
                std::cout << "(";
91
                std::apply([](auto&&... args){ ((std::cout << args << ","), ...); }, p.first);
92
                std::cout << "->" << p.second << ") ";
93
            }
94
            std::cout << "\n";
95
        }
96
    }
97
};
98

99
// -------------------- 测试 --------------------
100

101
int main() {
102
    TupleHashMap<int, int, int> map;
103

104
    map.put(std::make_tuple(1, 2, 3), 100);
105
    map.put(std::make_tuple(4, 5, 6), 200);
106
    map.put(std::make_tuple(1, 2, 3), 150); // 更新
107

108
    map.print();
109

110
    int value;
111
    if (map.get(std::make_tuple(1, 2, 3), value)) {
112
        std::cout << "Value for (1,2,3) = " << value << "\n";
113
    }
114

115
    map.remove(std::make_tuple(4, 5, 6));
116
    map.print();
117

118
    return 0;
119
}

哈希表及其工作原理

哈希表#

哈希表的简介#

哈希表的数学描述#

哈希表的性能特性#

时间复杂度#

空间复杂度#

哈希表的在哈希冲突上的解决方案#

分离存储（拉链法 / Separate Chaining）#

开放定址（Open Addressing）#

哈希表的代码实现(统一c++写)#

1. 先来个简单的，字母到数字的映射：
#

2. 然后写一个int->int的哈希表，但是这次要求数据和桶下标是不能一样的，不然又是创建一个数组记录就解决的事了#

3. tuple->int的哈希函数写法#

4. 最后，不用unordered_map实现一次哈希表#

支持与分享

目录

哈希表及其工作原理

哈希表#

哈希表的简介#

哈希表的数学描述#

哈希表的性能特性#

时间复杂度#

空间复杂度#

哈希表的在哈希冲突上的解决方案#

分离存储（拉链法 / Separate Chaining）#

开放定址（Open Addressing）#

哈希表的代码实现(统一c++写)#

1. 先来个简单的，字母到数字的映射：#

2. 然后写一个int->int的哈希表，但是这次要求数据和桶下标是不能一样的，不然又是创建一个数组记录就解决的事了#

3. tuple->int的哈希函数写法#

4. 最后，不用unordered_map实现一次哈希表#

支持与分享

目录

1. 先来个简单的，字母到数字的映射：
#