一、哈希表的使用
代码用法几乎与 map 和 set 一样。
区别：
C++算法
C++ 哈希表原理及开放寻址与链地址法实现
详细讲解了 C++ 哈希表的原理与实现。内容包括哈希函数的设计方法（除法、乘法、全域散列）、冲突解决策略（开放寻址法中的线性探测、二次探测、双重散列，以及链地址法）。文章还涵盖了哈希表的扩容机制、负载因子处理、迭代器封装以及模拟实现 unordered_map 和 unordered_set 的完整代码示例。适合希望深入理解底层数据结构实现的开发者阅读。
详细讲解了 C++ 哈希表的原理与实现。内容包括哈希函数的设计方法（除法、乘法、全域散列）、冲突解决策略（开放寻址法中的线性探测、二次探测、双重散列，以及链地址法）。文章还涵盖了哈希表的扩容机制、负载因子处理、迭代器封装以及模拟实现 unordered_map 和 unordered_set 的完整代码示例。适合希望深入理解底层数据结构实现的开发者阅读。
代码用法几乎与 map 和 set 一样。
区别：
同样支持 multi 的键值冗余。
好的哈希函数可以让 N 尽可能均匀分布在 M 中。
H(key) = key % M
M 应避免为某些值如 2 的幂，10 的幂。
对哈希表的大小 M 没有要求。取 kA（0<A<1）的小数部分，再M（按比例映射）。A 可以取根号 5-1/2(黄金分割数)。
为防止固定的哈希函数的服务器被攻击，新增两个随机数 a,b。 ((a*k+b)%p)%M 其中，p 为较大的质数，a，b 为随机整数 (a 为 [1,p-1],b 为 [0,p-1))。在任务开始前随机选取，但再映射，查找时 a,b 值不变。
enum state { EXIST, EMPTY, DELETE };
为什么要有 DELETE 状态？ 原因：表大小为 11，如果插入 12（->1）,23(->1,冲突，->2)。我们删除 12，如果直接将 1 的状态设置为 empty，那我们查找 23 时，会找到 1，发现为 empty，就会返回找不到，但实际上时有 23 的。
template<class K,class V> struct hashdata {
std::pair<K, V> _kv;
state _state=EMPTY;
};
template<class K, class V> class hash {
public:
hash() :_tables(23) ,_n(0) { }
private:
std::vector<hashdata<K, V>> _tables;
size_t _n;
};
bool insert(const std::pair<K,V>& kv) {
size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state == EXIST) {
hashi = (hash0 + i) % _tables.size();
++i;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
当位置存在时，就一直找，找到不为存在时就插入。
(1) 二次探测：由于直接这么探测，要是数据堆积那么效率较低。因此，可以将+i 改成+-i 方，让数据更加分散。其它都一样，将 hash0 + i 改为 hash+i*i 即可。
(2) 双重散列法：由于二次探测在冲突时+-的值时一样的，依旧不能解决堆积问题。因此，可以再用一个独立的函数去计算+-的值。要求：函数值<M 且与 M 互质（否则就是在原地几个数中踏步）。
将原来的 vector 拷贝到新的更大的 vector。但是由于 size 不一样，开放寻址的_tables.size() 也不一样，因此需要重新建立关系。并且，不是满了扩容，而是当负载超过一定数时就扩容。
if (_n * 100 / _tables.size() >= 70) {
hash<K, V> newhash;
newhash._tables.resize(2 * _tables.size());
for (auto& e : _tables) {
if (e._state == EXIST) {
newhash.insert(e._kv);
}
}
_tables.swap(newhash._tables);
}
可以参考现代写法，建一个新的哈希表类，再复用插入逻辑，再交换两个 vector。
2 * _tables.size() 由于新哈希表的大小为两倍以前的，因此一定不是质数。解决方案：弄一个质数数组，达到负载就取新的值。
newhash._tables.resize(prim(_tables.size()+1));
写了个二分查找，找到最小的大于 s 的数。
inline size_t prim(size_t s) {
static const size_t prime_list[] = { 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 size_t n = sizeof(prime_list) / sizeof(prime_list[0]);
size_t left = 0, right = n;
while (left < right) {
size_t mid = left + (right - left) / 2;
if (prime_list[mid] < s) left = mid + 1;
else right = mid;
}
if (left < n) return prime_list[left];
return prime_list[n - 1];
}
hashdata<K, V>* Find(const K& key) {
size_t hash0 = key % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY) {
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) {
return &_tables[hashi];
}
hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}
由于上面写的代码仅仅是针对于无符号整型的，但是其它的可以用仿函数的方式转。
template<class K> struct hashfunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<> struct hashfunc<std::string> {
size_t operator()(const std::string& str) {
size_t hash = 0;
for (auto&e:str) {
hash += e;
hash *= 131;
}
return hash;
}
};
在内置类型，如 double 等可以直接强转。但是，string 也可能出现在哈希表中，因此对模板进行特化，优先走特化函数。因此，哈希表要转 2 次，传值->无符号整型->哈希函数映射哈希值。
BKDR 哈希：String 如何转无符号整型。如果将每一位简单相加，那么很容易冲突。因此，可以加一位再乘一个质数（选择 131）以减少冲突。
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 cmp {
size_t operator()(const date& d) const {
size_t has = 0;
has += d._year;
has *= 10000;
has += d._month;
has *= 100;
has += d._day;
return has;
}
};
因此，哈希表做 key 的要求：能转为整型，可以有不等于的比较。
由于开放寻址法无论怎么探测都无法解决过多数据堆积问题。因此，将哈希表数组中存放链表将冲突的值挂下来。这个放地址的东西就叫桶。
struct hashnode {
std::pair<K, V> _kv;
hashnode* _next;
hashnode(const std::pair<K,V>&kv) :_kv(kv) ,_next(nullptr) { }
};
bool insert(const std::pair<K, V>& kv) {
hash ha;
if (_n * 100 / _tab.size() >= 70) {
hashtab<K, V, hash> newhash;
newhash._tab.resize(prim(_tab.size() + 1));
for (int i = 0; i < _tab.size(); i++) {
node* cur = _tab[i];
while (cur) {
node* next = cur->_next;
size_t has = ha(cur->_kv.first) % newhash._tab.size();
cur->_next = _tab[has];
_tab[has] = cur;
cur = next;
}
_tab[i] = nullptr;
}
_tab.swap(newhash._tab);
}
size_t has = ha(kv.first) % _tab.size();
node* newnode = new node(kv);
newnode->_next = _tab[has];
_tab[has] = newnode;
++_n;
return 1;
}
由于链地址法没有那么害怕哈希冲突，因此可以忍受较高的负载因子。甚至可以满了再扩容。但是，由于需要回收利用原先的节点，因此就不能让扩容直接复用插入了，否则会浪费。插入节点选择头插。
Iterator Find(const K& key) {
KofT kot;
hash _hash;
size_t hashi = _hash(key) % _tab.size();
node* cur = _tab[hashi];
while (cur) {
if (kot(cur->_data) == key) {
return Iterator(cur, this);
}
cur = cur->_next;
}
return End();
}
bool Erase(const K& key) {
KofT kot;
size_t hashi = key % _tab.size();
node* prev = nullptr;
node* cur = _tab[hashi];
while (cur) {
if (kot(cur->_data) == key) {
if (prev == nullptr) { // 头结点
_tab[hashi] = cur->_next;
} else { // 中间节点
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
} else {
prev = cur;
cur = cur->_next;
}
}
return false;
}
用哈希函数找到桶的地址，再头插到对应地点。查询返回迭代器和 bool 类型的 pair 值。
template<class K,class T,class ref,class ptr,class KofT,class hash> struct uniterator {
typedef hashtab<K, T, KofT, hash> utb;
typedef uniterator<K, T, ref, ptr, KofT, hash> self;
typedef unordered_node<T> node;
node* _node;
const utb* _utb;
uniterator(node* __node, const utb* __utb) :_node(__node) ,_utb(__utb) { }
};
(1) 模板的作用：由于需要普通迭代器和 const 迭代器，因此模板需要 ref 和 ptr 参数，并且由于需要算哈希函数，因此需要仿函数 KofT 取出 class T 的 T 中的 key。此外，在遍历时需要计算出从哪里开始，需要哈希函数。需要桶的指针，因此需要 K 和 T。
(2) 通指针要用 const：因为调用 const 迭代器时为了值不被修改，因此这么声明。
ConstIterator Begin() const
Const 表示 this 指针指向对象为 const，因此构造函数传也需要为 const，否则权限放大。
ref operator*() { return _node->_data; }
ptr operator->() { return &(_node->_data); }
bool operator!=(const self& s) { return _node != s._node; }
self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else {
KofT kot;
hash ha;
size_t hashi = ha(kot(_node->_data)) % _utb->_tab.size();
++hashi;
while (hashi < _utb->_tab.size()) {
_node = _utb->_tab[hashi];
if (_node) break;
else ++hashi;
}
// 所有桶都走完了，end() 给的空标识的_node
if (hashi == _utb->_tab.size()) {
_node = nullptr;
}
}
return *this;
}
Map:
template<class K,class V,class hash= hashfunc<K>> class unorderedmap {
struct KofT {
const K& operator()(const std::pair<K, V>& kv) {
return kv.first;
}
};
typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::Iterator iterator;
typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::ConstIterator const_iterator;
public:
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
const_iterator begin() const { return _ht.Begin(); }
const_iterator end() const { return _ht.End(); }
std::pair<iterator, bool> insert(const std::pair<K, V>& kv) { return _ht.Insert(kv); }
V& operator[](const K& k) {
std::pair<iterator, bool> ret = insert({ k,V() });
return ret.first->second;
}
iterator Find(const K& key) { return _ht.Find(key); }
bool Erase(const K& key) { return _ht.Erase(key); }
private:
hashtab<K, std::pair<const K, V>, KofT, hash> _ht;
};
Set:
template<class K, class hash = hashfunc<K>> class unorderedset {
struct KofT {
const K& operator()(const K& k) const {
return k;
}
};
typedef typename hashtab<K, K, KofT, hash>::Iterator iterator;
typedef typename hashtab<K, K, KofT, hash>::ConstIterator const_iterator;
public:
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
const_iterator begin() const { return _ht.Begin(); }
const_iterator end() const { return _ht.End(); }
std::pair<iterator, bool> insert(const K& k) { return _ht.Insert(k); }
K& operator[](const K& k) {
std::pair<iterator, bool> ret = insert(k);
return ret.first;
}
iterator Find(const K& key) { return _ht.Find(key); }
bool Erase(const K& key) { return _ht.Erase(key); }
private:
hashtab<K, K, KofT, hash> _ht;
};
和 map，set 类似，需要 key，data（map 为<K,V>,set 为 K）。同样需要传 keyoft 用来取出 key 值。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online