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 哈希表里本来就有vectorHashTable<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){// BKDRsize_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*10if (_n * 10 / _tables.size() >= 7){//创建一个新的哈希表 newht 哈希表里本来就有vectorHashTable<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){// BKDRsize_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;// 表中存储数据个数};
}

 

此间为迷迭

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/471536.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

苦等三年！金克斯大人回来了！

苦等三年！金克斯大人回来了！

2021年《英雄联盟&#xff1a;双城之战》第一季上线&#xff0c;该动画连续三周在全球 52 个国家和地区占据榜单前十&#xff0c;并在第49届安妮奖中斩获最佳电视 / 流媒体类动画、最佳艺术指导、最佳角色动画等9项大奖。 苦等三年&#xff01;&#xff01;&#xff01; 《双城…
阅读更多...
NVR录像机汇聚管理EasyNVR多品牌NVR管理工具/设备：大华IPC摄像头局域网访问异常解决办法

NVR录像机汇聚管理EasyNVR多品牌NVR管理工具/设备：大华IPC摄像头局域网访问异常解决办法

在当今社会&#xff0c;安全监控已成为各类场所不可或缺的一部分。无论是家庭、学校、商业场所还是公共场所&#xff0c;安全监控设备都扮演着至关重要的角色。在众多监控品牌中&#xff0c;大华IPC摄像头凭借其高清画质、强大功能和卓越稳定性&#xff0c;赢得了市场的广泛认可…
阅读更多...
随机数

随机数

目录 一、传统方式&#xff1a;std::rand 和 std::srand 使用方法&#xff1a; 优缺点&#xff1a; 二、现代方式&#xff1a; 库&#xff08;推荐&#xff09; 1. 随机整数 2. 随机浮点数 3. 布尔值 4. 字符 5. 正态分布&#xff08;高斯分布&#xff09; 6. 离散分…
阅读更多...
Python Plotly 库使用教程

Python Plotly 库使用教程

Python Plotly 库使用教程 引言 数据可视化是数据分析中至关重要的一部分&#xff0c;它能够帮助我们更直观地理解数据、发现潜在的模式和趋势。Python 提供了多种数据可视化库&#xff0c;其中 Plotly 是一个功能强大且灵活的库&#xff0c;支持交互式图表的创建。与静态图表…
阅读更多...
LeetCode题解：5.最长回文子串【Python题解超详细，中心拓展、动态规划、暴力解法】

LeetCode题解：5.最长回文子串【Python题解超详细，中心拓展、动态规划、暴力解法】

题目描述 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 解答 class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""# 思路一&#xff1a;中心拓展def extend_from_center(left,right):# 从中心向…
阅读更多...
企业一站式管理系统odoo的研究——PLM插件的搭建

企业一站式管理系统odoo的研究——PLM插件的搭建

大纲 1. 环境准备1.1 安装操作系统1.2 更新操作系统1.3 配置用户组和用户1.3.1 创建用户组 odoo1.3.2. 创建用户 odoo1.3.3. 设置用户 odoo 的密码1.3.4. 验证用户和组1.3.5. 将用户 odoo 添加到添加sudo组&#xff1a;1.3.6. 切到odoo用户 2. 安装 Odoo1. 安装依赖项目2.2. 安…
阅读更多...
Keil基于ARM Compiler 5的工程迁移为ARM Compiler 6的工程

Keil基于ARM Compiler 5的工程迁移为ARM Compiler 6的工程

环境&#xff1a; keil版本为5.38&#xff0c;版本务必高于5.30 STM32F4的pack包版本要高于2.9 软件包下载地址&#xff1a;https://zhuanlan.zhihu.com/p/262507061 一、更改Keil中编译器 更改后编译&#xff0c;会报很多错&#xff0c;先不管。 二、更改头文件依赖 观察…
阅读更多...
ABAP开发学习——ST05 ABAP SQL跟踪工具

ABAP开发学习——ST05 ABAP SQL跟踪工具

操作步骤 第一步使用ST05之前&#xff0c;将要查的程序停留想要看的操作的前一步&#xff0c;这里想看到取数操作&#xff0c;所以停留在选择界面 第二步进入ST05 选择SQL Trace 然后激活 第三步去执行程序 第四步ST05取消激活 第五步查看操作 选完时间直接执行
阅读更多...
C/C++语言基础--C++模板与元编程系列六，C++元编程相关库的讲解与使用

C/C++语言基础--C++模板与元编程系列六，C++元编程相关库的讲解与使用

本专栏目的 更新C/C的基础语法&#xff0c;包括C的一些新特性 前言 模板与元编程是C的重要特点&#xff0c;也是难点&#xff0c;本人预计将会更新10期左右进行讲解&#xff0c;这是第六期&#xff0c;讲解元编程相关库等&#xff0c;本人感觉这一部分内容还是比较复杂的&am…
阅读更多...
uni-app之数据驱动的picker选择器（ uni-data-picker）之可以选择到任意级别

uni-app之数据驱动的picker选择器（ uni-data-picker）之可以选择到任意级别

背景说明 uni-app 官方的插件市场有数据驱动选择器&#xff0c;可以用作多级分类的场景。本人引入插件后&#xff0c;发现&#xff0c;在h5和微信小程序都只能选择到叶子级。而在给出的官方组件示例中确并非如此。 以选择年级&#xff0c;而不选择班级。然后&#xff0c;想试试…
阅读更多...
探索 HTML 和 CSS 实现的蜡烛火焰

探索 HTML 和 CSS 实现的蜡烛火焰

效果演示 这段代码是一个模拟蜡烛火焰的HTML和CSS代码。它创建了一个具有动态效果的蜡烛火焰动画&#xff0c;包括火焰的摆动、伸缩和光晕的闪烁。 HTML <div class"holder"><div class"candle"><div class"blinking-glow"&g…
阅读更多...
react + ts定义接口类型写法

react + ts定义接口类型写法

接口&#xff08;未进行ts定义&#xff09; export async function UserList(params: {// keyword?: string;current?: number;pageSize?: number;},// options?: { [key: string]: any }, ) {return request<API1.UserList>(http://geek.itheima.net/v1_0/mp/artic…
阅读更多...
【教程】Ubuntu设置alacritty为默认终端

【教程】Ubuntu设置alacritty为默认终端

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 目录 背景介绍 设置教程 注意事项 背景介绍 alacritty是一个开源的终端&#xff0c;比默认的xterm更好看&#xff0c;甚至编辑文本时候还会代码高亮…
阅读更多...
使用Element UI实现前端分页，及el-table表格跨页选择数据，切换分页保留分页数据，限制多选数量

使用Element UI实现前端分页，及el-table表格跨页选择数据，切换分页保留分页数据，限制多选数量

文章目录 一、前端分页1、模板部分 (\<template>)2、数据部分 (data)3、计算属性 (computed)4、方法 (methods) 二、跨页选择1、模板部分 (\<template>)2、数据部分 (data)3、方法 (methods) 三、限制数量1、模板部分 (\<template>)2、数据部分 (data)3、方法…
阅读更多...
写给初学者的React Native 全栈开发实战班

写给初学者的React Native 全栈开发实战班

React Native 全栈开发实战班 亲爱的同学们&#xff1a; 很高兴在这里与大家相聚&#xff01;我是你们的讲师&#xff0c;将带领大家一起踏上 React Native 移动开发的学习之旅。 为什么选择 React Native&#xff1f; 在这个移动互联网时代&#xff0c;App 开发工程师已经…
阅读更多...
StarRocks Summit Asia 2024 全部议程公布！

StarRocks Summit Asia 2024 全部议程公布！

随着企业数字化转型深入&#xff0c;云原生架构正成为湖仓部署的新标准。弹性扩展、资源隔离、成本优化&#xff0c;帮助企业在云上获得了更高的灵活性和效率。与此同时&#xff0c;云原生架构也为湖仓与 AI 的深度融合奠定了基础。 在过去一年&#xff0c;湖仓技术与 AI 的结…
阅读更多...
[CKS] K8S Dockerfile和yaml文件安全检测

[CKS] K8S Dockerfile和yaml文件安全检测

最近准备花一周的时间准备CKS考试&#xff0c;在准备考试中发现有一个题目关于Dockerfile和yaml文件安全检测的题目。 ​ 专栏其他文章: [CKS] Create/Read/Mount a Secret in K8S-CSDN博客[CKS] Audit Log Policy-CSDN博客 -[CKS] 利用falco进行容器日志捕捉和安全监控-CSDN博…
阅读更多...
鸿蒙之多选框(Checkbox)

鸿蒙之多选框(Checkbox)

前言&#xff1a; 控制单个或者多个选项的选中状态&#xff0c;就可以使用 多选框组件 Checkbox:多选框组件CheckboxGroup:多选框组&#xff0c;控制多个多选框 Checkbox: 参数CheckboxOptions说明 名称 类型 必填 描述 name string 否 用于指定多选框名称。一般结合Ch…
阅读更多...
CSP/信奥赛C++语法基础刷题训练（8）：洛谷P5718：找最小值

CSP/信奥赛C++语法基础刷题训练（8）：洛谷P5718：找最小值

CSP/信奥赛C语法基础刷题训练&#xff08;8&#xff09;&#xff1a;洛谷P5718&#xff1a;找最小值 题目描述 给出 n n n 和 n n n 个整数 a i a_i ai​&#xff0c;求这 n n n 个整数中最小值是什么。 输入格式 第一行输入一个正整数 n n n&#xff0c;表示数字个数。…
阅读更多...
【云原生系列--Longhorn的部署】

【云原生系列--Longhorn的部署】

Longhorn部署手册 1.部署longhorn longhorn架构图&#xff1a; 1.1部署环境要求 kubernetes版本要大于v1.21 每个节点都必须装open-iscsi &#xff0c;Longhorn依赖于 iscsiadm主机为 Kubernetes 提供持久卷。 apt-get install -y open-iscsiRWX 支持要求每个节点都安装 N…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023