哈希表哈希表1概念2直接定址法3哈希冲突4负载因子5关键字转整数6哈希函数6.1除法散列法/除留余数法6.2乘法散列法6.3全域散列法7处理哈希冲突7.1开放定址法线性探测二次探测双重探测开放定址法表结构扩容key不能取模的问题完整代码7.2链地址法扩容完整代码1概念哈希(hash)算法又称散列算法是⼀种组织数据的⽅式。有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找。哈希表Hash Table是一种通过哈希函数将键Key映射到数组索引从而实现O(1)平均时间复杂度进行插入、查找和删除的高效数据结构。其核心思想是将键值对存储在一个固定大小的数组中通过哈希函数快速定位位置。直接看概念感觉还是有点难懂简单来说就是将一个键值key通过特定哈希函数计算后进行操作例如 1-经过特定算法- 100解释为1映射到了100当有索引100时又可以经过算法转化为原始元素1。而最重要的就是这个映射方式以及有大量原始元素映射到同一个位置即哈希冲突怎么来避免这是本篇学习的主要方向。2直接定址法介绍直接定址法是将关键字和相对位置绝对位置建立映射关系的一种简单粗暴方法。特点适用于关键字范围集中的场景。实现简单直接定址法虽然实现简单但是它的缺点也相当明显当关键字比较分散时会浪费大量内存。例如关键字都在[099]之间那么每个关键字的值就是对应存储位置的下标。再例如⼀组关键字值都在[a,z]的⼩写字⺟那么我们开⼀个26个数的数组每个关键字acsii码-a码值减a的码值ascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出⼀个绝对位置或者相对位置。例如在字符串中的第一个唯一字符中我们就使用了计算字符在一个相对位置的思想。387. 字符串中的第一个唯一字符给定一个字符串s找到它的第一个不重复的字符并返回它的索引。如果不存在则返回-1。示例 1输入: s leetcode 输出: 0示例 2:输入: s loveleetcode 输出: 2示例 3:输入: s aabb 输出: -1提示:1 s.length 105s只包含小写字母class Solution { public: int firstUniqChar(string s) { int count[26] { 0 }; for (auto ch : s) { count[ch - a]; } for (size_t i 0;i s.size();i) { if (count[s[i] - a] 1) { return i; } } return -1; } };3哈希冲突建立映射关系时不同的key可能会映射到相同位置上这就叫做哈希冲突或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数。4负载因子负载因子load factor也叫载荷因子/装载因子等。假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子N/M负载因子越⼤哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低当负载因子增长到某个临界值时我们就要对哈希表进行扩容重新映射以此来减小哈希冲突的概率。5关键字转整数将关键字映射到数组中的某个位置整数比较好做映射计算如果不是整数我们要想办法转换成整数 。templateclass KstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};// 特化templatestructHashFuncstd::string{size_toperator()(conststd::stringkey){size_thash0;for(autoe:key){hash*131;hashe;}returnhash;}};6哈希函数6.1除法散列法/除留余数法假设哈希表的⼤⼩为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key % M。当使⽤除法散列法时要尽量避免M为某些值如2的幂10的幂等。 如果是2^x那么key % (2^x)本质相当于保留key的后X位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了。建议M取不接近2的整数次幂的⼀个质数(素数)。6.2乘法散列法乘法散列法对哈希表⼤⼩M没有要求他的⼤思路第⼀步⽤关键字 K 乘上常数 A (0A1)并抽取出 k * A 的⼩数部分。第⼆步后再⽤M乘以k * A 的小数部分再向下取整。h(key) floor(M × ((A × key)%1.0))其中floor表⽰对表达式进⾏下取整A∈(0,1)这⾥最重要的是A的值应该如何设定Knuth认为 A ( 5 - 1)/2 0.6180339887… (⻩⾦分割点])⽐较好。乘法散列法对哈希表⼤小M是没有要求的假设M为1024key为1234A 0.6180339887, A * key 762.6539420558取⼩数部分为0.6539420558, M×((A×key)%1.0) 0.6539420558 * 1024 669.6366651392那么h(1234) 669。6.3全域散列法全域散列法是一种用于减少散列冲突的技术。它通过选择多个散列函数来确保对于任意两个不同的输入散列函数集合中的散列函数重合次数不会超过某个特定值。这种方法可以有效地控制冲突率特别是在面对恶意输入时。hab(key) ((a × key b)%P ) % MP需要选⼀个⾜够⼤的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了⼀个P*(P-1)组全域散列函数组。假设P17M6a 3 b 4, 则h34(8) ((3 × 8 4)%17)%6 5。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的⼀个散列函数使⽤后续增删查改都固定使⽤这个散列函数否则每次哈希都是随机选⼀个散列函数那么插⼊是⼀个散列函数查找⼜是另⼀个散列函数就会导致找不到插⼊的key了。7处理哈希冲突开放定址法线性探测二次探测双重探测链地址法哈希桶7.1开放定址法开放定址法依次将全部元素插入哈希表中当⼀个关键字key使用哈希函数计算出的位置冲突了也就是该位置已经有元素了此时就按照特定规则继续寻找到下一个空闲位置。这⾥的规则有三种线性探测、⼆次探测、双重探测。注意开放定址法中负载因⼦⼀定⼩于1。一般来说当开放定址法的负载因子增长到0.7左右就要扩容进行重新映射了。线性探测类似于沿着一条直线进行探测。如果在某一个位置发生冲突则从该位置依次向后查找直到找到一个没有存储数据的位置为止如果在探测时走到哈希表尾部则回绕到哈希表表头继续探测。假设hash0 key % M, 如果位置冲突了则线性探测公式为hashi (hash0 i) % M i {1, 2, 3…, M - 1} 因为负载因⼦⼩于1则最多探测M-1次⼀定能找到⼀个存储key的位置。注M是哈表长度例如将{19,30,5,36,13,20,21,12} 这⼀组值映射到M11的表中。h(19) 8h(30) 8h(5) 5h(36) 3h(13) 2h(20) 9h(21) 10h(12) 1。优点实现简单。缺点会出现位置连续冲突的情况。假设hash0hash1hash2位置已经存储数据了后续hash3映射到hash0发现冲突了顺序向后移动到hash1又冲突了再移动到hash2又又冲突了…没完没了了。这种现象叫做**群集/堆积。**所以真正实现哈希表一般不使用开放定址法。二次探测注意二次探测并不是进行两次探测而是二次方查找的探测方式双重探测才是探测两次。如果在某一个位置发生冲突则从该位置依次左右二次方跳跃查找直到找到一个没有存储数据的位置为止如果在探测时走到哈希表尾部则回绕到哈希表头继续探测。hash0 key % M , hash0位置冲突了则⼆次探测公式为hashi (hash0 ± i^2) % Mi {1, 2, 3, …, M/2}⼆次探测当 hashi (hash0 - i^2) % M 时当 hashi 0 时需要 hashi M二次探测实例{19,30,52,63,11,22} 这⼀组值映射到M11的表中h(19) 8, h(30) 8, h(52) 8, h(63) 8, h(11) 0, h(22) 0特点优点实现简单略微优于线性探测。缺点这种方法也算不上特别优秀也可能会出现连续冲突的情况比较中庸吧比上不足比下有余。双重探测第⼀个哈希函数计算出的值发⽣冲突使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值不断往后探测直到寻找到下⼀个没有存储数据的位置为⽌。h1(key) hash0 key % M, hash0位置冲突了则双重探测公式为hc(key, i) hashi (hash0 i ∗ h2(key)) % M i {1, 2, 3, …, M}要求h2(key) M且 h2(key)和M互为质数有两种简单的取值⽅法当M为2整数幂时从[0M-1]任选⼀个奇数当M为质数时h2(key) key % (M - 1) 1保证 h2(key) 与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群若最⼤公约数p gcd(M, h1(key)) 1那么所能寻址的位置的个数为M/P M使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说若初始探查位置为1偏移量为3整个散列表⼤⼩为12那么所能寻址的位置为{1, 4, 7, 10}寻址个数为12/gcd(12, 3) 4双重探测实例{19,30,52,74} 等这⼀组值映射到M11的表中设 h2(key) key%10 1特点优点比较线性和二次探测减少了哈希冲突。缺点实现略微复杂。开放定址法表结构enumState{EXIST,EMPTY,DELETE};templateclass K,class VstructHashData{std::pairK,V_kv;State _stateEMPTY;};templateclass K,class Vclass HashTable{public:HashTable(){}~HashTable(){}private:std::vectorHashDataK,V_tables;size_t_n0;// 数据个数};注意需要给每个存储值的位置加⼀个状态标识否则删除⼀些值以后会影响后⾯冲突的值的查找。如下图我们删除30会导致查找20失败当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE} 删除30就可以不⽤删除值⽽是把状态改为 DELETE 那么查找20时是遇到 EMPTY 就可以正常找到20。h(19) 8h(30) 8h(5) 5h(36) 3h(13) 2h(20) 9h(21) 10h(12) 1扩容一般我们哈希表负载因⼦控制在0.7当负载因⼦到0.7以后我们就需要扩容了。扩容大小按照2倍扩容但是同时我们要保持哈希表⼤⼩是⼀个质数第⼀个是质数2倍后就不是质数了。如何解决⼀种⽅案就是上⾯除法散列中使⽤2的整数幂但是计算时不能直接取模。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法给了⼀个近似2倍的质数表每次取质数表获取扩容后的⼤⼩。inlineunsignedlong__stl_next_prime(unsignedlongn){// Note: assumes long is at least 32 bits.staticconstint__stl_num_primes28;staticconstunsignedlong__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};constunsignedlong*first__stl_prime_list;constunsignedlong*last__stl_prime_list__stl_num_primes;constunsignedlong*poslower_bound(first,last,n);returnposlast?*(last-1):*pos;}key不能取模的问题当key是string、Date等类型时key不能取模那么我们需要给HashTable增加⼀个仿函数这个仿函数⽀持把key转换成⼀个可以取模的整型如果key可以转换为整型并且不容易冲突那么这个仿函数就⽤默认参数即可如果这个Key不能转换为整型我们就需要⾃⼰实现⼀个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每值都参与到计算中让不同的key转换出的整型值不同。string做哈希表的key⾮常常⻅所以我们可以考虑把string特化⼀下templateclass KstructHashFunc{size_toperator()(constKkey){return(size_t)key;}};// 特化templatestructHashFuncstd::string{// 字符串转换成整型可以把字符ascii码相加但是类似abc和bca这样的字符串计算出是相同的值// 使⽤BKDR哈希的思路⽤上次的计算结果乘⼀个质数这个质数⼀般取31, 131等size_toperator()(conststd::stringkey){size_thash0;for(autoe:key){hash*131;hashe;}returnhash;}};templateclass K,class V,class HashHashFuncKclass HashTable{public:private:vectorHashDataK,V_tables;size_t_n0;// 表中存储数据个数}完整代码7.2链地址法开放定址法中所有的元素都放到哈希表⾥链地址法中所有的数据不再直接存储在哈希表中哈希表中存储⼀个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成⼀个链表挂在哈希表这个位置下⾯链地址法也叫做拉链法或者哈希桶。示例{19,30,5,36,13,20,21,12,24,96}h(19) 8h(30) 8h(5) 5h(36) 3h(13) 2h(20) 9h(21) 10h(12) 1,h(24) 2,h(96) 88特点优点比较开放定址法即使存在少量哈希冲突也可以接受可以说解决冲突具有很大的优势了。缺点增加额外的链表空间开销查找效率可能降低。实现较为复杂。扩容开放定址法负载因⼦必须⼩于1链地址法的负载因⼦就没有限制了可以⼤于1。负载因⼦越⼤哈希冲突的概率越⾼空间利⽤率越⾼负载因⼦越⼩哈希冲突的概率越低空间利⽤率越低stl中unordered_xxx的最⼤负载因⼦基本控制在1⼤于1就扩容我们下⾯实现也使⽤这个⽅式。如果极端场景下某个桶特别⻓怎么办其实我们可以考虑使⽤全域散列法这样就不容易被针对了。但是假设不是被针对了⽤了全域散列法但是偶然情况下某个桶很⻓查找效率很低怎么办当桶的⻓度超过⼀定阀值(8)时就把链表转换成红⿊树。完整代码