跳到主要内容C++ 哈希表原理与实现详解 | 极客日志C++算法
C++ 哈希表原理与实现详解
本文介绍了 C++ 中哈希表（Hash Table）的核心原理及实现细节。涵盖 unordered_map/set 底层结构，哈希函数设计（包括仿函数与模板特化），冲突解决策略（闭散列线性探测与拉链法），负载因子控制与扩容机制，以及迭代器的封装实现。通过完整代码示例展示了如何从零构建支持字符串 Key 的哈希表，并封装为 unordered_set 和 unordered_map。
接口猎人1 浏览 1. unordered 系列关联式容器
下面来看哈希，首先看关联式容器 unordered_map 和 unordered_set，它们底层是哈希表，用法和 map set 一样。下面浅浅过一下，它是单向迭代器，因为没有 rbegin 和 rend。也就是红黑树和哈希表实现的 map 和 set 用法几乎相同，区别是：1.unorder 系列是单向迭代器。2.unorder 系列遍历出来不是有序的。
它只能去重，不能排序，它也是有 multi 版本的。再演示一下 unordered_map：
2. 哈希
下面正式介绍哈希。什么是哈希呢？我们以前遇到的搜索有这样几类：首先是暴力查找，在一个数组里都查，这样非常慢。于是有人衍生出了有序数组的二分查找，但它的前提是排序，而且增删查改不方便，过程中为了保证有序会涉及大量的数据挪动。因此衍生出了平衡搜索树，此时基础上又出现了新的搜索，这种搜索叫哈希 (散列)。它的本质是存储的值跟存储位置建立出一个映射关系，什么意思呢，先来看一个计数排序的样例：
有上面这样的一组值，最小的值是 15，最大的值是 30，总共开了 16 个空间。然后存映射关系 (次数)，15 映射第一个位置，16 映射第二个位置……以后值是多少去对应的位置找，这就是一种哈希 (再如图书馆按照字母号找书等)。但上述如果数据太分散空间消耗量会很大，之前的方式在哈希表中叫直接定址法 (用于值的分布范围集中)，它是根据值相对直接找一个位置，数据太分散不适合。此时若数据比较分散：
还是开固定空间，比如开 20 个。来个值 key，这用除留系数法，通过除留的系数确定位置，满了再考虑扩容。用 i = key % 20(空间个数)，这样算出来第 i 个位置，然后把值放进去。它的问题是会引发哈希冲突或碰撞，也就是不同的值，可能会映射到同一个位置，值和位置是多对一的关系，比如下图：
27 和 47 模 20 都是 7，在同一个位置，那怎么办？有一种方法是再按照一种规则去找下一个位置存，比如有种方式叫闭散列——开放定址法：1.线性探测 2.二次探测。也就是找的这个位置被占了，再去找其它位置占。还有一种方式叫拉链法，也叫哈希桶。这个位置存指针，把桶用指针链接起来，一个位置有多个值来个多对一的关系，这种方式不影响别人：
3. 闭散列——开放定址法
下面看看闭散列（开放地址法）中的线性探测，如图：
空间大小是 10，来了一堆值映射到这些位置。在看下图：
现在来了 111 和 1 冲突了，放到下一个位置。44 和 4 冲突了，然后不断向后探测都有值，找到 8 位置有空位就把值放进去了。如果走完了没找到空位置，要立刻扩容吗？比如下图场景：
只有 19 个，现在来了个 29，往后走越界了，不需要立刻扩容，循环回到开头继续寻找空位放。再看一个问题，下图中想查找 44 怎么查找：
44%10 算出在 4 的位置，但 44 不在这个位置，不一定停，可能在下一个位置，就不断往后找，找到 8 位置就找到了。如果找的是 54，模出来在 4 位置，不是 54 往后走，找到空位置可以停下来。侧面反映出如果表太满了，此时查找一些不存在的值效率必然下降，接近暴力查。还有个问题是比如要删 6，是找到 6 在的位置然后删 6 吗：
这样会有些问题：1.把 6 删了该位置的值抹成 0 还是随机值？2.此时查 44 会发生什么？找到空就结束了，这样删除影响了查找。怎么解决？这里要想办法用一个标记，用状态标记，这严格说有三种状态：1.EXIST 存在 2.EMPTY 空 3.DELETE 删除。此时想删 6，不需要真干了 6，把这个状态设置为 DELETE，然后查 44 时遇到 DELETE 不停止，遇到 EMPTY 才停止。下面来写一下：还是定义为 KV 结构，如果自己写就需要写个数组并定义数组大小及容量，现在用 vector 就行。这里不能直接定义出是一个 pair 的结构，因为除了 KV 还有状态，所以枚举状态。再定义一个哈希的数据，给个 pair 和 STATE 数据。哈希表中定义一个 vector，里面放 HashDate，再定义一个 n，那 vector 已有 size 了为啥还要定义 n 呢？因为它和顺序表的区别是它的数据要分散存储，它的物理结构是数组，逻辑上是个哈希表，这的 n 表示存储的有效数据的个数：
vector 可以不初始化，因为它有默认构造，n 可以给个值。下一步来 insert 一个值，insert 一个 pair(先不考虑扩容，把算位置的问题解决了)：先算一个起始位置，可以用 first 模上表的大小。这的大小是 size 还是 capacity 呢？假设模的是_table.capacity，模完后刚好那个位置没有被占，就把它的值正常放进去：
假设 vector 是这样的：
现在比如模出的位置在 18，此时 18 这个位置不能访问，方括号中会断言下标在 0~size-1。所以这里不能模 capacity，要模 size，其次最好让 size 和 capacity 相等，这样不存在空间浪费的问题 (后面扩容想办法)：
下面继续完善，如果这个位置有值要继续探测，探测到空说明没值可以放；遇到这个位置是删除也是可以填值的：
还有个问题是这个表不敢太满，比如只剩下 1 或 2 个位置随便来个值都可能冲突，若满了来值还会造成死循环，因此哈希表中引入了一个概念叫负载或载荷因子：
它用来标识存的值占空间的比列。负载因在越大，冲突概率越大，空间利用率越高；负载因为越小，冲突概率越小，空间利用率越低。通过上述介绍可以看到，哈希表不能满了再扩容，控制负载因子到一定值就扩容。下面写写扩容逻辑：如果 table 大小为 0 或者有效数据个数除大小大于等于 0.7 就扩容，为了有小数记得隐式转化为 double。但 table 刚开始为 0，可写个构造用 resize 让 size 和 capacity 为 10：
现在如果符合条件扩容 2 倍，可以这样写吗：
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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
现在查找 111，111%20==11，会导致去 11 的位置找。这里扩容不是重点，重点是值的重新映射。因此不能直接用 resize 下来值，因为所有的值扩容后映射关系变了，需要重新映射。那应该怎么弄？可以去开一个新的 vector，把原来的值重新插入到 vector 里面：
这有两种方法，第一种方法是弄一个 newtable，newtable resize 一下到当前 2 倍，下一步依旧遍历旧表，重新映射到新表。但是取出旧表的值映射到新表是很麻烦的，因为要重新算位置，并且可能冲突时可能还要把冲突逻辑走一遍：
那怎么解决呢？我不定义一个 vector 的 newtable，而是定义一个哈希表的 newHT，newHT 里面有一个 vector，把这个 vector resize 一下：
然后遍历旧表的数据插入到新表即可，如果状态是存在，插入到新表里面，最后旧表不要了，旧表和新表变换：
这里的亮点是再次复用了 insert 函数，进而复用了线性探测逻辑，空间开好后不走 if 的逻辑。下面测试一下：
下面写一下查找：来一个 key 取模算出一个位置，找到空时还没有找到就结束了，否则继续。值为存在状态且如果第一个值等于 key 就找到了，返回该位置对象，没找到就返回空指针：
再来写一下删除，可以复用 find 找到要删除的值，如果找到了改为删除即可，--n 并返回 true；没有找到返回 false：
这还是有个小问题，Find 这里返回的是 HashData 类型的指针，万一别人拿上后改状态就比较麻烦了。可以选择 Find 那里返回一个 pair，但是 Erase 那的 ret 又不可以了。所以还是这样改：
这里也不可以直接在 HashData 中把 pair 的 k 改成 const key，若改了都没有办法赋值。再看下一部分：
还有一个问题是 key 可能不能取模，整型才能取模，key 可能是 string 或 double 等。此时就要走两层映射，哈希表里把存的值和位置建立出映射关系。用除留余数法必须是整型，若不是整型想办法让它变为整型，如字符串先和整型建立映射，然后再和存储位置建立映射。这里用仿函数解决问题：
需要写两个，一个是默认的 HashFunc，能取模的转化为整型就可以：
哈希中传一个默认的哈希 func，里面所有取模的地方多走一层，定义个 Hashfunc 的对象，调它的 ()：
但是 string 不能转整型，再写个 StringFunc，返回 string 的第 0 个字符：
然后 HashFunc 默认传 DefaultHashFunc，若自己传了就用自己的：
平时用 unordered_map/set 也要取模，但用的时候也没有写仿函数，所以这里可用模板特化解决：
这样就可以做到不传仿函数，当 K 是 string 时走特化的，其余走正常的。但是 string 第一个字母 ASCII 值再这取模也不好，第一个字母相同的都冲突了，可以考虑把所有 ASCII 值加起来，这样就会好很多：
这样还是会引发很多冲突，所以有人专门对这做了研究叫字符串哈希算法：
我们可以把大佬的方法用一下，每次加之前乘一个 131，这样冲突就可以大大减少了：
4. 二次探测及拉链法
以上说的方式叫闭散列的开放定址法，特点是从当前空间里去找下一个位置，但它有很强的局限性。以上说的核心方法是线性探测，它的特征是当前位置已有值，就去后面依次找其它位置。缺陷是会导致互相堵，此时有人想能不能冲突时让它们往外分散一些，所以有人提出了二次探测。二次探测不是说探测两次，是按二次方的角度探测。比如线性探测是模一个值算出一个位置，若该位置有值不断向后找；二次探测就是每次走 i^2 探测：
下面再来说一个方法，能不能不要说你的空间被占了就去占别人的空间，想个办法别互相影响，于是有人提出了拉链法，也叫哈希桶。它是把数组弄成指针数组，数组中不存值了，位置冲突了内部消化。如下图：
比如来了 1，开一个结点把 1 挂起来；来了 111，继续开一个结点挂起来。也就是冲突的值不是用探测的方式解决，而是用一个链表把它挂起来。下面先来搭个框架 (为了防止命名冲突，前面的方法用 open_address 括起来，下面的方法叫 hash_bucket)：现在的重点是，HashTable 第一层基础结构是个指针数组，原来按照原生写法要定义二级指针之类的，现在可以用 vector，同时也要给 n 记录存储了多少个有效数据。顺便写一下构造：
下面实现一下 insert，先算一下位置，然后头插：
这里让 newnode 的 next 指向第一个结点，第一个结点的地址在 hashi 的位置，newnode 此时要成为第一个，把 hashi 位置的地址改为 newnode 的就完成头插了：
完成后++n，返回 true，最基本的插入逻辑就完成了：
思考一下这里需要扩容吗？需要扩容，假如不扩容有大量数据时单个桶的拉链会特别长，这样查找数据时效率大大下降，和链表没什么差异了。因此还是要控制负载因子，只不过负载因子可控制的大一些，一般负载因子控制在 1，意味着平均下来每个桶一个数据 (理想状况)。下面实现扩容，如果_n 等于_table 的 size 就扩容。还是用原来的思想，newsize 是原表的两倍，再弄个新表，把旧表数据变换到新表：
但是这种思路这里不太推荐，因为这里复用 insert 时会不断的新开结点，最后还要把结点一个个释放了。相当于把这些结点新开了一遍，旧节点又释放了一遍，太浪费了。因此把结点挪下去就可以了：可以定义 newTable，resize 一下，然后遍历旧链表，把结点迁下来到新表，当前位置迁走后置空一下。都迁走后新表是想要的，变换一下 (底层是 finish，start，endofstor 等的交换)：
下面测试一下 (顺便写个 print 函数方便查看)：
还有个问题，最后新表结束要去调用析构函数，先调 delete[] 数组，delete[] 中先针对每个数组中的对象调用析构函数，但表上每个对象是内置类型，没有析构函数，因此 HashTable 是要单独写析构的 (后面来说)。
下面来写 find，find 就是链表的查找，查找到位置以后再遍历链表就行：
实现完 find 后再补充一下 Insert，如果值已经有了就别插入了，返回 false(同时补充之前的 insert)：
下面来实现删除，这里删除不好复用 find，因为要找前一个和后一个，所以还是找到要删除的位置，再找到前一个：
当 cur 删除 1 位置时，此时 prev 是空，表示头删，所以分两种情况写：
之前写的开放定址法的哈希不用写析构，vector 调用自己的析构时全都干了。哈希桶这里要写析构，因为这只会释放 vector 的空间，不会把桶释放了，桶是内置类型，所以自己实现：
还有像 string 这样的类型也要解决，可以把前面写的 DefaultHashFunc 写到全局，这样大家都可以用，然后再改一下 (所有取模的地方用仿函数转化一下)：
5. 完整代码
template<class K> struct DefaultHashFunc {
size_t operator()(const K& key) { return (size_t)key; }
};
template<> struct DefaultHashFunc<string> {
size_t operator()(const string& str) {
size_t hash = 0;
for (auto ch : str) {
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace open_address {
enum STATE { EXIST, EMPTY, DELETE };
template<class K, class V> struct HashData {
pair<K, V> _kv;
STATE _state = EMPTY;
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable {
public:
HashTable() { _table.resize(10); }
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) { return false; }
if (_n * 10 / _table.size() >= 7) {
size_t newSize = _table.size() * 2;
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
for (size_t i = 0; i < _table.size(); i++) {
if (_table[i]._state == EXIST) {
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST) {
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY) {
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key) {
HashData<const K, V>* ret = Find(key);
if (ret) {
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0;
};
}
namespace hash_backet {
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 HashFunc = DefaultHashFunc<K>> class HashTable {
typedef HashNode<K, V> Node;
public:
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 pair<K, V>& kv) {
if (Find(kv.first)) { return 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(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kv.first) % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) { return cur; }
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) {
_table[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print() {
for (size_t i = 0; i < _table.size(); i++) {
printf("[%d]->", i);
Node* cur = _table[i];
while (cur) {
cout << cur->_kv.first << "->";
cur = cur->_next;
}
printf("NULL\n");
}
}
private:
vector<Node*> _table;
size_t _n;
};
}
6. 封装
下面开始进行封装，先来搭一下 set 架子，它里面是个哈希表，用桶的方法。先改一下：
因为现在不确定是 K 还是 KV 的，是要用第二个模板参数来确定是 K 还是 KV 的。对于 set 而言是 K，对于 map 而言是个 pair：
因为若没有 K find 和 erase 都不好写，假如写成 T：
对 set 可以，对于 map 不可以，难道要传个 pair？显然不合适。然后都跟着改一下，插入的是一个 data：
下面来实现迭代器，对哈希表而言要把迭代器封装一下：
begin 后找到第一个桶的位置，++ 找 node 的 next 就可往下走。那当前桶走完了怎么走到下一个桶？需要用表帮我们找下一个桶。先实现起来走着看，里面需要一个结点指针，迭代器需要用结点指针来构造：
下面看 operator++，简单实现是如果_node 的 next 不为空，就继续往下走；若为空，就相当于一个桶走完了，那就要找后一个桶。找后一个桶时先算一下自己当前在几号桶，可提前存一个下标以便知道在几号桶：
除了下标在哪知道外，还需要哈希表对象，因为光有下标也没法往后走，因此最好都传过来，定义一个 HashTable 的指针：
这样可算出当桶的位置，算完后++hashi，从下一个位置查找下一个不为空的桶。如果桶不为空就 break 找到了，为空就++：
循环出来要么找到了，要么找到了结尾也没有找到，所以这样写：
这样不用外面再判断了，循环出来说明所有桶都走完了。若走完了找不到让空充当结束位置：
下面实现 begin，找第一个桶就行，遍历找，找到第一个桶后就构造一个迭代器返回，第一个是个结点指针，第二个可传 this，this 就是哈希表指针，没找到就返回空：
下面先从 set 中套一层，再从 map 中套一层：
HashTable 里用迭代器没事，因为迭代器的实现在前面，HTIterator 里面会用 HashTable。这样谁在前面都会有问题，因此可以做一个前置声明，就是告诉你 HashTable 是定义了的：
最后再实现一下 operator*和 operator->：
说是类外面不能访问私有，可以弄一个友元，类模板这友元带模板参数：
可以测试看一下 (erase 最后补一下--_n)：
可以被修改是一个问题，我们的目标是 key 不能被修改。还是老方法，弄个 const 迭代器，控制返回值 T 就可以了，所以多加参数改一下：
现在把 const 迭代器外层壳套上了，开始套里面的：
现在先完成 set，set 这 K 不允许修改，可以这样：
这样普通和 const 对象都可以调用。下面编译一下：
报错说构造有问题，const 修饰*this，因为 const 修饰后传的时候是这样：
权限放大传不过去。可以考虑重载一下，把成员遍量也改成 const 的：
下面来看 map 的，还是老样子，pair 的位置改为 const K：
再完善 insert 这里，插入失败返回 false；若是新插入的返回新结点和 true：
set 这里看起来没有问题，我调用你的，你返回 pair 类型，类型看起来是完全匹配的。实际上上框的代码是 unordered_set 里面的，下框的代码是 hashtable 里面的。hashtable 里面的就是个普通迭代器，set 里看起来是普通，实际上是 const 迭代器。也就是这两个 pair 是不一样的 pair 类型，所以它报错了。这里再把 map 中的 const 迭代器加一下：
map 不报错是因为 map 这的 iterator 就是 iterator。那怎么让一个类型转化为另一个类型呢？可以模仿之前的思路，我们需要 pair 中的普通迭代器可转化为 const 迭代器，因此就支持一个相关的构造函数：
当你是 const 迭代器时这是一个构造，当你是普通迭代器时是拷贝构造。改一下错误：
上次的写是先接收 pair，再用 pair 参数构造，相当于把两个参数提取出来，单独调用 pair 构造。这里相当于编译器不严格的检查，因为毕竟是不同类型的 iterator，显然中间支持了转化，保险起见这样写肯定没有问题：
为什么要大费力气的把 insert 返回一个 pair 呢？因为要实现 operator[]：
7. 完整代码
namespace yxx {
template<class K, class V> class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<const K, V>& kv) { return kv.first; }
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::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:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}
namespace yxx {
template<class K> class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) { return key; }
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const { return _ht.begin(); }
iterator end() const { return _ht.end(); }
pair<iterator, bool> insert(const K& key) {
pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<const_iterator, bool>(ret.first, ret.second);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}
template<class K> struct DefaultHashFunc {
size_t operator()(const K& key) { return (size_t)key; }
};
template<> struct DefaultHashFunc<string> {
size_t operator()(const string& str) {
size_t hash = 0;
for (auto ch : str) {
hash *= 131;
hash += ch;
}
return hash;
}
};
namespace open_address {
enum STATE { EXIST, EMPTY, DELETE };
template<class K, class V> struct HashData {
pair<K, V> _kv;
STATE _state = EMPTY;
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable {
public:
HashTable() { _table.resize(10); }
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) { return false; }
if (_n * 10 / _table.size() >= 7) {
size_t newSize = _table.size() * 2;
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
for (size_t i = 0; i < _table.size(); i++) {
if (_table[i]._state == EXIST) {
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST) {
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY) {
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key) {
HashData<const K, V>* ret = Find(key);
if (ret) {
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0;
};
}
namespace hash_bucket {
template<class T> struct HashNode {
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr) {}
};
template<class K, class T, class KeyOfT, class HashFunc> class HashTable;
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;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht) :_node(node), _pht(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; }
};
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>> class HashTable {
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;
}
}
pair<iterator, 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);
}
iterator 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 iterator(cur, this); }
cur = cur->_next;
}
return end();
}
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;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
--_n;
return false;
}
void Print() {
for (size_t i = 0; i < _table.size(); i++) {
printf("[%d]->", i);
Node* cur = _table[i];
while (cur) {
cout << cur->_kv.first << "->";
cur = cur->_next;
}
printf("NULL\n");
}
}
private:
vector<Node*> _table;
size_t _n;
};
}
