C++ —— 哈希详解 - 开散列与闭散列
目录
1. 哈希的概念
1.1 直接定址法
1.2 哈希冲突
1.3 负载因子
1.4 哈希函数
1.4.1 除法散列法/除留余数法
1.4.2 乘法散列法
1.4.3 全域散列法
1.5 处理哈希冲突
1.5.1 开放定址法（闭散列）
1. 线性探测（挨着查找）
2. 二次探测（跳跃着查找）
3. 双重散列
2. 闭散列实现哈希表
2.1 开发地址法的基础构架
2.2 扩容
2.3 插入
2.4 查找
2.5 删除
2.6 闭散列代码
3. key不能取模的问题
4. 链地址法（开散列/哈希桶）
4.1 链地址法的基础框架
4.2 插入
4.3 扩容
4.4 查找
4.5 删除
4.6 开散列代码
1. 哈希的概念
哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找
1.1 直接定址法
当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标
也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置
直接定址法的缺点也⾮常明显：当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤
假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间
1.2 哈希冲突
这⾥存在的⼀个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞
理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案
1.3 负载因子
假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么 负载因⼦ = N/M（M分之N），负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低
负载因子的大小最好是<=0.7
1.4 哈希函数
⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计
1.4.1 除法散列法/除留余数法
1. 除法散列法也叫做除留余数法，顾名思义，假设哈希表的空间大小为M，那么通过Key%M
key(数据个数)除以M(表的空间大小）得到的余数作为映射位置的下标
也就是哈希函数为：h(key) = key % M
2. 当使⽤除法散列法时，要尽量避免M为某些值，如2的冥，10的冥等
如果是 2X ，那么key %本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了
如：{63 , 31}看起来没有关联的值，如果M是16，也就是 24 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 10X ，就更明显了，保留的都是10进值的后x位，如：{112, 12312}，如果M是100，也就是 102 ，那么计算出的哈希值都是122X
3. 当使⽤除法散列法时，建议M取不太接近2的整数次冥的⼀个质数(素数)
1.4.2 乘法散列法
1. 乘法散列法对哈希表大小M没有要求，他的⼤思路第⼀步：
a. ⽤关键字 K 乘上常数 A (0<A<1)，并抽取出 k*A 的⼩数部分
b. 再⽤M乘以k*A 的⼩数部分，再向下取整
本质就是用M*（0~1）之间的小数
2. h(key) = floor(M × ((A × key)%1.0)) ，其中floor表⽰对表达式进⾏下取整，A∈(0,1)，这⾥最重要的是A的值应该如何设定，Knuth认为 A = ( 5 − 1)/2 = 0.6180339887.... (⻩⾦分割点)⽐较好
3. 乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key= 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669
1.4.3 全域散列法
1. 如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集
⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列
2. hab (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, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5
3. 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了
1.5 处理哈希冲突
实践中哈希表⼀般还是选择除法散列法作为哈希函数，当然哈希表⽆论选择什么哈希函数也避免不了冲突，那么插⼊数据时，如何解决冲突呢？主要有两种两种⽅法，开放定址法和链地址法
1.5.1 开放定址法（闭散列）
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的下一个”空位置中去。
在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测
1. 线性探测（挨着查找）
1. 从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置（回绕方法就是进行取模）
//如果到达表的最后一个位置那么就模一下表的空间大小 hashi = (hash0 + i) % _tables.size();
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位置，这种现象叫做群集/堆积，下⾯的⼆次探测可以⼀定程度改善这个问题
下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M=11的表中（key%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
线性探测法占别人的位置会导致堆积
2. 二次探测（跳跃着查找）
1. 从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置
2. h(key) = hash0 = key % M , hash0位置冲突了，则⼆次探测公式为：
hc(key, i) = hashi = (hash0 ± i *i) % M， i = {1, 2, 3, ..., M/2（二分之M）}
hashi = (hash0 + (i*i*flag)) % _tables.size();3. ⼆次探测当 hashi = (hash0 − i )%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}
也跳跃着查找，但是使用i*下一个哈希函数算出来的值
3. 要求 h2 (key) < M 且 h2 (key) 和M互为质数，有两种简单的取值⽅法：
a. 当M为2整数冥时，h2 (key) 从[0，M-1]任选⼀个奇数
b. 当M为质数时， h2 (key) = key % (M − 1) + 1
4. 保证 h2 (key) 与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最⼤公约数说⽆法充分利⽤整个散列表
举例来说，若初始探查位置为1，偏移量为3，整个散列表⼤⼩为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为p = gcd(M, h1 (key)) > 1 ，那么所能寻址的位置的个数为 M/P < M ，使得对于⼀个关键字来12/gcd(12, 3) = 4
下⾯演⽰ {19,30,52} 等这⼀组值映射到M=11的表中，设 h2 (key) = key%10 + 1
上面的三种方法都无法完全解决哈希冲突的问题，只有跳出内卷循环才能解决问题，也就是链地址法
2. 闭散列实现哈希表
2.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
{
public:
private:
vector<HashData<K, V>> _tables;//表的空间大小
size_t _n; // 记录数据个数
};哈希是通过哈希函数使得元素的存储位置与它的关键码之间能够建立一一映射的关系，需要使用pair<K,V>类型进行存储。采用vector作为底层逻辑，存储元素类型为哈希节点类型HashData<K, V>
这里不采用size作为哈希表中有效元素个数，考虑到容器中结构的差异性，是由于_ size一般用于序列式容器中表示有效元素个数，在关联式容器中命名约定一般规定_n作为记录有效元素个数
要注意的是这⾥需要给每个存储值的位置加⼀个状态标识，否则删除⼀些值以后，会影响后⾯冲突的值的查找
如下图，我们删除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
2.2 扩容
这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，我们还是按照2倍扩容，但是同时我们要保持哈希表⼤⼩是⼀个质数，第⼀个是质数，2倍后就不是质数了。那么如何解决了，⼀种⽅案就是上⾯1.4.1除法散列中我们讲的Java HashMap的使⽤2的整数冥，但是计算时不能直接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的⼤⼩
负载因子 >= 0.7扩容 n/m 数据个数/表的空间大小
当哈希表进行扩容时，表的长度发生了变换。这也意味着通过哈希函数(开发定址法)得到的位置需要重新安排插入，所以需要再开辟空间和插入数据，重新进行映射到新表中 ，遍历旧表，将旧表的数据映射到新表，然后再使用新对象去调用插入，把旧表的数据插入到新表，交换新旧表的空间
素数表：
//素数表
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;
}扩容代码：
//扩容
// 负载因子 >= 0.7扩容 n/m 数据个数/表的空间大小
//为了方便计算分子n*10
if (_n * 10 / _tables.size() >= 7)
{
//创建一个新的哈希表 newht 哈希表里本来就有vector
HashTable<K, V> newht;
//*2是无法一直保持素数的
//newht._tables.resize(_tables.size() * 2);
//使用素数表来获取比素数表的值大一点的值
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (auto& data : _tables)
{
// 遍历旧表，旧表的数据映射到新表
if (data._state == EXIST)
{
//使用新对象去调用插入，把旧表的数据插入到新表
newht.Insert(data._kv);
}
}
//交换新旧表的空间
_tables.swap(newht._tables);
}2.3 插入
在插入过程，元素通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入
bool Insert(const pair<K, V>& kv)
{
//如果值已经存在
if (Find(kv.first))
return false;
Hash hash;//仿函数，用于转换成为无符号整形
//插入值之后从起始位置hash0去用插入的值对表的大小取模算出值对应的位置
size_t hash0 = hash(kv.first) % _tables.size();//hash0是第一次算出来的位置
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state == EXIST)//如果hashi的状态为存在
{
//进行线性探测
//如果到达表的最后一个位置那么就模一下表的空间大小
hashi = (hash0 + i) % _tables.size();
++i;
//二次探测
/*hashi = (hash0 + (i*i*flag)) % _tables.size();
if (hashi < _tables.size())
hashi += _tables.size();
if (flag == 1)
{
flag = -1;
}
else
{
++i;
flag = 1;
}*/
}
//当遇到空的位置就插入
_tables[hashi].kv = kv;
_tables[hashi]._state = EXIST;//将插入的位置标记为存在
++_n;
return true;
}2.4 查找
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;
}2.5 删除
删除只用改变位置状态就可以了
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
return true;
}
else
{
return false;
}
}2.6 闭散列代码
//定义一个枚举来记录数组的三个状态
enum State
{
EXIST,//存在
EMPTY,//空
DELETE//删除
};
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;//状态为空
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
/*
1. 将string类型转换成无符号整形(BKDR_Hash)
2. 字符串转换成整形，可以把字符ascii码相加即可
3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
4. 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去
乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
*/
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};
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;
}
namespace open_address//开发定址法
{ //加上一个仿函数Hash，用于转换成为无符号整形
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
:_tables(__stl_next_prime(0))//给一个0去获取>=0的素数
, _n(0)//数据个数
{}
bool Insert(const pair<K, V>& kv)
{
//如果值已经存在
if (Find(kv.first))
return false;
//扩容
// 负载因子 >= 0.7扩容 n/m 数据个数/表的空间大小
//为了方便计算分子n*10
if (_n * 10 / _tables.size() >= 7)
{
//创建一个新的哈希表 newht 哈希表里本来就有vector
HashTable<K, V> newht;
//*2是无法一直保持素数的
//newht._tables.resize(_tables.size() * 2);
//使用素数表来获取比素数表的值大一点的值
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (auto& data : _tables)
{
// 遍历旧表，旧表的数据映射到新表
if (data._state == EXIST)
{
//使用新对象去调用插入，把旧表的数据插入到新表
newht.Insert(data._kv);
}
}
//交换新旧表的空间
_tables.swap(newht._tables);
}
Hash hash;//仿函数，用于转换成为无符号整形
//插入值之后从起始位置hash0去用插入的值对表的大小取模算出值对应的位置
size_t hash0 = hash(kv.first) % _tables.size();//hash0是第一次算出来的位置
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state == EXIST)//如果hashi的状态为存在
{
//进行线性探测
//如果到达表的最后一个位置那么就模一下表的空间大小
hashi = (hash0 + i) % _tables.size();
++i;
//二次探测
/*hashi = (hash0 + (i*i*flag)) % _tables.size();
if (hashi < _tables.size())
hashi += _tables.size();
if (flag == 1)
{
flag = -1;
}
else
{
++i;
flag = 1;
}*/
}
//当遇到空的位置就插入
_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)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
// 头结点
_tables[hashi] = cur->_next;
}
else
{
// 中间节点
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<HashData<K, V>> _tables;//表的空间大小
size_t _n; // 记录数据个数
};
}
3. key不能取模的问题
当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数⽀持把key转换成⼀个可以取模的整形
如果key可以转换为整形并且不容易冲突，那么这个仿函数就⽤默认参数即可，如果这个Key不能转换为整形，我们就需要⾃⼰实现⼀个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每值都参与到计算中，让不同的key转换出的整形值不同
string做哈希表的key⾮常常⻅，所以我们可以考虑把string特化⼀下
//将普通类型转换成无符号整形
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
/*
1. 将string类型转换成无符号整形(BKDR_Hash)
2. 字符串转换成整形，可以把字符ascii码相加即可
3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
4. 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去
乘以⼀个质数，这个质数⼀般去31, 131等效果会⽐较好
*/
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};4. 链地址法（开散列/哈希桶）
解决冲突的思路
开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶
下⾯演⽰ {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
4.1 链地址法的基础框架
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()
:_tables(11)
, _n(0)
{}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0;// 表中存储数据个数
};
}4.2 插入
bool Insert(const pair<K, V>& kv)
{
Hash hs;
size_t hashi = kv.first % _tables.size();
// 头插
//让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
Node* newnode = new Node(kv);//创建一个新节点new Node
//将新节点的下一个节点指向原来的第一个节点的地址
//第一个节点的地址在哈希表里
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;//再把新节点给与_tables[hashi]里存储的指针
++_n;
return true;
}
4.3 扩容
开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1
负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低
// 负载因子 == 1时扩容
if (_n == _tables.size())
{
vector<Node*> newTatble(_tables.size() * 2);
//遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表数据头插到新表
size_t hashi = cur->_kv.first % newTatble.size();
cur->_next = newTatble[hashi];
newTatble[hashi] = cur;
cur = next;
}
//交换
_tables[i] = nullptr;
}
_tables.swap(newTatble);
}4.4 查找
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;
}4.5 删除
两种情况：一种是删除第一个节点，另一种是删除其他节点prev->_next = cur->_next
在删除节点需要前后兼顾，保存下前驱指针指向节点
bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
// 头结点
_tables[hashi] = cur->_next;
}
else
{
// 中间节点
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}4.6 开散列代码
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()
:_tables(11)
, _n(0)
{}
bool Insert(const pair<K, V>& kv)
{
// 负载因子 == 1时扩容
if (_n == _tables.size())
{
vector<Node*> newTatble(_tables.size() * 2);
//遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 旧表数据头插到新表
size_t hashi = cur->_kv.first % newTatble.size();
cur->_next = newTatble[hashi];
newTatble[hashi] = cur;
cur = next;
}
//交换
_tables[i] = nullptr;
}
_tables.swap(newTatble);
}
size_t hashi = kv.first % _tables.size();
// 头插
//让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
Node* newnode = new Node(kv);//创建一个新节点new Node
//将新节点的下一个节点指向原来的第一个节点的地址
//第一个节点的地址在哈希表里
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;//再把新节点给与_tables[hashi]里存储的指针
++_n;
return true;
}
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->_kv.first;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
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)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0;// 表中存储数据个数
};
}
此间为迷迭