跳到主要内容C++ 哈希表全家桶：unordered_map/set 底层实现与位图布隆过滤器 | 极客日志C++算法
C++ 哈希表全家桶：unordered_map/set 底层实现与位图布隆过滤器
深入讲解 C++ 中基于哈希表的容器实现原理。涵盖哈希冲突解决方案（闭散列线性探测、开散列链地址法），详细模拟实现 unordered_map 和 unordered_set 底层结构。介绍位图（BitMap）在大数据统计中的应用及内存优化，阐述布隆过滤器（Bloom Filter）的存在性判断机制及其无法删除的特性。最后探讨哈希切割技术在海量数据交集查找中的精确与近似算法方案，并结合力扣例题巩固知识点。
活在当下4.1K 浏览 unordered 系列关联式容器
有 unordered_map, unordered_set, unordered_multimap, unordered_multiset
这些是用哈希表实现的，用法跟 set 几乎相同，接口都差不多。
它们可以用范围 for 去遍历。
跟 set 那些的区别:
-
unordered 系列的容器的迭代器是单向迭代器。
-
unordered 系列中序遍历出来不是有序的。
-
unordered 系列的容器的性能比 set 等稍微好些；但是升序或降序的数据插入的话，set 好些。
引申：比较性能要在 release 模式下比较。
哈希
哈希也叫做散列，是存储的值跟存储位置建立出的一个对应关系，跟计数排序很像。
自己模拟实现的哈希不要存同一个 key 进去！
哈希是以牺牲空间为代价，提高查询的效率。
建立对应关系的时候有两个常用的方法:
-
直接定址法 (值分布范围集中得时候用这个)
比如：统计字符串中字符出现的次数，可以把字符跟下标一一对应。
-
除留余数法 (适用于值分布范围分散的)
例如：值 % n，把这个东西放在对应下标下面。
哈希冲突
其实就是不同的值映射到了相同的位置上，这个位置存不下了。
解决哈希冲突的方案:
-
闭散列 – 也叫做开放定址法
做法：当前位置被占用了，按规则去找下一个位置存着。
其中又分为 1. 线性探测 2. 二次探测 …
-
开散列 – 也叫做链地址法 – 自己一般叫哈希桶
闭散列的模拟实现
这里的话个人搭配的是除留余数法加上线性探测。
二次探测的方法跟线性探测的区别就是:
线性探测是这个位置满了去下一个位置找 (也就是下标加 i 去找)。
二次探测是这个位置满了，下标加上 i^2 去找，比如：本来应该在 0 下标，但是满了，去 1, 4, 9 这样。
enum State { EXIST, EMPTY, DELETE };
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K>
struct DefaultHashFunc {
{
()key;
}
};
< , , = DefaultHashFunc<K>>
HashTable {
:
() {
_table.();
}
{
(_n * / _table.() >= ) {
newSize = _table.() * ;
HashTable<K, V, HashFunc> newHT;
newHT._table.(newSize);
( i = ; i < _table.(); i++) {
(_table[i]._state == EXIST) {
newHT.(_table[i]._kv);
}
}
_table.(newHT._table);
}
HashFunc hf;
hashi = (kv.first) % _table.();
(_table[hashi]._state == EXIST) {
++hashi;
hashi %= _table.();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
;
}
{
HashFunc hf;
hashi = (key) % _table.();
(_table[hashi]._state != EMPTY) {
(_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
(HashData< K, V>*)&_table[hashi];
}
++hashi;
hashi %= _table.();
}
;
}
{
HashData< K, V>* ret = (key);
(ret) {
ret->_state = DELETE;
--_n;
;
}
;
}
:
vector<HashData<K, V>> _table;
_n = ;
};
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
size_t
operator
()
(const K& key)
return
size_t
template
class
K
class
V
class
HashFunc
class
public
HashTable
resize
10
bool Insert(const pair<K, V>& kv)
if
10
size
7
size_t
size
2
resize
for
size_t
0
size
if
Insert
swap
size_t
hf
size
while
size
return
true
HashData<const K, V>* Find(const K& key)
size_t
hf
size
while
if
return
const
size
return
nullptr
bool Erase(const K& key)
const
Find
if
return
true
return
false
private
size_t
0
这里的话是用了 EXIST, EMPTY, DELETE 去做了状态标记。
这个 DELETE 就巧妙地解决了想删除数据，但是又不想填啥进去的问题。
注意：在扩容的时候，DELETE 的是不用搞到新表里面的哈。
线性探测的 Find 的实现：这个位置是 EXIST 并且值是 key 的话才要，如果到空了还没找到的话就是没有。开始的话就是从 key % _n 那个位置开始找。
用开放定址法的话不能让这个存数据的 vector 太满了，不然在插入那些的时候会很费时间，有些的位置要往后找。
所以负载因子越大，冲突概率越大，但是空间利用率越高；负载因子越小，冲突概率越小，但是空间利用率越低。当然这个方法也保证了哈希表不会满出来，一直都会有空位。
开散列的模拟实现
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable {
struct HashNode {
T _data;
HashNode* _next;
HashNode(const T& data) : _data(data), _next(nullptr) {}
};
typedef HashNode<T> Node;
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin() {
for (size_t i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
if (cur) return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end() {
return iterator(nullptr, this);
}
const_iterator begin() const {
for (size_t i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
if (cur) return const_iterator(cur, this);
}
return const_iterator(nullptr, this);
}
const_iterator end() const {
return const_iterator(nullptr, this);
}
HashTable() {
_table.resize(10, nullptr);
}
~HashTable() {
for (size_t i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
bool Insert(const T& data) {
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end()) {
return make_pair(it, false);
}
HashFunc hf;
if (_n == _table.size()) {
size_t newSize = _table.size() * 2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}
Node* Find(const K& key) {
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur) {
if (kot(cur->_data) == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key) {
HashFunc hf;
KeyOfT kot;
size_t hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev == nullptr) {
_table[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _table;
size_t _n = 0;
};
这个 vector<Node*> _table 里面存的是指针哈，然后有需要插一个位置的话，就头插到这个位置。
这个哈希桶的打印的话，最好是 vector 里面的一个'链表'打成一行这样好看些。
哈希桶走到尽头了的话是不会重头再走的！
关于这个哈希桶的扩容问题：等负载因子到 1 就扩容。不扩容的话效率会有点低。
新旧表的转移跟闭散列那个有点不一样，这里是把旧的节点搞到新表上 (一个一个拆)。
有些地方的扩容说法是：扩容成素数。给里面一个素数表，然后超过当前容量了，就扩容到下一个素数那么多。
关于这个哈希桶的删除问题：分两种情况，1. 删除的这个节点没有 prev 就直接把 vector 里面的改成 cur->_next。
哈希桶的节点其实可以从链表结构换成树结构（这也是种优化方法）：节点'连接'的东西长度超过一定数量时，把他改成树结构，然后节点里面存根节点的指针。
哈希桶里面迭代器的模拟实现
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
Node* _node;
HashTable<K, T, KeyOfT, HashFunc>* _pht;
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht) : _node(node), _pht(const_cast<HashTable*>(pht)) {}
HTIterator(const Iterator& it) : _node(it._node), _pht(it._pht) {}
Ref operator*() {
return _node->_data;
}
Ptr operator->() {
return &_node->_data;
}
Self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else {
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size()) {
if (_pht->_table[hashi]) {
_node = _pht->_table[hashi];
return *this;
} else {
++hashi;
}
}
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s) {
return _node != s._node;
}
bool operator==(const Self& s) {
return _node == s._node;
}
};
问题：迭代器里面要用到哈希表，哈希表里面也要用到迭代器，怎么办？
解决方法：用前置声明。
unordered_set 的封装
namespace my_hash {
template<class K>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) {
return key;
}
};
public:
typedef typename HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() {
return _ht.begin();
}
iterator end() {
return _ht.end();
}
pair<const_iterator, bool> insert(const K& key) {
pair<typename HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<const_iterator, bool>(ret.first, ret.second);
}
private:
HashTable<K, K, SetKeyOfT> _ht;
};
}
unordered_map 的封装
namespace my_hash {
template<class K, class V>
class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) {
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin() {
return _ht.begin();
}
iterator end() {
return _ht.end();
}
const_iterator begin() const {
return _ht.begin();
}
const_iterator end() const {
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv) {
return _ht.Insert(kv);
}
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}
位图
就是用数的比特位去表达信息。
这个位图其实在库里面也是有实现的，那个函数也叫 bitset。
接口的话，常用的也就三个：test, set, reset。
跟下面的模拟实现其实差不多。
应用
面试题：给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。
这个题的话用 set 或者排序＋二分查找的话需要的空间都是很大的，因为有 40 亿个数。
所以的话需要采取位图的方法。这里的话就是一个 int 类型的数有 32 个比特位，比如：第一个比特位表示 1 这个数在还是不在这样。
注意的是，要有 size_t 范围个比特位，而不是单单 40 亿个比特位哈。
template<size_t N>
class bitset {
public:
bitset() {
_a.resize(N / 32 + 1);
}
void set(size_t x) {
size_t i = x / 32;
size_t j = x % 32;
_a[i] |= (1 << j);
}
void reset(size_t x) {
size_t i = x / 32;
size_t j = x % 32;
_a[i] &= (~(1 << j));
}
bool test(size_t x) {
size_t i = x / 32;
size_t j = x % 32;
return _a[i] & (1 << j);
}
private:
vector<int> _a;
};
引申：比特位是从右到左排的，位运算的角度。跟大端小端没关系，大端小端影响的只是在内存中的存储。
给定 100 亿个无符号整数，设计算法找到只出现一次的整数。
这个的话 100 亿个整数其实没这么多，顶多也就 size_t 那么多，也就 42 亿多点。
就用两个位图存就行了，两个位图的同一个位置表示数的二进制就行了。
给两个文件，分别有 100 亿个整数，我们只有一个 G 的内存，如果找到两个文件的交集。
用一个位图存 42 亿多个的整数的话要 512MB，正好够存用两个位图的空间。
可以把两个文件分别映射到两个位图，如果对应位置都是 1 的话，这个数就是交集。
或者一个文件存位图里，遍历另一个文件去比对，放入交集的值在位图里面要 reset 掉。
布隆过滤器
就是把一个东西他的特性用类似哈希函数的方法放入位图里面，如果这些位置都为 1 的话，说明这个东西可能存在，反之，则这个东西一定不在这里面。
布隆过滤器是一种利用多个独立哈希函数 + 位图实现的高效存在性判断结构。
应用场景：用于那些不需要精确的场景。
比如：快速判断昵称是否注册过。
如果想精确的话，就查询出来是在的时候去数据库里再查一遍，这样照样可以减轻数据库查询的压力，提高效率。
布隆过滤器的模拟实现
template<size_t N, class K, class Hash1, class Hash2, class Hash3>
class BloomFilter {
public:
void Set(const K& key) {
size_t hash1 = Hash1()(key) % N;
_bs.set(hash1);
size_t hash2 = Hash2()(key) % N;
_bs.set(hash2);
size_t hash3 = Hash3()(key) % N;
_bs.set(hash3);
}
bool Test(const K& key) {
size_t hash1 = Hash1()(key) % N;
if (_bs.test(hash1) == false) return false;
size_t hash2 = Hash2()(key) % N;
if (_bs.test(hash2) == false) return false;
size_t hash3 = Hash3()(key) % N;
if (_bs.test(hash3) == false) return false;
return true;
}
private:
bitset<N> _bs;
};
关于这个 K 的话，一定要让他是唯一的。如果没有唯一信息的话，可以用不同信息的组合来让他唯一。
注意：布隆过滤器一般不支持删除操作，支持删除的话会导致本来在的检查出来发现不在。
如果硬要加上删除操作的话，需要：多个位标识一个值，然后使用引用计数，标记这个位被标记了多少次。
关于布隆过滤器的优化：k 是哈希函数个数，m 是布隆过滤器长度，n 是插入的元素个数。
struct BKDRHash {
size_t operator()(const string& str) {
size_t hash = 0;
for (auto ch : str) {
hash = hash * 131 + ch;
}
return hash;
}
};
哈希切割
也就是运用哈希函数把一个大文件的数据根据特征分到好几个小文件里面。
哈希切割的应用
给两个文件，分别有 100 亿个 query，我们只有 1G 内存，如何找到两个文件交集？分别给出精确算法和近似算法。
query 在这里是待处理的字符串、数据项。
近似算法的话就是：用布隆过滤器。
精确算法的话：用哈希切割。这两个文件用相同的哈希函数分，但是结果不存同一个文件里面，两个文件相同的 query 肯定会进到'相同编号'去。
分成多少个小文件的话要看情况。
使用哈希切割发生的冲突太多了怎么办，内存只有 1G 不够用啊：
这时的内存不够用有两种场景：1. 相同的 query 太多了 2. 冲突的太多了。
解决方法：先把小文件的 query 读到 set 里面，如果 set 的 insert 报错抛异常 (抛的 bad_alloc)，那么久说明冲突的太多了；如果能够全部存进入，就说明是相同的太多了。
有大量冲突的话，就要换一个哈希函数，进行二次切分。
跟上面类似的题目：给一个超过 100G 大小的 log file, log 中存着 IP 地址，设计算法找到出现次数最多的 IP 地址以及求最多的 K 个地址。
关于求最多的 K 个地址的话，自己的想法：每一个小文件中的前 k 多的地址保留到堆和 map 里面，最后再终极比较。
练习题
散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。
A.最大概率 B.最小概率 C.同等概率 D.平均概率
解决散列法中出现冲突问题常采用的方法是 (D)
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
已知有一个关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，若散列函数为 H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为 (A)
A.1.5 B.1.7 C.2.0 D.2.3
已知某个哈希表的 n 个关键字具有相同的哈希值，如果使用二次探测再散列法将这 n 个关键字存入哈希表，至少要进行（E）次探测。
A.n-1 B.n C.n+1 D.n(n+1) E.n(n+1)/2 F.1+n(n+1)/2
力扣 350. 两个数组的交集 II
这个题的话主要核心就是怕前面的数已经给了 vectorv，但是后面又给重复统计进去了。这时就需要，在给 v 之后，把 hash1,hash2 里面的这个值对应的东西记为 0 就行了。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hash1;
unordered_map<int, int> hash2;
vector<int> v;
for (auto e : nums1) hash1[e]++;
for (auto e : nums2) hash2[e]++;
for (auto e : nums1) {
if (hash1.count(e) && hash2.count(e)) {
for (int i = 0; i < min(hash1[e], hash2[e]); i++) {
v.push_back(e);
}
hash1[e] = 0;
hash2[e] = 0;
}
}
return v;
}
};
下面关于位图说法错误的是（D）
A.位图就是用比特位表示一个数据的状态信息
B.通过位图可以求两个集合的交集
C.位图实际是哈希变形思想的一种应用
D.位图可以很方便的进行字符串的映射以及查找
力扣 884. 两句话中的不常见单词
引申：""代表的是空字符串，没有''这个东西！！！只有 multi_map 和 multi_set 的 count 会返回对应出现的次数，set map unordered_set unordered_set 都是返回的 1 或者 0。
class Solution {
public:
vector<string> uncommonFromSentences(string s1, string s2) {
unordered_map<string, int> hash1;
unordered_map<string, int> hash2;
vector<string> v;
string a;
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == ' ') {
hash1[a]++;
a = "";
} else a += s1[i];
}
hash1[a]++;
a = "";
for (int i = 0; i < s2.size(); i++) {
if (s2[i] == ' ') {
hash2[a]++;
a = "";
} else a += s2[i];
}
hash2[a]++;
a = "";
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == ' ') {
if (hash1[a] == 1 && hash2.count(a) == 0) v.push_back(a);
a = "";
} else a += s1[i];
}
if (hash1[a] == 1 && hash2.count(a) == 0) v.push_back(a);
a = "";
for (int i = 0; i < s2.size(); i++) {
if (s2[i] == ' ') {
if (hash2[a] == 1 && hash1.count(a) == 0) v.push_back(a);
a = "";
} else a += s2[i];
}
if (hash2[a] == 1 && hash1.count(a) == 0) v.push_back(a);
a = "";
return v;
}
};
关于 unordered_map 和 unordered_set 说法错误的是（D）
A.它们中存储元素的类型不同，unordered_map 存储键值对，而 unordered_set 中只存储 key
B.它们的底层结构相同，都使用哈希桶
C.它们查找的时间复杂度平均都是 O(1)
D.它们在进行元素插入时，都得要通过 key 的比较去找待插入元素的位置
