二次探测开散列

二、闭散列哈希表的模拟实现2.1、框架2.2、哈希节点状态的类2.3、哈希表的扩容2.4、构建仿函数把所有数据类型转换为整型并特化2.5、哈希表的插入2.6、哈希表的查找2.7、哈希表的删除2.8闭散列模拟实现代码

三、开散列哈希桶的模拟实现3.1、框架3.2、构建仿函数把字符类型转为整型并特化3.3、哈希桶的插入3.4、哈希桶的查找3.5、哈希桶的删除3.6开散列模拟实现代码

一、哈希常识

在顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。

顺序查找时间复杂度为O(N)平衡树中为树的高度即O(logN)搜索的效率决于搜索过程中元素的比较次数。

理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。

如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。

当进行如下操作时

插入元素根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功

该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash

Table)(或者称散列表)

问题按照上述哈希方式向集合中插入元素44会出现什么问题这就涉及到了哈希冲突

1.2、哈希冲突

Hash(j)即不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢这里我们首先使用哈希函数解决数据范围广不集中key的数据不是整数的问题再来解决哈希冲突。

1.3、哈希函数直接定执

哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单

常见哈希函数

设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key)

key%

比如我给出的数据集合为{58100999920-10}如此不集中分布广的数据就不能用直接定址法因为分布太广会导致空间浪费过多。

这就需要用到除留余数法来解决

除留余数法就是先统一将数字转换为无符号解决了负数的问题再用key%表的大小随后映射到哈希表中图示

此时如果插入数字35的话那么哈希冲突就会出现了根据除留余数法的规则35理应映射到下标5的位置可是该位置已经有数值了这就需要通过后文的开散列和闭散列的相关知识点来帮助我们解决哈希冲突。

假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址

再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况

选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key)

random(key),其中random为随机数函数。

通常应用于关键字长度不等时采用此法

设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。

可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。

例如

假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是

相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现

冲突还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成123446)等方法。

数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

**注意**哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。

1.4、哈希冲突解决

闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个”

1、线性探测

线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。

找下一个空位置的方法为hash(key)%N

比如我在此基础上继续插入103050。

首先10%100下标0的位置有了20继续往后找下标1是空的把10放进去20%100下标0为20往后找下标1是10往后找下标2是空的放进去……。

线性探测优点实现非常简单

线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。

当再插入数值21时21%101可是下标1位置被下标0位置的冲突而被10占了于是继续往后找空位恶行循环导致拥堵。

2、二次探测

线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为hash(key)

i^2i

二次探测就是对上述线性探测的优化不那么拥堵。

简而言之线性探测是依次寻找空位置必然拥堵而二次探测跳跃着寻找空位置就没那么拥堵。

不过这俩方法没有本质的冲突本质都是在占别人的位置只是一个挨着占一个分散着占的区别罢了。

研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。

因此只要表中有一半的空位置就不会存在表满的问题。

在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。

因此闭散列最大的缺陷就是空间利用率比较低这也是闭散列的缺陷但是往后又推出一种开散列来解决哈希冲突的问题此法还是比较优的。

开散列

开散列法又叫链地址法(开链法、哈希桶)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中

简而言之就是我的数据不存在表中表里面存储一个链表指针就是把冲突的数据通过链表的形式挂起来示例

从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素大大减少了闭散列法冲突的弊端性。

后文将会详细讲解闭散列哈希表以及开散列哈希桶的具体模拟实现。

2.1、框架

如果某下标没有值则代表空EMPTY如果有值在代表存在EXIST如果此位置的值被删掉了则表示为DELETE

而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。

这里我们专门封装一个类来记录每个位置的状态以此汇报给后续的哈希表。

enum

DefaultHashK//添加仿函数便于把其他类型的数据转换为整型数据

class

50%100下标0的值不是50继续下标往后查找直至下标3的下标为止。

2、查找60

60%100下标0不是往后下标继续查找找到下标4发现状态为EMPTY空此时停止查询因为往后就不可能出现了

3、删除10再查找50

50%100下标0的值不是下标到下标1发现状态为DELETE删除继续下标直至下标3的值为50找到了。

散列表的长度α是散列表装满程度的标志因子。

由于表长是定值α与“填入表中的元素个数”成正比所以α越大表明填入表中的元素越多产生冲突的可能性就越大反之α越小表明填入表中的元素越少产生冲突的可能性就越小。

实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数。

对于开放定址法闭散列载荷因子是特别重要因素应严格限制在0.7

missing按照质数曲线上升。

因此一些采用开放定址法的hash库如Java的系统库限制了载荷因子为0.75超过此值将resize散列表。

综上我们在后续的插入操作中必然要考虑到扩容的情况我们直接把负载因子控制在0.7超过了就扩容。

具体操作见下文哈希表的插入操作。

在我们后续的插入操作中插入的数据类型如果是整数那么可以直接建立映射关系可若是字符串就没那么容易了因此我们需要套一层仿函数来帮助我们把字符串类型转换成整型的数据再建立映射关系。

主要分为以下三类需要写仿函数的情况

只用首字母的ascii码来映射此法不合理因为abc和axy本是俩不用字符串经过转换会引发冲突。

字符串内所有字符ASCII码值之和此法也会产生冲突因为abcd和bcad在此情况就会冲突。

为了避免冲突几位大佬推出多种算法思想下面我取其中一种算法思想来讲解

BKDR哈希算法

也可以乘以31、131、1313、13131、131313..

为了能够让我们的哈希表能够自动识别传入数据的类型不用手动声明这里我们可以借助特化来解决仿函数特化总代码如下

//利用仿函数将数据类型转换为整型

复用Find查找函数去帮助我们查找插入的值是否存在若存在直接返回false不存在再进行后续的插入操作

2、扩容操作

表的大小7就扩容*10是为了避免出现size_t的类型相除不会有小数的情况扩容以后要重新建立映射关系创建一个新的哈希对象扩容到需要的内存大小遍历旧表把旧表每个存在的元素依据该哈希表的规则如除留余数法插入到新表此步骤让新表自动完成映射关系无序手动构建利用swap函数把新表和旧表中的数据进行交换此时的旧表就是已经扩好容且建立好映射关系的哈希表

3、插入操作

借助仿函数把插入的数据类型转为整型并定义变量保存插入键值对的key用此变量%哈希表的size()因为我们初始化的时候已经将哈希表的值全部赋零值了且对于哈希表应该尽量控制size和capacity一样大遍历进行线性探测

二次探测如果这个位置的状态为EXIST存在说明还要往后遍历查找遍历结束说明此位置的状态为空EMPTY或删除DELETE可以放值把插入的值放进该位置更新状态为EXIST有效数据个数

//插入

(Find(kv.first)){//说明此值已经有了直接返回falsereturn

(_tables.size()

newHT;newHT._tables.resize(newSize);//遍历旧表把旧表每个存在的元素插入newHTfor

(auto

EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc

hf;size_t

hf(kv.first);//取出键值对的key并且避免了负数的情况借用仿函数确保是整型数据starti

hashi

_tables.size();//防止hashi超出数组}_tables[hashi]._kv

EXIST;_n;return

查找的核心逻辑就是找到key相同就返回此对象的地址找到空就返回nullptr具体细分规则如下

先去判断表的大小是否为0为0直接返回nullptr按照线性探测

二次探测的方式去遍历遍历的条件是此位置的状态不为空EMPTY如果遍历到某哈希表中的对象的值等于要查找的值前提是此位置的状态不为DELETE删除返回此对象的地址当遍历结束后说明此位置的状态为空EMPTY哈希表没有我们要查找的值返回nullptr

//查找

hf(key);//通过仿函数把其它类型数据转为整型数据starti

hashi

_tables[hashi];//找到了就返回此对象的地址}hashi

starti

_tables.size();//防止hashi超出数组}return

nullptr;

复用Find函数去帮我们查找删除的位置是否存在若存在把此位置的状态置为DELETE即可此时表中的有效数据个数_n需要减减最后返回true若不存在直接返回false

//删除

{//复用Find函数去帮助我们查找删除的值是否存在Data*

ret

(ret){//若存在直接把此位置的状态置为DELETE即可ret-_state

DELETE;return

DefaultHashK//添加仿函数便于把其他类型的数据转换为整型数据

class

(Find(kv.first)){//说明此值已经有了直接返回falsereturn

(_tables.size()

newHT;newHT._tables.resize(newSize);//遍历旧表把旧表每个存在的元素插入newHTfor

(auto

EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc

hf;size_t

hf(kv.first);//取出键值对的key并且避免了负数的情况借用仿函数确保是整型数据starti

hashi

_tables.size();//防止hashi超出数组}_tables[hashi]._kv

EXIST;_n;return

hf(key);//通过仿函数把其它类型数据转为整型数据starti

hashi

_tables[hashi];//找到了就返回此对象的地址}hashi

starti

_tables.size();//防止hashi超出数组}return

nullptr;

{//复用Find函数去帮助我们查找删除的值是否存在Data*

ret

(ret){//若存在直接把此位置的状态置为DELETE即可ret-_state

DELETE;return

根据我们先前对开散列哈希桶的了解得知其根本就是一个指针数组数组里每一个位置都是一个链表指针因此我们要单独封装一个链表结构的类以此来告知我们哈希表类的每个位置为链表指针结构。

//结点类

此步操作的方法和闭散列哈希表所实现的步骤一致目的都是为了能够让后续操作中传入的所有数据类型转换为整型数据以此方便后续建立映射关系直接看代码

//利用仿函数将数据类型转换为整型

复用Find查找函数去帮助我们查找插入的值是否存在若存在直接返回false不存在再进行后续的插入操作

2、扩容操作

针对哈希桶的扩容我们有两种方法进行扩容法一和哈希表扩容的方法一致

当负载因子1时扩容扩容后重新建立映射关系创建一个新的哈希桶对象扩容到newSize的大小遍历旧表把旧表每个存在的元素插入到新表此步骤让新表自动完成映射关系无序手动构建利用swap函数把新表和旧表交换此时的旧表就是已经扩好容且建立号映射关系的哈希表

当我们把旧表的元素映射插入到新表的时候最后都要释放旧表按照先前哈希表的释放我们无需做任何处理但是现在定义的结构是vector是自定义类型会自动调用析构函数进行释放vector存储的数据是Node*Node*是内置类型不会自动释放最后会出现表我们释放了但是链表结构的数据还没释放因此我们还需借助手写析构函数来帮助我们释放。

//析构函数

这里我们没必要再创建新的节点相反把扩容前的节点拿过来重新映射到新表中大体逻辑和前面差不太多只是这里不需要再创建新节点。

直接利用原链表里的节点。

3、头插操作

借助仿函数找到映射的位置头插的位置进行头插的操作更新有效数据个数

//插入

false;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hf;//2、负载因子

newHT;//newHT._tables.resize(newSize,

nullptr);//遍历旧表把旧表的数据重新映射到新表for

(size_t

(cur)//如果cur不为空就插入{newHT.Insert(cur-_kv);cur

cur-_next;}}newHT._tables.swap(_tables);*///法二size_t

newSize

newTable;newTable.resize(newSize,

nullptr);for

newSize;//确认映射到新表的位置//头插cur-_next

newTable[hashi];newTable[hashi]

cur;cur

nullptr;}newTable.swap(_tables);}//3、头插//找到对应的映射位置size_t

hashi

_tables.size();//头插到对应的桶即可Node*

newnode

先去判断表的大小是否为0为0直接返回nullptr利用仿函数去找到映射的位置在此位置往后的一串链表中进行遍历查找找到了返回节点指针遍历结束说明没找到返回nullptr

//查找

nullptr;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hashi

_tables[hashi];//在此位置的链表中进行遍历查找while

(cur){if

cur-_next;}//遍历结束没有找到返回nullptrreturn

nullptr;

找到删除的值对应哈希桶的下标映射位置按照单链表删除节点的方法对该值进行删除

//删除

false;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hashi

cur-_next;}else//非头删{prev-_next

cur-_next;}delete

上述的删除是实打实的删除建立prev作为cur的前指针以此利用prev和cur-next来建立关系从而删除cur节点但是我们可以不用借助prev指针就利用先前二叉搜索树的替换法删除的思想来解决。

图示

当我要删除88时把节点88的下一个节点的值78替换掉88随后删除节点78再建立链表的关系即可。

当删除的是尾节点98时直接和头节点进行交换删除头节点并建立链表关系。

3.6开散列模拟实现代码

false;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hf;//2、负载因子

newHT;//newHT._tables.resize(newSize,

nullptr);//遍历旧表把旧表的数据重新映射到新表for

(size_t

(cur)//如果cur不为空就插入{newHT.Insert(cur-_kv);cur

cur-_next;}}newHT._tables.swap(_tables);*///法二size_t

newSize

newTable;newTable.resize(newSize,

nullptr);for

newSize;//确认映射到新表的位置//头插cur-_next

newTable[hashi];newTable[hashi]

cur;cur

nullptr;}newTable.swap(_tables);}//3、头插//找到对应的映射位置size_t

hashi

_tables.size();//头插到对应的桶即可Node*

newnode

nullptr;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hashi

_tables[hashi];//在此位置的链表中进行遍历查找while

(cur){if

cur-_next;}//遍历结束没有找到返回nullptrreturn

Erase(const

false;}//构建仿函数把数据类型转为整型便于后续建立映射关系HashFunc

hashi

cur-_next;}else//非头删{prev-_next

cur-_next;}delete

false;}/*法二替换法……*/private://指针数组vectorNode*

_tables;size_t