哈希表基本原理
数组查询是 O(1), 哈希表通过 key 找到 value 也是 O(1), 原理：哈希表底层是一个数组。它先把 key 通过哈希函数转换成数组的索引，然后增删改查的基本操作与数组相同。
- key 是唯一的， value 可以重复
- 哈希函数将任意长度的输入，转换成固定的输出。
- key 可以是整型、字符串等不可变类型， key 必须是不可变的
哈希冲突
- 拉链法：纵向延伸，数组中存链表。多个相同的key挂在链表上。
- 线性探查法（开放寻址法）：横向延伸，一个 key 被 index 占用了，那就 index + 1 看看是否有空，没有继续往下找。
拉链法
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| #include <vector>
#include <iostream>
// 链表节点结构
struct Node {
int key;
int value;
Node* next;
Node(int k, int v) : key(k), value(v), next(nullptr) {}
};
class MyHashMap {
private:
// 底层是一个 Node 指针的数组（即桶数组）
std::vector<Node*> table;
// 固定容量，可以根据需要调整
static const int CAPACITY = 10000;
int hash(int key) {
return key % CAPACITY;
}
public:
MyHashMap() : table(CAPACITY, nullptr) {}
// 释放所有动态分配的内存，防止内存泄漏
~MyHashMap() {
for (Node* bucketHead : table) {
Node* current = bucketHead;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
}
// 插入或更新键值对
void put(int key, int value) {
int idx = hash(key);
// 1. 遍历链表，检查 key 是否已存在
Node* current = table[idx];
while (current != nullptr) {
if (current->key == key) {
current->value = value; // 更新 value
return;
}
current = current->next;
}
// 2. key 不存在，创建新节点并插入到链表头部（头插法）
Node* newNode = new Node(key, value);
newNode->next = table[idx]; // 新节点的 next 指向原链表头
table[idx] = newNode; // 桶指向新节点
}
int get(int key) {
int idx = hash(key);
Node* current = table[idx];
// 遍历链表查找 key
while (current != nullptr) {
if (current->key == key) {
return current->value;
}
current = current->next;
}
return -1; // 未找到
}
void remove(int key) {
int idx = hash(key);
Node* head = table[idx];
// 处理空链表的情况
if (head == nullptr) return;
// 1. 如果要删除的是头节点
if (head->key == key) {
table[idx] = head->next; // 桶指向下一个节点
delete head;
return;
}
// 2. 遍历链表，寻找目标节点的前驱节点
Node* prev = head;
while (prev->next != nullptr) {
if (prev->next->key == key) {
Node* toDelete = prev->next;
prev->next = toDelete->next; // 跳过目标节点，不能之间next->next,赋值，需要释放内存
delete toDelete;
return;
}
prev = prev->next;
}
}
};
int main() {
MyHashMap myHashMap;
std::cout << "=== MyHashMap 测试开始 ===" << std::endl;
// 1. 测试 put 和 get
std::cout << "\n[测试 1] 插入和获取 (Put & Get):" << std::endl;
myHashMap.put(1, 1);
myHashMap.put(2, 2);
std::cout << "put(1, 1), put(2, 2)" << std::endl;
std::cout << "get(1): " << myHashMap.get(1) << " (预期: 1)" << std::endl;
std::cout << "get(2): " << myHashMap.get(2) << " (预期: 2)" << std::endl;
// 2. 测试更新值
std::cout << "\n[测试 2] 更新值 (Update):" << std::endl;
myHashMap.put(2, 100);
std::cout << "put(2, 100)" << std::endl;
std::cout << "get(2): " << myHashMap.get(2) << " (预期: 100)" << std::endl;
// 3. 测试获取不存在的键
std::cout << "\n[测试 3] 获取不存在的键 (Get Non-existent):" << std::endl;
std::cout << "get(3): " << myHashMap.get(3) << " (预期: -1)" << std::endl;
// 4. 测试删除
std::cout << "\n[测试 4] 删除键 (Remove):" << std::endl;
myHashMap.remove(2);
std::cout << "remove(2)" << std::endl;
std::cout << "get(2): " << myHashMap.get(2) << " (预期: -1)" << std::endl;
// 5. 测试哈希冲突 (Collision)
// CAPACITY = 10000, 所以 1 和 10001 会映射到同一个桶
std::cout << "\n[测试 5] 哈希冲突处理 (Collision Handling):" << std::endl;
myHashMap.put(10001, 999);
std::cout << "put(10001, 999) -> 应该与 key=1 冲突" << std::endl;
std::cout << "get(1): " << myHashMap.get(1) << " (预期: 1)" << std::endl;
std::cout << "get(10001): " << myHashMap.get(10001) << " (预期: 999)" << std::endl;
// 删除冲突链中的一个
myHashMap.remove(1);
std::cout << "remove(1) -> 删除链表头节点" << std::endl;
std::cout << "get(1): " << myHashMap.get(1) << " (预期: -1)" << std::endl;
std::cout << "get(10001): " << myHashMap.get(10001) << " (预期: 999)" << std::endl;
std::cout << "\n=== 测试结束 ===" << std::endl;
return 0;
}
|
线性探查法
环形数组技巧
当遍历数组到末尾后，需要从数组头部继续遍历。
必须将数组视为一个环形结构。每当索引 index 超过数组边界时，就让它从头开始。
1
| index = (index + 1) % table.size();
|
通过这种方式，探查过程可以在数组末尾无缝地跳转到开头，确保能够遍历整个哈希表，直到找到空位或目标键。
删除操作复杂
“空洞”问题，如果多个key哈希到同一个索引上，中间有key被删除了，那么这个索引就成了空洞，后续的key就无法被找到。
方法一：数据搬移避免空洞
核心思想：删除一个元素后，检查它后面的元素是否是因为哈希冲突而被“挤”到当前位置的。如果是，就把它们向前移动一位来填补空洞。
这种方法能保持哈希表的连续性，但实现复杂，且删除操作的最坏时间复杂度可能退化到 O(n)。
方法二：占位符标记删除（Tombstone / Lazy Deletion）
核心思想：不真正清空槽位，而是用一个特殊的“墓碑”（Tombstone）标记来表示“此处已删除”。
具体实现：
定义一种特殊的状态（例如，在节点中增加一个 is_deleted 布尔标志，或者使用一个特殊的键值如 -1 来代表墓碑）。
删除操作：找到键后，不释放内存或置空，而是将其状态标记为“已删除”（is_deleted = true）。
查找操作：在探查过程中，遇到“已删除”的槽位时，不能停止，必须继续向后探查，因为目标键可能在更后面。
插入操作：在探查过程中，遇到“已删除”的槽位时，可以将其视为一个可用的空位，用于插入新元素。
优缺点：
优点：实现简单，删除操作非常快（O(1)）。
缺点：随着时间推移，哈希表中会积累大量“墓碑”，导致查找和插入的效率逐渐下降（因为需要跳过更多无效槽位）。通常需要配合一个清理机制（例如，当墓碑数量超过阈值时，重建整个哈希表）。
1
2
3
4
| #include <vector>
#include <optional>
#include <memory>
#include <functional>
|
简化版代码（基础框架）
展示线性探查的基本逻辑，未实现删除操作。
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
| class SimplifiedHashMap {
private:
struct Node {
int key, value;
Node(int k, int v) : key(k), value(v) {}
};
std::vector<std::unique_ptr<Node>> table;
static const int CAPACITY = 10000;
int find(int key) {
int idx = hash(key);
while (table[idx] != nullptr && table[idx]->key != key) {
idx = (idx + 1) % CAPACITY;
}
return idx;
}
int hash(int key) { return key % CAPACITY; }
public:
SimplifiedHashMap() : table(CAPACITY) {}
void put(int key, int value) {
int idx = find(key);
if (table[idx] == nullptr) {
table[idx] = std::make_unique<Node>(key, value);
} else {
table[idx]->value = value;
}
}
int get(int key) {
int idx = find(key);
if (table[idx] == nullptr) return -1;
return table[idx]->value;
}
};
|
搬移数据的线性探查法
删除后通过搬移后续元素填补“空洞”，保持查找路径连续。
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
| class LinearProbingWithMove {
private:
struct Node {
int key, value;
Node(int k, int v) : key(k), value(v) {}
};
std::vector<std::unique_ptr<Node>> table;
static const int CAPACITY = 10000;
int find(int key) {
int idx = hash(key);
while (table[idx] != nullptr && table[idx]->key != key) {
idx = (idx + 1) % CAPACITY;
}
return idx;
}
int hash(int key) { return key % CAPACITY; }
bool inBetween(int del_idx, int curr_idx, int origin_hash) {
if (origin_hash <= curr_idx) {
return (del_idx < origin_hash || origin_hash <= curr_idx);
} else {
return (del_idx < origin_hash && origin_hash <= curr_idx + CAPACITY);
}
}
public:
LinearProbingWithMove() : table(CAPACITY) {}
void put(int key, int value) {
int idx = find(key);
if (table[idx] == nullptr) {
table[idx] = std::make_unique<Node>(key, value);
} else {
table[idx]->value = value;
}
}
int get(int key) {
int idx = find(key);
if (table[idx] == nullptr) return -1;
return table[idx]->value;
}
void remove(int key) {
int del_idx = find(key);
if (table[del_idx] == nullptr) return;
int curr_idx = (del_idx + 1) % CAPACITY;
while (table[curr_idx] != nullptr) {
int origin_hash = hash(table[curr_idx]->key);
if (!inBetween(del_idx, curr_idx, origin_hash)) {
break;
}
table[del_idx] = std::move(table[curr_idx]);
del_idx = curr_idx;
curr_idx = (curr_idx + 1) % CAPACITY;
}
table[del_idx].reset();
}
};
|
特殊占位符的线性探查法（Tombstone）
使用全局唯一的 TOMBSTONE 对象标记已删除位置。
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
| class LinearProbingWithTombstone {
private:
struct Node {
int key, value;
Node(int k, int v) : key(k), value(v) {}
};
static const std::unique_ptr<Node> TOMBSTONE;
std::vector<std::unique_ptr<Node>> table;
static const int CAPACITY = 10000;
int hash(int key) { return key % CAPACITY; }
public:
LinearProbingWithTombstone() : table(CAPACITY) {}
void put(int key, int value) {
int idx = hash(key);
while (table[idx] != nullptr &&
table[idx] != TOMBSTONE &&
table[idx]->key != key) {
idx = (idx + 1) % CAPACITY;
}
if (table[idx] == nullptr || table[idx] == TOMBSTONE) {
table[idx] = std::make_unique<Node>(key, value);
} else {
table[idx]->value = value;
}
}
int get(int key) {
int idx = hash(key);
while (table[idx] != nullptr) {
if (table[idx] != TOMBSTONE && table[idx]->key == key) {
return table[idx]->value;
}
idx = (idx + 1) % CAPACITY;
}
return -1;
}
void remove(int key) {
int idx = hash(key);
while (table[idx] != nullptr) {
if (table[idx] != TOMBSTONE && table[idx]->key == key) {
table[idx] = const_cast<std::unique_ptr<Node>&>(TOMBSTONE);
return;
}
idx = (idx + 1) % CAPACITY;
}
}
};
// 类外定义静态成员
const std::unique_ptr<LinearProbingWithTombstone::Node>
LinearProbingWithTombstone::TOMBSTONE =
std::make_unique<LinearProbingWithTombstone::Node>(-1, -1);
|
特殊值标记版本（Deleted Flag）
通过 Node 内部的布尔字段 deleted 标记删除状态。
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
| class LinearProbingWithFlag {
private:
struct Node {
int key, value;
bool deleted;
Node(int k, int v) : key(k), value(v), deleted(false) {}
};
std::vector<std::unique_ptr<Node>> table;
static const int CAPACITY = 10000;
int hash(int key) { return key % CAPACITY; }
public:
LinearProbingWithFlag() : table(CAPACITY) {}
void put(int key, int value) {
int idx = hash(key);
while (table[idx] != nullptr &&
(!table[idx]->deleted && table[idx]->key != key)) {
idx = (idx + 1) % CAPACITY;
}
if (table[idx] == nullptr) {
table[idx] = std::make_unique<Node>(key, value);
} else {
table[idx]->key = key;
table[idx]->value = value;
table[idx]->deleted = false;
}
}
int get(int key) {
int idx = hash(key);
while (table[idx] != nullptr) {
if (!table[idx]->deleted && table[idx]->key == key) {
return table[idx]->value;
}
idx = (idx + 1) % CAPACITY;
}
return -1;
}
void remove(int key) {
int idx = hash(key);
while (table[idx] != nullptr) {
if (!table[idx]->deleted && table[idx]->key == key) {
table[idx]->deleted = true;
return;
}
idx = (idx + 1) % CAPACITY;
}
}
};
|
完整版代码（支持 Rehash 的泛型版本）
生产级实现：支持泛型、动态扩容、nullptr 值，并使用 std::optional 区分“无此键”和“值为 null”。
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
| template<typename K, typename V>
class GenericHashMap {
private:
struct Node {
K key;
std::optional<V> value;
bool deleted;
Node(const K& k, const std::optional<V>& v)
: key(k), value(v), deleted(false) {}
};
std::vector<std::unique_ptr<Node>> table;
size_t size;
static const size_t DEFAULT_CAPACITY = 16;
static const double LOAD_FACTOR = 0.75;
size_t hash(const K& key) {
std::hash<K> hasher;
return hasher(key) % table.size();
}
int find(const K& key) {
size_t idx = hash(key);
while (table[idx] != nullptr) {
if (!table[idx]->deleted && table[idx]->key == key) {
return static_cast<int>(idx);
}
idx = (idx + 1) % table.size();
}
return static_cast<int>(idx);
}
void rehash() {
auto old_table = std::move(table);
table.resize(old_table.size() * 2);
size = 0;
for (auto& node : old_table) {
if (node != nullptr && !node->deleted) {
put(node->key, node->value);
}
}
}
public:
GenericHashMap() : table(DEFAULT_CAPACITY), size(0) {}
void put(const K& key, const V& value) {
if (size >= table.size() * LOAD_FACTOR) {
rehash();
}
int idx = find(key);
if (table[idx] == nullptr) {
table[idx] = std::make_unique<Node>(key, value);
size++;
} else if (table[idx]->deleted) {
table[idx]->key = key;
table[idx]->value = value;
table[idx]->deleted = false;
size++;
} else {
table[idx]->value = value;
}
}
std::optional<V> get(const K& key) {
int idx = find(key);
if (table[idx] == nullptr || table[idx]->deleted) {
return std::nullopt;
}
return table[idx]->value;
}
bool containsKey(const K& key) {
int idx = find(key);
return (table[idx] != nullptr && !table[idx]->deleted);
}
void remove(const K& key) {
int idx = find(key);
if (table[idx] != nullptr && !table[idx]->deleted) {
table[idx]->deleted = true;
size--;
}
}
};
|
| 实现方式 | 删除复杂度 | 内存开销 | 查找性能稳定性 | 实现难度 |
|---|
| 简化版 | ❌ 不支持 | 低 | — | 简单 |
| 搬移数据 | O(n) 最坏 | 低 | 高（无空洞） | 复杂 |
| Tombstone | O(1) | 中（需额外对象） | 随时间下降 | 中等 |
| Deleted Flag | O(1) | 低（每个节点多1字节） | 随时间下降 | 简单 |
| 完整版 (Rehash) | O(1) amortized | 动态 | 高（自动清理） | 复杂 |
这些实现了线性探查法的核心思想与工程权衡，适用于不同场景。
扩容和负载因子
负载因子是一个哈希表装满的程度的度量。一般来说，负载因子越大，说明哈希表里面存储的 key-value 对越多，哈希冲突的概率就越大，哈希表的操作性能就越差。
负载因子的计算公式也很简单，就是 size / table.length。其中 size 是哈希表里面的 key-value 对的数量，table.length 是哈希表底层数组的容量。
用拉链法实现的哈希表，负载因子可以无限大，因为链表可以无限延伸；用线性探查法实现的哈希表，负载因子不会超过 1
当哈希表内元素达到负载因子时，哈希表会扩容。就是把哈希表底层 table 数组的容量扩大，把数据搬移到新的大数组中。size 不变，table.length 增加，负载因子就减小了
哈希表自动扩缩容后，同一个 key 存储在 table 的索引可能发生变化
用数组加强哈希表（ArrayHashMap）
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| #include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
#include <stdexcept>
#include <cstdlib>
#include <ctime>
template<typename K, typename V>
class ArrayHashMap {
private:
std::vector<K> keys; // 存储所有 key（紧凑）
std::vector<V> values; // 存储对应 value
std::unordered_map<K, int> indexMap; // key -> 在 keys 中的索引
int size;
// 用最后一个元素覆盖指定位置，并删除最后一个元素
void swapAndPopLast(int idx) {
if (idx >= static_cast<int>(keys.size())) return;
// 获取最后一个元素
K lastKey = keys.back();
V lastVal = values.back();
// 覆盖要删除的位置
keys[idx] = lastKey;
values[idx] = lastVal;
// 更新最后一个元素在 hash map 中的索引
indexMap[lastKey] = idx;
// 删除最后一个元素
keys.pop_back();
values.pop_back();
indexMap.erase(lastKey);
}
public:
ArrayHashMap() : size(0) {
srand(time(nullptr)); // 初始化随机种子
}
void put(const K& key, const V& value) {
auto it = indexMap.find(key);
if (it != indexMap.end()) {
// 已存在，更新 value
int idx = it->second;
values[idx] = value;
} else {
// 新增
keys.push_back(key);
values.push_back(value);
indexMap[key] = size;
size++;
}
}
V get(const K& key) {
auto it = indexMap.find(key);
if (it == indexMap.end()) {
throw std::out_of_range("Key not found");
}
int idx = it->second;
return values[idx];
}
bool containsKey(const K& key) const {
return indexMap.find(key) != indexMap.end();
}
void remove(const K& key) {
auto it = indexMap.find(key);
if (it == indexMap.end()) return;
int idx = it->second;
swapAndPopLast(idx);
size--;
}
K randomKey() {
if (size == 0) {
throw std::out_of_range("Cannot call randomKey on empty map");
}
// 生成 [0, size) 的随机索引
int randomIndex = rand() % size;
return keys[randomIndex];
}
int getSize() const { return size; }
void print() const {
std::cout << "{ ";
for (int i = 0; i < size; ++i) {
std::cout << keys[i] << ": " << values[i];
if (i < size - 1) std::cout << ", ";
}
std::cout << " }" << std::endl;
}
};
int main() {
ArrayHashMap<std::string, int> map;
// 添加数据
map.put("apple", 10);
map.put("banana", 20);
map.put("cherry", 30);
map.put("date", 40);
map.put("elderberry", 50);
std::cout << "Map: ";
map.print();
// 测试 randomKey 多次
std::cout << "\nRandom Keys (10 times):" << std::endl;
for (int i = 0; i < 10; ++i) {
std::cout << map.randomKey() << " ";
}
std::cout << std::endl;
// 删除一个 key 后再随机
std::cout << "\nRemoving 'banana'..." << std::endl;
map.remove("banana");
std::cout << "Map after remove: ";
map.print();
std::cout << "Random Keys after remove:" << std::endl;
for (int i = 0; i < 10; ++i) {
std::cout << map.randomKey() << " ";
}
std::cout << std::endl;
return 0;
}
|
用链表加强哈希表（ListHashMap）
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 <unordered_map>
#include <list>
#include <memory>
template<typename K, typename V>
class LinkedHashMap {
private:
// 双向链表存储键值对，维护插入顺序
std::list<std::pair<K, V>> order_list_;
// 哈希表：键 -> 链表迭代器的映射
std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> map_;
public:
// 插入或更新键值对
void put(const K& key, const V& value) {
auto it = map_.find(key);
if (it != map_.end()) {
// 键已存在，更新值
it->second->second = value;
// 可选：将更新的元素移到链表尾部（保持最近更新在尾部）
// order_list_.splice(order_list_.end(), order_list_, it->second);
} else {
// 键不存在，插入新元素到链表尾部
order_list_.push_back({key, value});
map_[key] = std::prev(order_list_.end());
}
}
// 获取值，返回指针（nullptr 表示未找到）
V* get(const K& key) {
auto it = map_.find(key);
if (it == map_.end()) {
return nullptr;
}
// 可选：实现访问顺序（LRU策略），将访问的元素移到尾部
// order_list_.splice(order_list_.end(), order_list_, it->second);
return &(it->second->second);
}
// 删除键值对
void remove(const K& key) {
auto it = map_.find(key);
if (it != map_.end()) {
order_list_.erase(it->second);
map_.erase(it);
}
}
// 检查是否包含指定键
bool contains(const K& key) const {
return map_.find(key) != map_.end();
}
// 获取元素数量
size_t size() const {
return map_.size();
}
// 检查是否为空
bool empty() const {
return map_.empty();
}
// 清空所有元素
void clear() {
order_list_.clear();
map_.clear();
}
// 迭代器支持（按插入顺序遍历）
auto begin() const { return order_list_.begin(); }
auto end() const { return order_list_.end(); }
// 反向迭代器
auto rbegin() const { return order_list_.rbegin(); }
auto rend() const { return order_list_.rend(); }
// 获取所有键（按插入顺序）
std::vector<K> keys() const {
std::vector<K> result;
for (const auto& pair : order_list_) {
result.push_back(pair.first);
}
return result;
}
// 获取所有值（按插入顺序）
std::vector<V> values() const {
std::vector<V> result;
for (const auto& pair : order_list_) {
result.push_back(pair.second);
}
return result;
}
};
|
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
| #include <unordered_set>
#include <list>
template<typename T>
class LinkedHashSet {
private:
// 使用一个 dummy 值来复用 LinkedHashMap 的实现
LinkedHashMap<T, bool> map_;
static constexpr bool DUMMY_VALUE = true;
public:
// 添加元素
void add(const T& element) {
map_.put(element, DUMMY_VALUE);
}
// 删除元素
void remove(const T& element) {
map_.remove(element);
}
// 检查是否包含元素
bool contains(const T& element) const {
return map_.contains(element);
}
// 获取元素数量
size_t size() const {
return map_.size();
}
// 检查是否为空
bool empty() const {
return map_.empty();
}
// 清空所有元素
void clear() {
map_.clear();
}
// 迭代器支持（按插入顺序遍历）
auto begin() const {
// 创建一个转换迭代器，只返回键
return map_.begin();
}
auto end() const {
return map_.end();
}
// 获取所有元素（按插入顺序）
std::vector<T> toVector() const {
std::vector<T> result;
for (const auto& pair : map_) {
result.push_back(pair.first);
}
return result;
}
};
|
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
| template<typename T>
class LinkedHashSetDirect {
private:
std::list<T> order_list_;
std::unordered_set<T> set_;
public:
void add(const T& element) {
if (set_.find(element) == set_.end()) {
order_list_.push_back(element);
set_.insert(element);
}
}
void remove(const T& element) {
if (set_.erase(element)) {
// 需要从链表中删除，但 unordered_set 不提供位置信息
// 这里需要遍历链表，效率较低
order_list_.remove(element);
}
}
bool contains(const T& element) const {
return set_.find(element) != set_.end();
}
size_t size() const {
return set_.size();
}
bool empty() const {
return set_.empty();
}
void clear() {
order_list_.clear();
set_.clear();
}
auto begin() const { return order_list_.begin(); }
auto end() const { return order_list_.end(); }
std::vector<T> toVector() const {
return std::vector<T>(order_list_.begin(), order_list_.end());
}
};
|
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
| #include <iostream>
#include <string>
#include <vector>
#include "list_hashmap.h"
#include "list_hashset.h"
#include "list_hashset_direct.h"
int main() {
// LinkedHashMap 示例
std::cout << "=== LinkedHashMap 测试 ===" << std::endl;
LinkedHashMap<std::string, int> lmap;
lmap.put("apple", 1);
lmap.put("banana", 2);
lmap.put("cherry", 3);
// 按插入顺序遍历
std::cout << "按插入顺序遍历:" << std::endl;
for (const auto& pair : lmap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 更新现有键
lmap.put("banana", 20);
std::cout << "\n更新 banana 后:" << std::endl;
std::cout << "banana: " << *(lmap.get("banana")) << std::endl;
// LinkedHashSet 示例
std::cout << "\n=== LinkedHashSet 测试 ===" << std::endl;
LinkedHashSet<std::string> lset;
lset.add("first");
lset.add("second");
lset.add("third");
lset.add("first"); // 重复添加，应该被忽略
std::cout << "按插入顺序遍历 LinkedHashSet:" << std::endl;
for (const auto& elem : lset.toVector()) {
std::cout << elem << std::endl;
}
std::cout << "\nLinkedHashSet 大小: " << lset.size() << std::endl;
return 0;
}
|
当遍历数组到末尾后，需要从数组头部继续遍历。
哈希集合（HashSet）
哈希集合的核心特性：
- 元素唯一性：集合中不会存在重复元素
- 无序性：元素的存储顺序与插入顺序无关
- 高效操作：插入、删除、查找的时间复杂度都是 O(1)（平均情况）
哈希集合代码实现
- 拉链法
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
| #include <vector>
#include <list>
#include <functional>
#include <utility>
template <typename T,
typename Hash = std::hash<T>,
typename Equal = std::equal_to<T>>
class MyHashSet {
private:
static constexpr double LOAD_FACTOR = 0.75;
size_t capacity;
size_t size;
std::vector<std::list<T>> buckets;
Hash hashFunc;
Equal equalFunc;
size_t hash(const T& key) const {
return hashFunc(key) % capacity;
}
void resize() {
std::vector<std::list<T>> oldBuckets = std::move(buckets);
// 扩大容量
capacity *= 2;
buckets.resize(capacity);
// 重置大小
size = 0;
// 重新哈希所有元素
for (const auto& bucket : oldBuckets) {
for (const auto& key : bucket) {
insert(key);
}
}
}
public:
explicit MyHashSet(size_t initialCapacity = 16,
const Hash& hash = Hash(),
const Equal& equal = Equal())
: capacity(initialCapacity), size(0),
buckets(initialCapacity), hashFunc(hash), equalFunc(equal) {}
void insert(const T& key) {
if (contains(key)) return;
// 检查是否需要扩容
if (size >= capacity * LOAD_FACTOR) {
resize();
}
size_t index = hash(key);
buckets[index].push_back(key);
size++;
}
void erase(const T& key) {
if (!contains(key)) return;
size_t index = hash(key);
auto& bucket = buckets[index];
// 使用equalFunc比较元素
for (auto it = bucket.begin(); it != bucket.end(); ++it) {
if (equalFunc(*it, key)) {
bucket.erase(it);
size--;
break;
}
}
}
bool contains(const T& key) const {
size_t index = hash(key);
const auto& bucket = buckets[index];
for (const auto& k : bucket) {
if (equalFunc(k, key)) {
return true;
}
}
return false;
}
size_t getSize() const { return size; }
bool isEmpty() const { return size == 0; }
};
|
- 线性探查法
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
| #include <vector>
#include <optional>
#include <functional>
template <typename T, typename Hash = std::hash<T>, typename Equal = std::equal_to<T>>
class LinearProbingHashSet {
private:
struct Node {
T value;
bool deleted;
Node(const T& v) : value(v), deleted(false) {}
};
std::vector<std::optional<Node>> table;
size_t size;
static const size_t DEFAULT_CAPACITY = 16;
static constexpr double LOAD_FACTOR = 0.75;
Hash hashFunc;
Equal equalFunc;
size_t hash(const T& key) const {
return hashFunc(key) % table.size();
}
int find(const T& key) const {
size_t idx = hash(key);
while (table[idx]) {
if (!table[idx]->deleted && equalFunc(table[idx]->value, key)) {
return static_cast<int>(idx);
}
idx = (idx + 1) % table.size();
}
return static_cast<int>(idx);
}
void rehash() {
auto old_table = std::move(table);
table.resize(old_table.size() * 2);
size = 0;
for (auto& node : old_table) {
if (node && !node->deleted) {
insert(node->value);
}
}
}
public:
LinearProbingHashSet(const Hash& hash = Hash(), const Equal& equal = Equal())
: table(DEFAULT_CAPACITY), size(0), hashFunc(hash), equalFunc(equal) {}
void insert(const T& value) {
if (size >= table.size() * LOAD_FACTOR) {
rehash();
}
int idx = find(value);
if (!table[idx]) {
table[idx] = Node(value);
size++;
} else if (table[idx]->deleted) {
table[idx]->value = value;
table[idx]->deleted = false;
size++;
}
// 如果已存在，不执行任何操作
}
void erase(const T& value) {
int idx = find(value);
if (table[idx] && !table[idx]->deleted) {
table[idx]->deleted = true;
size--;
}
}
bool contains(const T& value) const {
int idx = find(value);
return (table[idx] && !table[idx]->deleted);
}
size_t getSize() const { return size; }
bool isEmpty() const { return size == 0; }
};
|
- 基于标准库实现
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
| #include <unordered_set>
class SimpleHashSet {
private:
std::unordered_set<int> set;
public:
void add(int key) {
set.insert(key);
}
void remove(int key) {
set.erase(key);
}
bool contains(int key) const {
return set.find(key) != set.end();
}
size_t size() const {
return set.size();
}
bool empty() const {
return set.empty();
}
};
|
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
| #include <iostream>
#include <string>
#include "myhashset.h"
#include "LinearProbingHashSet.h"
#include "StdUnorderSet.h"
int main() {
// 使用自定义哈希集合
MyHashSet<int> intSet;
intSet.insert(1);
intSet.insert(2);
intSet.insert(3);
std::cout << "Contains 2: " << (intSet.contains(2) ? "Yes" : "No") << std::endl;
intSet.erase(2);
std::cout << "After erase, contains 2: " << (intSet.contains(2) ? "Yes" : "No") << std::endl;
// 存储字符串
MyHashSet<std::string> stringSet;
stringSet.insert("hello");
stringSet.insert("world");
std::cout << "Contains 'hello': " << (stringSet.contains("hello") ? "Yes" : "No") << std::endl;
// 使用标准库版本
SimpleHashSet simpleSet;
simpleSet.add(10);
simpleSet.add(20);
std::cout << "Simple set contains 10: " << (simpleSet.contains(10) ? "Yes" : "No") << std::endl;
return 0;
}
|
布隆过滤器
核心能力是：在超大规模的数据集中，仅使用少量内存空间，即可快速判断一个元素是否存在。具备数据隐私性，即可以在不暴露具体数据的情况下，判断一个元素是否存在。
精髓在于：不存储具体数据，而仅仅存储数据指纹（哈希值），通过比对指纹来判断数据是否存在。
典型应用场景
- 恶意URL检测：判断一个HTTP请求的URL是否在恶意URL列表中（列表数量可达上亿）
- 大数据存储系统：为每个文件在内存中维护布隆过滤器，避免无效的磁盘IO操作
- 缓存穿透防护：快速判断某个key是否可能存在于数据库中
布隆过滤器 vs 哈希集合
| 特性 | 哈希集合 (HashSet) | 布隆过滤器 (Bloom Filter) |
|---|
| 空间复杂度 | O(N)，随元素数量线性增长 | O(1)，固定大小的位数组（与元素数量无关） |
| 时间复杂度 | O(1) 平均情况（理想哈希） | O(k)，k 为哈希函数个数（通常为常数） |
| 准确性 | 100% 准确，无误判 | 存在假阳性(False Positive)，但无假阴性(False Negative) |
| 数据隐私 | 存储实际数据，无隐私性 | 只存储哈希指纹，具备隐私性（无法还原原始数据） |
| 删除操作 | 支持删除 | 标准布隆过滤器不支持删除（可使用计数布隆过滤器变体） |
| 适用场景 | 数据规模适中，需要精确判断的场景
（如去重、成员查询） | 超大规模数据，可接受少量误判的场景
（如缓存穿透防护、垃圾邮件过滤、数据库预检） |
| 内存占用 | 较高（需存储完整数据） | 极低（仅需位数组） |
| 扩容能力 | 支持动态扩容 | 固定大小，扩容需重建 |
| 典型应用 | Java HashSet，Python set | Redis 的 BF 模块，Google Bigtable，Chrome 黑名单检测 |
关键差异说明
🔍 假阳性率 (False Positive Rate)
- 布隆过滤器：可通过公式精确控制：
p = (1 - e^(-kn/m))^k
其中 m=位数组大小，n=元素数量，k=哈希函数数量 - 哈希集合：无假阳性
🛡️ 隐私保护
- 布隆过滤器无法还原原始数据，适合敏感数据场景（如存储用户邮箱哈希）
- 哈希集合直接暴露原始数据
⚙️ 删除操作
- 计数布隆过滤器 (Counting Bloom Filter) 通过整数计数器替代位数组，支持删除，但空间开销增大 4-8 倍
💡 选择建议：
- 需要100%准确或频繁删除 → 选哈希集合
- 海量数据 + 容忍少量误判 + 内存敏感 → 选布隆过滤器
布隆过滤器代码实现
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
| #include <vector>
#include <functional>
#include <cmath>
class BloomFilter {
private:
std::vector<bool> bitArray; // 位数组
size_t numHashFunctions; // 哈希函数个数
// 多个哈希函数的实现
size_t hash1(const std::string& key) const {
std::hash<std::string> hasher;
return hasher(key) % bitArray.size();
}
size_t hash2(const std::string& key) const {
// 使用不同的哈希策略
size_t hash = 0;
for (char c : key) {
hash = hash * 31 + c;
}
return hash % bitArray.size();
}
// 生成第i个哈希值
size_t getHash(const std::string& key, size_t i) const {
if (i == 0) return hash1(key);
else return (hash1(key) + i * hash2(key)) % bitArray.size();
}
public:
// 构造函数：根据预期元素数量和误判率计算最优参数
BloomFilter(size_t expectedElements, double falsePositiveRate = 0.01) {
// 计算位数组大小 m = -n * ln(p) / (ln(2))^2
// 计算位数组大小 m = -n * ln(p) / (ln(2))^2
// 注意：必须先将 expectedElements 转为 double，否则 -expectedElements (unsigned) 会溢出
size_t m = static_cast<size_t>(
-static_cast<double>(expectedElements) * std::log(falsePositiveRate) /
(std::log(2) * std::log(2))
);
if (m == 0) m = 1; // 避免大小为0
// 计算哈希函数个数 k = (m/n) * ln(2)
numHashFunctions = static_cast<size_t>(
(static_cast<double>(m) / expectedElements) * std::log(2)
);
// 确保至少有1个哈希函数
if (numHashFunctions == 0) numHashFunctions = 1;
bitArray.resize(m, false);
}
// 添加元素
void add(const std::string& key) {
for (size_t i = 0; i < numHashFunctions; ++i) {
size_t index = getHash(key, i);
bitArray[index] = true;
}
}
// 检查元素是否存在
bool contains(const std::string& key) const {
for (size_t i = 0; i < numHashFunctions; ++i) {
size_t index = getHash(key, i);
if (!bitArray[index]) {
return false; // 确定不存在
}
}
return true; // 可能存在（可能有误判）
}
// 获取位数组大小
size_t getSize() const {
return bitArray.size();
}
// 获取哈希函数个数
size_t getNumHashFunctions() const {
return numHashFunctions;
}
};
|
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
98
99
100
101
102
103
104
105
| #include <vector>
#include <cstdint>
class OptimizedBloomFilter {
private:
std::vector<uint64_t> bitArray; // 使用uint64_t提高空间效率
size_t numHashFunctions;
size_t bitSize;
// MurmurHash3 的简化版本
uint32_t murmurHash(const char* data, size_t len, uint32_t seed) const {
uint32_t h = seed;
uint32_t c1 = 0xcc9e2d51;
uint32_t c2 = 0x1b873593;
const uint32_t* chunks = reinterpret_cast<const uint32_t*>(data);
const uint32_t* end = chunks + (len / 4);
while (chunks < end) {
uint32_t k = *chunks++;
k *= c1;
k = (k << 15) | (k >> 17);
k *= c2;
h ^= k;
h = (h << 13) | (h >> 19);
h = h * 5 + 0xe6546b64;
}
const uint8_t* tail = reinterpret_cast<const uint8_t*>(chunks);
uint32_t k1 = 0;
switch (len & 3) {
case 3: k1 ^= tail[2] << 16;
case 2: k1 ^= tail[1] << 8;
case 1: k1 ^= tail[0];
k1 *= c1;
k1 = (k1 << 15) | (k1 >> 17);
k1 *= c2;
h ^= k1;
}
h ^= len;
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
bool getBit(size_t index) const {
size_t wordIndex = index / 64;
size_t bitIndex = index % 64;
return (bitArray[wordIndex] >> bitIndex) & 1ULL;
}
void setBit(size_t index) {
size_t wordIndex = index / 64;
size_t bitIndex = index % 64;
bitArray[wordIndex] |= (1ULL << bitIndex);
}
public:
OptimizedBloomFilter(size_t expectedElements, double falsePositiveRate = 0.01) {
size_t m = static_cast<size_t>(
-expectedElements * std::log(falsePositiveRate) /
(std::log(2) * std::log(2))
);
numHashFunctions = static_cast<size_t>(
(static_cast<double>(m) / expectedElements) * std::log(2)
);
if (numHashFunctions == 0) numHashFunctions = 1;
bitSize = m;
bitArray.resize((m + 63) / 64, 0);
}
void add(const std::string& key) {
const char* data = key.c_str();
size_t len = key.length();
for (size_t i = 0; i < numHashFunctions; ++i) {
uint32_t hash = murmurHash(data, len, static_cast<uint32_t>(i));
size_t index = hash % bitSize;
setBit(index);
}
}
bool contains(const std::string& key) const {
const char* data = key.c_str();
size_t len = key.length();
for (size_t i = 0; i < numHashFunctions; ++i) {
uint32_t hash = murmurHash(data, len, static_cast<uint32_t>(i));
size_t index = hash % bitSize;
if (!getBit(index)) {
return false;
}
}
return true;
}
};
|
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
| #include <iostream>
#include <string>
#include "base_bloom_filter.h"
#include "optimized_bloom_filter.h"
int main() {
// 创建布隆过滤器，预期10000个元素，误判率1%
BloomFilter bf(10000, 0.01);
std::cout << "位数组大小: " << bf.getSize() << " bits" << std::endl;
std::cout << "哈希函数个数: " << bf.getNumHashFunctions() << std::endl;
// 添加一些元素
bf.add("apple");
bf.add("banana");
bf.add("cherry");
// 测试存在性
std::cout << "\n测试存在性:" << std::endl;
std::cout << "apple: " << (bf.contains("apple") ? "可能存在" : "确定不存在") << std::endl;
std::cout << "banana: " << (bf.contains("banana") ? "可能存在" : "确定不存在") << std::endl;
std::cout << "orange: " << (bf.contains("orange") ? "可能存在" : "确定不存在") << std::endl;
// 注意：orange 可能会误判为存在（假阳性），但概率很低（约1%）
return 0;
}
|
Reference
https://labuladong.online/algo/data-structure-basic/hashmap-basic/