商城网站设计一站式服务,什么平台可以接国外订单,台州网站建设蓝渊,建设银行无锡分行网站文章目录 前言1. 哈希的概念2. 哈希冲突3. 哈希函数3.1 直接定址法3.2 除留余数法--(常用)3.3 平方取中法--(了解)3.4 折叠法--(了解)3.5 随机数法--(了解)3.6 数学分析法--(了解) 4. 哈希冲突的解决方法及不同方法对应的哈希表实现4.1 闭散列#xff08;开放定址法#xff0… 文章目录 前言1. 哈希的概念2. 哈希冲突3. 哈希函数3.1 直接定址法3.2 除留余数法--(常用)3.3 平方取中法--(了解)3.4 折叠法--(了解)3.5 随机数法--(了解)3.6 数学分析法--(了解) 4. 哈希冲突的解决方法及不同方法对应的哈希表实现4.1 闭散列开放定址法线性探测二次探测平方探测法 4.2 闭散列哈希表实现闭散列的插入闭散列的删除伪删除法结构定义插入函数insert实现载荷因子/负载因子扩容Insert测试查找函数Find实现删除函数Erase实现Find、Erase测试bug解决 4.3 开散列拉链法4.4 开散列哈希表实现结构定义析构插入函数insert实现扩容扩容优化insert和扩容测试查找函数Find实现删除函数Erase实现Find、Erase测试 5. 思考存储整型之外的其它类型元素6. 字符串哈希7. 哈希表性能测试分析8. 除留余数法最好模一个素数9. 源码9.1 HashTable.h9.2 Test.cpp 前言 上一篇文章我们学习了STL中unordered系列容器的使用并且提到unordered系列容器的效率之所以比较高尤其是查找是因为它底层使用了哈希结构即哈希表。 那这篇文章我们就来学习一下哈希表
1. 哈希的概念 顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即 O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数 理想的搜索方法 可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(一般称为哈希函数hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系那么在查找时通过该函数可以很快找到该元素 当向该结构中
插入元素 根据待插入元素的关键码以此函数即上面提到的哈希函数计算出该元素的存储位置并按此位置进行存放 搜索元素 对元素的关键码进行同样的函数计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
举个栗子 待插入数据集合{176459} 哈希函数设置为hash(key) key % capacity capacity为存储元素底层空间总的大小 假设表的capacity为10那插入之后就是这样的 那查找的时候我们直接通过函数获取下标位置查找即可 用该方法进行搜索不必进行多次关键码的比较元素的存储位置与它的关键码之间能够建立一 一映射的关系那么在查找时通过该函数可以很快找到该元素因此搜索的速度比较快 但是按照上述哈希方式向集合中插入元素44会出现什么问题 44%10结果也是4但是之前4这个元素已经存在下标为4的位置了 那这种现象我们把它叫做哈希冲突。
2. 哈希冲突
对于两个数据元素的关键字 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)即 不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 那引起哈希冲突的一个原因可能是 哈希函数设计不够合理 那下面我们来介绍一下哈希函数。
3. 哈希函数
哈希函数Hash Function在哈希表中起着关键的作用。它接收键作为输入并计算出一个索引或哈希码用于确定键在哈希表中的位置。
哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 那常见的哈希函数都有哪些呢
3.1 直接定址法
第一种哈希函数——直接定址法 取关键字的某个线性函数为散列地址通常是键值直接映射HashKey A*Key B 优点简单高效 缺点适用场景有限 使用场景适合于键值比较均匀、分布比较集中的情况 我们之前文章里讲过一道题 就这个这道题其实就用了哈希的思想 我们来复习一下。
当时讲的思路是这样的 字符串中字符的范围就是【a,z】那我们就可以创建一个大小为26的整型数组然后用一个相对映射去统计每个字母的出现次数a就映射到下标为0的位置b就映射到下标为1的位置依次类推。 那怎么让这些字母映射到对应的位置呢 减去’a’得到的值是不是就是它们映射的位置啊然后遍历字符串每个字母映射的值是几就让下标为几的元素初值全为0这样遍历过后每个字母出现的次数就统计出来了。下标0的元素的值就是a出现的次数1位置就是b出现的次数… 但是现在有一个问题那就是出现一次的字母可能不止一个我们怎么判断那个是第一个只出现一次的字母呢 这里我们不要去遍历统计次数的数组还是从前往后去遍历字符串然后看哪个字母的次数是1第一个是1的就是第一个只出现一次的字母。 这是我们当时写的代码。 大家看这不就是运用了哈希的思想嘛——使元素的存储位置与它的关键码之间能够建立一 一映射的关系。 这里用的哈希函数就是一种直接定址法嘛哈希函数就是key-a 当然现在我们学了unordered系列的容器就可以这样写了 统计次数用unorder_map就行了。 但是我们上面提到直接定址法只适用于键值比较均匀、分布比较集中的情况 比如这种情况 如果我们选择用键值直接映射直接定址法HashKeykey当前这几个值的话开这10个空间就够了但是如果是这样一组值呢 4512335515552333 难道我们要开2333个空间吗 可以是可以的但是不就太浪费了嘛。 所以呢出来直接定址法还提供了一些其它的哈希函数
3.2 除留余数法–(常用)
什么是除留余数法呢 其实最开始给大家介绍的那个例子里面的哈希函数就是除留余数法。
除留余数法的概念 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm)将关键码转换成哈希地址 举个例子 比如有这样一组值1 2 5 1333 2447 如果用直接定址法的话搞一个绝对映射那就需要开好多个空间。 但是如果用除留余数法的话那我们可以只开10个空间p取10 那存储结果就是这样的 这样虽然key值得分布很不均匀但是我们也能耗费比较小的空间把他们存起来。 但是有没有什么问题呢 如果我再加几个值比如12225534712 这是是不是会出现一个问题就是我们上面提到的哈希冲突/哈希碰撞 那问题来了对于哈希冲突我们如何解决呢 哈希冲突的解决是我们下面要重点讲解的一个问题。 不过在讲解之前还有几个哈希函数需要我们了解一下下面几个不常用所以我们了解即可 3.3 平方取中法–(了解) 假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合不知道关键字的分布而位数又不是很大的情况 3.4 折叠法–(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址因为散列低地址不能超过表长。 折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况 3.5 随机数法–(了解) 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key)其中random为随机数函数。 通常应用于关键字长度不等时采用此法 3.6 数学分析法–(了解)
举个例子供大家了解一下 有学生的生日数据如下 年.月.日 75.10.03 75.11.23 76.03.02 76.07.12 75.04.21 76.02.15 … 经分析第一位第二位第三位重复的可能性大取这三位造成冲突的机会增加所以尽量不取前三位取后三位比较好。 注意 哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。 所以接下来我们就来讲一下如何处理哈希冲突。
4. 哈希冲突的解决方法及不同方法对应的哈希表实现
解决哈希冲突两种常见的方法是闭散列和开散列
4.1 闭散列开放定址法
闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢
线性探测
线性探测 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止将新插入的值放到该空位置。 即 H i H_i Hi ( H 0 H_0 H0 i i i )% mi1,2,3,4… H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小 H i H_i Hi是向后探测的位置 为什么加完i还要模m呢因为一直加的话可能会超过表长这时就要回到开头往后进行探测了 比如上面我们举例的那种情况 现在我要插入122那根据哈希函数122%10定位到下标为2的位置但是这个位置已经被占用了怎么办 向后进行线性探测找下一个空位置所以122就会放到下标4这个位置 那后续的插入如果发生冲突也是如此 当然如果插入满了的话肯定要涉及到扩容的问题这个我们后面会说。 那大家觉得线性探测这样搞好不好啊我们来简单分析一下 线性探测优点实现非常简单 线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”我向后探测放到后面的空位置就占用了别的位置其它key定位到这个位置也需要再向后探测即冲突值占据了可利用的空位置使得寻找某关键码的位置需要许多次比较从冲突位置可能要向后查找多次导致搜索效率降低。 可以认为闭散列本质是就是一种零和游戏 那如何缓解呢
二次探测平方探测法
二次探测的产生呢能够在一定程度上缓解上面的问题 二次探测找下一个空位置的方法为 H i H_i Hi ( H 0 H_0 H0 i 2 i^2 i2 )% m 或者 H i H_i Hi ( H 0 H_0 H0 - i 2 i^2 i2 )% m 其中i 1,2,3… H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小 H i H_i Hi是向后探测的位置 那我们看到 二次探测它在向后探测的过程中使用了二次增量第一次冲突 1 2 1^2 12第二次 2 2 2^2 22第三次 3 2 3^2 32…而不是线性增量这样在寻找下一个可用槽位时可以跳过一些位置从而减少关键字在哈希表中的聚集程度提高散列效果。 4.2 闭散列哈希表实现
闭散列的插入 那我们接下来一起来探讨一下以闭散列线性探测的方式处理哈希冲突哈希函数我们以除留余数法为例具体如何进行插入删除并带大家实现一下相关的代码 我们先来分析一下插入 那思路是很清晰的也比较简单 首先通过哈希函数获取待插入元素在哈希表中的位置然后如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 这里前面几个值插入都没有冲突直接根据哈希函数获得的位置插入即可44插入发生冲突进行线性探测探测到下一个空位置8进行插入。 闭散列的删除
然后我们分析一下删除
大家想一下要删除一个值的时候怎么做 比如这样的场景 我们能看出来现在是存在一些冲突的。 假设我们现在要删除33怎么做 那首先我们还是根据哈希函数确定它的映射33%10结果是3但是3这个位置现在不是存的33那这能证明33不存在吗 不能因为他有可能发生了冲突在后面存着呢所以如果第一次没找到的话就要线性探测继续往后找找到这个过程和你如何存是对应着的那这里我们往后一个位置就找到了。 那找到了如何删除呢 把后面的值移动覆盖吗 那这样效率就太低了。 那做一个标识吗 比如删除一个值之后把它置成0或者-1表示这个位置为空那最开始可以把所有位置初始化成0或-1表示全空。 好像也不好如果你要存的就是0或-1呢。 另外如果这样处理的话会影响到查找。 大家想一下查找一个值的话什么时候结束 其实分为两种情况如果不冲突的话其实一下直接就找到了因为不冲突的话他就直接存到哈希函数确定的那个映射位置了。 如果冲突的话就往后探测嘛我们这里是线性探测那就继续往后找那往后找的话找到了好说找不到的话什么时候结束呢 走到哈希表结尾吗 那这样如果表比较长就太慢了效率太低了。当然其实也不需要走到表尾。 大家看 比如这种情况我们现在查找13 那首先定位到下标3这个位置但是不是所以要往后探测一直走到5这个空位置还是没有找到大家想还有必要往后查找吗 我们查找的时候是按照对应的探测方法去查找的所以我们往后查找的值一定是对应位置的冲突值如果走到一个探测位置为空了那就说明从这个位置开始以及后面都没有其它冲突值了后面即使还有值它们对应的散列地址都跟你查找的这个不是一个值了所以也没必要再往后查找了。 就我们当前这个情况查找13的散列地址是3但是那个空位置后面其它非空值的散列地址都不是3了。 那我们再过回来上面那样删除如何就影响查找了呢 回到上面删除的场景——删除33 删除之后是这样的 那然后我想查找13大家看现在能查找到吗 按照我们上面的分析正常查找到空就结束了现在查找13的话散列地址是3从下标3的位置开始走到空并没有找到因为要查找的13在空位置的后面。 但是这里13是真的不存在吗我们看到并不是。 所以上面的删除方法是不行的那如何搞呢 我们这里采用标记的伪删除法删除一个元素 伪删除法
那具体怎么做呢
我们给每个位置增加一个状态 状态有三种取值——空、存在、删除 空不用解释存在就是当前这个位置有值删除就是这个位置存过值但是现在被删除了。 这样我们进行相应的操作之后去该这个状态就行了当然初始状态就应该全为空 结构定义
那接下来我们就来实现一下代码这里我们以KV模型为例
首先我们定义一下大致的结构 然后哈希表的底层结构呢一般就使用数组那我们用vector就可以了也很方便 那用vector的话需要我们增加一个变量来记录哈希表中的数据个数。 那大家可能会疑问用vector的话vector.size()不就是数据个数嘛。 注意我们这里的插入不像vector的正常插入那样从前往后连续插入我们是按照得到的散列地址去插入的vector的size不一定就是我们真实插入数据的size而且我们哈希表删除只是把状态置为删除也不会影响vector的size。 这里大家要区分一下。 插入函数insert实现
那然后我们来写一下插入——Insert 首先第一个问题我们这里用vector实现哈希表那我们除留余数法模的这个值应该是size还是capacity 这里不能去%capacity要去%size才可以。 为什么呢 因为如果%capacity的得到的那个散列值是可能会大于size的。 那我们之前也模拟实现过vector要知道vector在进行插入操作的时候是会检查插入的那个位置是否在start和finish之间的 包括它对方括号的重载也会检查插入位置的下标是否小于size的。 所以如果这里%capacity的话有可能会越界当然如果出现这种情况vector里面直接就报断言错误了。 那我们写一下插入的具体代码 那就按照我们上面分析的逻辑走就行了 大家自己看一看理解一下 那大家有没有发现什么问题啊就上面插入的实现 刚开始的时候size为0啊那这里是不是就是除0错误了。 那除了size为0的情况我们还要考虑什么问题 我们不断的插入是不是要考虑在合适的时候进行扩容啊 另外size是不是会发生变化啊size一变这个映射关系是不是也就随之改变了 那不着急下面这些问题我们都会一一处理
载荷因子/负载因子
思考哈希表什么情况下进行扩容如何扩容 对于哈希表来说它的扩容不是等到当前表插入满了才去扩容。 而是去衡量哈希表的装满程度如果当前表里面插入的元素已经比较多了那这时再去插入新元素发生冲突的可能性就比较大了那冲突值就会增多冲突值越多那哈希表查找的效率就越低了。 所以当哈希表的装满程度已经比较大的时候即使还没满这个时候就要扩容了。 扩容
所以这里引入了载荷因子来衡量一个哈希表的装满程度来判断要不要进行扩容 散列表的载荷因子定义为 α 填入表中的元素个数/散列表的长度 α是散列表装满程度的标志因子。 α越大表明填入表中的元素越多产生冲突的可能性就越大 反之α越小表明填入表中的元素越少产生冲突的可能性就越小。 实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数。 **对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0.8以下。**超过0.8查表时的CPU缓存不命中(cache missing按照指数曲线上升。 所以当负载因子超过规定值就要扩容。 那我们来完善一下上面的代码 我们这里可以取0.7为负载因子的最大值大于等于这个值就扩容。 代码 大家看这样可以了吗还有其它问题吗 大家翻上去看一下上面提到的几个问题处理完了吗 是不是还没有啊刚才的代码解决了扩容和size为0情况的处理。 但是还有一个问题 就是我们使用resize扩容之后哈希表的size改变了而我们用的哈希函数是除留余数法Hash(key) key% size那size变了映射关系也就变了 扩容之后原来表里面已经插入的值它现在新的散列地址如果还用之前的可能就不对了。 所以这里的扩容操作 我们要这样做 不能在原表的基础上进行扩容而是要重新去开一块空间该空间的大小就是扩容之后的大小然后在新表上面把旧表的元素重新进行散列定位和插入。 那我们来修改补充一下上面的代码 然后红框这里其实就是还是走一个插入的逻辑我们可以把下面之前写的插入的代码拷贝上来修改一下。 这样写当然是可以的如果嫌这样冗余的话也可以单独把插入的部分封装一个函数需要的地方直接调用就行了。 但是这里我们介绍一个新玩法 这样就可以很好的实现一个复用。 Insert测试
那插入写好了我们来测试一下 比如我们就拿前面的这组数组测试一下 插入之后我们看跟图上一样不一样 来通过监视窗口看一下 大家可以自己对比一下是完全一致的。 然后我们再来针对扩容的情况测试一下 我们的平衡因子设置的是0.7而上面我们刚好已经插入7个值了对应的size是10 所以按理说我们再去插入一个值就会去扩容了我们来看一下 比如我们再插入一个15插入之后是这样的 我们来看一下 没有问题。 查找函数Find实现
上面把插入写好了find我们顺便直接写一下因为下面删除也要先查找 那查找的话就按照对应的哈希函数确定散列地址就行了然后如果有哈希冲突的话就按对应的探测方法往后查找就行了找到了我们可以返回一下这个元素的指针如果走到空还没找到就是没有这个值返回空如果表为空也没必要查找直接返回 写一下代码 那find写好之后的话其实insert里面我们可以再加一个如果到时候封装unordered_map/set的时候它们可以去重嘛所以 insert之前可以判断一下如果存在就不再插入了。 删除函数Erase实现
那我们再来看一下删除的实现 那删除的逻辑呢我们上面已经讲过了利用伪删除法其实就是去改它的状态就行了。 那当然我们得先查找一下确保这个值存在我们才能删除 来我们写一下 Find、Erase测试
然后查找删除我们一块测试一下 没什么问题。 bug解决
但是现在我们上面写的代码在Find那里还有一个隐藏的bug如果出现下面这种特殊情况就会有问题 那种情况呢 大多数情况下我们插入只要负载因子达到设定值就会扩容。 但是不排除可能会出现这样的情况就是我们插入了一些值之后只要再插入一个值就会扩容但是没有继续插入而是删除了一些元素删除一些之后又重新插入这样没有引起扩容但是导致了表中的状态只有删除和存在而没有空的状态。 那此时我们的查找 就会陷入一个死循环如果找不到的时候因为这里这个while循环是遇到空才结束的 那如何解决呢 也好办加一个判断就行了 这样就可以了 那我们闭散列的实现差不多就到这里当然我们这里是以线性探测为例实现大家有兴趣可以自己写一下二次探测的版本。当然除了线性探测和二次探测也有其他的一些方法大家有兴趣可以自行去了解。
闭散列的缺陷 空间利用率低、冲突频率高 开放定址法容易产生冲突特别是当哈希表的负载因子较大时即哈希表的装满程度更高。这会导致性能下降因为冲突的数量会增加导致查找的效率降低。而一旦减小负载因子又会导致频繁扩容空间利用率低。 聚集问题 开放定址法在处理冲突时有时会出现聚集问题。聚集是指数据项在哈希表中被连续地存储在相邻的位置上这样会导致冲突更加频繁并且会造成某些位置的利用率低而其他位置的利用率高的情况。 所以实际应用中处理哈希冲突更常用的是下面的方法
4.3 开散列拉链法
开散列/拉链法的概念 开散列法又叫链地址法(拉链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素 4.4 开散列哈希表实现
那下面我们就用拉链法来重新实现一个哈希表。
结构定义
那我们来定义一下结构还是以KV模型为例 当然这里你直接用vector listK,V 也可以但是直接用list里面有些地方会不太好处理所以这里里面的链接我们自己搞。 析构 那由于我们这样实现vector里面存的是一个个的结点这些结点可能指向空链表为空还没有插入值但也可能指向一个链表vector里面存的相当于链表的头指针嘛因为这种实现我们的元素就是存在每个哈希桶链表里面的嘛 所以这里我们要写一下析构因为里面的链表是涉及到资源管理的vector的和我们用库里面的不用管 插入函数insert实现
我们来实现一下insert
首先不考虑扩容我们先写一下仅仅是插入的过程 怎么插入呢 根据哈希函数算出元素的散列地址将它链接到对应的单链表哈希桶上就行了 至于插入的方式头插尾插都可以这里我们选择头插因为单链表的头插是比较方便的 代码 扩容
然后我们来讨论一下扩容的问题 其实按理来说我们这里如果不对表的大小或者说哈希表的长度进行扩容也可以不断插入值即使有冲突那我们就一直往每个对应的链表后面链接就行了。 这样好像也没什么问题。 确实但是如果我们插入的值比较多而表的长度有限那它每个链表里面的冲突值肯定会一直增多那这样效率就会大打折扣。 所以这里依然使用负载因子来控制在合适的时机进行扩容 那对于这里的拉链法我们可以把负载因子设置成1。 那1的话就是哈希表里面所有的链表哈希桶里面插入的元素之和等于表的长度的时候我们进行扩容。平均一点的话就是每个哈希桶里面都有一个元素。 这样是比较合适的当然不一定非要设置成1。 那我们来把扩容的代码加上 那我们这里还是先按扩容之后的size创建一个新表然后把旧表的值依次重新插入因为size改变了映射关系也会变最后把哈希表和新表进行交换 和上面闭散列扩容的逻辑一下嘛 这样写没什么问题。 扩容优化
但是呢我们可以进行一些优化 怎么优化呢 我们上面的写法遍历旧表依次把每个哈希桶里面的数据重新插入到新表newht里面虽然我们遍历用了引用但是它里面调inert的时候在insert里面还是会拿旧表里面每个结点的_kv去重新开结点然后插入最后还要一个一个结点释放旧表。 所以我这里想这样优化一下 我想直接把旧表的结点直接拿下来插入到新表里面这样即不用开新结点最终交换之后也不用释放旧表的结点。 那这样的话我们就不去复用insert了自己去搞 来实现一下 我们取旧表结点重新进行散列头插到新表就行了 就写好了 insert和扩容测试
然后我们来测试一下insert和扩容一起测一下 先不扩容用这个用例测试一下 我们运行通过监视窗口看一下 大家看一下没有问题跟图上是一样的。 然后扩容的情况 我们插入第11个值得时候就会扩容 我们来调试看一下 大家可以自己画图对比一下是没问题的。 查找函数Find实现
那我们再来写一下查找 那这里的查找就是根据散列地址去对应的链表里面查找就行了 然后insert里面也可以加一个这个 key不允许重复。 删除函数Erase实现
接着写一下删除Erase 那删除的话也是先走查找的逻辑嘛先根据散列地址去对应的链表里面找找到了就进行删除那这就是链表里面删除元素的操作了找不到返回false即可 来写一下 看不太懂的可以看之前文章复习一下单链表的删除 Find、Erase测试
我们来测试一下查找和删除 删除之前 删除之后 没问题 相比于开放定址等方法拉链法无需在哈希表中预留额外的空间只需在桶内分配链表节点即可。这样可以有效利用内存空间利用率更高。
5. 思考存储整型之外的其它类型元素
我们来思考一个问题 我们上面用两种方式实现了哈希表当然接口可能没有实现特别完整但是我们上面的实现哈希表里面存的都是整型而我们的哈希函数用整型进行计算刚好是比较好的比如我们上面用的是除留余数法。 但是如果是其它类型要是浮点型或者char类型还比较好处理因为可以强转但是如果是除此之外的其它类型比如string或者其它的自定义类型我们的程序还能很好的处理吗 我们可以先来试一下就用我们刚才实现的开散列的哈希表 来运行一下 是不行的。 因为string类型是无法进行取模运算的。 那我们如何解决一下呢 我们可以用一个仿函数来解决。 这个仿函数的作用就是把key无论是什么类型 转换成整型。 那我们来写一下 如果是对于doublechar这些能够隐式类型转换为整型的那我们的仿函数这样写就行了 这样的话如果是这些可以隐式类型转换的类型用这个仿函数就可以转换成整型因为这里的返回值是size_t无符号整型嘛其实就是起了一个类型转换的作用。 当然我们这里可以把这个设置为缺省值 这样这些可以支持隐式类型转换的这些类型就默认支持了对于这些类型我们就不用手动传了。 那使用仿函数的话我们代码里面取模的地方就得改一下 下面还有我就不截图了 但是呢 string这些自定义类型还是不支持啊因为它们不能转换为整型。 那这时候呢我们就可以针对具体的类型再去实现对应的仿函数然后自己显式传第三个仿函数的参数。 比如对于string类型我们来搞一下 首先下一个针对string的仿函数 至于在仿函数内部如何将string转换为整型方法有很多种 比如 我们这里返回string第一个字符的ASCII码值。 那现在就可以了。 不过我们这种方法其实不太好因为有可能是空串另外这样只要key的第一个字符相等那他们就会冲突。 所以我们也可以考虑这样写 用所有字符ASCII值之和作为返回结果这样冲突可能会少一点。 那对于其它自定义类型也是一样大家可以根据实际情况自己写仿函数控制。 那这样的话我们猜想库里面肯定也要解决这种情况 我们看到库里面也是通过仿函数来解决这种问题的。 ps下面那个Pred那个是用来控制比较两个键是否相等的。 但是我们会发现 库里面的unordered_map如果key是string的时候也不需要传仿函数可以直接用。 因为string这个类型还是比较常用的所以库里面直接默认就支持了。 那它是如何做到的呢 那其实很简单做一个特化就行了嘛这是我们模板那里学过的知识 那现在我们用string就也不用再手动传仿函数了 那上面把字符串所有的字符之和作为key去散列在一定程度上可以减少冲突但是避免不了这样的情况 即两个字符串是不相同的但是它们的字符ASCII码值之和是相同的比如两个字符串只是有些字符顺序不同。 如果这样情况比较多的话还是会造成大量冲突。 前三个相同后两个相同。 6. 字符串哈希
所以其实现在也有很多的字符串哈希函数来解决这个问题 常见的比如 种类很多大家有兴趣可以自行去了解。 那我们这里重点来了解一种 BKDR哈希 也是去算字符串所有字符的ASCII码值之和但是它每次都把前一个值乘一个数这个数也可以去好多种值。 那我们把自己写的改造一下比如我们乘31 然后我们再来测一下这个 看看结果 大家看这次就没有重复值了。 7. 哈希表性能测试分析
大家算一下再哈希表里面查找一个元素时间复杂度是多少 对于哈希表的查找如果我们考虑最坏的情况的话是O(N)即在插入的元素里面大部分的值都冲突到一个位置被放到同一个桶里面。 但是这种最坏的情况几乎不会出现。 因为我们插入的过程还会不断扩容而扩容的过程旧表的值重新散列到扩容之后的新表里面它的冲突值是会不断减少的。 另外我们的负载因子也在控制嘛像我们上面设置负载因子为1平均情况就是每个哈希桶上面挂一个值再插入就要扩容了。 所以如果按平均情况的话哈希表的查找就是O(1)这是很快的。 当然我们也可以通过程序来感受一下 多搞一些随机值插入到哈希表里面然后我们可以观察一下插入这么多随机值以后哈希表里面所有的哈希桶中高度最高是多少如果它的高度能一直保存在一个比较低的水平那它的效率就一定是很高的。 那我们来写一个求哈希桶最大高度的函数 然后我们来测试一下 先来10万个数据 我们看到最长的哈希桶长度才是1当然这里实际插入的值应该只有3万多个因为rand产生的随机数有大量重复值。 所以我们可以这样 这下重复值就少了 再测试 这次最长是2 数据量再增大100万 还是2。 这个效率还是非常好的最长的哈希桶才为2着查找起来是很快的。 那再问大家一个问题如果现在就是出现了某种比较特殊、比较极端的场景使得哈希表里面某些桶比较长那我们可以如何解决呢 首先我们可能会想到缩小负载因子这肯定能缓解一下。 然后这里有人提供这样一种思路 就是如果真的出现了某个桶特别长那针对这个桶我们可以不用链表而改用挂红黑树去存储该桶里面的值。 即有的地方挂链表有的地方链表比较长就把里面的值放到红黑树里面挂上去既有的位置挂链表有的位置挂红黑树可以借助联合体实现。 8. 除留余数法最好模一个素数 有些书上提出用除留余数法的时候模一个素数是比较好的。 那就有一个问题 如何每次快速取一个类似两倍关系的素数作为每次扩容前后表的size 那其实SGI版本的STL里面就使用了这种方式我们可以看一下他怎么搞的 我们看到他其实就是给了一个现成的素数表每次扩容就从这里面选取一个比当前size大的数作为下一次的容量第一次取53。 而且我们的哈希表去扩容它是不可能扩到大于这里的最大值的这个不用担心。 那我们可以就用它这个表把我们实现的改造一下 首先来一个这个函数 作用就是你给我一个素数我们从这里面找一个比你大的返回。 那我们代码里面扩容的size就可以这样获取 这个大家了解一下即可。
9. 源码
9.1 HashTable.h
#pragma once
#include stdbool.hnamespace OpenAddress
{enum State{EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class Vclass HashTable{public:bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}//先判断负载因子是否0.7超过就扩容//if (_table.size() 0 || (double)_n / (double)_table.size() 7)if (_table.size() 0 || _n * 10 / _table.size() 7){size_t newsize _table.size() 0 ? 10 : _table.size() * 2;//创建一个新哈希表HashTableK, V newht;newht._table.resize(newsize);for (auto data : _table){if (data._state EXIST){//把旧表里面的元素重新映射插入到新表里面newht.Insert(data._kv);}}//将哈希表底层旧表的新哈希表进行交换_table.swap(newht._table);}size_t hashi kv.first % _table.size();//判断是否发生冲突并进行线性探测size_t i 1;size_t index hashi;while (_table[index]._state EXIST){index hashi i;index % _table.size();i;}//在合适的位置进行插入_table[index]._kv kv;_table[index]._state EXIST;_n;return true;}HashDataK, V* Find(const K key){if (_table.size() 0){return nullptr;}size_t hashi key % _table.size();//判断是否发生冲突并进行线性探测寻找size_t i 1;size_t index hashi;while (_table[index]._state ! EMPTY){if (_table[index]._state EXIST key _table[index]._kv.first){return _table[index];}index hashi i;index % _table.size();i;//如果index在向后探测的过程中没有找到且又回到了起始点//就说明表中只有DELETE和EXIST我们手动结束循环if (index hashi){break;}}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_state DELETE;--_n;return true;}else{return false;}}private:vectorHashDataK, V _table;size_t _n 0;//记录哈希表中的有效数据个数};void test_hash1(){int arr[] { 3,33,2,13,5,12,1002 };HashTableint, int ht;for (auto e : arr){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));if (ht.Find(13)){cout 存在 endl;}else{cout 不存在 endl;}ht.Erase(13);if (ht.Find(13)){cout 存在 endl;}else{cout 不存在 endl;}}
}//-----------------------------------------------------------------------------------------------------------------
namespace HashBucket
{templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass Kstruct keyToIntFunc{size_t operator()(const K key){return key;}};//对string类型进行特化templatestruct keyToIntFuncstring{size_t operator()(const string key){size_t sum 0;for (auto e : key){sum sum * 31 e;}return sum;}};templateclass K, class V, class keyToInt keyToIntFuncKclass HashTable{typedef HashNodeK, V Node;public:~HashTable(){for (auto cur : _table){while (cur){Node* next cur-_next;delete cur;cur next;}cur nullptr;}}size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}//负载因子1进行扩容//复用insert/*if (_n _table.size()){size_t newsize _table.size() 0 ? 10 : _table.size() * 2;HashTableK, V newht;newht.resize(newsize);for (auto cur : _table){while (cur){newht.insert(cur-_kv);cur cur-_next;}}_table.swap(newht._table);}*///自己搞if (_n _table.size()){//size_t newsize _table.size() 0 ? 10 : _table.size() * 2;size_t newsize GetNextPrime(_table.size());vectorNode* newtable(newsize, nullptr);for (auto cur : _table){while (cur){Node* next cur-_next;size_t hashi keyToInt()(cur-_kv.first) % newtable.size();//把结点头插到新表cur-_next newtable[hashi];newtable[hashi] cur;cur next;}}_table.swap(newtable);}//计算散列地址size_t hashi keyToInt()(kv.first) % _table.size();//链到散列地址对应的单链表上头插Node* newNode new Node(kv);newNode-_next _table[hashi];_table[hashi] newNode;_n;return true;}Node* Find(const K key){if (_table.size() 0){return nullptr;}size_t hashi keyToInt()(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 keyToInt()(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (key cur-_kv.first){//头删if (prev nullptr){_table[hashi] cur-_next;}//非头删else{prev-_next cur-_next;}delete cur;return true;}else{prev cur;cur cur-_next;}}return false;}size_t MaxBucketSize(){size_t max 0;for (auto cur : _table){size_t size 0;while (cur){size;cur cur-_next;}if (size max){max size;}}return max;}private:vectorNode* _table;size_t _n 0;};void test_hash1(){int arr[] { 1,4,5,6,7,9,44,13,24,37 };HashTableint, int ht;for (auto e : arr){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(99, 99));if (ht.Find(13)){cout 存在 endl;}else{cout 不存在 endl;}ht.Erase(13);ht.Erase(4);if (ht.Find(13)){cout 存在 endl;}else{cout 不存在 endl;}} /*struct strToInt{size_t operator()(const string key){size_t sum 0;for (auto e : key){sum sum * 31 e;}return sum;}};*/void test_hash2(){HashTablestring, string ht;ht.Insert(make_pair(, 字符串));ht.Insert(make_pair(left, 左边));ht.Insert(make_pair(right, 右边));ht.Insert(make_pair(count, 数量));/*strToInt hashstr;cout hashstr(abcd) endl;cout hashstr(bcda) endl;cout hashstr(aadd) endl;cout hashstr(eat) endl;cout hashstr(ate) endl;*/}void test_hash3(){size_t N 1000000;HashTableint, int ht;srand((unsigned int)time(nullptr));for (size_t i 0; i N; i){size_t x rand() i;ht.Insert(make_pair(x, x));}cout 最长哈希桶长度为 ht.MaxBucketSize() endl;}
}9.2 Test.cpp
#include HashTable.hint main()
{//OpenAddress::test_hash1();HashBucket::test_hash3();return 0;
}
