文章目录
目录
前言
在这之前，我们学习了C++中各种数据结构，今天我们再来学习一种C++中十分好用的结构——哈希表，它是一种由映射所产生的结构，它对于数据查找的时间复杂度甚至可以达到O(1)的程度。
一、哈希概念
我们在学习一个东西之前，我们得先弄明白这个东西是什么。哈希（hash)又被称之为散列，是一种组织数据的形式。从名字上来看，有散乱排列的意思。本质上就是通过哈希函数将关键字Key与存储位置构建一个映射关系，查找时通过哈希函数计算出Key的存储位置，进行快速查找的方式。看到这里，会不会想起我们在数据结构阶段学习的基数排序有点像，都是对数据进行处理，然后再通过某种映射关系将那些数据都映射到数组中，我们最后通过几个排序算法的效率比较，基数排序的效率还是十分高效的，但是它也有一点瑕疵：对于排列十分分散的数据处理起来就不太友好了，我们需要空间开销可能很大。
二、哈希的相关概念
2.1 负载因子
假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子的大小就是N/M；负载因子在有些地方又被翻译为载荷因子/装载因子等，它的英文名字为load factor。负载因子越大，则其哈希冲突的概率越高，空间利用率越高，负载因子越小，则其哈希冲突的概率越低，空间利用率越低。
2.2 哈希冲突
我们哈希表的最核心操作就是映射，但是我们在对那么多数据进行映射操作时，难免会有一些数据会映射到一个位置上，我们把这种情况叫做哈希冲突。（如果我们记不清概念，我们可以这样联想的记忆：如果某个人提前占据了本来属于你的位置，那么可能就会起冲突了）这个冲突和我们理工科中常说的误差一样，是不可避免的，我们只能够减少。我们后面的一些操作就是想办法减少哈希冲突的概率，并且使得空间有效利用。
2.3 将关键字转换为整数
我们哈希表的底层实现结构是一个数组，数组的下标是由整数进行表示的，而我们使用哈希表存储数据不可能仅仅存储一些整数，我们肯定会存储一些其他数据类型的数据，因此这时候我们就要想办法去将关键字转换为整数类型的（一般为size_t 无符号整型类型的，数组的下标没有负数，最小从0开始）
那么我们如果将那些关键字的类型转换为整型呢？对于一些那些内置类型，我们可以直接使用强制类型转换将那些关键字的数据类型转换为size_t 类型，但是对于string这种类型，它不属于我们的内置类型，我们无法使用强制类型转换，于是我们就使用它们的ASCII码值来进行表示，但是仅仅将字符串中所有字符的ASCII码值进行相加，还是太草率了（对于几个数相加的和相等，有好几种排列组合，字符中也是如此，例如：abbc,bcba,abad等它们的ASCII码值都是相等的）因此我们需要对它们的ASCII码值再进行一些处理，我们每加上一个字符的ASCII码值之后再对其乘上一个131（这个值是前人们进行大量实验得出的一个经验值），经过这一系列处理后，我们得到的值重复的概率就大大降低了。
如上方法是我们自行实现函数进行处理的，除此之外，C++中对于基本类型和标准库类型可以直接使用std::hash进行处理，如下代码所示
#include <functional>
#include <string>
std::hash<int> int_hash;
int key = 42;
size_t hash_value = int_hash(key); // 转换为size_t
std::hash<std::string> string_hash;
std::string s = "hello";
size_t string_hash_value = string_hash(s);除此之外，库函数Boost还提供了一个更加强大的哈希支持：
#include <boost/functional/hash.hpp>
struct Person {
std::string name;
int age;
};
size_t hash_value(const Person& p) {
size_t seed = 0;
boost::hash_combine(seed, p.name);
boost::hash_combine(seed, p.age);
return seed;
}2.4 哈希函数
一个好的哈希算法离不开一个好的哈希函数，而一个好的哈希函数应该将N个数据等概率地均匀地散列分布在哈希表M个空间中，但是这只是在理论中的，现实中是很难打出这样的操作的，但是我们还是朝着这个方向努力的。接下来我来介绍一些常见的哈希函数。
2.4.1 除法散列法/除留余数法
- 除法散列法又被称之为除留余数法，顾名思义就是对数据进行除法处理，假设哈希表的大小为M,那么将Key除以M的余数作为映射位置的下标，也就是哈希函数：h(Key)=Key%M;
- 当我们使用除留余数法时，我们应该避免M为这些数：某些数的幂次方，比如2^x,10^x等。因为当我们的M等于2^x时，我们进行除法处理时，其余数是那个除数转换为2进制后的后x位数字比如{63，31}看起来没有关联的值，我们将其转换为2进制表示{00111111，00011111}，我们将M设为2^4,于是我们得到的余数即哈希值都是15（1111），这样就会导致哈希冲突。如果M是10^x的话就更加明显了，我们将M设置为10^2,给两个数据{95412，612}。我们最后的哈希值都是12，即它们的最后两个值。
- 因此我们在使用除留余数法时，应该将M取一个不太接近2的整数次幂的素数（质数）
- 注意一下，上面那条是我们的一个经验之谈，并非一定要这样取值，在java中的除留余数法，它的M取值就是一个2的整数次幂，但是它不是直接进行取模，而是进行位运算，这样对于一个数据的几乎所有二进制都参与了运算，这样一来可能重复的可能性就大大降低了，因此我们后面如果想要哈希冲突低一点，我们就要考虑能否将数据变得更加“独特"一点呢？
2.4.2 乘法散列法
- 乘法散列法对于哈希表的大小M并没有要求，它的大思路为：第一步用关键字K除上一个值A（0<A<1）,并抽取K*A的小数部分；第二步：用M与K*A的小数部分进行相乘，再向下取整；
- h(Key)=floor(M*((A*Key)%1.0))其中floor表示对表达式进行下取整，A∈(0,1)，这里最重要的是A的值应该如何设定，Knuth认为A = ( √5 − 1)/2 = 0.6180339887....（黄金分割点) 比较好.
- 乘法散列法对哈希表大小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。
2.4.3 全域散列法
- 如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集， 比如，让所有关键字全部落入同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
- 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 。
- 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插入是⼀个散列函数， 查找又是另⼀个散列函数，就会导致找不到插入的key了。
上面三种都是我们的哈希函数，除此之外还有平方取中法、折叠法、随机数法、数学分析法等，这些方法相对更适用于⼀些局限的特定场景，我们最常用的还是上面的第一种方法——除留余数法，后面两种方法我们了解即可。
2.5 哈希表确定位置的方法
哈希表中除了对于哈希冲突有针对方法，对于每一个值的位置确定也有好几种方法，接下来我来一一介绍一下：
2.5.1 直接定址法
顾名思义，这种定址法是直接确定地址位置的，这种方法适用于关键字的范围比较集中的情景，比如一组关键字都是在[1,99]这个范围内，我们就可以开辟一个大小为100的哈希表，这时候每一个关键字的值就是存储位置的下标。后面我们在做一些简单的哈希表的OJ题时，我们可能会将一些小写字母或者大小字母放到哈希表中，我们知道大小字母的个数都是26，因此我们可以直接创建一个26大小的哈希表，然后我们再将这些字符映射到哈希表中。
2.5.2 开放定址法
在上面的直接定址法，是将关键字与位置一对一的进行对应，这样是很容易造成哈希冲突的，为了解决哈希冲突，我们又设计了一种定址法——开放定址法。我们会将关键字全部放到哈希表中，当一个关键字用哈希函数计算出来的哈希值出现冲突时，我们就按照某种规则往后查找一个没有存储数据的位置进行存储，这些规则有：线性探测，二次探测，双重探测。
线性探测
- 从发生冲突的位置开始，依次线性往后探查，直到找到下一个没有存储数据的位置为止，如果探测到了哈希表尾，就绕到哈希表头再进行探测；
- h(key) = hash0 = key % M, hash0位置冲突了，则线性探测公式为：hc(key,i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M − 1}，因为负载因子小于1， 则最多探测M-1次，一定能找到一个存储key的位置；
- 线性探测的比较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1， hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位 置，这种现象叫做群集/堆积。下面的二次探测可以⼀定程度改善这个问题。
- 下面演示{19,30,5,36,13,20,21,12}这组数据映射到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(key) = hash0 = key % M，hash0位置冲突了，则二次探测的公式为：hc(key,i) = 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。
双重探测
- 第一个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出一个跟key相关的偏移量值，并不断往后探测，直到找寻到下一个没有存储数据的位置为止；
- h1 (key) = hash0 = key % M，hash0位置冲突了，则双重探测的公式为：hc(key,i) = hashi = (hash0 + i ∗ h2 (key)) % M，i = {1, 2, 3, ..., M}
- 要求h2 (key) < M h2 (key)和M互为质数，有两种简单的取值方法：1.当M为2的整数次幂时，h2（key）从 [0，M-1]任选⼀个奇数；2.当M为质数时，h2(key)=key%(M-1)+1
- 保证h2(key)与M互质是因为根据固定的偏移量所寻址的所有位置将会形成一个群，若最大公约数p=gcd(M,h1(key))>1,那么所能寻址的位置个数为M/P<M,使得对于一个关键字来说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表的大小为12，那么所能够寻址的位置为{1，4，7，10}，寻址个数为12/gcd(12,3)=4
- 下面演示{19,30,52,74}等这一组值映射到M=11的表中，设h2 (key) = key%10 + 1
2.5.3 链地址法
这种存储数据地址的方法和上面两种方法有所差异，上面两种方法都是直接将数据根据索引值放到对应的位置中，而链地址法中所有的数据不再直接存储在哈希表中了，它在哈希表中存储指针，如果没有数据映射这个位置的话，那么这个指针就是空，如果有多个数据映射那个位置的话，我们就把这些冲突的数据接成一个链表，挂在这个哈希表的下面，链地址法也叫做拉链法或者哈希桶。
下面演示 {19,30,5,36,13,20,21,12,24,96} 等这一组值映射到M=11的表中
三、哈希表的模拟实现
介绍了这么多，我们现在也知道了什么是哈希表，哈希表如何使用了。那么我们现在常识一下如何去模拟实现它呢？我们这里的寻址方法选择的是比较常用的开放定址法中的线性探测法来模拟实现。
3.1 哈希表的结构
我们在实现一个结构前，我们要先了解它的整体框架。我们上面说了这么多，说到底哈希表就是一个数组，进行一个封装实现。我们要设计一个哈希值类型（我们要对这个值中的关键字进行转换已经对其进行映射处理）
enum State
{
EMPTY,
EXIST,
DELETE
};
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};我们看上面的代码，我在定义一个哈希数据类的上面还写了一个枚举来存放一些状态。因为我们在进行线性探测的时候，我们逐个探测的依据就是这个位置上的状态，因此我们需要一个这样的属性来表示当前位置的状态。
另外我们在上面介绍概念的时候就提到过，我们映射之前会先将关键字转换为整数，这一实现我们通过一个仿函数来实现，而仿函数我们可以直接写模板类来进行封装即可。
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
class HashFunc<string>
{
public:
size_t operator()(const string& s)
{
size_t hash = 0;
for ( auto ch:s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};哈希表的模板类框架（我们定义两个变量：一个变量为一个vector，其数据类型就是我们上面定义的HashData；还有一个变量是表的大小_n.)
template<class K,class V,class Hash=HashFunc<K>>
class Hashtable
{
public:
private:
vector<HashData<K, V>> _table;
size_t _n=0;
};3.2 哈希表的构造
我们哈希表的构造函数需要我们自己来实现，编译器的默认构造函数无法满足我们的要求。对于哈希表的构造就是给哈希表开辟一定大小的初始空间。对于哈希表的表长的要求，我们在介绍概念的时候也着重说了，我们要给一个不太接近2的整数次幂的素数作为表长。那么这个素数应该给什么呢?这个就不用你考虑了，在stl源码中就给了我们一个素数表，其中放了好多素数，我们可以直接般过来作为我们的内联函数，我们可以从中挑选素数进行初始化，以及扩容。
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;
}有了上面这个素数表了，我们可以对我们的哈希表的大小进行一个初始化，我们可以直接调用vector的接口resize，提前开辟size的空间。
Hashtable()
{
_table.resize(__stl_next_prime(1));
}3.3 哈希表的查找
对于哈希表的查找，我们是直接使用线性探测进行寻找的，我们定义一个hash0和一个hash表示的是关键字映射到表上的位置，我们通过它们位置上的状态表示来进行判断，如果它们的状态表示是EXIST的话，我们就要检查一下那个位置上的关键字是不是我们给定的关键字。
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hash0 = hs(key) % _table.size();
size_t i = 1;
size_t hashi = hash0;
while (_table[hashi]._state!=EMPTY)
{
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
return &_table[hashi];
hashi = (hash0 + i) % _table.size();
++i;
}
return nullptr;
}3.4 哈希表的删除
对于哈希表的删除，实现起来十分容易。上面我们已经实现了哈希表的查找，我们有了这个函数的基础，我们可以通过这个函数来查找我们要删除的位置，如果找到了话，我们直接将这个位置上状态表示修改为DELETE，再将表长-1即可，这种虚拟删除的把戏其实我们当时学习栈的时候就已经使用过了，当时我们出栈的时候直接将栈中数据-1即可。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
--_n;
return true;
}
}3.5 哈希表的插入
最后我们再来介绍如何实现哈希表的插入，这个较之前两个接口的实现就麻烦一点了。我们在学习栈的插入时，我们不管是前插还是尾插，是不是都得先检查一下栈的空间是否足够，如果不够的话，我们还需要进行扩容操作。对于哈希表的插入，我们同样进行扩容操作，我们检查它的空间是否足够的标准是我们在之前概念中所介绍的负载因子，我们统一规定当负载因子的值大于0.7时，我们就需要进行扩容操作了。对于扩容，我们是这样做的：首先我们要定义一个新的表长（还是从我们之前的素数表中挑选一个素数）然后我们再定义一个新的哈希表，然后将旧表中的值放到新表中去。那么我们如何去实现呢？新表的大小一定是比旧表的大小大的，那么在旧表中会发生冲突的数据，可能在新表中就不会发生冲突了，因此我们不能简单地对应位置将值传递给新表。我们可以再定义一个哈希表newHT，然后调用它的成员变量_table，我们通过判断旧表中的每个位置上的状态表示（如果是EXIST）我们就插入到新的_table中去，最后我们再将新旧_table进行一个swap，交换后的新的_table由于是一个局部变量，出了作用域就销毁了。而旧的_table的空间大小也扩容了。扩容之后，我们就可以使用线性探测来找寻状态为EMPTY的位置来进行插入数据了。
bool Insert(const pair<K,V>& kv)
{
if (Find(kv))
return false;
//扩容
if ((double)_n/(double)_table.size()>=0.7)
{
size_t newSize = __stl_next_prime(_table.size() + 1);
Hashtable<K, V, Hash> newHT;
newHT._table.resize(newSize);
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
Hash hs;
size_t hash0 = hs(kv.first) % _table.size();
size_t i = 1;
size_t hashi = hash0;
while (_table[hashi]._state ==EXIST) //我们这个循环是为了找出空（EMPTY）位置进行插入的，因此EXIST进入循环中
{
//线性探测
hashi = (hash0 + i) % _table.size();
++i;
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}3.6 哈希表实现的完整源代码
enum State
{
EMPTY,
EXIST,
DELETE
};
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
class HashFunc<string>
{
public:
size_t operator()(const string& s)
{
size_t hash = 0;
for ( auto ch:s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};
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()
{
_table.resize(__stl_next_prime(1));
}
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hash0 = hs(key) % _table.size();
size_t i = 1;
size_t hashi = hash0;
while (_table[hashi]._state!=EMPTY)
{
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
return &_table[hashi];
hashi = (hash0 + i) % _table.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;
}
}
bool Insert(const pair<K,V>& kv)
{
if (Find(kv))
return false;
//扩容
if ((double)_n/(double)_table.size()>=0.7)
{
size_t newSize = __stl_next_prime(_table.size() + 1);
Hashtable<K, V, Hash> newHT;
newHT._table.resize(newSize);
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
Hash hs;
size_t hash0 = hs(kv.first) % _table.size();
size_t i = 1;
size_t hashi = hash0;
while (_table[hashi]._state ==EXIST) //我们这个循环是为了找出空（EMPTY）位置进行插入的，因此EXIST进入循环中
{
//线性探测
hashi = (hash0 + i) % _table.size();
++i;
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
private:
vector<HashData<K, V>> _table;
size_t _n=0;
};四、哈希桶的模拟实现
上面那种哈希表的定址法是开放定址法，数据直接存储在哈希表中，接下来我们模拟实现的哈希表是通过链地址法来进行寻址的，它是将数据链接在存储在哈希表中指针上。由于它就像一个桶，因此我们叫做它为哈希桶。
4.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)
{}
};
template<class K,class V>
class Hashtable
{
typedef HashNode<K, V> Node;
public:
private:
vector<Node*> _table;
size_t _n=0;
};4.2 哈希桶的构造
对于哈希桶的构造和我们哈希表的构造是一样的，我们都是对哈希表的表大小进行一个初始化。同样地，我们也是将stl源码中的一个素数表搬过来，我们从中挑选我们的表大小。
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()
{
_table.resize(__stl_next_prime(1), nullptr);
}4.3 哈希桶的析构
哈希桶的底层结构虽然是一个vector，但是编译器默认的析构函数却无法将其析构，因为vector的数据类型是结点指针类型，我们需要自己实现一个析构函数逐个释放结点空间。这里删除的逻辑就是我们对整个表的位置进行遍历，定义两个指针，一个指针表示当前位置的指针，另一个指针表示当前位置的下一个位置的指针（这个是用来提前保存它的指针值的，防止它被修改了）。我们delete当前位置的指针，并不断往后移，直至将所有结点释放掉。
~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;
}
}4.4 哈希桶的查找
这个查找操作和我们上面哈希表的查找操作如出一辙，这里我就不过多赘述了。直接上代码吧
Node* Find(const K& key)
{
size_t hashi = key % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}4.5 哈希桶的删除
哈希桶的删除相较于哈希表中的删除操作稍微麻烦一点，由于哈希桶中并没有状态表示这一属性，因此它无法通过修改状态来实现虚拟删除。在哈希桶中，数据就像链表中的结点那样挂在哈希表中，因此如果我们想要进行删除的话，就要像链表那样进行删除。我们在删除操作之前，我们先使用上面实现的Find接口来找出要删除数据的位置，然后使用链表中删除结点的操作进行即可。
bool Erase(const K& key)
{
size_t hashi = key % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}4.6 哈希桶的插入
我们在哈希表扩容的标准是负载因子>=0.7,而我们在哈希桶中，由于数据是像链表一样挂在哈希表中，因此不存在哈希冲突的问题。因此我们将负载因子等于1时（表长=表中数据个数），我们就进行扩容。扩容操作，我们不能够像哈希表中那样重新定义一个哈希表类，然后进行插入，我们直接定义一个新哈希桶，遍历旧的哈希表，然后使用链表插入的方式进行插入（我们这里模拟实现的使用的是头插）。其余的操作基本和哈希表的插入操作差不多，这里就不多赘述了。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if (_n == _table.size())
{
size_t newSize = __stl_next_prime(_table.size() + 1);
vector<Node*> newtable(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newSize;
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table, swap(newtable);
}
Node* newnode = new Node(kv);
size_t hashi = kv.first % _table.size();
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}4.7 哈希桶实现的完整源代码
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 Hashtable
{
typedef HashNode<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);
return pos == last ? *(last - 1) : *pos;
}
Hashtable()
{
_table.resize(__stl_next_prime(1), nullptr);
}
~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;
}
}
Node* Find(const K& key)
{
size_t hashi = key % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
size_t hashi = key % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if (_n == _table.size())
{
size_t newSize = __stl_next_prime(_table.size() + 1);
vector<Node*> newtable(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newSize;
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table, swap(newtable);
}
Node* newnode = new Node(kv);
size_t hashi = kv.first % _table.size();
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
private:
vector<Node*> _table;
size_t _n=0;
};