『 C++ 入门到放弃』- 哈希表

一、哈希的概念

哈希，也称「散列」是一种用来进行高效查找的数据结构，查找的时间复杂度平均为O(1)，其本质就是依赖哈希函数这个算法来将 key 和该 key 存储位置建立一个映射关系。

而因为是有着映射关系，所以哈希的事件复杂度为 O (1)
key => hash function => position
采用哈希处理时，一般所需空间都会比元素个数多，否则产生冲突的概率就比较大，影响哈希的性能 => 因此哈希是以空间的代价换取较高的效率

二、相关名词解释

哈希冲突：也称哈希碰撞，也就是不同的key映射到了同一个位置

实际上任何哈希函数都可能发生哈希冲突，我们能做的就是设计出一个好的哈希函数尽可能的减少哈希冲突发生的概率

负载因子：假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，则负载因子为 $NM{\frac{N}{M}}$

负载因子的值越大，意味着哈希冲突的发生率越高，空间使用率高。反之负载因子越小，哈希冲突的发生率越低，空间使用率低。因此负载因子也是后续模拟实现当中用来判断是否要扩容的一个标准

三、哈希函数的定义

3.1 直接定址法

直接定址法适用于 key ( 或称关键字 => 非C++中定义的关键字 ) 范围较集中的情况

直接定址法本质就是⽤ key 计算出⼀个绝对位置或者相对位置

leetcode-387 题目描述如下

我们可以手动模拟哈希
class Solution {public:int firstUniqChar(string s) {int hash[26] = {0}; // 26 对应26个字母for(int i = 0;i<s.size();++i){hash[s[i] - 'a']++; // 直接通过 s 中每一个字符的值 去映射一个位置}for(int i = 0;i<s.size();++i){if(hash[s[i] - 'a'] == 1){return i;}}return -1;}
};

3.2 除法散列法

除法散列法也叫做除留余数法，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标

也就是哈希函数为：h(key) = key % M

在使用除法散列法时应避免 M 的大小取 2 的幂次或 10 的幂次

如果 M 取的大小是 ${2^x}$ 那么key % ${2^x}$ 本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的就冲突了。

如：{63 , 31}看起来没有关联的值，如果M是16，那么计算出的哈希值都是15

因为63的⼆进制后4位是 1111，31的⼆进制后4位是 1111。如果是 ${10^x}$ ，就更明显了，保留的都是
10进值的后x位，如：{112, 12312}，如果M是100，那么计算出的哈希值都是12

为了避免前面提到的问题，当使用除法散列法时建议M取不太接近2的整数次幂的⼀个质数

散列函数有一个共同性质，即函数值应按同等概率取其值域的每一个值

四、哈希碰撞的解决方法

4.1 开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了

则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的

这⾥有三种：线性探测、⼆次探测、双重探测

4.1.1 线性探测

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

采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找

4.1.2 二次探测

从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为
⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表
尾的位置

4.1.3 开放定址法代码实现

开放定址法在实践中，不如链地址法，因为开放定址法解决冲突不管使⽤哪种⽅法，占⽤的都是哈希表中的空间

始终存在互相影响的问题。所以开放定址法，我们简单选择线性探测进行实现

#include <iostream>
using namespace std;namespace OpenAddress {// 仿函数template <class K> struct HashFunc {size_t operator()(const K &key) {return (size_t)key; // 把 key 转成整数 ( 为了处理 key 非整的情况 =>// 因为要取模，非整没办法取模 )// 如果是自定义类型，也可以将赅仿函数进行特化 来处理自定义类型转整的问题}};// 特化 处理stringtemplate <> struct HashFunc<string> {size_t operator()(const string &key) {size_t hash = 0;for (auto ch : key) {hash = hash * 131 + ch;}return hash;}};enum State { EMPTY, EXISTED, DELETED };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:// 这里提供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);// 如果 n 的值超出 [first,last) 的最大值 => return 最后一个元素的下一个位置;// 如果小于 return 第一个元素的位置return pos == last ? *(last - 1) : *pos;}HashTable() { _table.resize(__stl_next_prime(0)); }bool insert(const pair<K, V> &kv) {// 插入时先确定该值是否已存在表中if (find(kv.first)) {return false;}// 先判断当前的负载因子大小( N(数据个数) / M(表大小) )if (_n * 10 / _table.size() >= 7) { // 这里我们将负载因子控制在0.7// 扩容的逻辑就是先开空间 把元素 _table 中的元素插入到新开的空间中// 再将新的空间和旧的空间交换HashTable<K, V, Hash> newht;newht._table.resize(__stl_next_prime(_table.size() + 1));for (size_t i = 0; i < _table.size(); ++i) {if (_table[i]._state == EXISTED) {newht.insert(_table[i]._kv);}}_table.swap(newht._table);}// 如果负载因子小于0.7 则直接插入Hash hash;size_t hash0 = hash(kv.first) % _table.size();size_t hashi = hash0;size_t i = 1;while (_table[hashi]._state == EXISTED) {// 线性探测hashi = (hash0 + i) % _table.size();// 如果是二次探测 就改成 +- i^2++i;}_table[hashi]._kv = kv;_table[hashi]._state = EXISTED;++_n;return true;}HashData<K, V> *find(const K &key) {Hash hash;size_t hash0 = hash(key) % _table.size();size_t hashi = hash0;size_t i = 1;while (_table[hashi]._state != EMPTY) {// 如果找到if (_table[hashi]._state == EXISTED && _table[hashi]._kv.first == key) {return &_table[hashi];}// 如果当前的 index 不是目标值 ( 可能是原本就被占用了，所以要往后找// 直到找完整个 _table) => 所以其实开放定址法的效率不及链定址法hashi = (hash0 + i) % _table.size();++i;}// while 结束代表没有找到目标值return nullptr;}bool erase(const K &key) {HashData<K, V> ret = find(key);if (ret == nullptr) {return false;}ret->_state = DELETED;--_n;return true;}private:vector<HashData<K, V>> _table;size_t _n = 0; // 哈希表中存儲的數據個數};void HashTest1() {HashTable<int, int> ht;ht.insert(make_pair(1, 1));ht.insert(make_pair(2, 2));ht.insert(make_pair(3, 3));ht.insert(make_pair(4, 4));ht.insert(make_pair(5, 5));ht.insert(make_pair(6, 6));ht.erase(2);ht.erase(3);}
}

4.2 链定址法

链定址法的思想：开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中

哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时**

把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶

namespace HashBucket {
// 仿函数
template <class K> struct HashFunc {size_t operator()(const K &key) { return (size_t)key; }
};
template <class K, class V> struct HashData {pair<K, V> _kv;HashData<K, V> *_next;HashData(const pair<K, V> &kv) : _kv(kv), _next(nullptr) {}
};template <class K, class V, class Hash = HashFunc<K>> class HashTable {typedef HashData<K, V> Node;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);// 如果 n 的值超出 [first,last) 的最大值 => return 最後一個元素的下一個位置;// 如果小於 return 第一個元素的位置return pos == last ? *(last - 1) : *pos;}// 初始化HashTable() { _table.resize(__stl_next_prime(0)); }~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) {Hash hs;size_t hashi = hs(kv.first) % _table.size();// 扩容// 这路就不用判断负载因子了，因为相同的位置都会像链表一样串接起来if (_n == _table.size()) {// 怎么扩？vector<Node *> newht(__stl_next_prime(_table.size() + 1), nullptr);for (size_t i = 0; i < _table.size(); ++i) {// 挪动数据Node *cur = _table[i];while (cur) {// 先保留_next;Node *next = cur->_next;// 将旧表的数据挪动到新表size_t hashi = hs(cur->_kv.first) % newht.size();cur->_next = newht[hashi];newht[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newht);}// 如果有其他数据 => 直接头插Node *newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;}Node *find(const K &key) {Hash hs;size_t hash0 = hs(key) % _table.size();Node *cur = _table[hash0];while (cur) {if (cur->_kv.first == key) {return cur;}cur = cur->_next;}return nullptr;}bool erase(const K &key) {Hash hs;size_t hash0 = hs(key) % _table.size();Node *cur = _table[hash0];Node *prev = nullptr;while (cur) {if (cur->_kv.first == key) {if (prev == nullptr) { // prev 为空 代表删除的是第一个数据_table[hash0] = cur->_next;} else {prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node *> _table;size_t _n = 0; // 数据个数
};
void HashBucketTest1() {HashTable<int, int> ht;ht.insert(make_pair(1, 1));ht.insert(make_pair(2, 2));ht.insert(make_pair(3, 3));ht.insert(make_pair(4, 4));ht.insert(make_pair(5, 5));ht.insert(make_pair(6, 6));ht.insert(make_pair(7, 7));ht.insert(make_pair(8, 8));ht.insert(make_pair(9, 9));ht.insert(make_pair(10, 10));
}
void HashBucketTest2() {HashTable<int, int> ht;ht.insert(make_pair(1, 1));ht.insert(make_pair(2, 2));ht.insert(make_pair(3, 3));ht.insert(make_pair(4, 4));ht.insert(make_pair(5, 5));ht.erase(2);ht.erase(3);ht.erase(4);ht.erase(5);ht.erase(6);ht.erase(7);ht.erase(8);ht.erase(9);
}
} // namespace HashBucket

五、选择题解析

已知有一个关键字序列：（19,14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中

若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为?

其呈现如上图

14,1,23,10,11,19,20 比较 1 次就可以找到

84,79,68,27 2次

55 3 次

总共：1 * 7 + 2 * 4 + 3 * 1 = 18 数据个数：12

18 / 12 =1.5

已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行几次探测

有 n 个数据，第一个数据 1 次，第二个数据 2 次，。。。第 n 个数据 n 次

总共：1 + 2 + 。。。 + n = $n∗(n+1)2{\frac{n*(n+1)}{2}}$

用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，会受堆积现象直接影响的是平均查找長度