哈希表实现原理与代码详解

这题最直接的思路是遍历每个数来统计出现的次数，如果使用前文的 map 和 set 来统计，那么就题目本身来说，使用容器本身的消耗相对较大，没必要用。

因为只会出现小写字母，所以我们创建大小为 26 的数组，根据距离'a'的距离确定相对位置，26 个小写字母每个都有对应的位置，遍历字符串，根据对应位置数据确定字母出现次数。

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

直接定址法的缺点也非常明显，直接定址法是根据数据本身的大小或者到最小值的距离来确定绝对/相对位置，当关键字的范围比较分散时，最大值与最小值间的距离就很大，就很浪费内存甚至内存不够用。

比如最大值与最小值差值达到 10 亿，但是数据本身只有 20 个数，那么根据最大最小值的距离开辟 10 大小的数组，但是浪费也基本达到 10 亿。所以对于较分散的数据，我们需要再采取其他数据映射的方式

5.2 除法散列法/除留余数法

• 除法散列法也叫做除留余数法，顾名思义，假设哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

• 当使用除法散列法时，要尽量避免 M 为某些值，如 2 的幂，10 的幂等。如果是，**那么 key %**本质相当于保留 key 二进制形式的后 X 位，那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。

如：{63 , 31}看起来没有关联的值，如果 M 是 16，也就是

，那么计算出的哈希值都是 15，因为 63 的二进制后 8 位是 00111111，31 的二进制后 8 位是 00011111。如果是

，就更明显了，保留的都是 10 进值的后 x 位，如：{112, 12312}，如果 M 是 100，也就是

，那么计算出的哈希值都是 12。

• 当使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个质数 (素数)。

• 需要说明的是，实践中也是八仙过海，各显神通，Java 的 HashMap 采用除法散列法时就是 2 的整数次幂做哈希表的大小 M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效一些。

但是他不是单纯的去取模，比如 M 是 2^16 次方，本质是取后 16 位，那么用 key' =key>>16，然后再把 key 和 key' 异或的结果作为哈希值。因为只取后 16 位，那么后 16 位相同，数据就会冲突，哈希冲突概念很大，为了避免冲突，我们要采取方式使得每一个数据尽可能具有唯一性，取后 16，再取前 16 位异或，这样相当于让原数据的每一数位上的数都参与计算，计算出 h(key)。

如果我们 M 是 2^4 次方，本质取后 4 位，这时候前 28 位是没利用上的，这时候异或，我们发现如下图蓝色区间的部分是多出来的，如果前 28 位对应蓝色部分二进制形式数位上有不为一处，那么异或之后的 h(key) 就会超过 M，溢出了。

因此对于如下图这种不对称的形式，我们要循环取位，每次从 28 位中取 4 位出来，与原四位异或，注意的是，我们这里循环按固定数位取数，只是希望让更多数位加入运算，尽可能使结果独一无二。

总的来说我们映射出的值还是在[0,M) 范围内，但是通过移位尽量让 key 所有的位都参与计算，这样映射出的哈希值更均匀一些即可。

所以我们上面建议 M 取不太接近 2 的整数次幂的一个质数的理论是大多数数据结构书籍中写的理论，但是实践中，灵活运用，抓住本质，而不能死读书。

5.3 乘法散列法（了解）

• 乘法散列法对哈希表大小 M 没有要求，他的大思路第一步：用关键字 K 乘上常数 A (0<A<1)，并抽取出 kA 的小数部分。第二步：后再用 M 乘以 kA 的小数部分，再向下取整。

•h(key) = floor(M × ((A × key)%1.0))，其中floor 表示对表达式进行下取整，A∈(0,1)，这里最重要的是 A 的值应该如何设定，Knuth 认为A = ( **- 1)/2 = 0.6180339887.... (黄金分割点])比较好，**这个数据是经过大量实验验证之后的可以使数据分布较为均匀的一种设计。

乘法散列法对哈希表大小 M 是没有要求的，假设 M 为 1024，key 为 1234，A = 0.6180339887, Akey= 762.6539420558，取小数部分为 0.6539420558, M×((A×key)%1.0) = 0.65394205581024 =669.6366651392，那么 h(1234) = 669。

5.4 全域散列法（了解）

基于哈希的各种数据结构被应用到各个领域，比如下图的分布式集群，我们根据哈希函数来确定数据存储到哪一台主机上，使得数据分布均匀存储，避免大量数据超出某一台主机存储上限，以及影响查找数据效率。

但是如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生会严重冲突的数据集，比如，让所有关键字经过散列函数运算后全部落入同一台主机上，进而导致严重后果。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。

解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。

•(key) = ((a × key + b)%P )%M，P 需要选一个足够大的质数，a 可以随机选[1,P-1]之间的任意整数，b 可以随机选[0,P-1]之间的任意整数，这些函数构成了一个 P(P-1) 组全域散列函数组（函数组中存放的是不同的哈希函数），然后我们根据随机选取一个哈希函数进行使用*。

假设 P=17，M=6，a = 3，b = 4, 则

(8) = ((3 × 8 + 4)%17)%6 = 5。那么就从函数组中选取对应的哈希函数，然后使用哈希函数计算 h(key)，因为这个哈希函数也是我们通过计算随机选取的，

这样恶意分子就无法设计出针对的数据集了。

• 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的一个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致找不到插入的 key 了。

5.5 其他方法（了解）

上面的几种方法是《算法导论》书籍中讲解的方法。

《殷人昆 数据结构：用面向对象方法与 C++ 语言描述（第二版）》和 《[数据结构 (C 语言版)].严蔚敏_吴伟民》等教材型书籍上面还给出了平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于一些局限的特定场景，有兴趣可以去看看这些书籍。

6. 处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然相对于数据来说，哈希表的 M 永远小，永远都存在两个不同的数经过计算到了同一位置上，无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种两种方法，开放定址法和链地址法。

6.1 开放定址法

在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于 1 的。这里的规则有三种：线性探测、二次探测、双重探测。

线性探测

• 从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置，继续寻找。

• h(key) = hash0 = key % M, hash0 位置冲突了，则线性探测公式为：****(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M − 1}，因为负载因子小于 1（存在空位），则最多探测 M-1 次，一定能找到一个存储 key 的位置。

a.线性探测的问题

线性探测的比较简单且容易实现，线性探测的问题是目前有多个值映射到哈希表的同一位置，假设 hash0 位置连续冲突，第一个冲突值向后找到空的 hash1 位置存放，第二个冲突值向后找到空的 hash2 位置存储数据，我们发现之前冲突的多个数据会抢占之后数据的存储位置，那么之后的数据就要从被抢占的位置向后不断遍历找到空位置，也就是说空位置越少，找到空位置需要遍历的次数就越多，效率越低，所以实际中一般我们会保持负载因子小于 0.7，负载因子大于 0.7 则进行扩容。

hash0，hash1，hash2 位置已经存储数据了，后续映射到 hash0，hash1，hash2，hash3 的值都会争夺 hash3 位置，这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。

下面演示 {19,30,5,36,13,20,21,12} 等这一组值映射到 M=11 的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1

开放定址法代码实现

开放定址法在实践中，不如下面讲的链地址法，因为开放定址法解决冲突不管使用哪种方法，占用的都是哈希表中的空间，数据之间相互竞争空间，始终存在互相影响的问题。再考虑到线性探测较为简单，所以开放定址法，我们选择线性探测的实现来详细说明开放定制法的各项细节。

开放定址法的哈希表结构和查找设计

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 HashTable { private: vector<HashData<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 };

我们这里底层封装 vector 来存储数据，要注意的是，因为查找需要找到空位置，所以这里需要给每个存储值的位置加一个状态标识，状态表示需要有存在、空、删除三种状态，否则删除一些值以后，会影响后面冲突的值的查找。

如下图，我们删除 30，30 映射的位置就变空了，那么我们查找 20 时，因为线性探测的逻辑是冲突了，就往后找空位存放，反过来说如果找到空位置了，那空位置之后一定也是空的，没有数据，所以如果我们查找 20，那么查找到第 9 位为空，就不会继续往后查了，导致查找 20 失败。

当我们给每个位置加一个状态标识{EXIST,EMPTY,DELETE}，删除 30 就可以不用删除值，而是把状态改为 DELETE，那么查找 20 时是遇到 EMPTY 才能停，我们就可以找到 20 了。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1

 HashData<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; }

key 不能取模的问题

当 key 是 string/Date 等类型时，key 不能取模，那么我们需要给 HashTable 增加一个仿函数，

**这个仿函数支持把 key 转换成一个可以取模的整形。**这样这个 key 就与转换后的整形存在一层映射关系，然后这个转换后的整形由于哈希表存在映射关系，间接的，key 就与哈希表存在映射关系了。

如果 key 可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可（默认的仿函数，我们使用强转即可），如果这个 Key 不能转换为整形，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量 key 的每值都参与到计算中，让不同的 key 转换出的整形值不同。

由于 string 做哈希表的 key 非常常见，所以 STL 库中 unordered 系列使用不需要我们传递仿函数，就是因为针对 string 类型特化了。

针对 string 类型的转换，方式有很多种，比如讲 string 中的每个字符加起来得到一个整形值，但这种方式容易出现字符一致、但字符顺序不一致字符串冲突。

经过科学家的大量实验研究，发现可以如下图，将字符串挨个取出，乘上某个固定数，再与下个字符相加，再乘上固定数…………直到结束，由于不同字母的 ASCII 不同，那乘固定数的结果就不同，这样字符串映射冲突的可能性就大大降低了。

template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> struct HashFunc<string> { // 字符串转换成整形，可以把字符 ascii 码相加即可 // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 // 这里我们使用 BKDR 哈希的思路，用上次的计算结果去乘以一个质数，这个质数一般去 31, 131 //等效果会比较好 size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash *= 131; hash += e; } return hash; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: private: vector<HashData<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 };

开放定址法的插入和删除

template<class K> struct HashFunc//针对可以转换成整形的数据 { size_t operator()(const K& key) { return (size_t)key;//如浮点数、字符等 } }; // 特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash *= 31; hash += e; } 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 Hash = HashFunc<K>> class HashTable { public: HashTable() { _tables.resize(10); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子控制在 0.7 以下，超过 0.7，效率较低，需要扩容 //通过*10，避免出现浮点数比较 if (_n * 10 / _tables.size() >= 7) { //vector<HashData<K, V>> newTables(_tables.size() * 2); //// 遍历旧表，将所有数据映射到新表 //// ... //_tables.swap(newTables); 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) { HashData<K, V>* ret = Find(key); if (ret == nullptr)//当前位置为空，也意味着之后没有数据了 { return false; } else { ret->_state = DELETE; return true; } } private: vector<HashData<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 }; 

 // 对 key 为 int 的键值对测试 void TestHT1() { HashTable<int, int> ht; int a[] = { 11,21,4,14,24,15,9 }; for (auto e : a) { ht.Insert({ e,e }); } ht.Insert({ 19,19 }); ht.Insert({ 19,190 }); ht.Insert({ 19,1900 }); ht.Insert({ 39,1900 }); cout << ht.Find(24) << endl; ht.Erase(4); cout << ht.Find(24) << endl; cout << ht.Find(4) << endl; } // 字符串转整形处理方式 struct StringHashFunc { size_t operator()(const string& s) { size_t hash = 0; for (auto e : s) { hash *= 31; hash += e; } return hash; } }; // 对 key 为 string 类型键值对进行测试 void TestHT2() { HashTable<string, string> ht; ht.Insert({ "sort", "排序" }); ht.Insert({ "left", "左边" }); //string s1("sort"); //string s2("sort"); cout << StringHashFunc()("bacd") << endl; cout << StringHashFunc()("abcd") << endl; cout << StringHashFunc()("aadd") << endl; } }

扩容

这里我们哈希表负载因子控制在 0.7，当负载因子到 0.7 以后我们就需要扩容了，我们还是按照 2 倍扩容（简单点）。

之前文章中我们讲过扩容一般来说扩容两倍左右为宜，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2 倍后就不是质数了。那么如何解决了，一种方案就是上面 1.4.1 除法散列中我们讲的 Java HashMap 的使用 2 的整数幂，但是计算时不能直接取模的改进方法。

另外一种方案是 sgi 版本的哈希表使用的方法，给了一个近似 2 倍的质数表，每次去质数表获取扩容后的大小。

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; }

二次探测

• 从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；

• h(key) = hash0 = key % M, hash0 位置冲突了，则二次探测公式为：

(key, i) = hashi = (hash0 ±****) % M，i = {1, 2, 3, ...,}

• 二次探测当 hashi = (hash0 −****)%M 时，当 hashi<0 时，需要 hashi += M，是映射位置绕回到哈希表内。

• 下面 {19,30,52,63,11,22} 等这一组值映射到 M=11 的表中。

h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0

双重散列（了解）

• 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟 key 相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。本质来说双重散列是通过跳跃映射来减少冲突堆积。

• , hash0 位置冲突了，则双重探测公式为：(key) = hash0 = key % M，(key, i) = hashi = (hash0 + i ∗(key)) % M，i = {1, 2, 3, ...,M}

• 要求**(key) < M )且****(key)和 M 互为质数**，有两种简单的取值方法：1、当 M 为 2 整数幂时，(key)从[0，M-1]任选一个奇数；2、当 M 为质数时，(key) = key % (M − 1) + 1

• 保证 (key)与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，映射范围固定在这个群众，若最大公约数 p = gcd(M,****(key)) > 1，那么所能寻址的位置的个数为 M/P < M，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为 1，偏移量为 3，整个散列表大小为 12，那么所能寻址的位置固定在为{1, 4, 7, 10}，寻址个数为 12/gcd(12, 3) = 4

• 下面 {19,30,52,74} 等这一组值映射到 M=11 的表中，设 (key) = key%10 + 1

完整代码实现

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 Hash = HashFunc<K>> class HashTable { public: 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; } HashTable() { _tables.resize(__stl_next_prime(0)); } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; // 负载因子大于 0.7 就扩容 if (_n * 10 / _tables.size() >= 7) { // 这里利用类似深拷贝现代写法的思想插入后交换解决 HashTable<K, V, Hash> newHT; newHT._tables.resize(__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 hash; size_t hash0 = hash(kv.first) % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state == EXIST) { // 线性探测 hashi = (hash0 + i) % _tables.size(); // 二次探测就变成 +- i^2 ++i; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; } HashData<K, V>* Find(const K& key) { Hash hash; size_t hash0 = hash(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; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret == nullptr) { return false; } else { ret->_state = DELETE; --_n; return true; } } private: vector<HashData<K, V>> _tables; size_t _n = 0; // 表中存储数据个数 }; }

6.2 链地址法

6.2.1 链地址法的探讨

解决冲突的思路

开放定址法中所有的元素都放到哈希表里，不管怎么处理数据都存在互相竞争同一块空间的可能性。

而链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，而哈希表（数组）中一个一个位置，我们也叫作哈希桶，链地址法也叫做拉链法或者哈希桶。

• 下面 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到 M=11 的表中。

h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1,h(24) = 2,h(96) = 88

扩容

开放定址法负载因子必须小于 1，链地址法的负载因子就没有限制了，可以大于 1，但是过多因子过大也会导致单个数据链过长，效率也会损失。

所以总的来说负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；stl 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就扩容，我们下面实现也使用这个方式。

6.2.2 链地址法代码实现

链地址法与开放定址法不同是会开辟出节点，因此实现过程中涉及到拷贝（深拷贝）、析构等情况，我们需要自己实现相关函数，处理好资源

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) { } }; //sgi 版本的哈希表使用的方法，给了一个近似 2 倍的质数表，每次去质数表获取扩容后的大小 template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; inline unsigned long __stl_next_prime(unsigned long n) { 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; } public: HashTable() { _tables.resize(__stl_next_prime(0), 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) { Hash hs; size_t hashi = hs(kv.first) % _tables.size(); // 负载因子==1 扩容 if (_n == _tables.size()) { /*HashTable<K, V> newHT; newHT._tables.resize(__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; // 旧表中节点，挪动新表重新映射的位置 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; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; }

极端场景

那如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对了。但是假设不是被针对了，偶然情况下，某个桶很长，查找效率很低怎么办？这里介绍在 Java8 的 HashMap 中，当桶的长度超过一定阀值 (8) 时就把链表转换成红黑树。一般情况下，不断扩容，单个桶很长的场景还是比较少的，下面我们实现就不搞这么复杂了，这个解决极端场景的思路，大家了解一下。