【高阶数据结构】哈希表

char ch[26] = { 0 }; ch['a' - 'a'] = 'a'; // 存储字符a ch['g' - 'a'] = 'g'; // 存储字符g // 根据映射关系直接找到相应的字符 cout << ch['a' - 'a'] << endl; cout << ch['g' - 'a'] << endl;

1.2、哈希冲突

可是直接定址法只适用于数据比较集中的场景，对于数据分散的情况，缺点就会暴露无遗。

举个例子，你有5个值：1， 2， 3， 4 ，10000001。

直接开一个10000001大小的数组，数据存储在对应下标位置，查找非常快，时间复杂度O(1)。但这未必也太浪费空间了，开这么大的空间就存这几个货😑，cuo，太cuo。

但这能难到那些大佬吗？

这时候我们就可以通过哈希函数将这 N 个分散的数映射到一个M大小的数组（M >= N），就比如拿取模的方法来说。

我们知道，n % M，得到的数肯定小于M，这不就将这一组数限制到M大小的数组中了吗。

但是细心的小伙伴肯定已经发现了。

5 % 20， 25 % 20，45 % 20...，不都等于5吗，那么同一个位置不就重复了，即不同的值映射到了一个位置，这就是哈希冲突。

理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。

1.3、负载因子

假设哈希表中已经映射存储了N个值，哈希表的大小为M，负载因子 = N / M。

负载因子越大，即映射的值越多，哈希冲突的概率越高，空间利用率越高；负载因子越小，即映射的值越少，哈希冲突的概率越低，空间利用率越低。

所以，当负载因子达到一定的大小时，就需要我们对数组进行扩容。

但是，对于扩容的条件，不同的哈希表结构不同，对于线性探测的结构，一般当负载因子>=0.7时，进行扩容；哈希桶结构当映射值的数量与数组大小相同时，进行扩容。

1.4、哈希函数

一个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个方向去考量设计。

1.4.1、除法散列法 / 保留余数法（重点）

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

那么问题就来了。

对于哈希表的大小M，怎么取才合适呢？怎么才能保证将所有的数均匀的映射到数组中呢？

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

什么意思呢，如果将key写成二进制的形式，不难看出，%一个2^X，结果就是key的后X二进制位组成的数。

当使用除法散列法时，建议M取不太接近2的整数次幂的一个质数(素数)。尽可能让所有数均匀发布到数组中，但是，冲突肯定是无法完全避免的，所以，当一个位置已经有数据时，就在这位置的后面找空位。

我们可以通过下面的代码来找一个大于或等于n的素数，作为数组的大小：

inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes = 28; // __stl_prime_list数组有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; // 数组末尾的下一个位置 // 找[first,last)区间中第一个大于或等于 n 的的素数 const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; }

1.4.2、其他

还有乘法散列法，全域散列法等，也比较巧妙，感兴趣可以自己了解，这里我们最常用的还是取余数的这种方式。

二、哈希冲突处理

2.1、开放定址法

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

2.1.1、线性探测

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

• 线性探测的比较简单且容易实现，线性探测的问题在于，由于hash0位置连续冲突，使得原本应该映射到hash0位置的值，占了后续映射到hash1，hash2位置的值的位置，这种现象叫做群集/堆积。下面的二次探测可以一定程度改善这个问题。

2.1.2、二次探测

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

2.2、链地址法

开放定址法，不论怎样处理，冲突不可避免，对于一些极端情况：

假如我有一组数据，取完余数，好家伙，发现全部冲突了，这还怎么玩。难道还线性探测，二次探测吗？cuo，真的cuo。

这时候哈希桶闪亮登场：我给你全部串起来，余数相同怎么了，全部冲突怎么了，用一个链表串起来一挂，解决了。好，你说串的太多了，我可以扩容，实在不行我再来个红黑树。

三、哈希表设计实现

3.1、开放定址法

3.1.1、定义数据结构

实现一个键值对（key_value）类型的哈希表，即需要一个pair类型的对象存储数据，由于线性结构的哈希表，不可避免地存在哈希冲突，所以在插入，查找数据时，就需要知道当前位置的状态，所以还需要一个存储状态的量。由于一个位置状态无非就是存在值，空和被删除，所以考虑用一个枚举类型存储状态。

// 枚举：记录每个HashData的状态 enum State { EXITE, DELETE, EMPTY }; template<class K,class V> struct HashData { pair<K, V> _kv; // 键值对 State _state = EMPTY; // 状态 };

3.1.2、哈希表结构

哈希表底层核心载体就是一个数组，而线性结构的数据又全部存储在数组中，所以直接用一个vector数组，数据类型即为上面定义的自定义类型。用_size记录数据个数。

template<class K, class V, class Hash=HashFunc<K>> class HashTables { typedef HashNode<K,V> Node; // 重命名 public: // 构造 HashTables() :_tables(__stl_next_prime(0)) // 用找素数函数初始化 , _size(0) { } // 素数函数：用来扩容 // 找一个比n大的素数，作为哈希表扩容的大小 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; // __stl_prime_list数组有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; // 找[first,last)区间中第一个大于或等于 n 的的素数 const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } private: vector<HashNode<K,V>> _tables; // 数组 size_t _size = 0; // 存储数据个数 };

3.1.3、数据类型处理---仿函数

由于只有对无符号整形取模运算时，才能获得有效的下标，所以必须将int，double等数据强转为unsigned int类型来计算映射位置；同时，对于字符串，日期类等不能强转为unsigned int类型的数据类型，就需要单独处理。

对于字符串，我们可以将字符串的所有字符的ASCII码值加起来，然后计算映射的相对位置，同时，由于字符串这样计算出的值一般较大，哈希冲突的概率变大，所以，又有人提出：在逐字符相加的过程中对每个字符进行乘131的处理方法。为什么选择乘131，有兴趣的可以查阅资料，反正肯定是能够更好地减少哈希冲突。

我们采用仿函数来解决这个问题，这样更方便我们在外部控制。

// 仿函数，用来将负数，double等类型的数据先转化为无符号整形 template<class K> struct HashFun { int operator()(const K& key) { return (size_t)key; // 强转 } }; // 模板函数：特化，专门处理字符串 template<> struct HashFun<string> { size_t operator()(const string& key) { size_t ch = 0; auto it = key.begin(); for (size_t i = 0; i < key.size(); i++) { ch += *it * 131; // 由于字符串转为unsigned int，取模后容易重复，为了使哈希值更分散，对每个字符的ASCII值乘以一个131 it++; } return ch; } };

3.1.4、插入

我们默认不插入相同的值，所以，当键值重复时直接返回；同时，我们还需要关注负载因子的大小，理论上当负载因子大于或等于0.7时，进行扩容；由于哈希冲突的原因，我们还需要关注要插入的位置是否已经被其他值占了。

bool Insert(const pair<K, V>& kv) { // 数据不冗余 if (Find(kv.first)) { return false; } // 扩容 // 负载因子：当前存储的数据个数 / 哈希表大小，这里当负载因子大于或等于0.7时进行扩容 if (_size * 10 / _tables.size() >= 7) { HashTables<K, V> newtables; //newtables._tables.resize(_tables.size() * 2); // 二倍扩容 newtables._tables.resize(__stl_next_prime(_tables.size() + 1)); // 为了防止lower_bound每次找到的值相同 // 旧表的数据映射到新表 for (auto& data : _tables) { if(data._state==EXITE) { newtables.Insert(data._kv); } } _tables.swap(newtables._tables); //将新表与旧表交换 } size_t hash0 = kv.first % _tables.size(); // 找key键值对应的位置（下标） size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state == EXITE) { // 线性探测：找状态为DELETE或EMPTY的位置 hashi = (hash0 + i) % _tables.size(); //// 二次探测 //hashi = (hash0 + i * i) % _tables.size(); i++; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXITE; _size++; return true; }

3.1.5、查找

唯一需要注意的就是，由于哈希冲突，我们要查找的值可能并不在我们计算出的位置处，即所有不为空的位置，我们都要进行查找（遍历）。

HashData<K, V>* Find(const K& key) { size_t hash0 = key % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state != EMPTY) { // 线性探测：找状态为DELETE或EXITE的位置 if (_tables[hashi]._state==EXITE && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi = (hash0 + i) % _tables.size(); i++; } return nullptr; }

3.1.6、删除

bool Erase(const K& key) { if (Find(key)) { HashData<K, V>* pos = Find(key); pos->_state = DELETE; return true; } return false; }

3.2、链地址法（哈希桶）

3.2.1、定义哈希桶节点结构

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

3.2.2、定义哈希表结构

底层认为数组作为核心载体，只是数组中应该存储节点类型的指针。_size记录插入节点个数，方便扩容。

template<class K, class V, class Hash = HashFun<K>> class Hash_Bucket { typedef HashNode<K, V> Node; public: // 构造 Hash_Bucket() :_tables(11) , _size(0) {} // 析构 ~Hash_Bucket() { 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; } } // 找一个比n大的素数，作为哈希表扩容的大小 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; // __stl_prime_list数组有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); // 找[first,last)区间中第一个大于或等于 n 的的素数 return pos == last ? *(last - 1) : *pos; } private: vector<Node*> _tables; size_t _size = 0; };

3.2.3、插入---头插

数据不能冗余；如果当前位置为空则直接插入数组对应的位置；若当前位置已经有节点，则头插；

当节点数等于，数组大小时，扩容，这样也可以起到防止链表过长的情况发生，因为，扩容后，我们需要将所有的节点拿下来重新映射到新表中。

记得最后++_size。

bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hash; // 仿函数 // 扩容 if (_size == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size() + 1)); // 创建一个新表 // 遍历旧表，将旧表的节点拿下来插入到新表，然后交换 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hash(cur->_kv.first) % newtables.size(); // 头插 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); // 交换 } size_t hashi = hash(kv.first) % _tables.size(); Node* newnode = new Node(kv); Node* cur = _tables[hashi]; // 头插 newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; }

3.2.5、查找

根据key算出映射位置的下标，然后遍历链接的单链表即可。

Node* Find(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; }

3.2.6、删除

删除时需要注意，该节点是存储在数组中的节点还是链接在中间的节点，因为对于这两种情况，在删除节点后的处理不同。我们可以用一个prev指针来进行判断。

bool Erase(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { // cur为桶的第一个节点 if (prev == nullptr) { _tables[hashi] = nullptr; } // 中间节点 else { prev->_next = cur->_next; } // 释放 delete cur; --_size; return true; } else { prev = cur; cur = cur->_next; } } return false; }

四、完整源码

开放定址法：HashTables.h测试代码：test.cpp

哈希桶：HashBucket.h

测试：test.cpp

同学，都看到这了，顺手给咱点个赞吧~