封装哈希表实现 unordered_set/unordered_map

一 STL 标准库中 unordered_set/unordered_map 的使用

1.1 参考文档

unordered_set 文档解析

unordered_map 文档解析

这两个的使用 set 和 map 一样，这里我只讲一讲它们的区别和效率上的差异。

unordered_set vs unordered_map

二哈希表的实现 (抓住映射)

哈希表概念图

2.1 哈希表的概念

哈希 (hash) 又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。

2.2 哈希表的实现方法一直接定址法

顾名思义 哈希表中每个数据的储存位置是确定的，当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在 [0,99] 之间，那么我们开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ascii 码 -a ascii 码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。【例体统计字符串中字符的第一个唯一出现的个数，并且字符串中只有小写】这里我们就可以使用直接定址法因为小写字母只有 26 个很集中，这里我们开一个 26 个数的数组，每个关键字 ascii 码-a ascii 码就是存储位置的下标即可。字符串中的第一个唯一字符

【题解】

class Solution { 
public: 
    int firstUniqChar(string s) { 
        // 每个字母的 ascii 码-'a'的 ascii 码作为下标映射到 count 数组，数组中存储出现的次数 
        int count[26] = {0}; 
        // 统计次数 
        ( ch : s) { 
            count[ch-]++; 
        } 
        ( i = ; i < s.(); ++i) { 
            (count[s[i]-] == )  i; 
        } 
         ; 
    } 
};

//解决 M 表的大小是质数，因为我们是两倍扩容，所以要同时保证其两倍扩容后的 M 也是质数 //这里还有一个很难的问题，就是我们取的表的大小，要不是 2 和 10 的幂，并且是要为质数 //并且我们的扩容是两倍增长，就算满足上面的条件其扩容后其表的大小也可能不是质数。 //那怎么解决这个问题呢？ //这里我们可以建立一个近似两倍增长的质数表即可 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, 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); return pos == last ? *(last - 1) : *pos; } //这里还有一个问题，哈希中对于 key 的要求是可以取模 (即可以转化为整形) //而在生活中 string 对象经常作为 key，那怎么解决这个问题呢？ //这里我们可以学红黑树中获取 key 的方法，实现一个仿函数 (因为要将可以其整和不能取整的进行分类)，使用一种方法将其转化取模 //这里常见的方法是计算 string 中每个字母的 ascii 码值之和，但是如果字母顺序不同等不同情况都可能导致 string 中每个字母的 ascii 码值之和相等 //这个问题我们可以先加 string 对象中一个字母的 ascii 码值在将结果*一个数，不断重复对 string 对象中的每个字母进行相同操作即可 //可以取整 template<class K> struct HashFunc { size_t operator()(const K& key) const { return (size_t)key; } }; //这里将 string 类型转化为整形，单独封装一种方法，的方法不好 // 这里只是参数类型不同，这里我们可以对于将对象转化为可以取整的方法，进行特化，特化出 string 对象的即可 //对于 string 类型对象我们可以求 string 对象中每个字母的 ascii 码之和， // 但是 string 对象的字母实现不同、字母个数不同等等原因可能导致 string 对象中每个字母的 ascii 码之和相等 //所以为了防止这种情况的发生，这里我们对 string 对象的每个字母相加的同时，再乘一个数 (这个数大佬经过验证给的是 131) template<> struct HashFunc<string> { size_t operator()(const string& key) const { size_t hash = 0; for (auto ch : key) { hash += ch; hash *= 131; } return hash; } }; //将 string 类型转化为整形，单独封装一种方法 //struct StringHashFunc //{ // size_t operator()(const string& key) const // { // size_t hash = 0; // for (auto ch : key) // { // hash += ch; // hash *= 131; // } // return hash; // } //}; //上面这种方法很好，在实际中我们经常使用这种方法，例如在结构体中我们可能取其中的一两项进行区分 //例如储存 r 信息的一个结构体，我们可以取其身份证的出生日期 + 名字进行区分等等 //例如下面的 pair 类型 struct pairHash { size_t operator()(const pair<int, int>& kv) const { size_t hash = 0; hash += kv.first; hash *= 131; hash += kv.second; hash *= 131; cout << hash << endl; return hash; } }; //开放地址法 //因为后面要顺序别的方法，可能会其冲突，所以这里我们使用命名空间进行封装 namespace open_adrress { //定义节点的状态 //这里接节点的状态不仅有存在、空；还有删除。 //因为由于存在哈希冲突，可能导致一些节点储存位置的改变，如果只有存在和空两种状态 //节点删除之后，节点的状态改成空时会影响查找，可能查找的值在其中，但是因为删除节点之后变成空 //而未找到 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 Hash = HashFunc<K>> class HashTable { public: HashTable(size_t n = 11) :_tables(n), _n(0) { } //插入 bool Insert(const pair<K, V>& kv) { //查找去重 if (Find(kv.first)) return false; //负载因子>0.7 是要扩容 //这里有一个问题就是，由于空间的扩大，之前数据的映射关系可能也会改变 //所以这里要对数据进行重新映射，那怎么解决呢？这里有两种方法 if ((double)_n / (double)_tables.size() >= 0.7) { //方法一： //这里我们创建一个容量是之前两倍大小的 vector 容器，在将旧哈希表中节点状态是存在的节点 //进行重新映射到新表中 //vector<HashData<K, V>> newtables; //newtables.resize(_tables.size * 2); ////遍历旧表将旧表中的数据全部映射到新表中 //for (size_t i = 0; i < _tables.size(); i++) //{ // if (_tables[i]._state == EXIST) // { // //重复插入操作 // } //} ////在用现代写法交换一下新旧表即可 //_tables.swap(newtables); //由于上面方法并不好，因为在将旧表中的数据重新映射到新表中的步骤和插入一样，所以这里我们不用方法一。 //方法二 //我们建立一个空间大小是之前两倍大小的新的哈希表，在遍历旧表中的数据，将其插入到新表中 //方法一的重新映射插入要自己实现，而方法二是将旧表中得到的数据插入到新表中 (自己调用 insert 一种复用) //HashTable<K, V> newht(_tables.size() * 2); HashTable<K, V, Hash> newht(__stl_next_prime(_tables.size() + 1)); 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; //1 找到要映射的位置 size_t hash0 = hs(kv.first) % _tables.size(); size_t hashi = hash0; size_t i = 1; //找到要映射的位置，后进行线性探测，直到找到节点的状态不是存在时就插入 while (_tables[hashi]._state == EXIST) { hashi = hashi + i; i++; hashi %= _tables.size(); } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; } //查找 HashData<K, V>* Find(const K& key) { Hash hs; //查找和插入一样，走相同步骤 size_t hash0 = key % _tables.size(); size_t hashi = hash0; size_t i = 1; //找到映射位置，从映射位置的节点开始，只要节点位置的状态不是空 //如果此时 key 不相等要不断相互找，因为可能因为还想冲突，导致其储存位置向后变了 while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } //线性探测 hashi = hashi + i; i++; hashi %= _tables.size(); } } //删除 //删除很简单，找到对应节点，在把其节点的存在状态改为删除 //注意这里不能改成空，因为由于哈希冲突导致一些值插入在后面，为了不影响查找这里把节点的状态改成删除 bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; size_t _n;//实际储存的实际个数 }; }

//解决 M 表的大小是质数，因为我们是两倍扩容，所以要同时保证其两倍扩容后的 M 也是质数 //这里还有一个很难的问题，就是我们取的表的大小，要不是 2 和 10 的幂，并且是要为质数 //并且我们的扩容是两倍增长，就算满足上面的条件其扩容后其表的大小也可能不是质数。 //那怎么解决这个问题呢？ //这里我们可以建立一个近似两倍增长的质数表即可 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, 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); return pos == last ? *(last - 1) : *pos; } //这里还有一个问题，哈希中对于 key 的要求是可以取模 (即可以转化为整形) //而在生活中 string 对象经常作为 key，那怎么解决这个问题呢？ //这里我们可以学红黑树中获取 key 的方法，实现一个仿函数 (因为要将可以其整和不能取整的进行分类)，使用一种方法将其转化取模 //这里常见的方法是计算 string 中每个字母的 ascii 码值之和，但是如果字母顺序不同等不同情况都可能导致 string 中每个字母的 ascii 码值之和相等 //这个问题我们可以先加 string 对象中一个字母的 ascii 码值在将结果*一个数，不断重复对 string 对象中的每个字母进行相同操作即可 //可以取整 template<class K> struct HashFunc { size_t operator()(const K& key) const { return (size_t)key; } }; //这里将 string 类型转化为整形，单独封装一种方法，的方法不好 // 这里只是参数类型不同，这里我们可以对于将对象转化为可以取整的方法，进行特化，特化出 string 对象的即可 //对于 string 类型对象我们可以求 string 对象中每个字母的 ascii 码之和， // 但是 string 对象的字母实现不同、字母个数不同等等原因可能导致 string 对象中每个字母的 ascii 码之和相等 //所以为了防止这种情况的发生，这里我们对 string 对象的每个字母相加的同时，再乘一个数 (这个数大佬经过验证给的是 131) template<> struct HashFunc<string> { size_t operator()(const string& key) const { size_t hash = 0; for (auto ch : key) { hash += ch; hash *= 131; } return hash; } }; //将 string 类型转化为整形，单独封装一种方法 //struct StringHashFunc //{ // size_t operator()(const string& key) const // { // size_t hash = 0; // for (auto ch : key) // { // hash += ch; // hash *= 131; // } // return hash; // } //}; //上面这种方法很好，在实际中我们经常使用这种方法，例如在结构体中我们可能取其中的一两项进行区分 //例如储存 r 信息的一个结构体，我们可以取其身份证的出生日期 + 名字进行区分等等 //例如下面的 pair 类型 struct pairHash { size_t operator()(const pair<int, int>& kv) const { size_t hash = 0; hash += kv.first; hash *= 131; hash += kv.second; hash *= 131; cout << hash << endl; return hash; } }; //链地址法 - 这种方法更好，所以我们封装顺序 unordered_set/unordered_map //因为不管上面。。。。三种探测 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(size_t n = __stl_next_prime(0)) :_tables(n,nullptr),_n(0) { }*/ HashTable(size_t n = 11) :_tables(n, nullptr), _n(0) { } //插入 bool Insert(const pair<K, V>& kv) { //1 查找去重 if (Find(kv.first)) return false; Hash hs; //2 扩容 //根据负载因子来判断，但是这里和开发地址法不一样 //这里是负载因子到 1 时才扩容 //这里的结构和开发地址法的结构不一样，所以细节和开发地址法也不一样。 //虽然大思路也是两种，但是每种思路的细节是先找哈希表中是否有数据，有就遍历哈希桶 (链表) 将数据插入到新的哈希表中 //走完一个哈希桶，中间的哈希桶可能为空，所以要遍历判断哈希桶，遇到哈希桶不为空，就将其中的数据到人到新的哈希表中 //这里还有一个问题，交换后的新旧哈希表，因为哈希表是用 vector 实现，所以旧的哈希表会自动调用对应的析构函数 //但是定义哈希表中 vector 容器中储存的链式结构 (链表) 是一个自定义类型，此时不会自动调用对应的析构函数 //所以这里我们要中间写析构函数，这里有人想把哈希表用 vector<forwand_list<pair<k,v>>不就好了 //注意虽然这种方法在这里很方便，但是在迭代器的实现上就难以实现了。所以这里我们要自己写析构函数。 if (_n == _tables.size()) { //HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1)); //// 遍历旧表，将旧表的数据全部重新映射到新表 //for (size_t i = 0; i < _tables.size(); i++) //{ // Node* cur = _tables[i]; // while (cur) // { // newht.Insert(cur->_kv); // cur = cur->_next; // } //} //_tables.swap(newht._tables); // 扩容 vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); // 遍历旧表，将旧表的数据全部重新映射到新表 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // cur 头插到新表 size_t hashi = hs(cur->_kv.first) % newtables.size(); cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } //3 找到数据要插入哈希表中对应的位置 //然后头插进哈希桶 - 这里可以是头插也可以尾插，两者都可以肯定选头插 size_t hashi = hs(kv.first) % _tables.size(); 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; } } //删除 - 这里就不能像直接地址法一样，先查找在删除 //因为我们这里要改变前后指针的指向，所以要找到当前节点和当前节点的前一个 //（因为这里是单向迭代器，所以无法得到一个节点，根据该节点得到上一个节点，这也是无法通过先查找在删除的原因) bool Erase(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { //这里有一种情况如果_tables[hashi] 就是要删的节点时，不会进行改变 prev 和 cur 的指向操作（不断向后遍历查找） //此时 prev==nullptr，此时就会出错，所以这里要分类讨论 /*if (cur->_kv.first == key) { prev->_next = cur->_next; --_n; delete cur; return true; }*/ if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } --_n; delete cur; return true; } prev = cur;//将上一个节点指向 cur，不断向后遍历查找 cur = cur->_next; } return false; } private: vector<Node*> _tables;//用于储存顺序哈希表，可以自己写一个数组，这里有现成的 vector //所以这里用 vector 来储存. size_t _n;//实际储存的数据个数 }; }

#pragma once #include<iostream> #include<vector> using namespace std; //解决 M 表的大小是质数，因为我们是两倍扩容，所以要同时保证其两倍扩容后的 M 也是质数 //这里还有一个很难的问题，就是我们取的表的大小，要不是 2 和 10 的幂，并且是要为质数 //并且我们的扩容是两倍增长，就算满足上面的条件其扩容后其表的大小也可能不是质数。 //那怎么解决这个问题呢？ //这里我们可以建立一个近似两倍增长的质数表即可 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, 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); return pos == last ? *(last - 1) : *pos; } //这里还有一个问题，哈希中对于 key 的要求是可以取模 (即可以转化为整形) //而在生活中 string 对象经常作为 key，那怎么解决这个问题呢？ //这里我们可以学红黑树中获取 key 的方法，实现一个仿函数 (因为要将可以其整和不能取整的进行分类)，使用一种方法将其转化取模 //这里常见的方法是计算 string 中每个字母的 ascii 码值之和，但是如果字母顺序不同等不同情况都可能导致 string 中每个字母的 ascii 码值之和相等 //这个问题我们可以先加 string 对象中一个字母的 ascii 码值在将结果*一个数，不断重复对 string 对象中的每个字母进行相同操作即可 //可以取整 template<class K> struct HashFunc { size_t operator()(const K& key) const { return (size_t)key; } }; //这里将 string 类型转化为整形，单独封装一种方法，的方法不好 // 这里只是参数类型不同，这里我们可以对于将对象转化为可以取整的方法，进行特化，特化出 string 对象的即可 //对于 string 类型对象我们可以求 string 对象中每个字母的 ascii 码之和， // 但是 string 对象的字母实现不同、字母个数不同等等原因可能导致 string 对象中每个字母的 ascii 码之和相等 //所以为了防止这种情况的发生，这里我们对 string 对象的每个字母相加的同时，再乘一个数 (这个数大佬经过验证给的是 131) template<> struct HashFunc<string> { size_t operator()(const string& key) const { size_t hash = 0; for (auto ch : key) { hash += ch; hash *= 131; } return hash; } }; //将 string 类型转化为整形，单独封装一种方法 //struct StringHashFunc //{ // size_t operator()(const string& key) const // { // size_t hash = 0; // for (auto ch : key) // { // hash += ch; // hash *= 131; // } // return hash; // } //}; //上面这种方法很好，在实际中我们经常使用这种方法，例如在结构体中我们可能取其中的一两项进行区分 //例如储存 r 信息的一个结构体，我们可以取其身份证的出生日期 + 名字进行区分等等 //例如下面的 pair 类型 struct pairHash { size_t operator()(const pair<int, int>& kv) const { size_t hash = 0; hash += kv.first; hash *= 131; hash += kv.second; hash *= 131; cout << hash << endl; return hash; } }; //链地址法 - 这种方法更好，所以我们封装顺序 unordered_set/unordered_map //因为不管上面。。。。三种探测 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 Hash> class HashTable; //定义迭代器 template<class K,class T,class Ref,class Ptr, class KeyOft,class Hash> struct HTIterator { typedef HashNode<T> Node; typedef HashTable<K, T, KeyOft, Hash> HT; typedef HTIterator<K, T, Ref, Ptr, KeyOft, Hash> Self; Node* _node; const HT* _pht; //这里用 const 修饰时因为再 const 迭代器中的 this 指针应该也要 const 修饰，如果没用则会权限放大， //反之普通的迭代器的 this 指针时普通指针，而这里是 const 指针权限缩小，因为权限可以缩小不能放大，所以这里用 const 修饰 HTIterator(Node* node, const HT* pht) :_node(node),_pht(pht) { } //难点++ Self& operator++() { if (_node->_next) { _node = _node->_next; } else { KeyOft kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); //先 hasi++ 后进入循环，因为当前哈希桶遇到不为空 hashi++; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) { _node = _pht->_tables[hashi]; break; } ++hashi; } if (hashi == _pht->_tables.size()) { //当所以走完时返回 End 空 _node = nullptr; } } return *this; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; } }; //定义哈希表 template<class K,class T, class KeyOft, class Hash> class HashTable { typedef HashNode<T> Node; //永远声名 - 因为迭代器要访问私有成员_tables。 template<class K,class T,class Ref,class Ptr,class KeyOft,class Hash> friend struct HTIterator; public: typedef HTIterator<K, T, T&, T*, KeyOft, Hash> Iterator; typedef HTIterator<K, T, const T&, const T*, KeyOft, Hash> ConstIterator; HashTable(size_t n = __stl_next_prime(0)) :_tables(n,nullptr),_n(0) { } ~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; } } //HashTable(size_t n = 11) // :_tables(n, nullptr) // , _n(0) //{ //}//测试是否正确 //迭代器 Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return Iterator(_tables[i], this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } //const 迭代器 ConstIterator Begin() const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]) { return ConstIterator(_tables[i], this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } //插入 pair<Iterator,bool> Insert(const T& data) { KeyOft kot; //1 查找去重 Iterator it = Find(kot(data)); if(it != End()) return { it,false }; Hash hs; //2 扩容 //根据负载因子来判断，但是这里和开发地址法不一样 //这里是负载因子到 1 时才扩容 //这里的结构和开发地址法的结构不一样，所以细节和开发地址法也不一样。 //虽然大思路也是两种，但是每种思路的细节是先找哈希表中是否有数据，有就遍历哈希桶 (链表) 将数据插入到新的哈希表中 //走完一个哈希桶，中间的哈希桶可能为空，所以要遍历判断哈希桶，遇到哈希桶不为空，就将其中的数据到人到新的哈希表中 //这里还有一个问题，交换后的新旧哈希表，因为哈希表是用 vector 实现，所以旧的哈希表会自动调用对应的析构函数 //但是定义哈希表中 vector 容器中储存的链式结构 (链表) 是一个自定义类型，此时不会自动调用对应的析构函数 //所以这里我们要中间写析构函数，这里有人想把哈希表用 vector<forwand_list<pair<k,v>>不就好了 //注意虽然这种方法在这里很方便，但是在迭代器的实现上就难以实现了。所以这里我们要自己写析构函数。 if (_n == _tables.size()) { //HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1)); //// 遍历旧表，将旧表的数据全部重新映射到新表 //for (size_t i = 0; i < _tables.size(); i++) //{ // Node* cur = _tables[i]; // while (cur) // { // newht.Insert(cur->_kv); // cur = cur->_next; // } //} //_tables.swap(newht._tables); // 扩容 vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); // 遍历旧表，将旧表的数据全部重新映射到新表 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // cur 头插到新表 size_t hashi = hs(kot(cur->_data)) % newtables.size(); cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } //3 找到数据要插入哈希表中对应的位置 //然后头插进哈希桶 - 这里可以是头插也可以尾插，两者都可以肯定选头插 size_t hashi = hs(kot(data)) % _tables.size(); Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return { Iterator(newnode,this),true }; } //查找 Iterator Find(const K& key) { Hash hs; KeyOft kot; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) return Iterator(cur,this); cur = cur->_next; } return End(); } //删除 - 这里就不能像直接地址法一样，先查找在删除 //因为我们这里要改变前后指针的指向，所以要找到当前节点和当前节点的前一个 //（因为这里是单向迭代器，所以无法得到一个节点，根据该节点得到上一个节点，这也是无法通过先查找在删除的原因) bool Erase(const K& key) { Hash hs; KeyOft kot; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { //这里有一种情况如果_tables[hashi] 就是要删的节点时，不会进行改变 prev 和 cur 的指向操作（不断向后遍历查找） //此时 prev==nullptr，此时就会出错，所以这里要分类讨论 /*if (cur->_kv.first == key) { prev->_next = cur->_next; --_n; delete cur; return true; }*/ if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } --_n; delete cur; return true; } prev = cur;//将上一个节点指向 cur，不断向后遍历查找 cur = cur->_next; } return false; } private: vector<Node*> _tables;//用于储存顺序哈希表，可以自己写一个数组，这里有现成的 vector //所以这里用 vector 来储存. size_t _n;//实际储存的数据个数 }; }

封装哈希表实现 unordered_set/unordered_map