哈希的介绍

1. unordered系列关联式容器

    下面来看哈希，首先看关联式容器unorder_map和unorder_set，它们底层是哈希表，用法和map set一样。下面浅浅过一下，它是单向迭代器，因为没有rbegin和rend。也就是红黑树和哈希表实现的map和set用法几乎相同，区别是：1.unorder系列是单向迭代器。2.unorder系列遍历出来不是有序的。下面演示一下：

它只能去重，不能排序，它也是有multi版本的。再演示一下unorder_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倍，可以这样写吗：

用resize开一段大空间，把数据拷贝下来：

现在查找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，若自己传了就用自己的：

再看一个方法：

平时用unorder_map/set也要取模，但用的时候也没有写仿函数，所以这里可用模板特化解决：

这样就可以做到不传仿函数，当K是string时走特化的，其余走正常的。但是string第一个字母ASCII值再这取模也不好，第一个字母相同的都冲突了，可以考虑把所有ASCII值加起来，这样就会好很多：

但可能还会有换顺序的场景：

这样还是会引发很多冲突，所以有人专门对这做了研究叫字符串哈希算法：

各种字符串Hash函数 - clq - 博客园 (cnblogs.com)https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html我们可以把大佬的方法用一下，每次加之前乘一个131，这样冲突就可以大大减少了：

4.二次探测及拉链法

    以上说的方式叫闭散列的开放定址法，特点是从当前空间里去找下一个位置，但它有很强的局限性。以上说的核心方法是线性探测，它的特征是当前位置已有值，就去后面依次找其它位置。缺陷是会导致互相堵，此时有人想能不能冲突时让它们往外分散一些，所以有人提出了二次探测。二次探测不是说探测两次，是按二次方的角度探测。比如线性探测是模一个值算出一个位置，若该位置有值不断向后找；二次探测就是每次走i^2探测：

这样多值冲突时会相对分散开。

    下面再来说一个方法，能不能不要说你的空间被占了就去占别人的空间，想个办法别互相影响，于是有人提出了拉链法，也叫哈希桶。它是把数组弄成指针数组，数组中不存值了，位置冲突了内部消化。如下图：

比如来了1，开一个结点把1挂起来；来了111，继续开一个结点挂起来。也就是冲突的值不是用探测的方式解决，而是用一个链表把它挂起来。下面先来搭个框架(为了防止命名冲突，前面的方法用open_address括起来，下面的方法叫hash_backet)：现在的重点是，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.完整代码

//HashTable.h #pragma once #include <vector> #include <string> #include <stdio.h> template<class K> struct DefaultHashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //struct StringHashFunc //{ // size_t operator()(const string& str) // { // return str[0]; // } //}; 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((double)_n / (double)_table.size() >= 0.7) 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); } ////扩容 ////if((double)_n / (double)_table.size() >= 0.7) //if (_n*10 / _table.size() >= 7) //{ // size_t newSize = _table.size() * 2; // vector<HashData> newtable; // newtable.resize(newSize); // //遍历链表，重新映射到新表 //} //线性探测 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; //负载因子到1就扩容 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：

find这里还要补充keyofT：

补完后都跟着改了：

改正个错误：

    下面实现set和map的插入：

    下面来实现迭代器，对哈希表而言要把迭代器封装一下：

begin后找到第一个桶的位置，++找node的next就可往下走。那当前桶走完了怎么走到下一个桶？需要用表帮我们找下一个桶。先实现起来走着看，里面需要一个结点指针，迭代器需要用结点指针来构造：

下面看operator++，简单实现是如果_node的next不为空，就继续往下走；若为空，就相当于一个桶走完了，那就要找后一个桶。找后一个桶时先算一下自己当前在几号桶，可提前存一个下标以便知道在几号桶：

除了下标在哪知道外，还需要哈希表对象，因为光有下标也没法往后走，因此最好都传过来，定义一个HashTable的指针：

有了上述后来看下图：

这样可算出当桶的位置，算完后++hashi，从下一个位置查找下一个不为空的桶。如果桶不为空就break找到了，为空就++：

循环出来要么找到了，要么找到了结尾也没有找到，所以这样写：

这样不用外面再判断了，循环出来说明所有桶都走完了。若走完了找不到让空充当结束位置：

下面进一步完善一下：

    现在有了++和构造，再来补充一下!=和==：

下面实现begin，找第一个桶就行，遍历找，找到第一个桶后就构造一个迭代器返回，第一个是个结点指针，第二个可传this，this就是哈希表指针，没找到就返回空：

再来实现end，构造一个空的返回去：

下面先从set中套一层，再从map中套一层：

但这里还是有相互依赖的问题：

HashTable里用迭代器没事，因为迭代器的实现在前面，HTIterator里面会用HashTable。这样谁在前面都会有问题，因此可以做一个前置声明，就是告诉你HashTable是定义了的：

最后再实现一下operator*和operator->：

测试时会遇到这样的问题：

说是类外面不能访问私有，可以弄一个友元，类模板这友元带模板参数：

可以测试看一下(erase最后补一下--_n)：

    下面来解决const迭代器的问题：

可以被修改是一个问题，我们的目标是key不能被修改。还是老方法，弄个const迭代器，控制返回值T就可以了，所以多加参数改一下：

现在把const迭代器外层壳套上了，开始套里面的：

现在先完成set，set这K不允许修改，可以这样：

这样普通和const对象都可以调用。下面编译一下：

报错说构造有问题，const修饰*this，因为const修饰后传的时候是这样：

权限放大传不过去。可以考虑重载一下，把成员遍量也改成const的：

下面来看map的，还是老样子，pair的位置改为const K：

再改一下返回值问题：

再完善insert这里，插入失败返回false；若是新插入的返回新结点和true：

改完insert后其余位置就要变了：

编译后set出现了老问题：

set调用的是哈希表中的insert：

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.完整代码

//unordered_map.h #pragma once #include "HashTable.h" 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; }; }

//unordered_set.h #pragma once #include "HashTable.h" 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) { //return _ht.Insert(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; }; }

//HashTable.h #pragma once #include <vector> #include <string> #include <stdio.h> #include <string> template<class K> struct DefaultHashFunc { size_t operator()(const K& key) { return (size_t)key; } }; //struct StringHashFunc //{ // size_t operator()(const string& str) // { // return str[0]; // } //}; 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((double)_n / (double)_table.size() >= 0.7) 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); } ////扩容 ////if((double)_n / (double)_table.size() >= 0.7) //if (_n*10 / _table.size() >= 7) //{ // size_t newSize = _table.size() * 2; // vector<HashData> newtable; // newtable.resize(newSize); // //遍历链表，重新映射到新表 //} //线性探测 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; //负载因子到1就扩容 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; //存储了多少个有效数据 }; }