✨✨ 欢迎大家来到小伞的大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：C++学习
小伞的主页：xiaosan_blog制作不易！点个赞吧！！谢谢喵！！！
1.哈希概念
1.1 直接链址法
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
这是一种空间换时间的一种方式，假如开辟无限大的空间，查找一个数为O(n),而插入则是O(1);
class Solution {
public:
int firstUniqChar(string s) {
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;
}
};1.2 哈希冲突
1.3 哈希因子
假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因⼦ = M/N，负载因⼦有些地方也翻译为载荷因⼦/装载因⼦等，他的英文为load factor。负载因⼦越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；
1.4 哈希函数
1.4.1 除法散列法/除留余数法
1.4.2 乘法散列法
1.4.3 全域散列法
1.4.4 其他方法
1.平方取中法
假设关键码为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键码为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
平方取中法比较适合：不知道关键码的分布，而位数又不是很大的情况
2.折叠法
关键码从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键码的分布且位数比较多的情况
3.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。
通常应用于关键字长度不等时采用此法
4.数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀，只有某几种符号经常出现。此时可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
比如：假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的4位作为散列地址，如果这样的抽取工作还容易出现冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环移位(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况
1.5 处理哈希冲突
哈希表无论选择什么方法都会产生哈希冲突，那如何解决冲突呢？主要有两个方法，开放定址法和链地址法
1.5.1 开放定址法概念
1.线性探测
1.从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。2.h(key) = hash0 = key % M, hash0位置冲突了，则线性探测公式为：hc(key,i) = hashi = (hash0 + i) % M， i = {1, 2, 3, ..., M − 1}， 因为负载因⼦⼩于1， 则最多探测M-1次，⼀定能找到⼀个存储key的位置。3.线性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1， hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。
| h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1 |
2.二次探测
1.从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置；
2.h(key) = hash0 = key % M，hash0位置冲突了，则二次探测公式为：
hc(key, i) = hashi = (hash0 ± i^2) % M， i = {1, 2, 3, ... ,M/2 }
3.二次探测当 hashi = (hash0 - i^2)%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
3.双重散列
1.第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
2.h1(key) = hash0 = key % M, hash0位置冲突了，则双重探测公式为：
hc(key, i) = hashi = (hash0 + i ∗ h2(key)) % M， i = {1, 2, 3,... ,M/2 }
3.要求h2（key）<M且h2（key）和M互为质数，有两种简单的取值方法：1、当M为2整数幂时，h2（key）从[0，M-1]任选一个奇数；2、当M为质数时，h2（key）=key%（M－1）+1
4.保证h2（key）与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数p=gcd（M,h（key)）>1，那么所能寻址的位置的个数为M/FV，使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1,4,7，10}，寻址个数为12/gcd（12,3）=4
例：下面演示{19,30,52,74}等这一组值映射到M=11的表中，设h2（key）=key%10+1
1.5.1.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; // 表中存储数据个数 };
要注意的是这里需要给每个存储值的位置加一个状态标识，否则删除一些值以后，会影响后面冲突的值的查找。如下图，我们删除30，会导致查找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 |
扩容
这里我们哈希表负载因子控制在0.7，当负载因子到0.7以后我们就需要扩容了，我们还是按照2倍扩容，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2倍后就不是质数了。那么如何解决了，一种方案就是上面1.4.1除法散列中我们讲的JavaHashMap的使用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;//三目表达式 }
key不能取模的问题
当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加一个仿函数，这个仿函数支持把key转换成一个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整形，我们就需要自已实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同。string做哈希表的key非常常见，所以我们可以考虑把string特化一下。
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; // 表中存储数据个数
}完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
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;
}
};
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));
} b
ool 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);
} H
ash 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;
} H
ashData<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; // 表中存储数据个数
};
}开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
1.5.2链地址法
下面演示{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。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；st中unordered_xxx的最大负载因子基本控制在1，大于1就扩容，我们下面实现也使用这个方式。
极端场景
如果极端场景下，某个桶特别长怎么办？其实我们可以考虑使用全域散列法，这样就不容易被针对
了。但是假设不是被针对了，用了全域散列法，但是偶然情况下，某个桶很长，查找效率很低怎么
办？这里在Java8的HashMap中当桶的长度超过一定阀值(8)时就把链表转换成红黑树。一般情况下，不断扩容，单个桶很长的场景还是比较少的。
代码实现
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;
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;
} e
lse
{
prev->_next = cur->_next;
} d
elete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};
}