哈希表、哈希桶的实现
文章目录哈希概念哈希冲突哈希函数哈希冲突解决闭散列开散列哈希概念顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)O(N)O(N)，平衡树中查找的时间复杂度为树的高度O(logN)O(logN)O(logN)。而最理想的搜索方法是，可以不经过任何比较，一
文章目录
哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为 O ( N ) O(N) O(N)，平衡树中查找的时间复杂度为树的高度 O ( l o g N ) O(logN) O(logN)。
而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为 O ( 1 ) O(1) O(1)。
如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素。
向该结构当中插入和搜索元素的过程如下：
- 插入元素： 根据待插入元素的关键码，用此函数计算出该元素的存储位置，并将元素存放到此位置。
- 搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。
该方式即为哈希（散列）方法， 哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（散列表）。
例如，集合{1, 7, 6, 4, 5, 9}
哈希函数设置为： h a s h ( k e y ) = k e y % c a p a c i t y hash(key)=key\%capacity hash(key)=key%capacity，其中capacity为存储元素底层空间的总大小。
若我们将该集合存储在capacity为10的哈希表中，则各元素存储位置对应如下：
用该方法进行存储，在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素，而不必进行多次关键码的比较，因此搜索的速度比较快。
哈希冲突
不同关键字通过相同哈希函数计算出相同的哈希地址，这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。
例如，在上述例子中，再将元素11插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同，都是下标为1的位置
h a s h ( 11 ) = 11 % 10 = 1 hash(11)=11\%10=1 hash(11)=11%10=1。
哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
哈希函数设计的原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，且如果散列表允许有m个地址，其值域必须在0到m-1之间。
- 哈希函数计算出来的地址能均匀分布在整个空间中。
- 哈希函数应该比较简单。
常见的哈希函数如下：
一、直接定址法（常用）
取关键字的某个线性函数为哈希地址：
H
a
s
h
(
K
e
y
)
=
A
∗
K
e
y
+
B
Hash(Key)=A*Key+B
Hash(Key)=A∗Key+B。
优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。
缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。
使用场景：适用于整数，且数据范围比较集中的情况。
二、除留余数法（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：
H
a
s
h
(
K
e
y
)
=
K
e
y
%
p
(
p
<
=
m
)
Hash(Key)=Key\%p(p<=m)
Hash(Key)=Key%p(p<=m)，将关键码转换成哈希地址。
优点：使用场景广泛，不受限制。
缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。
三、平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。
使用场景：不知道关键字的分布，而位数又不是很大的情况。
四、折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
使用场景：折叠法适合事先不需要知道关键字的分布，或关键字位数比较多的情况。
五、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H
a
s
h
(
K
e
y
)
=
r
a
n
d
o
m
(
K
e
y
)
Hash(Key)=random(Key)
Hash(Key)=random(Key)，其中random为随机数函数。
使用场景：通常应用于关键字长度不等时。
六、数字分析法
设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。
例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。
如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。
数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突。
哈希冲突解决
解决哈希冲突有两种常见的方法：闭散列和开散列。
闭散列 —— 开放定址法
闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去。
寻找“下一个位置”的方式多种多样，常见的方式有以下两种：
一、线性探测
当发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。
H i = ( H 0 + i ) % m Hi=(H0+i)\%m Hi=(H0+i)%m ( i = 1 , 2 , 3 , . . . ) (i=1,2,3,...) (i=1,2,3,...)
H
0
H0
H0：通过哈希函数对元素的关键码进行计算得到的位置。
H
i
Hi
Hi：冲突元素通过线性探测后得到的存放位置。
m
m
m：表的大小。
例如，我们用除留余数法将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：
通过上图可以看到，随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在40进行插入的时候更是连续出现了四次哈希冲突。
我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子（载荷因子）：
负载因子 = 表中有效数据个数 / 空间的大小
- 负载因子越大，产出冲突的概率越高，增删查改的效率越低。
- 负载因子越小，产出冲突的概率越低，增删查改的效率越高。
例如，我们将哈希表的大小改为20，可以看到在插入相同序列时，产生的哈希冲突会有所减少：
但负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。
线性探测的优点：实现非常简单。
线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据“堆积”，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应），导致搜索效率降低。
二、二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
H i = ( H 0 + i 2 ) % m Hi=(H0+i^2)\%m Hi=(H0+i2)%m ( i = 1 , 2 , 3 , . . . ) (i=1,2,3,...) (i=1,2,3,...)
H
0
H0
H0：通过哈希函数对元素的关键码进行计算得到的位置。
H
i
Hi
Hi：冲突元素通过二次探测后得到的存放位置。
m
m
m：表的大小。
例如，我们用除留余数法将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的二次探测找到下一个空位置进行插入，插入过程如下：
采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。
和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为20的哈希表，产生冲突的次数也会有所减少：
因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
开散列 —— 链地址法（拉链法、哈希桶）
开散列，又叫链地址法（拉链法），首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
例如，我们用除留余数法将序列{1, 6, 15, 60, 88, 7, 40, 5, 10}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：
闭散列解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而开散列解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以‘挂’在这个位置下面”。
与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。
- 闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]之间。
- 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间。
在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：
- 哈希桶的负载因子可以更大，空间利用率高。
- 哈希桶在极端情况下还有可用的解决方案。
哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了
O
(
N
)
O(N)
O(N)：
这时，我们可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中。
在这种情况下，就算有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找30次左右，这就是所谓的“桶里种树”。
为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构，比如在JAVA中比较新一点的版本中，当桶当中的数据个数超过8时，就会将该桶当中的单链表结构换成红黑树结构，而当该桶当中的数据个数减少到8或8以下时，又会将该桶当中的红黑树结构换回单链表结构。
但有些地方也会选择不做此处理，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。
哈希表的闭散列实现
哈希表的结构
在闭散列的哈希表中，哈希表每个位置除了存储所给数据之外，还应该存储该位置当前的状态，哈希表中每个位置的可能状态如下：
- EMPTY（无数据的空位置）。
- EXIST（已存储数据）。
- DELETE（原本有数据，但现在被删除了）。
我们可以用枚举定义这三个状态。
//枚举：标识每个位置的状态
enum State
{
EMPTY,
EXIST,
DELETE
};
为什么需要标识哈希表中每个位置的状态？
若是不设置哈希表中每个位置的状态，那么在哈希表中查找数据的时候可能是这样的。以除留余数法的线性探测为例，我们若是要判断下面这个哈希表是否存在元素40，步骤如下：
- 通过除留余数法求得元素40在该哈希表中的哈希地址是0。
- 从0下标开始向后进行查找，若找到了40则说明存在。
但是我们在寻找元素40时，不可能从0下标开始将整个哈希表全部遍历一次，这样就失去了哈希的意义。我们只需要从0下标开始往后查找，直到找到元素40判定为存在，或是找到一个空位置判定为不存在即可。
因为线性探测在为冲突元素寻找下一个位置时是依次往后寻找的，既然我们已经找到了一个空位置，那就说明这个空位置的后面不会再有从下标0位置开始冲突的元素了。比如我们要判断该哈希表中是否存在元素90，步骤如下：
- 通过除留余数法求得元素90在该哈希表中的哈希地址是0。
- 从0下标开始向后进行查找，直到找到下标为5的空位置，停止查找，判定元素90不存在。
但这种方式是不可行的，原因如下：
- 如何标识一个空位置？用数字0吗？那如果我们要存储的元素就是0怎么办？因此我们必须要单独给每个位置设置一个状态字段。
- 如果只给哈希表中的每个位置设置存在和不存在两种状态，那么当遇到下面这种情况时就会出现错误。
我们先将上述哈希表当中的元素1000找到，并将其删除，此时我们要判断当前哈希表当中是否存在元素40，当我们从0下标开始往后找到2下标（空位置）时，我们就应该停下来，此时并没有找到元素40，但是元素40却在哈希表中存在。
因此我们必须为哈希表中的每一个位置设置一个状态，并且每个位置的状态应该有三种可能，当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为DELETE。
这样一来，当我们在哈希表中查找元素的过程中，若当前位置的元素与待查找的元素不匹配，但是当前位置的状态是EXIST或是DELETE，那么我们都应该继续往后进行查找，而当我们插入元素的时候，可以将元素插入到状态为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>> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
};
哈希表的插入
向哈希表中插入数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
- 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
- 将键值对插入哈希表。
- 哈希表中的有效元素个数加一。
其中，哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10。
- 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
注意： 在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入。
将键值对插入哈希表的具体步骤如下：
- 通过哈希函数计算出对应的哈希地址。
- 若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
- 将键值对插入到该位置，并将该位置的状态设置为EXIST。
注意： 产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满。
//插入函数
bool Insert(const pair<K, V>& kv)
{
//1、查看哈希表中是否存在该键值的键值对
HashData<K, V>* ret = Find(kv.first);
if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
{
return false; //插入失败
}
//2、判断是否需要调整哈希表的大小
if (_table.size() == 0) //哈希表大小为0
{
_table.resize(10); //设置哈希表初始空间大小
}
else if ((double)_n / (double)_table.size() > 0.7) //负载因子大于0.7需要增容
{
//增容
//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍
HashTable<K, V> newHT;
newHT._table.resize(2 * _table.size());
//b、将原哈希表当中的数据插入到新哈希表
for (auto& e : _table)
{
if (e._state == EXIST)
{
newHT.Insert(e._kv);
}
}
//c、交换这两个哈希表
_table.swap(newHT._table);
}
//3、将键值对插入哈希表
//a、通过哈希函数计算哈希地址
size_t start = kv.first%_table.size(); //除数不能是capacity
size_t index = start;
size_t i = 1;
int base = index;
//b、找到一个状态为EMPTY或DELETE的位置
while (_table[index]._state == EXIST)
{
index = start + i; //线性探测
//index = start + i*i; //二次探测
index %= _table.size(); //防止下标超出哈希表范围
i++;
}
//c、将数据插入该位置，并将该位置的状态设置为EXIST
_table[index]._kv = kv;
_table[index]._state = EXIST;
//4、哈希表中的有效元素个数加一
_n++;
return true;
}
哈希表的查找
在哈希表中查找数据的步骤如下：
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 从哈希地址处开始，采用线性探测向后向后进行数据的查找，直到找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
注意： 在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。
//查找函数
HashData<K, V>* Find(const K& key)
{
if (_table.size() == 0) //哈希表大小为0，查找失败
{
return nullptr;
}
size_t start = key % _table.size(); //通过哈希函数计算哈希地址（除数不能是capacity）
size_t index = start;
size_t i = 1;
//直到找到空位置为止
while (_table[index]._state != EMPTY)
{
//若该位置的状态为EXIST，并且key值匹配，则查找成功
if (_table[index]._state == EXIST&&_table[index]._kv.first == key)
{
return &_table[index];
}
index = start + i; //线性探测
//index = start + i*i; //二次探测
index %= _table.size(); //防止下标超出哈希表范围
i++;
}
return nullptr; //直到找到空位置还没有找到目标元素，查找失败
}
哈希表的删除
删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。
在哈希表中删除数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若不存在则删除失败。
- 若存在，则将该键值对所在位置的状态改为DELETE即可。
- 哈希表中的有效元素个数减一。
注意： 虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。
//删除函数
bool Erase(const K& key)
{
//1、查看哈希表中是否存在该键值的键值对
HashData<K, V>* ret = Find(key);
if (ret)
{
//2、若存在，则将该键值对所在位置的状态改为DELETE即可
ret->_state = DELETE;
//3、哈希表中的有效元素个数减一
_n--;
return true;
}
return false;
}
哈希表的开散列实现（哈希桶）
哈希表的结构
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
//每个哈希桶中存储数据的结构
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)
{}
};
为了让代码看起来更加清晰，在实现哈希表时，我们最好将结点的类型进行typedef。
typedef HashNode<K, V> Node;
与闭散列的哈希表不同的是，在实现开散列的哈希表时，我们不用为哈希表中的每个位置设置一个状态字段，因为在开散列的哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。
哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
//哈希表
template<class K, class V>
class HashTable
{
public:
//...
private:
vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
};
哈希表的插入
向哈希表中插入数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
- 判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
- 将键值对插入哈希表。
- 哈希表中的有效元素个数加一。
其中，哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10。
- 若哈希表的负载因子已经等于1了，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
重点： 在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。
实际上，我们只需要遍历原哈希表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，不用进行结点的创建与释放。
说明一下： 下面代码中为了降低时间复杂度，在增容时取结点都是从单链表的表头开始向后依次取的，在插入结点时也是直接将结点头插到对应单链表，作图时不方便头取头插，于是图中都是尾取尾插。
将键值对插入哈希表的具体步骤如下：
- 通过哈希函数计算出对应的哈希地址。
- 若产生哈希冲突，则直接将该结点头插到对应单链表即可。
//插入函数
bool Insert(const pair<K, V>& kv)
{
//1、查看哈希表中是否存在该键值的键值对
Node* ret = Find(kv.first);
if (ret) //哈希表中已经存在该键值的键值对（不允许数据冗余）
{
return false; //插入失败
}
//2、判断是否需要调整哈希表的大小
if (_n == _table.size()) //哈希表的大小为0，或负载因子超过1
{
//增容
//a、创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍（若哈希表大小为0，则将哈希表的初始大小设置为10）
vector<Node*> newtable;
size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
newtable.resize(newsize);
//newtable.resize(GetNextPrime(_table.size()));
//b、将原哈希表当中的结点插入到新哈希表
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i]) //桶不为空
{
Node* cur = _table[i];
while (cur) //将该桶的结点取完为止
{
Node* next = cur->_next; //记录cur的下一个结点
size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
//将该结点头插到新哈希表中编号为index的哈希桶中
cur->_next = newtable[index];
newtable[index] = cur;
cur = next; //取原哈希表中该桶的下一个结点
}
_table[i] = nullptr; //该桶取完后将该桶置空
}
}
//c、交换这两个哈希表
_table.swap(newtable);
}
//3、将键值对插入哈希表
size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点
//将该结点头插到新哈希表中编号为index的哈希桶中
newnode->_next = _table[index];
_table[index] = newnode;
//4、哈希表中的有效元素个数加一
_n++;
return true;
}
哈希表的查找
在哈希表中查找数据的步骤如下：
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。
//查找函数
HashNode<K, V>* Find(const K& key)
{
if (_table.size() == 0) //哈希表大小为0，查找失败
{
return nullptr;
}
size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
//遍历编号为index的哈希桶
HashNode<K, V>* cur = _table[index];
while (cur) //直到将该桶遍历完为止
{
if (cur->_kv.first == key) //key值匹配，则查找成功
{
return cur;
}
cur = cur->_next;
}
return nullptr; //直到该桶全部遍历完毕还没有找到目标元素，查找失败
}
哈希表的删除
在哈希表中删除数据的步骤如下：
- 通过哈希函数计算出对应的哈希桶编号。
- 遍历对应的哈希桶，寻找待删除结点。
- 若找到了待删除结点，则将该结点从单链表中移除并释放。
- 删除结点后，将哈希表中的有效元素个数减一。
注意： 不要先调用查找函数判断待删除结点是否存在，这样做如果待删除不在哈希表中那还好，但如果待删除结点在哈希表，那我们还需要重新在哈希表中找到该结点并删除，还不如一开始就直接在哈希表中找，找到了就删除。
//删除函数
bool Erase(const K& key)
{
//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）
size_t index = key % _table.size();
//2、在编号为index的哈希桶中寻找待删除结点
Node* prev = nullptr;
Node* cur = _table[index];
while (cur) //直到将该桶遍历完为止
{
if (cur->_kv.first == key) //key值匹配，则查找成功
{
//3、若找到了待删除结点，则删除该结点
if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
{
_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
}
else //待删除结点不是哈希桶的第一个结点
{
prev->_next = cur->_next; //将该结点从哈希桶中移除
}
delete cur; //释放该结点
//4、删除结点后，将哈希表中的有效元素个数减一
_n--;
return true; //删除成功
}
prev = cur;
cur = cur->_next;
}
return false; //直到该桶全部遍历完毕还没有找到待删除元素，删除失败
}
哈希表的大小为什么建议是素数
都说使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数。
下面用合数（非素数）10和素数11来进行说明。
- 合数10的因子有：1，2，5，10。
- 素数11的因子有：1，11。
我们选取下面这五个序列：
- 间隔为1的序列：s1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
- 间隔为2的序列：s2 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
- 间隔为5的序列：s3 = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}
- 间隔为10的序列：s4 = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
- 间隔为11的序列：s5 = {11, 22, 33, 44, 55, 66, 77, 88, 99, 110}
实验一：将s1插入表长为10的哈希表，即模10：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
实验二：将s1插入表长为11的哈希表，即模11：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
实验三：将s2插入表长为10的哈希表，即模10：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 2 | 4 | 6 | 8 | ||||||
| 20 | 12 | 14 | 16 | 18 |
实验四：将s2插入表长为11的哈希表，即模11：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 12 | 2 | 14 | 4 | 16 | 6 | 18 | 8 | 20 | 10 |
实验五：将s3插入表长为10的哈希表，即模10：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 5 | |||||||||
| 20 | 15 | |||||||||
| 30 | 25 | |||||||||
| 40 | 35 | |||||||||
| 50 | 45 |
实验六：将s3插入表长为11的哈希表，即模11：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 45 | 35 | 25 | 15 | 5 | 50 | 40 | 30 | 20 | 10 |
实验七：将s4插入表长为10的哈希表，即模10：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | ||||||||||
| 20 | ||||||||||
| 30 | ||||||||||
| 40 | ||||||||||
| 50 | ||||||||||
| 60 | ||||||||||
| 70 | ||||||||||
| 80 | ||||||||||
| 90 | ||||||||||
| 100 |
实验八：将s4插入表长为11的哈希表，即模11：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 100 | 90 | 80 | 70 | 60 | 50 | 40 | 30 | 20 | 10 |
实验九：将s5插入表长为10的哈希表，即模10：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 110 | 11 | 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 |
实验十：将s5插入表长为11的哈希表，即模11：
| 哈希表 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 11 | |||||||||||
| 22 | |||||||||||
| 33 | |||||||||||
| 44 | |||||||||||
| 55 | |||||||||||
| 66 | |||||||||||
| 77 | |||||||||||
| 88 | |||||||||||
| 99 | |||||||||||
| 110 |
根据上述实验，我们可以得出以下结论：
- 如果一个序列中，每个元素之间的间隔为1，那么不管哈希表的大小为几，该序列插入哈希表后都是均匀分布的（实验一、实验二）。
- 如果一个序列中，每个元素之间的间隔刚好是哈希表大小或哈希表的倍数，那么该序列插入哈希表时，将全部产生冲突（实验七、实验十）。
- 哈希表中的分布按照序列的间隔进行分隔，如果序列的间隔恰好是哈希表大小的因子，那么哈希表的分布就会产生间隔（实验三、实验五、），反之则不会（实验三、实验四、实验五、实验六、实验八、实验九）。
某个随机序列当中，每个元素之间的间隔是不定的。因此，为了尽量减少冲突，我们就需要让哈希表的大小的因子最少，这样才能最大可能避免让某两个元素之间的间隔是哈希表的因子，所以哈希表的大小最好是素数。
如何实现？
我们如果每次增容时让哈希表的大小增大两倍，那么增容后哈希表的大小就不是素数了。因此我们可以将需要用到的素数序列提前用一个数组存储起来，当我们需要增容时就从该数组当中进行获取就行了。
例如，下面这些都是素数，且它们近似以2倍的形式进行增长，我们就可以将它们用一个数组存储起来。
//素数序列
const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
当我们需要增容时，就在该素数数组中找到下一个素数作为哈希表增容后的大小即可。
//获取本次增容后哈希表的大小
size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
size_t i = 0;
for (i = 0; i < PRIMECOUNT; i++)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
40
0- 0
已为社区贡献74条内容
所有评论(0)