阅读量:0
目录
1、unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到O(logN)，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，其底层结构是使用哈希表实现的。
这四个容器是unordered_set、unordered_map、unordered_multiset和unordered_multimap。这四个容器后序会有详细介绍，这里就简单介绍一下unordered_set和set的区别，为了后面更好地介绍哈希表
unoredered_set和set百分之90的内容都是相同的，不同点有：
1. 对key的要求不同
set：支持比较大小(自定义类型自己写比较函数)
unordered_set：支持key转化为整型 + 比较相等
2. set遍历有序，unordered_set遍历无序
3. set是双向迭代器，unordered_set是单向迭代器
4. 性能差异(插入、删除、搜索)
set：O(logN) unordered_set：O(1)
2、哈希概念
哈希/散列是一种思想，指的是值与值建立映射关系
哈希表/散列表是根据哈希思想设计出来的数据结构，是将值与存储位置建立映射关系
我们使用一道题来引入哈希表
这道题是只包含小写字母的，所以我们可以想到，创建一个大小为26的整型数组，用一个下标代表一个字符，下标 = 字符 - ‘a’，然后遍历一遍字符串s，统计出每个字符出现的个数，完成之后，再遍历一次字符串s，如果遍历到的字符对应的下标的值是1，就代表这个字符再字符串中只出现了1次，也就是结果
class Solution { public: int firstUniqChar(string s) { // 统计每个字符出现的次数 int count[26] = {0}; int size = s.size(); for(int i = 0; i < size; ++i) count[s[i] - 'a'] += 1; // 按照字符次序从前往后找只出现一次的字符 for(int i = 0; i < size; ++i) if(1 == count[s[i] - 'a']) return i; return -1; } };这就是哈希思想，那个数组就是哈希表。将字符串中可能出现的字符与数组的下标(存储位置)建立起了映射关系。当搜索一个值出现的次数时count[s[i] - 'a']，时间复杂度就是O(1)。但与真正的哈希表也是有些区别，真正的哈希表是将值(在这里也就是字符)放到映射的存储位置，而这里是将值出现的次数放到映射的存储位置。
我们之前学过的顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该结构中：
插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
若要将值与存储位置建立映射关系，就需要使用哈希函数
3、哈希函数
将值与存储位置建立关系的函数，称为哈希函数
常用的哈希函数有多种，这里仅介绍两种
3.1 直接定址法
取关键字的某个线性函数为散列地址：Hash(Key)= A*Key + B
用key的值映射一个绝对位置或相对位置
优点：简单、均匀、没有冲突
缺点：只适合范围集中的数据
使用场景：适合查找比较小且连续的情况
上面的题目使用的就是这种方法，地址 = 字符 - 'a'，之所以适用这种方法，是因为26个字母是连着的，是范围集中的数据，加入有一组数据是10，20，15，35，66，16，10000，如果使用直接定址法，需要开一个10000大小的数组，并且里面的数据十分分散，显然是不适用的
3.2 除留余数法
key模表的大小N后，映射到表中的一个位置
hashi = key % N，N是表的大小
假设有一组数据10，20，15，35，66，16，10000，表的大小是10，会发现，用10和20模表的大小，结果都是0，那是将10和20都放到下标为0的位置吗？这种情况称为哈希冲突
4、哈希冲突
哈希冲突就是指不同值，取模以后映射到相同位置，也称为哈希碰撞
解决哈希冲突的两种常用方式是：闭散列和开散列
4.1 闭散列(开放定址法)
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？
闭散列就是按规则去其他位置找一个空位置存储，也就是根据这个规则去寻找“下一个”位置，寻找下一个位置的方法有两种，线性探测和二次探测
4.1.1 线性探测
线性探测就是若映射到的位置已经被占了，则从这个位置开始，往下寻找空的位置，如何将数据放入空位置中。但这种方法容易造成一片拥堵，因为这个值占用了别人的位置，后面插入的值又要往后占位置
当前位置 + 1 ，若还被占了，当前位置+2，...，一直到空位置
4.1.2 二次探测
二次探测与线性探测是类似的，都是当映射到的位置已经被占了，当前位置 + 1^2 ，若还被占了，当前位置 + 2^2，...，一直到空位置
在前面，我们有提到set和unordered_set对key的要求不同， unordered_set要求key可以比较相等，正是在这里体现了这个作用。并且支持将key转为整型就是为了能够取模
在代码实现，我们只实现线性探测，因为两者是类似的
4.1.3 线性探测代码实现
我们前面只是了解了线性探测的插入操作，接下来我们了解一下线性探测的查找和删除操作
查找16：先去16映射到的位置查看，比较这个位置存储的值与16是否相等，若不想等，则继续往后查找，若到了空，则表中没有这个数据。像这里，16映射到的位置存放的是35，不是16，所以继续向后查找，一直到下标为8的时候找到16。假设要查找的是26，则26映射到的位置是35，继续向后查找，会发现，一直到下标为9没有存放值的位置都没有找到26，所以表中没有26
删除66：先查找66，若66存在，则删除
此时如果再查找16，会发现表中有16，但是找不到。所以，表中存数据时，每个位置不应该只存数据，还应该存放这个数据的状态。数据的状态有3种：存在、不存在、删除。此时也需要修改一下上面的查找和删除逻辑。查找除了要比较值是否相同，并且还需要这个值的状态是存在，才算找到，找不到时，是从映射的位置一直向后找，直到状态为空，才算找不到，如果遇到状态是删除的，仍然需要向后找。删除可以不改变这个结点的数据，只需要将这个结点的状态改成删除即可
搜索、插入、删除也不是完全只需要1次，可能需要几次，但仍然是常数时间，所以时间复杂度是O(1)
enum State { EXIST, EMPTY, DELETE }; template<class K,class V> struct HashDate // 哈希表是这个类型的数组 { pair<K, V> _kv; State _state = EMPTY; // 默认状态为空 }; template<class K,class V> class HashTable { public: HashTable() { _tables.resize(10); } private: vector<HashDate<K, V>> _tables; };插入
首先要注意，取模时，数组的大小需要根据size()计算，不能用capacity来计算，因为是需要将数据放进算出的位置的，若是用capacity，operator[]会报错
bool Insert(const pair<K, V>& kv) { size_t hashi = kv.first % _tables.size(); // 找到空或删除的位置将数据往里面放 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); // 防止++后超过数组范围 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; return true; }此时当哈希表满了时，会出现死循环，所以，需要对哈希表进行扩容操作
哈希表需要在什么时候进行扩容？如何扩容呢？
哈希表的载荷因子定义为;a = 填入表中的数据个数 / 哈希表的长度
a是哈希表装满程度的标志因子，由于表长是定值，a与"填入表中的数据个数"成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性越大，反之，a越小，表明填入表中的元素越少，产生冲突的可能性越小。实际上，哈希表的平均查找长度是载荷因子a的函数，只是不同的处理冲突的方法有不同的函数。
对于开放定址法，载荷因子是特别重要的因素，应严格限制载0.7~0.8以下，当载荷因子过大，就要扩容。所以，哈希表永远不会满，当快满时就扩容了，无需担心上面的死循环
扩容时，不能直接对这个vector进行resize，因为扩容后，原来冲突的数据，现在可能不冲突了
10，20，10000原本3个都是冲突的，现在只有20和10000冲突了，66和16也是同理
扩容方法：
方法一：当满了，创建一个vector，然后遍历原来的哈希表，将这些数据插入到新开的vector中，最后再swap两个vector。这种方法不好，因为需要重复写插入函数中的代码
方法二：创建一个哈希表对象，然后遍历原来的哈希表，通过新创建的哈希表对象调用Insert函数，将原来哈希表中的值一个一个插入，这样就能完成代码的复用
bool Insert(const pair<K, V>& kv) { // 扩容 if (_n * 10 / _tables.size() >= 7) { HashTable<K, V> newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]._state == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } size_t hashi = kv.first % _tables.size(); // 找到空或删除的位置将数据往里面放 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); // 防止++后超过数组范围 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; }搜索
Find不能只比较key是否相同，因为在删除操作中，删除数据时，只会将其状态修改为删除，并不会将数据真的删除，所以除了比较key相同，还需要状态是存在才是真的找到了
HashDate<K, V>* Find(const K& key) { size_t hashi = key % _tables.size(); while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } ++hashi; hashi %= _tables.size(); } return nullptr; }这时候我们可以对插入进行修改，使之不能放入重复元素
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 扩容 if (_n * 10 / _tables.size() >= 7) { HashTable<K, V> newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]._state == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } size_t hashi = kv.first % _tables.size(); // 找到空或删除的位置将数据往里面放 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); // 防止++后超过数组范围 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; }删除
bool Erase(const K& key) { HashDate<K, V>* ret = Find(key); if (ret == nullptr) return false; ret->_state = DELETE; return true; }不需要写析构、拷贝构造和赋值运算符重载，因为成员变量是vector和内置类型
对于不可以取模的类型
我们可以使用下面的代码对我们上面实现的哈希表进行测试
void test_hash1() { HashTable<int, int> hash; int a[] = { 10,20,15,35,66,16,10000 }; for (auto e : a) { hash.Insert({ e,e }); } hash.Insert({ 9,9 }); hash.Insert({ 3,3 }); hash.Erase(66); }此时建立的哈希表的key是整型，是可以取模的。那若是存储的key是string等不可取模的类型，又该怎么办呢？
此时就需要用到仿函数了，对于int、size_t、double、float、long、long long、char等可以直接取模的类型，就使用仿函数的缺省值，对于string等无法取模的类型，就自己写仿函数，然后定义哈希表时传过去
template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable() { _tables.resize(10); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 扩容 if (_n * 10 / _tables.size() >= 7) { HashTable<K, V> newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]._state == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hs; size_t hashi = hs(kv.first) % _tables.size(); // 找到空或删除的位置将数据往里面放 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); // 防止++后超过数组范围 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; } bool Erase(const K& key) { HashDate<K, V>* ret = Find(key); if (ret == nullptr) return false; ret->_state = DELETE; return true; } HashDate<K, V>* Find(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } ++hashi; hashi %= _tables.size(); } return nullptr; } private: vector<HashDate<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 };可以看到，对于可以直接取模的类型，是先转化为size_t，再取模。对于string等不能取模的类型也是类似。此时是完成了两层映射，先用string去映射整型，再用整型去映射出对于的存储位置。注意，在这两层映射中，每一层都可能会产生冲突
那string要如何映射为整型呢？
此时就涉及到了字符串哈希算法。
可不可以取地址，将地址转为整型呢？不可以，因为两个相同的字符串的地址会不同，这样映射成的整型也是不同的
应当将string中的每个字母的ASCII相加，但是这样太容易发生冲突了，因为像abcd和dcba映射为整型时就会产生冲突，为了减少冲突，没加一个值时，可以对目前的和乘一个固定的数
struct StringHashFunc { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash *= 31; hash += e; } return hash; } }; void test_hash2() { HashTable<string, string, StringHashFunc> hash; hash.Insert({ "left","左边" }); hash.Insert({ "right","右边" }); }在我们使用unordered_map时，会发现当存储的key是string时，并不需要自己写仿函数，这是因为string很常用，所以STL底层对string进行了特化。我们实现时可以对其进行模板的特化
namespace open_address // 开放定址法 { enum State { EXIST, EMPTY, DELETE }; template<class K, class V> struct HashDate // 哈希表是这个类型的数组 { pair<K, V> _kv; State _state = EMPTY; // 默认状态为空 }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> // 对string类型进行特化 struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash *= 31; hash += e; } return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable() { _tables.resize(10); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 扩容 if (_n * 10 / _tables.size() >= 7) { HashTable<K, V, Hash> newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]._state == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hs; size_t hashi = hs(kv.first) % _tables.size(); // 找到空或删除的位置将数据往里面放 while (_tables[hashi]._state == EXIST) { ++hashi; hashi %= _tables.size(); // 防止++后超过数组范围 } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; _n++; return true; } bool Erase(const K& key) { HashDate<K, V>* ret = Find(key); if (ret == nullptr) return false; ret->_state = DELETE; return true; } HashDate<K, V>* Find(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } ++hashi; hashi %= _tables.size(); } return nullptr; } private: vector<HashDate<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 }; }实际上，解决哈希冲突的闭散列方式，无论是线性探测还是二次探测都不是太好，因为本质都是一种零和博弈
4.2 开散列(哈希桶/拉链法)
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
上面的数据10，20，15，35，66，16，10000，使用开散列就是
这里的哈希表就是一个指针数组，下面挂着的就是链表，所以结点除了要存储值，还要存储下一个结点的地址。每一个链表称为一个哈希桶
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 HashTable { typedef HashNode<K, V> Node; public: HashTable() { _tables.resize(10, nullptr); } private: vector<Node*> _tables; size_t _n = 0; // 表中存储数据个数 }; }插入
插入首先计算出插入值的插入位置，然后往插入位置的链表中插入该值。因为冲突的这些值的先后顺序是任意的，所以插入一个值时既可以头插，也可以尾插，我们这里采用的是头插
bool Insert(const pair<K, V>& kv) { size_t hashi = kv.first % _tables.size(); // 头插 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; }
使用哈希桶扩容时与前面有些不同，是当载荷因子等于1时才进行扩容
bool Insert(const pair<K, V>& kv) { size_t hashi = kv.first % _tables.size(); // 负载因子==1，扩容 if (_n == _tables.size()) { HashTable<K, V> newHT; newHT._tables.resize(_tables.size() * 2); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; // 遍历整个哈希表，当桶不为空时，让cur遍历这个桶，然后插入，直到cur为空，说明这个桶已经完了 while (cur) { newHT.Insert(cur->_kv); cur = cur->_next; } } _tables.swap(newHT._tables); } // 头插 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; }在前面，完美看到了哈希表底层就是一个vector<Node*>，是一个指针数组，下面挂着的那些链表是我们new出来的，所以也需要我们自己释放，所以是需要自己实现析构函数的
~HashTable() { // 依次释放每个桶 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } }此时的插入操作中的扩容是不好的，因为我们没有利用表中原有的结点，而是重新创建结点，原来的结点还会delete掉，倘若扩容前有10000个结点，那么会进行10000次new和delete，这样消耗是比较大的。所以我们不应该调用Insert，因为一旦调用Insert就一定会有new和delete。此时应该创建一个vector<Node*>，并且复用原来的结点，即用上面提到的方法一
bool Insert(const pair<K, V>& kv) { size_t hashi = kv.first % _tables.size(); // 负载因子==1，扩容 if (_n == _tables.size()) { vector<Node*> newtables(_tables.size() * 2, nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中的结点，挪动到新表重新映射的位置 size_t hashi = cur->_kv.first % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } // 原来的桶取完后要置空 _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; }搜索
Node* Find(const K& key) { size_t hashi = key % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; }为了防止冗余，可以修改插入
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; Hash hs; size_t hashi = hs(kv.first) % _tables.size(); // 负载因子==1，扩容 if (_n == _tables.size()) { vector<Node*> newtables(_tables.size() * 2, nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中的结点，挪动到新表重新映射的位置 size_t hashi = hs(cur->_kv.first) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } // 原来的桶取完后要置空 _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; }删除
删除操作，记录当前遍历到的结点cur和cur的前一个结点prev，删除时让prev的_next指向cur的下一个即可，然后释放cur，但若cur是头结点需要特殊考虑，因为头结点没有前一个结点，此时直接让表里的指针指向cur的下一个
bool Erase(const K& key) { size_t hashi = key % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) _tables[hashi] = cur->_next; else prev->_next = cur->_next; delete cur; return true; } prev = cur; --_n; cur = cur->_next; } return false; }对于不可取模的类型
与开放定址法是类似的
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> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> // 对string类型进行特化 struct HashFunc<string> { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash *= 31; hash += e; } return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: HashTable() { _tables.resize(10, nullptr); } ~HashTable() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; Hash hs; size_t hashi = hs(kv.first) % _tables.size(); // 负载因子==1，扩容 if (_n == _tables.size()) { //HashTable<K, V> newHT; //newHT._tables.resize(_tables.size() * 2); //for (size_t i = 0; i < _tables.size(); i++) //{ // Node* cur = _tables[i]; // // 遍历整个哈希表，当桶不为空时，让cur遍历这个桶，然后插入，直到cur为空，说明这个桶已经完了 // while (cur) // { // newHT.Insert(cur->_kv); // cur = cur->_next; // } //} //_tables.swap(newHT._tables); vector<Node*> newtables(_tables.size() * 2, nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中的结点，挪动到新表重新映射的位置 size_t hashi = hs(cur->_kv.first) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } // 原来的桶取完后要置空 _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newNode = new Node(kv); newNode->_next = _tables[hashi]; _tables[hashi] = newNode; ++_n; return true; } Node* Find(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } bool Erase(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) _tables[hashi] = cur->_next; else prev->_next = cur->_next; delete cur; return true; } prev = cur; --_n; cur = cur->_next; } return false; } private: vector<Node*> _tables; size_t _n = 0; // 表中存储数据个数 }; }