常州市住房建设局网站,廊坊网站制作套餐,在微信上做彩票网站吗,广州中小学安全教育平台文章目录什么是哈希问题引入哈希函数直接定址法除留余数法 #xff08;常用、重点#xff09;哈希冲突哈希冲突的解决方法闭散列开散列unordered_map unordered_set 封装实现哈希的应用位图布隆过滤器哈希经典面试题哈希切分位图应用布隆过滤器什么是哈希
在上一…
文章目录什么是哈希问题引入哈希函数直接定址法除留余数法 常用、重点哈希冲突哈希冲突的解决方法闭散列开散列unordered_map unordered_set 封装实现哈希的应用位图布隆过滤器哈希经典面试题哈希切分位图应用布隆过滤器什么是哈希
在上一篇博客map和set我们详细的介绍了以红黑树为底层的数据结构本篇博客论述的哈希这种数据结构实际上是unordered_map和unordered_set的数据结构的底层。
哈希实际上是一种映射关系map和set实际上在搜索的时候对树进行遍历理论上的时间复杂度是O(log2N)但是哈希是可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。
问题引入
先来一道OJ387. 字符串中的第一个唯一字符
解决这个问题有一个常见的解法开一个26个空间的int数组每一个位置映射26个字母表中一个字母该位置储存的数为该位置映射字母出现的个数。只要遍历一遍字符串即可得到答案。这里就用了哈希的思想。
注意
哈希函数HashFunc 这里26个英文字母的映射方法可以是不同的例如可以a映射数组下表为0b映射下表为2以此类推…也可以z映射数组下表为0y映射下表为2以此类推…。这就是哈希函数函数实际上是一种线性映射关系哈希函数是可以自定义的。散列表HashTable这里开辟的空间为26的int数组就是散列表与哈希函数计算出来的存储位置对应。 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值 域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 面对哈希冲突有两种常见的方法
直接定址法
直接定址法就是上面OJ题的思路是一种一对一的映射关系 取关键字的某个线性函数为散列地址HashKey A*Key B
优点简单、均匀缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况
除留余数法 常用、重点
设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址
注意
这里的Key与我们在KV模型中的key略有不同 key由于需要取模所以必须是一个正整数——这同时也决定了key是存在范围一般定义成size_t类型也就是key只有4294967295种不同情况如果你想映射一个字符串理论上不同字符串种类要远远大于不同Key值种类的范围如果一定让一个字符串对应一个Key就一定有一些字符串会具有相同的Key值。
哈希冲突
那么问题就出现了如果不同的值x进入哈希函数计算出了相同的值y类比yx^2一个y对应两个x这时就出现了哈希冲突 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
造成哈希冲突有两个原因以除留余数法为例
哈希表开的空间太小导致不同的key映射到了相同数组下表解决方法也非常简单——数组增容就完事了当你插入值的范围大于Key值的范围时不管你空间开多大都会造成哈希冲突因为不同插入的值会对应相同的Key这个解决方法是更换哈希函数
哈希冲突的解决方法 闭散列
闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止 对于每一个节点设置三种状态占用FULL空EMPTY删除DELETE 插入就是修改节点的值和节点的状态为FULL 删除 则是直接修改节点的状态为DELETE实际上是一种伪删除 散列表的载荷因子就是插入元素的个数/哈希表的大小一般在插入的过程中要控制载荷因子在一定的范围内否则需要扩容来人为降低载荷因子 二次探测 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位 置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法 key值加上{1-1,4-4,9-9…}如果key加上值的位置已经被占用了就一直往后加知道找到空位为止。
总结 闭散列空间利用效率很低 开散列
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。 这样发送冲突之后就不会影响下一位
插入 插入操作就是先算出插入元素在开散列所在的位置然后采用链表头插
删除 插入操作就是先算出插入元素在开散列所在的位置然后删除方法同链表删除元素相同
扩容 先开辟一个新的指针数组然后遍历原来的开散列将每一个元素依次按上面的插入逻辑插入新的散列之中
开散列实现代码 unordered_map unordered_set 封装实现
这里提供unordered_map的封装的代码unordered_map底层用的是开散列封装的方式与map是一样的具体参考博客map和set 的封装
哈希的应用
位图
先来一道腾讯的面试题 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】
Solution
直接遍历——时间复杂度O(N)排序之后二分查找——时间复杂度O(log2N)位图 位图就是每一个元素都是bit的一维数组位图的映射是直接定址法位图仗着自己单个空间小所以开辟一个很大的数组表示一个很大的范围。但是缺点也很明显数组元素是bit只能表示两种状态。至于表示多种状态一种常用的方法开辟若干个位图这样k值映射的位置就对应了多个bit位
布隆过滤器 前面说过一个问题就是哈希函数是由Key模上散列的大小得出最后的存储位置但是由于Key必须是正整数所以限制了Key的不同的个数最多只有42亿。但是遇到插入的是字符串这种不同个数是无穷的值时很容易就发生冲突了如上图所示。
于是我们做出以下改变使插入的值不在映射一个位置而是映射多个位置。相比映射了一个位置添加了多个保险 假设插入顺序是{hello,world,repeat,bye} 插入 插入的逻辑非常简单将插入值映射的所有位的值全部置1 检查是否存在 不存在——只要检查值所对应的位中存在一个位没有被置1则说明该值未被插入也就不存在。这个结果是100%确定的。存在——检查值所有对应的位如果全为1 则说明该值存在。但是这个结果准确吗 存在的结果是不准确的例如上面案例在插入hello和world之后如果检查bye是否存在的时候你就会发现bye所有映射的位全部都置成了1 但是显然bye并未被插入。
布隆过滤器应用场景 我们在注册账号的时候输入昵称的时候需要快速检测该昵称是否被注册过。可以设置一个布隆过滤器在数据库的上层输入昵称之后不用先到数据库中查询而是先在布隆过滤器中查询如果查出来没有那么一定数据库中不存在该昵称。如果查出来存在则在去数据库里面查找一下到底是否存在。 代码实现 布隆过滤器的底层是一个位图
实现中的问题
如何确定位图应该开多大 实际上是有公式的 k为哈希函数个数m为布隆过滤器底层位图的大小n为插入元素的个数。因为k是在实现过程中是确定的所以m和n就成了一个正比例函数 代码
哈希经典面试题
哈希切分
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 思路 假设内存为4GB100G的ip地址不可能都加载到内存中这里采用一个变式 的哈希桶但是这个哈希桶挂的不是链表而是文件 100G中的所有ip都通过HashFunc函数分配到相应的桶之中保持每一个文件桶的大小在1GB左右分配完之后将每一个文件都加载到内存中用map来统计个数。这是大体思路。 思路漏洞 万一通过哈希函数分配过程中还没分配完某个文件就已经超过了1GB该如何处理 分为两种情况 冲突的ip多但都是不同的ipmap是无法计数的——解决方法更换哈希函数将该文件切分成若干子文件重复上述思路冲突的ip多但都是相同的ipmap是可以统计的 切分完之后分段放进内存用map统计次数 给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出 精确算法和近似算法 这道题和上一题的思路一致我们可以对两个文件分别做哈希切分但是要使用同样的哈希函数这样相同query才会分到同一个文件夹里面。然后我们在对两个小文件分别加载到内存里面使用set先去重再找交集
位图应用 给定100亿个整数设计算法找到只出现一次的整数 使用位图但是位图只能表示该数存在还是不存在并不能很好的标识出现的次数。所以这里使用两个位图来解决问题两个位图每个位对应两个bit位也就能表示四种状态。问题便得到了很好的解决。 思考 100亿个整数开辟位图是不是要100亿个bit位—— 注意bit位的数量是由数据的范围决定的而不是数据的个数这也是哈希的本质整数最多也就42亿个多出来的都是重复的 给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 使用位图先给一个文件所有整数标记注意只需注意文件里面数是否存在出现几次并不在处理范围内。然后遍历第二个文件并用改为图检查即可找出交集 注意 我们开辟一个42亿的位图~0.5G生下来0.5G内存用来重复读取文件 位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整 数 与第一题思路一模一样
布隆过滤器
如何扩展BloomFilter使得它支持删除元素的操作 现有的布隆过滤器是不支持删除操作的因为删除某一个元素意味着要清空所有他在位图中的对应位这可能影响别的元素因为一个位可能被多个元素共用。解决方法也很简单对每个位设置一个计数器删除某一个元素只需要该元素对应所有位的计数器减1即可。但是缺点也十分明显会消耗很大的空间本来位图的优势就是每一个位只占一个bit现在好了每个位变成一个计数器空间开销会变得巨大 文章转载自： http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.hqzmz.cn.gov.cn.hqzmz.cn http://www.morning.zxznh.cn.gov.cn.zxznh.cn http://www.morning.hlkxb.cn.gov.cn.hlkxb.cn http://www.morning.fhsgw.cn.gov.cn.fhsgw.cn http://www.morning.mqwdh.cn.gov.cn.mqwdh.cn http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.webife.com.gov.cn.webife.com http://www.morning.lzjxn.cn.gov.cn.lzjxn.cn http://www.morning.yxbdl.cn.gov.cn.yxbdl.cn http://www.morning.nwjd.cn.gov.cn.nwjd.cn http://www.morning.pcqdf.cn.gov.cn.pcqdf.cn http://www.morning.kzdgz.cn.gov.cn.kzdgz.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.cylbs.cn.gov.cn.cylbs.cn http://www.morning.drqrl.cn.gov.cn.drqrl.cn http://www.morning.llxyf.cn.gov.cn.llxyf.cn http://www.morning.rkqzx.cn.gov.cn.rkqzx.cn http://www.morning.sgbsr.cn.gov.cn.sgbsr.cn http://www.morning.cfccp.cn.gov.cn.cfccp.cn http://www.morning.lhjmq.cn.gov.cn.lhjmq.cn http://www.morning.xjkr.cn.gov.cn.xjkr.cn http://www.morning.ndynz.cn.gov.cn.ndynz.cn http://www.morning.tnrdz.cn.gov.cn.tnrdz.cn http://www.morning.hqllx.cn.gov.cn.hqllx.cn http://www.morning.mpwgs.cn.gov.cn.mpwgs.cn http://www.morning.bojkosvit.com.gov.cn.bojkosvit.com http://www.morning.kzcfp.cn.gov.cn.kzcfp.cn http://www.morning.ltffk.cn.gov.cn.ltffk.cn http://www.morning.mqwdh.cn.gov.cn.mqwdh.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.mltsc.cn.gov.cn.mltsc.cn http://www.morning.aowuu.com.gov.cn.aowuu.com http://www.morning.prhfc.cn.gov.cn.prhfc.cn http://www.morning.chmcq.cn.gov.cn.chmcq.cn http://www.morning.mhmcr.cn.gov.cn.mhmcr.cn http://www.morning.sffkm.cn.gov.cn.sffkm.cn http://www.morning.hmbtb.cn.gov.cn.hmbtb.cn http://www.morning.jlpdc.cn.gov.cn.jlpdc.cn http://www.morning.lwtfr.cn.gov.cn.lwtfr.cn http://www.morning.crqbt.cn.gov.cn.crqbt.cn http://www.morning.qlhwy.cn.gov.cn.qlhwy.cn http://www.morning.qlxgc.cn.gov.cn.qlxgc.cn http://www.morning.glcgy.cn.gov.cn.glcgy.cn http://www.morning.srnth.cn.gov.cn.srnth.cn http://www.morning.xdwcg.cn.gov.cn.xdwcg.cn http://www.morning.fbrshjf.com.gov.cn.fbrshjf.com http://www.morning.kqkmx.cn.gov.cn.kqkmx.cn http://www.morning.zrpys.cn.gov.cn.zrpys.cn http://www.morning.dfygx.cn.gov.cn.dfygx.cn http://www.morning.wwklf.cn.gov.cn.wwklf.cn http://www.morning.thmlt.cn.gov.cn.thmlt.cn http://www.morning.dbqg.cn.gov.cn.dbqg.cn http://www.morning.mfmx.cn.gov.cn.mfmx.cn http://www.morning.vehna.com.gov.cn.vehna.com http://www.morning.gxklx.cn.gov.cn.gxklx.cn http://www.morning.kfyjh.cn.gov.cn.kfyjh.cn http://www.morning.qclmz.cn.gov.cn.qclmz.cn http://www.morning.wmyqw.com.gov.cn.wmyqw.com http://www.morning.xrhst.cn.gov.cn.xrhst.cn http://www.morning.ghxsn.cn.gov.cn.ghxsn.cn http://www.morning.hkpyp.cn.gov.cn.hkpyp.cn http://www.morning.xfxlr.cn.gov.cn.xfxlr.cn http://www.morning.bgkk.cn.gov.cn.bgkk.cn http://www.morning.yqwsd.cn.gov.cn.yqwsd.cn http://www.morning.xqknl.cn.gov.cn.xqknl.cn http://www.morning.klwxh.cn.gov.cn.klwxh.cn http://www.morning.bqwrn.cn.gov.cn.bqwrn.cn http://www.morning.hlhqs.cn.gov.cn.hlhqs.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.mhcys.cn.gov.cn.mhcys.cn http://www.morning.rgmd.cn.gov.cn.rgmd.cn http://www.morning.fkgct.cn.gov.cn.fkgct.cn http://www.morning.kbqqn.cn.gov.cn.kbqqn.cn http://www.morning.jbfjp.cn.gov.cn.jbfjp.cn http://www.morning.hqbnx.cn.gov.cn.hqbnx.cn http://www.morning.ksggr.cn.gov.cn.ksggr.cn http://www.morning.zstry.cn.gov.cn.zstry.cn http://www.morning.ryfq.cn.gov.cn.ryfq.cn
