- 1在github上如何下载某个子文件夹_github 怎么下载子目录
- 2CentOS7(Linux)详细安装教程（手把手图文详解版）_centos7安装教程_linux centos 7
- 3数据库概念结构设计-设计步骤、设计方法、集成中去除冲突和冗余_数据库结构化设计步骤
- 4计算机网络【UDP和TCP首部字段详解】_数据包中什么字段指名这是一个udp
- 5【大数据技术原理与应用（概念、存储、处理、分析与应用）】第1章-大数据概述习题与知识点回顾_大数据技术原理与应用--概念、存储、处理、分析与应用
- 6AI降重技术：chatgpt降重工具在学术写作中的创新应用
- 7IKEv1报文交互简析_ike中prf
- 8井字棋(C语言实现,可运行玩耍,自行编写)_井字棋c语言代码
- 9模型资源导入Unity 3D中注意的问题_模之屋下载的动作怎么导入unity
- 10tkinter入门（9）--布局管理器（pack,grid,place）_tk pack 两个组件并排
C++进阶--哈希表的的闭散列和开散列（哈希桶）实现_开散列 c++
赞
踩
哈希表的的闭散列和开散列（哈希桶）实现
一、哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O(N)，平衡树中查找的时间复杂度为树的高度O(
l
o
g
2
N
log_2 N
log2N)。
而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到搜索的元素，即查找的时间复杂度为O(1)。
如果构造一种存储结构，通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一 一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
- 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放 - 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（Hash Table）（或者称散列表）
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash（key）=key%capacity；capacity为存储元素底层空间总的大小。
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
二、哈希冲突
对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i != j)，有 k i k_i ki != k j k_j kj，但有：Hash( k i k_i ki) ==Hash( k j k_j kj)，即不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
三、哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理
哈希函数设计原则
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
3.1 直接定址法–（常用）
取关键字的某个线性函数为散列地址：Hash（Key）=A*Key+B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
3.2 除留余数法–（常用）
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash（key）=key%p（p<=m），将关键码转换成哈希地址。
3.3 平方取中法–（了解）
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
3.4 折叠法–（了解）
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
3.5 随机数法–（了解）
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法
3.6 数学分析法–（了解）
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
四、哈希冲突解决
解决哈希冲突两种常见的方法是：闭散列和开散列
4.1 闭散列——开放定址法
闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的”下一个“空位置中去。
4.1.1 线性探测
当发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止。
Hi=(H0+i)%m (i=1,2,3,…)
H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过线性探测后得到的存放位置。
m：表的大小。
例如：我们用除留余数法将序列插入列表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入。
随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在1002进行插入的时候更是连续出现了四次哈希冲突。
我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。介于此，哈希表当中引入了负载因子（载荷因子）：
负载因子=表中有效数据个数/空间的大小
- 负载因子越大，产生冲突的概率越高，增删改查的效率越低。
- 负载因此越小，产生冲突的概率越低，增删改查的效率越高。
例如，我们将哈希表的大小改为20，可以看到在插入相同序列时，产生的哈希冲突会有所减少：
但负载因此越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。
线性探测的优点：实现非常简单。
线性探测的缺点：一旦发生冲突，所有的冲突连在一起，容易产生数据”堆积“，即不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要多次比较（踩踏效应），导致搜索效率降低。
4.1.2 二次探测
线性探测的缺陷是产生冲突的数据堆积在一起，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
Hi=(H0+i^2)%m (i=1,2,3,…)
H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过二次探测后得到的存放位置
m：表的大小
例如：我们用除留余数法将序列插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的二次探测找到下一个空位置进行插入。
采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。
和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为20的哈希表，产生冲突的次数也会有所减少，因此，闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
4.2 开散列——链地址法（拉链法、哈希桶）
开散列，又叫链地址法（拉链法），首先对关键码集合用哈希函数计算哈希地址，具有相同地址的关键码归于同一个集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
例如，我们用除留余数法将序列插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下。
闭散列解决哈希冲突，采用的是一种报复的方式，”我的位置被占用了我就去占用其他位置“。而开散列解决哈希冲突，采用的是一种乐观的方式，”虽然我的位置被占用了，但是没关系，我可以”挂“在这个位置下面。
与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删改查的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。
- 闭散列的开放定址法，负载因此不能超过1，一般建议控制在[0.0,0.7]之间。
- 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0,1.0]之间
在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：
1.哈希桶的负载因子可以更大，空间利用率高。
2.哈希桶在极端情况下还有可用的解决方案。
哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O(N)
五、哈希表的闭散列实现
5.1 哈希表的结构
在闭散列的哈希表中，哈希表每个位置除了存储所给数据之外，还应该存储该位置当前的状态，哈希表中每个位置的可能状态：
- EMPTY（无数据的空位置）
- EXIST（已存储数据）
- DELETE（原本有数据，但现在被删除了）
我们可以用枚举定义这三个状态
enum State
{
EMPTY,
EXIST,
DELETE
};
- 1
- 2
- 3
- 4
- 5
- 6
哈希表每个位置存储的结构
template <class K, class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
哈希表
template<class K, class V>
class HashTable
{
public:
//...
private:
vector<HashData<K, V>> _tables;
size_t _n = 0; //存储的数据个数
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
5.2 哈希表的插入
向哈希表中插入数据的步骤如下：
1.查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
2.判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
3.将键值对插入哈希表。
4.哈希表中的有效元素个数加一。
其中，哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10。
- 若哈希表的负载因子大于0.7，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
注意：在将原哈希表的数据插入到新哈希表的过程中，不能只是简单的将原哈希表中的数据对应的挪到新哈希表中，而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置，然后再进行插入。
将键值对插入哈希表的具体步骤如下：
1.通过哈希函数计算出对应的哈希地址。
2.若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。
3.将键值对插入到该位置，并将该位置的状态设置为EXIST。
注意：产生哈希冲突向后进行探测时，一定会找到一个合适位置进行插入，因为哈希表的负载因子是控制在0.7以下的，也就是说哈希表永远都不会被装满。
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; //负载因子超过0.7就扩容 //if((double)_n/(double)_tables.size()>=0.7) //if (_tables.size()==0 || _n * 10 / _tables.size() >= 7) //{ // 1、表为空，扩不上去 // 2、光扩容无法访问，size没变 // //_tables.reserve(_tables.capacity() * 2); //不能这么做 // size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2; // //_tables.resize(newsize); //有问题 // vector<HashData> newtables(newsize); // //遍历旧表，重新映射到新表 // for (auto& data : _tables) // { // if (data._state==EXIST) // { // //重新算在新表的位置 // size_t i = 1; // size_t index = hashi; // while (newtables[hashi]._state == EXIST) // { // index = hashi + i; // index %= newtables.size(); // ++i; // } // newtables[index]._kv = data._kv; // newtables[index]._state = EXIST; // } // } // _tables.swap(newtables); if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7) { size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V> newht; newht._tables.resize(newsize); //遍历旧表，重新映射到新表 for (auto& data : _tables) { if (data._state == EXIST) { newht.Insert(data._kv); } } _tables.swap(newht._tables); } size_t hashi = kv.first % _tables.size(); //线性探测 size_t i = 1; size_t index = hashi; while (_tables[index]._state == EXIST) { index = hashi + i; index %= _tables.size(); ++i; } _tables[index]._kv = kv; _tables[index]._state = EXIST; _n++; return true; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
5.3 哈希表的查找
在哈希表中查找数据的步骤如下：
1.先判断哈希表的大小是否为0，若为0则查找失败。
2.通过哈希函数计算出对应的哈希地址。
3.从哈希地址处开始，采用线性探测向后进行数据的查找，直接找到待查找的元素判定为查找成功，或找到一个状态为EMPTY的位置判定为查找失败。
注意：在查找过程中，必须找到位置状态为EXIST，并且key值匹配的元素，才算查找成功。若仅仅是key值匹配，但该位置当前状态为DELETE，则还需继续进行查找，因为该位置的元素已经被删除了。
HashData<K, V>* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } size_t hashi = key % _tables.size(); //线性探测 size_t i = 1; size_t index = hashi; while (_tables[index]._state != EMPTY) { if (_tables[index]._state == EXIST && _tables[index]._kv.first == key) { return &_tables[index]; } index = hashi + i; index %= _tables.size(); ++i; //如果已经查找一圈，那么说明全是存在+删除 if (index == hashi) { break; } } return nullptr; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
5.4 哈希表的删除
删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。
在哈希表中删除数据的步骤如下：
1.查看哈希表中是否存在该键值的键值对，若不存在则删除失败
2.若存在，则将该键值对所在位置的状态改为DELETE即可。
3.哈希表中的有效元素个数减一。
注意：虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
else
{
return false;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
六、哈希表的开散列实现（哈希桶）
6.1 哈希表的结构
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
template<class K,class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V>& kv)
:_next(nullptr)
,_kv(kv)
{}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
与闭散列的哈希表不同的是，在实现开散列的哈希表时，我们不用为哈希表中的每个位置设置一个状态字段，因为在开散列哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。
哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
template<class K,class V,class Hash=HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
//...
private:
vector<Node*> _tables; //指针数组
size_t _n=0; //存储有效数据个数
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
6.2 哈希表的插入
向哈希表中插入数据的步骤如下：
1.查看哈希表中是否存在该键值的键值对，若已存在则插入失败。
2.判断是否需要调整哈希表的大小，若哈希表的大小为0，或负载因子过大都需要对哈希表的大小进行调整。
3.将键值对插入哈希表。
4.哈希表中的有效元素个数加一。
其中，哈希表的调整方式如下：
- 若哈希表的大小为0，则将哈希表的初始大小设置为10.
- 若哈希表的负载因子已经等于1了，则先创建一个新的哈希表，该哈希表大大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
重点：在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要建立相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。
实际上，我们只需要遍历原哈希表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，不用进行结点的创建与释放。
说明：为了降低时间复杂度，在增容时取结点都是从单链表的表头开始向后依次取的，在插入结点时也是直接将结点头插到对应单链表。
将键值对插入哈希表的具体步骤如下：
1.通过哈希函数计算出对应的哈希地址。
2.若产生哈希冲突，则直接将该结点头插到对应单链表即可。
bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hash; //负载因子==1时扩容 if (_n == _tables.size()) { /*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V> newht; newht.resize(newsize); for (auto cur : _tables) { while (cur) { newht.Insert(cur->_kv); cur = cur->_next; } } _tables.swap(newht._tables);*/ size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newtables(newsize, nullptr); //for(Node*& cur:_tables) for (auto& cur : _tables) { /*for (size_t i=0;i<_tables.size();++i) { Node*& cur = _tables[i];*/ while (cur) { Node* next = cur->_next; size_t hashi = hash(cur->_kv.first) % newtables.size(); //头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } } _tables.swap(newtables); } size_t hashi = hash(kv.first) % _tables.size(); //头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
6.3 哈希表的查找
在哈希表中查找数据的步骤如下：
1.先判断哈希表的大小是否为0，若为0则查找失败。
2.通过哈希函数计算出对应的哈希地址。
3.通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。
Node* Find(const K& key) { if (_tables.size() == 0) return nullptr; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
6.4 哈希表的删除
在哈希表中删除数据的步骤如下：
1.通过哈希函数计算出对应的哈希桶编号。
2.遍历对应的哈希桶，存照待删除结点。
3.若找到了待删除结点，则将该结点从单链表中移除并释放。
4.删除结点后，将哈希表中的有效元素个数减一。
注意：不要先调用查找函数判断待删除结点是否存在，这样做如果待删除不在哈希表中那还好，但如果待删除结点在哈希表，那我们需要重新在哈希表中找到该结点并删除，还不如一开始就直接在哈希表中找，找到了就删除。
bool Erase(const K& key) { Hash hash; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
七、哈希表的大小为什么建议是素数
使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数。
八、完整代码
8.1 HashTable.h
#pragma once #include <vector> namespace OpenAddress { enum State { EMPTY, EXIST, DELETE }; template <class K, class V> struct HashData { pair<K, V> _kv; State _state = EMPTY; }; template<class K, class V> class HashTable { public: bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; //负载因子超过0.7就扩容 //if((double)_n/(double)_tables.size()>=0.7) //if (_tables.size()==0 || _n * 10 / _tables.size() >= 7) //{ // 1、表为空，扩不上去 // 2、光扩容无法访问，size没变 // //_tables.reserve(_tables.capacity() * 2); //不能这么做 // size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2; // //_tables.resize(newsize); //有问题 // vector<HashData> newtables(newsize); // //遍历旧表，重新映射到新表 // for (auto& data : _tables) // { // if (data._state==EXIST) // { // //重新算在新表的位置 // size_t i = 1; // size_t index = hashi; // while (newtables[hashi]._state == EXIST) // { // index = hashi + i; // index %= newtables.size(); // ++i; // } // newtables[index]._kv = data._kv; // newtables[index]._state = EXIST; // } // } // _tables.swap(newtables); if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7) { size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V> newht; newht._tables.resize(newsize); //遍历旧表，重新映射到新表 for (auto& data : _tables) { if (data._state == EXIST) { newht.Insert(data._kv); } } _tables.swap(newht._tables); } size_t hashi = kv.first % _tables.size(); //线性探测 size_t i = 1; size_t index = hashi; while (_tables[index]._state == EXIST) { index = hashi + i; index %= _tables.size(); ++i; } _tables[index]._kv = kv; _tables[index]._state = EXIST; _n++; return true; } HashData<K, V>* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } size_t hashi = key % _tables.size(); //线性探测 size_t i = 1; size_t index = hashi; while (_tables[index]._state != EMPTY) { if (_tables[index]._state == EXIST && _tables[index]._kv.first == key) { return &_tables[index]; } index = hashi + i; index %= _tables.size(); ++i; //如果已经查找一圈，那么说明全是存在+删除 if (index == hashi) { break; } } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_state = DELETE; --_n; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; size_t _n = 0; //存储的数据个数 /*HashData* tables; size_t size; size_t _capacity;*/ }; void TestHashTable1() { int a[] = { 3,33,2,13,5,12,1002 }; HashTable<int, int> ht; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Insert(make_pair(15, 15)); if (ht.Find(13)) { cout << "13在" << endl; } else { cout << "13不在" << endl; } ht.Erase(13); if (ht.Find(13)) { cout << "13在" << endl; } else { cout << "13不在" << endl; } } } namespace HashBucket { template<class K,class V> struct HashNode { HashNode<K, V>* _next; pair<K, V> _kv; HashNode(const pair<K,V>& kv) :_next(nullptr) ,_kv(kv) {} }; template<class K> struct HashFunc { size_t operator()(const K& key) { return key; } }; //特化 template<> struct HashFunc<string> { //BKDR size_t operator()(const string & s) { //return s[0]; size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 31; } return hash; } }; template<class K,class V,class Hash=HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: ~HashTable() { for (auto& cur : _tables) { while (cur) { Node* next = cur->_next; delete cur; cur = next; } cur = nullptr; } } Node* Find(const K& key) { if (_tables.size() == 0) return nullptr; Hash hash; size_t hashi = hash(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 hash; size_t hashi = hash(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; 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; } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hash; //负载因子==1时扩容 if (_n == _tables.size()) { /*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; HashTable<K, V> newht; newht.resize(newsize); for (auto cur : _tables) { while (cur) { newht.Insert(cur->_kv); cur = cur->_next; } } _tables.swap(newht._tables);*/ size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newtables(newsize, nullptr); //for(Node*& cur:_tables) for (auto& cur : _tables) { /*for (size_t i=0;i<_tables.size();++i) { Node*& cur = _tables[i];*/ while (cur) { Node* next = cur->_next; size_t hashi = hash(cur->_kv.first) % newtables.size(); //头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } } _tables.swap(newtables); } size_t hashi = hash(kv.first) % _tables.size(); //头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } size_t MaxBucketSize() { size_t max = 0; for (size_t i=0;i<_tables.size();++i) { auto cur = _tables[i]; size_t size = 0; while (cur) { ++size; cur = cur->_next; } printf("[%d]->%d\n", i,size); if (size > max) { max = size; } } return max; } private: vector<Node*> _tables; //指针数组 size_t _n=0; //存储有效数据个数 }; void TestHashTable1() { int a[] = { 3,33,2,13,5,12,1002 }; HashTable<int, int> ht; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Insert(make_pair(15, 15)); ht.Insert(make_pair(25, 25)); ht.Insert(make_pair(35, 35)); ht.Insert(make_pair(45, 45)); } void TestHashTable2() { int a[] = { 3,33,2,13,5,12,1002 }; HashTable<int, int> ht; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Erase(12); ht.Erase(3); ht.Erase(33); } struct HashStr { //BKDR size_t operator()(const string& s) { //return s[0]; size_t hash = 0; for (auto ch : s) { hash += ch; hash *= 31; } return hash; } }; void TestHashTable3() { //HashTable<string, string, HashStr> ht; HashTable<string, string> ht; ht.Insert(make_pair("sort", "排序")); ht.Insert(make_pair("string", "字符串")); ht.Insert(make_pair("left", "左边")); ht.Insert(make_pair("right", "右边")); ht.Insert(make_pair("", "右边")); HashStr hashstr; cout << hashstr("abcd") << endl; cout << hashstr("bcda") << endl; cout << hashstr("aadd") << endl; cout << hashstr("eat") << endl; cout << hashstr("ate") << endl; } void TestHashTable4() { size_t N = 10000; HashTable<int, int> ht; srand(time(0)); for (size_t i = 0; i < N; ++i) { size_t x = rand(); ht.Insert(make_pair(x, x)); } cout << ht.MaxBucketSize() << endl; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
8.2 test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include<unordered_set> #include<unordered_map> #include<string> using namespace std; #include "HashTable.h" int main() { //TestHashTable1(); //HashBucket::TestHashTable1(); //HashBucket::TestHashTable2(); //HashBucket::TestHashTable3(); HashBucket::TestHashTable4(); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
