哈希
unordered_set 和 unordered_map
unordered_set
set 和 unordered_set 的功能高度相似，只是底层结构不同。
unordered_set 与 set 的差异
- unordered_set 和 set 的第一个差异是对 key 的要求不同，set 要求 Key 支持小于比较，而 unordered_set 要求 Key 支持转成整形且支持等于比较。
- unordered_set 和 set 的第二个差异是迭代器的差异，set 的 iterator 是双向迭代器，unordered_set 是单向迭代器。其次 set 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 set 迭代器遍历是有序 + 去重。而 unordered_set 底层是哈希表，迭代器遍历是无序 + 去重。
- unordered_set 和 set 的第三个差异是性能的差异，整体而言大多数场景下，unordered_set 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而 哈希表增删查平均效率是 O(1)。
unordered_map
map 和 unordered_map 也是高度相似，只有些许差异。
- map 要求 Key 支持小于比较，而 unordered_map 要求 Key 支持转成整形且支持等于比较。
- map 的 iterator 是双向迭代器，unordered_map 是单向迭代器，map 底层是红黑树，unordered_map 底层是哈希表，迭代器遍历是 Key 无序 + 去重。
- 大多数场景下，unordered_map 的增删查改更快一些，因为红黑树增删查改效率是 O(logN)，而 哈希表增删查平均效率是 O(1)。
代码使用
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int main() {
unordered_set<int> s = {3, 1, 6, 7, 8, 2, 1, 1, 5, 6, 7, 6};
unordered_set<int>::iterator it = s.begin();
while(it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
unordered_multiset/unordered_multimap
unordered_multiset/unordered_multimap 与 multiset/multimap 也是高度相似，支持 Key 冗余。差异也如上。
哈希概念
哈希 (hash) 又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。
直接定址法
当关键字的范围比较集中时，如一组关键字都在 [0,99] 之间，那么开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ASCII 码 - 字符 a 得到的值就是存储位置的下标。也就是说 直接定址法本质即用关键字计算出一个绝对位置 或者 相对位置。（比如计数排序）
哈希冲突
使用直接定址法，当关键字的范围比较分散时，会很浪费内存甚至内存不够用。假设我们只有数据范围是 [0, 9999] 的 N 个值，要映射到一个 M 个空间的数组中（一般 M >= N），那么就要借助哈希函数 h(x)，关键字 key 被放到数组的 h(key) 位置，注意，h(key) 计算出的值必须在 [0, M) 之间。
这里存在的一个问题是，两个不同的 key 可能会映射到同一个位置，这种问题即 哈希冲突，或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。
负载因子
假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么 负载因子=N/M。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
将关键字转为 size_t
将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数。源码中用仿函数 Hash 把 key 转换成 size_t。如果遇到像 string、Date 无法强转的，则自己实现，string 较为常用，可以特化模板。
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& s) {
size_t hash = 0;
for(auto& e : s) //可以有效避免"abcd"，"bcad"冲突的情况
hash += e;
hash *= 131;
return hash;
}
};
哈希函数
一个好的哈希函数应该让 N 个关键字被等概率且均匀地散列分布到哈希表的 M 个空间中，实际中很难做到，但是要尽量往这个方向去考量设计。
除法散列法/除留余数法
除法散列法也叫除留余数法，假设哈希表的大小为 M，key 除以 M 的余数作为映射位置的下标，即哈希函数为：h(key) = key % M。
使用除法散列法时，要尽量 避免 M 为某些值，如 2 的幂，10 的幂等。如果是 2^x，key % 2^x 本质相当于保留 key 的后 X 位（把 key 转成二进制表示的位），那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。如果是 10^x，保留的都是 10 进值的后 x 位，如：{112, 12312}，如果 M 是 100，也就是 10^2，那么计算出的哈希值都是 12。
所以，使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个素数。
sgi 版本的哈希表使用的方法，给了一个 近似 2 倍的素数表。
inline unsigned long __stl_next_prime(unsigned long n) //会频繁调用，inline 修饰，减少消耗
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
//一个数组
53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
402653189, 805306457, 1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
pos == last ? *(last - ) : *pos;
}
初始时哈希表的大小 M 可以为 __stl_next_prime(0)，即 M=53，此时 M 既不接近 2^5，也不接近 2^6，同时也是素数。扩容后 M=97，也实现了近似 2 倍扩容。
哈希函数还有其他方法，如乘法散列法、全域散列法等。
处理哈希冲突：开放定址法
在开放定址法中，所有的元素都放到哈希表，当一个关键字 key 用哈希函数计算出的位置冲突了，则 按照某种规则找到一个没有存储数据的位置进行存储。规则有三种：线性探测、二次探测、双重探测。开放定址法要求 负载因子小于 1。
线性探测
- 从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。
- h(key)=hash0=key % M，hash0 位置 冲突了，则 线性探测公式为：hc(key,i)=hashi=(hash0+i) % M，i={1，2，3……M-1}。由于负载因子小于 1，哈希表中一定有空位置，所以最多探测 M-1 次，一定能找到一个存储 key 的位置。
- 如果 hash0 位置连续冲突，hash0，hash1，hash2 位置 已经存储数据，后续映射到 hash0，hash1，hash2，hash3 的值都会 争夺 hash3 位置，这种现象叫做 群集/堆积。二次探测可在一定程度上改善。
二次探测
- 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。
- h(key)=hash0=key % M，hash0 位置 冲突了，则 二次探测公式为：hc(key,i)=hashi=(hash0 ± i^2) % M，i={1，2，3……M/2}。
- 当 hashi=(hash0 - i^2) % M 时，若 hashi<0，则 hashi+=M。
开放定址法线性探测代码实现
要给每个存储位置加一个 状态标识，否则删除一些值以后，会影响后面冲突的值的查找。例如删除 30，查找 20，用哈希函数求得映射下标为 9，但是下标为 9 的位置已经为空，没找到，但哈希表中其实又是有 20 的。
给每个存储位置加一个标识状态 {EXIST，DELETE，EMPTY}。查找一个 key，求得 映射位置 h(key)，发现状态为 EMPTY，说明整个哈希表中没有 key。如果哈希表的其他位置存在 key，表明因为冲突，h(key) 位置已经被别的值占了，则 h(key) 位置的状态应是 EXIST 或 DELETE，矛盾，所以整个哈希表中绝对没有 key。
控制负载因子到 0.7 时 扩容。
如果 key 不能取模则用仿函数转成 size_t。
#include <vector>
enum State { EXIST, EMPTY, DELETE };
template<class K, class V>
struct HashData {
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& s) {
size_t hash = 0;
for(auto& e : s) {
hash += e;
hash *= 131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n) {
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
, , , , , , , , , ,
, , , , , , ,
, , , , , ,
, , , ,
};
* first = __stl_prime_list;
* last = __stl_prime_list + __stl_num_primes;
* pos = (first, last, n);
pos == last ? *(last - ) : *pos;
}
open_address {
< , , = HashFunc<K>>
HashTable {
:
() : _tables(__stl_next_prime()), _n() {}
( pair<K, V>& kv) {
((kv.first)) ;
(_n * / _tables.() >= )
{
HashTable<K, V, Hash> newht;
newht._tables.(__stl_next_prime(_tables.() + ));
(& e : _tables) {
(e._state == EXIST) newht.(e._kv);
}
_tables.(newht._tables);
}
Hash hash;
hash0 = (kv.first) % _tables.();
hashi = hash0;
i = ;
(_tables[hashi]._state == EXIST) {
hashi = (hash0 + i) % _tables.();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
;
}
{
Hash hash;
hash0 = (key) % _tables.();
hashi = hash0;
i = ;
(_tables[hashi]._state != EMPTY) {
(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
&_tables[hashi];
hashi = (hash0 + i) % _tables.();
i++;
}
;
}
{
HashData<K, V>* ret = (key);
(ret) {
ret->_state = DELETE;
;
}
;
}
:
vector<HashData<K, V>> _tables;
_n;
};
}
测试
#include "HashTable.h"
int main() {
open_address::HashTable<int, int> ht;
int a[] = {19, 30, 5, 36, 13, 20, 21, 12};
for(auto e : a) {
ht.Insert({e, e});
}
if(ht.Find(13)) ht.Erase(13);
else cout << "没找到" << endl;
return 0;
}
如果 key 为日期类，则要自己实现仿函数。
struct Date {
int _year;
int _month;
int _day;
Date(int year=1, int month=1, int day=1) : _year(year), _month(month), _day(day) {}
bool operator==(const Date& d) {
return _year == d._year && _month == d._month && _day == d._day;
}
};
struct DateHashFunc {
size_t operator()(const Date& d) {
size_t hash = 0;
hash += d._year; hash *= 131;
hash += d._month; hash *= 131;
hash += d._day; hash *= 131;
return hash;
}
};
int main() {
string a1[] = {"sort", "insert", "abcd", "bcad", "aadd"};
open_address::HashTable<string, string> ht;
for(auto& e : a1) ht.Insert({e, e});
int a2[] = {-19, -30, 5, 36, 13, 20, 21, 12};
open_address::HashTable<int, int> ht1;
(& e : a2) ht({e, e});
open_address::HashTable<Date, , DateHashFunc> ht2;
ht({{, , }, });
ht({{, , }, });
;
}
处理哈希冲突：链地址法
开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，则把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者 哈希桶。
链地址法对负载因子没有要求，我们把 负载因子控制在 1，如果某个桶特别长时，当桶的长度大于 8，就把链表转成红黑树。
代码实现
namespace hash_bucket {
template<class K, class V>
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K,V>& kv) : _kv(kv), _next(nullptr) {}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
public:
HashTable() : _tables(__stl_next_prime(0)), _n(0) {}
//拷贝构造
HashTable(const HashTable<K, V, Hash>& ht) {
_tables.resize(ht._tables.size());
for(int i = 0; i < ht._tables.size(); i++) {
Node* htcur = ht._tables[i];
while(htcur) {
Node* newnode = new Node(htcur->_kv); //尾插
Node* cur = _tables[i];
if(cur == nullptr) _tables[i] = newnode;
else {
while(cur->_next) cur = cur->_next;
cur->_next = newnode;
}
htcur = htcur->_next;
}
}
_n = ht._n;
}
~HashTable() {
for(int i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
cur;
cur = next;
}
_tables[i] = ;
}
}
{
((kv.first)) ;
Hash hash;
(_n == _tables.())
{
;
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
hashi = (kv.first) % newTable.();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = ;
}
_tables.(newTable);
}
hashi = (kv.first) % _tables.();
Node* newnode = (kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
;
}
{
Hash hash;
hashi = (key) % _tables.();
Node* cur = _tables[hashi];
(cur) {
(cur->_kv.first == key) cur;
cur = cur->_next;
}
;
}
{
Hash hash;
hashi = (key) % _tables.();
Node* prev = ;
Node* cur = _tables[hashi];
(cur) {
(cur->_kv.first == key)
{
(prev == )
_tables[hashi] = cur->_next;
prev->_next = cur->_next;
cur;
--_n;
;
} {
prev = cur;
cur = cur->_next;
}
}
;
}
:
vector<Node*> _tables;
_n = ;
};
}
测试
int main() {
int a[] = {19, 30, 5, 36, 13, 20, 21, 12, 24, 96};
hash_bucket::HashTable<int, int> ht;
for(auto& e : a) {
ht.Insert({e, e});
}
ht.Insert({100, 100});
ht.Insert({101, 101});
cout << ht.Find(19) << endl;
cout << ht.Find(36) << endl;
cout << ht.Find(96) << endl;
cout << ht.Find(101) << endl << endl;
ht.Erase(19);
ht.Erase(36);
ht.Erase(96);
ht.Erase(101);
cout << ht.Find(19) << endl;
cout << ht.Find(36) << endl;
cout << ht.Find(96) << endl;
cout << ht.Find(101) << endl << endl;
return 0;
}
哈希表封装 unordered_set 和 unordered_map
与红黑树封装 set 和 map 类似，HashTable 也实现了泛型，其中 HashTable 用链地址法实现，仿函数 KeyOfT 取出 T 类型对象的 Key 对象，仿函数 Hash 转成 size_t。
代码实现
//HashTable.h
#include <vector>
#include <string>
using namespace std;
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
struct HashFunc<string> {
size_t operator()(const string& s) {
size_t hash = 0;
for(auto& e : s) {
hash += e;
hash *= 131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n) {
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, , , , , , ,
, , , , , , ,
, , , , , ,
, , , ,
};
* first = __stl_prime_list;
* last = __stl_prime_list + __stl_num_primes;
* pos = (first, last, n);
pos == last ? *(last - ) : *pos;
}
hash_bucket {
< >
{
T _data;
HashNode<T>* _next;
( T& data) : _data(data), _next() {}
};
< , , , >
;
< , , , , , >
{
HashNode<T> Node;
HashTable<K, T, KeyOfT, Hash> HT;
HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
HT* _ht;
(Node* node, HT* ht) : _node(node), _ht(ht) {}
Ref *()
{
_node->_data;
}
Ptr ->()
{
&_node->_data;
}
!=( Self& s) {
_node != s._node;
}
Self& ++()
{
(_node->_next)
_node = _node->_next;
{
KeyOfT kot;
Hash hash;
hashi = ((_node->_data)) % _ht->_tables.();
hashi++;
(hashi < _ht->_tables.()) {
_node = _ht->_tables[hashi];
(_node) ;
hashi++;
}
(hashi == _ht->_tables.())
_node = ;
}
*;
}
};
< , , , = HashFunc<T>>
HashTable {
< K, T, Ref, Ptr, KeyOfT, Hash>
HTIterator;
HashNode<T> Node;
:
HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
HTIterator<K, T, T&, T*, KeyOfT, Hash> ConstIterator;
{
(_n == ) ();
( i = ; i < _tables.(); i++)
{
Node* cur = _tables[i];
(cur) (cur, );
}
();
}
{
(, );
}
{
(_n == ) ();
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) (cur, );
}
();
}
{
(, );
}
() : _tables(__stl_next_prime()), _n() {}
~() {
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
cur;
cur = next;
}
_tables[i] = ;
}
}
{
KeyOfT kot;
it = ((data));
(it != ()) {it, };
Hash hash;
(_n == _tables.())
{
vector<Node*> _newTable;
_newTable.(__stl_next_prime(_tables.() + ));
( i = ; i < _tables.(); i++) {
Node* cur = _tables[i];
(cur) {
Node* next = cur->_next;
hashi = ((cur->_data)) % _newTable.();
cur->_next = _newTable[hashi];
_newTable[hashi] = cur;
cur = next;
}
}
_tables.(_newTable);
}
hashi = ((data)) % _tables.();
Node* newnode = (data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
{(newnode, ), };
}
{
KeyOfT kot;
Hash hash;
hashi = (key) % _tables.();
Node* cur = _tables[hashi];
(cur) {
((cur->_data) == key) {cur, };
cur = cur->_next;
}
();
}
{
Hash hash;
KeyOfT kot;
hashi = (key) % _tables.();
Node* cur = _tables[hashi];
Node* prev = ;
(cur) {
((cur->_data) == key)
{
(prev == )
_tables[hashi] = cur->_next;
prev->_next = cur->_next;
cur;
--_n;
;
} {
prev = cur;
cur = cur->_next;
}
}
;
}
:
vector<Node*> _tables;
_n = ;
};
}
mine {
< , = HashFunc<K>>
unordered_set {
SetKeyOfT {
K& ()( K& key) {
key;
}
};
:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::Iterator iterator;
hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::ConstIterator const_iterator;
{
_ht.();
}
{
_ht.();
}
{
_ht.();
}
{
_ht.();
}
{
_ht.(key);
}
{
_ht.();
}
{
_ht.(key);
}
:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
{
unordered_set<>::const_iterator cit = us.();
cout << (us).() << endl;
(cit != us.()) {
cout << *cit << ;
++cit;
}
cout << endl;
( e : us) {
cout << e << ;
}
cout << endl << endl;
}
}
mine {
< , , = HashFunc<K>>
unordered_map {
MapKeyOfT {
K& ()( pair<K, V>& kv) {
kv.first;
}
};
:
hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash>::Iterator iterator;
hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
{
_ht.();
}
{
_ht.();
}
{
_ht.();
}
{
_ht.();
}
V& []( K& key) {
ret = ({key, ()});
ret.first->second;
}
{
_ht.(kv);
}
{
_ht.(key);
}
{
_ht.(key);
}
:
hash_bucket::HashTable<K, pair< K, V>, MapKeyOfT, Hash> _ht;
};
{
unordered_map<string, string>::const_iterator cit = um.();
(cit != um.()) {
cout << cit->first << << cit->second << endl;
++cit;
}
cout << endl;
(& e : um) {
cout << e.first << << e.second << endl;
}
}
}
测试 mine::unordered_set
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "UnorderedSet.h"
#include "UnorderedMap.h"
int main() {
int a[] = {3, 11, 86, 7, 88, 82, 1, 881, 5, 6, 7, 6};
mine::unordered_set<int> us;
for(auto e : a) {
us.insert(e);
}
auto it = us.begin();
while(it != us.end()) {
cout << *it << " ";
++it;
}
cout << endl;
for(auto& e : us) {
cout << e << " ";
}
cout << endl << endl;
mine::print(us);
return 0;
}
测试 mine::unordered_map
int main() {
mine::unordered_map<string, string> dict;
dict.insert({"sort", "排序"});
dict.insert({"字符串", "string"});
dict.insert({"left", "左"});
dict.insert({"right", "右"});
for(auto& e : dict) {
cout << e.first << "：" << e.second << endl;
}
cout << endl;
dict["left"] = "左，剩余";
dict["insert"] = "插入";
dict["string"];
auto it = dict.begin();
while(it != dict.end()) {
//it->second += "x";
cout << it->first << "：" << it->second << endl;
++it;
}
cout << endl;
print(dict);
return 0;
}
