【C++第二十二章】哈希与散列

前言 set、map解决的是有序查找而unordered_set、unordered_map解决的是快速查找。二者都能完成插入、查找、删除但底层思路完全不同前者依赖平衡搜索树维护顺序后者依赖hash把关键码映射到存储位置再尽量把查找范围缩小到极小的局部区域。这也是为什么很多场景下unordered_*的平均性能往往优于set/map。因为一旦哈希分布足够均匀查找不再需要沿树逐层比较而是可以直接落到目标桶再在很短的冲突链或探测区间内完成定位。不过哈希并不是“永远更快”的银弹。它换来了无序、依赖哈希函数质量、存在冲突、扩容成本明显、最坏情况性能退化等一系列问题。真正把哈希学明白关键不在于会用unordered_map而在于想清楚三件事为什么要映射、冲突怎么处理、工程上如何把它封装成稳定可用的容器。一. 为什么unordered_*往往更快哈希的核心思想 哈希首先是一种算法思想而哈希表则是用这种思想实现出来的数据结构。它的核心目标非常直接让关键码和存储位置建立关联关系从而减少查找时真正需要比较的数据量。例如在普通顺序结构里查找一个值可能要从头扫到尾在平衡树里查找一个值时间复杂度通常是O(logN)而在理想哈希表里目标位置可以通过哈希函数直接计算出来平均查找复杂度接近O(1)。1.1set/map和unordered_set/unordered_map的核心区别容器底层结构是否有序平均查找复杂度典型特点set/map红黑树等平衡搜索树有序O(logN)支持顺序遍历、范围查询unordered_set/unordered_map哈希表无序O(1)单点查找快但不维护顺序因此若业务强依赖区间查找、排序遍历、上下界查找set/map更合适若更关心单点插入、查找、删除效率unordered_*往往更占优。1.2 哈希快在哪里哈希的本质不是“比较得更快”而是让大部分无关元素根本不用参与比较。一旦 key 被映射到固定桶位真正要处理的范围就被压缩到了局部区域性能自然会更高。 避坑指南哈希表平均很快不代表最坏情况也快。一旦冲突集中哈希表同样可能退化甚至接近线性查找。二. 哈希函数与哈希冲突从直接定址到取模映射 要使用哈希表第一步一定是先解决“如何把 key 映射成位置”的问题。这个映射规则就是哈希函数。2.1 直接定址法如果 key 的范围非常集中而且取值空间不大那么最简单的办法就是直接把 key 当作下标使用。这种方法叫直接定址法。例如若 key 只可能落在0 ~ 9999那完全可以直接开一个长度为10000的数组让table[key]对应这个值的位置。这种方法的优点是极快缺点也很明显一旦 key 分布稀疏空间浪费会非常严重。2.2 除留余数法更常见的哈希方式是把 key 映射到有限范围hashikey%N;这样做的好处是空间可控但副作用也立刻出现不同 key 可能算出同一个位置。这就是哈希冲突。例如99%1099999%109两个不同的 key 落到了同一个位置冲突就产生了。2.3 冲突为什么不可避免只要“关键码空间”比“桶空间”更大冲突在数学上就是无法彻底避免的。哈希表真正能做的不是消灭冲突而是尽量让哈希分布更均匀让冲突发生后仍能高效定位控制装载程度避免局部过度拥挤三. 冲突怎么解决开放定址与哈希桶 哈希冲突出现后核心问题就变成了同一个位置已经被占了新的元素放哪主流方案通常分成两类开放定址法和开散列哈希桶 / 拉链法。3.1 开放定址法在表内继续找空位开放定址法也叫闭散列思路。它的逻辑是当前位置被占用后不额外挂链而是在表里按某种规则继续寻找下一个可用位置。常见方式有两种方式规则特点线性探测hashi i实现简单但容易产生聚集二次探测hashi i^2能缓解连续聚集但实现更复杂3.2 负载因子为什么重要开放定址法能否继续找到位置和负载因子关系极大。负载因子定义为α已存元素个数表长 \alpha \frac{\text{已存元素个数}}{\text{表长}}α表长已存元素个数​当负载因子越来越高可用空位越来越少探测距离就会越来越长插入与查找性能都会明显下降。3.3 哈希桶 / 拉链法把冲突元素挂到同一个桶里开散列的思路更常见让哈希表的每个槽位对应一个桶发生冲突的元素不再继续探测空位而是挂到同一个桶中。keyHash函数桶下标桶内链表/结点序列这种做法的好处是插入逻辑简单删除更自然不需要墓碑标记扩容和重排更容易实现3.4 链过长怎么办若某个桶过长查找效率会下降。工程上通常有两种思路通过合理扩容降低平均桶长在特定实现里对超长桶做进一步优化有些语言实现会在链表过长后转成红黑树以降低最坏情况复杂度但这不是 Cunordered_map的标准要求。在 C 里更常见的实现仍是哈希桶 链式结构。3.5 两种方案怎么选方案优点缺点开放定址数组连续缓存友好删除复杂负载高时性能下降明显哈希桶 / 拉链法插入删除自然扩容灵活结点分散额外指针开销更大在自己实现unordered_set/unordered_map时哈希桶 拉链法通常更容易封装成稳定容器。四. C 中如何封装一个可复用的哈希表 真正自己实现哈希表时难点并不只在“把元素挂进桶里”而在于如何把它做成一个既支持unordered_set又支持unordered_map的通用组件。4.1 通用设计树靠KeyOfT哈希表也一样要靠KeyOfT底层哈希表通常不应直接写死“值就是 key”否则只能支持一种容器。更合理的做法是让哈希表模板存储T同时额外传入一个KeyOfT仿函数用于从T中取出 key。templateclassKstructSetKeyOfT{constKoperator()(constKkey)const{returnkey;}};templateclassK,classVstructMapKeyOfT{constKoperator()(constpairconstK,Vkv)const{returnkv.first;}};这样底层HashTable就能统一支持unordered_setK值本身就是 keyunordered_mapK, V值是pairconst K, Vkey 来自first4.2 泛型哈希函数整型 key 最简单若 key 本身就是整数最直接的哈希函数通常就是把它转成无符号整数再参与映射templateclassKstructHashFunc{size_toperator()(constKkey)const{return(size_t)key;}};真正决定桶位的通常不是这里而是外层再做一次% bucket_count或位运算映射。4.3 为什么string不能简单按地址哈希字符串的相等语义看的是内容不是对象地址。若直接拿c_str()指针或对象地址做哈希同样内容的字符串可能得出完全不同的结果等价性就被破坏了。所以string需要基于字符内容计算哈希值。一个很常见的写法是乘法滚动哈希例如templatestructHashFuncstring{size_toperator()(conststringkey)const{size_t hash0;for(autoch:key){hash*31;hash(unsignedchar)ch;}returnhash;}};这种写法的思想和BKDR类哈希非常接近通过乘一个基数再累加字符值让不同位置的字符都参与结果从而降低简单冲突。4.4 为什么这里用特化而不是随手重载对于类模板哈希器更自然的方式是对特殊 key 类型做模板特化而不是在主模板里强行塞进多个重载版本。原因很简单当K string时HashFuncstring就应该有一套明确且唯一的字符串哈希逻辑。若在主模板里混入多个重载实例化到string时接口语义会变得混乱维护成本也更高。4.5 扩容时不要“重新构造结点”直接挪链更合理哈希表扩容时最笨的做法是把旧表中的元素重新拷贝一遍再在新表里重新插入。这种方法逻辑能跑通但代价偏大会多一次对象构造旧结点还要析构大对象移动成本明显若底层采用哈希桶链表结构更高效的方式通常是直接把旧结点重新挂到新桶里。也就是说重算桶号但尽量复用原有结点本身。4.6 迭代器为什么不能只存Node*红黑树迭代器通常存一个Node*就够了因为通过父子关系就能做中序前驱后继移动但哈希表迭代器不同它不仅要知道当前结点是谁还得知道当前属于哪张哈希表当前在哪个桶当前桶走完后下一桶该从哪里继续因此哈希表迭代器更常见的成员会包含Node*_node;HashTable*_pht;size_t _hashi;4.7const_iterator的一个典型坑权限放大如果const_iterator仍然持有普通的HashTable*那就可能在const场景里绕过限制导致“本应只读却能间接修改容器”的权限放大问题。更稳妥的做法通常是单独设计iterator/const_iterator或者用模板参数把Ref、Ptr、表指针类型一起区分开4.8unordered_*的遍历顺序为什么不要想当然unordered_set/unordered_map的顺序本来就是未指定的。不同标准库实现、不同扩容阶段、不同结点组织方式都可能让遍历结果不同。有些实现会用额外链指针让遍历体验更稳定有些实现则直接按桶和链表顺序走。只要容器语义正确就不应依赖它的“看起来像插入顺序”这种现象。4.9 “素数扩容一定更好”并不是铁律哈希表扩容时桶数选素数是一种常见经验目的是减少某些取模分布下的周期性冲突。但这不是绝对真理。现代实现里也有大量方案会直接使用2的幂次容量再配合高质量哈希函数和位运算优化。是否选择素数更像是实现策略而不是一条放之四海皆准的规则。五. 位图当 key 是整数时比哈希更省空间 ⚠️若 key 本身是整数而且问题只关心“在不在”“出现过没有”那很多场景里其实根本不需要哈希表位图会更直接、更省空间。5.1 位图的核心思想把一个整数是否存在映射成某一位是1还是0。这样一个 key 只需要占1 bit空间效率极高。例如对x的映射第几个整型块i x / 32第几位j x % 32设置该位voidset(size_t x){size_t ix/32;size_t jx%32;_bits[i]|(1uj);}5.2 为什么位图特别适合海量整数判重若要判断一个unsigned int是否出现过理论上值域是2^32。如果用位图表示总共只需要232 bits229 bytes512MB 2^{32} \text{ bits} 2^{29} \text{ bytes} 512\text{MB}232bits229bytes512MB这个空间虽然不小但比把40亿个整数完整存下来小得多也比排序加查找更适合某些判存在题。5.3 左移和右移到底在干什么位图操作经常和位运算一起出现。这里要分清一个基础概念从低位向高位移动从高位向低位移动这说的是二进制位的位置变化方向和机器是大端还是小端没有关系。大小端影响的是字节在内存中的布局不改变移位运算的逻辑语义。5.4 两个位图如何表达更多状态若一个位不够表示状态就可以用两个位图叠加。例如用两位表示一个整数出现次数状态状态含义00出现0次01出现1次10出现2次11出现3次及以上这样就能解决“找只出现一次的数”“找出现次数不超过两次的数”等变种问题。5.5 交集问题也能这么做若两个文件里都是整数集合可以分别映射到位图中。某个数在两个位图中都为1那它就是交集元素。 避坑指南位图非常省空间但前提是key 必须能自然映射到较小整数范围。一旦 key 是字符串、对象、超大稀疏整数位图就不再合适。六. 布隆过滤器允许误判时的超高性价比方案 ️位图适合整数而字符串等一般对象没有天然下标。这时如果仍然只关心“可能在不在”而且能接受少量误判就可以用布隆过滤器。6.1 布隆过滤器解决了什么问题对于海量字符串、昵称、URL、ID 等对象如果直接存哈希表空间不低还要保存完整元素长字符串比较本身也有成本布隆过滤器则只保留若干位图信息不保存原始元素从而显著降低空间消耗。6.2 它的核心机制是什么插入一个元素时不是只映射一个位置而是通过多个哈希函数映射到多个 bit 位把这些位置都置1。查询时只要有任意一位是0则一定不存在若所有位都是1则说明可能存在这就是它最经典的性质“判断不在是准确的判断在是不准确的。”6.3 为什么映射多个位置能降低误判如果只映射一个位置冲突很容易让不同元素撞在同一位上而映射多个位置后另一个元素要恰好把同一组位置都撞满概率会低得多。6.4 误判率和参数的关系设位数组长度为m插入元素个数为n哈希函数个数为k则布隆过滤器误判率近似为p≈(1−e−kn/m)k p \approx \left(1 - e^{-kn/m}\right)^kp≈(1−e−kn/m)k这意味着m越大误判率通常越低k太少不够分散k太多会把位图过快打满参数设计本质上是在空间、误判率、计算成本之间做平衡。6.5 典型使用场景布隆过滤器特别适合这类场景用户名是否可能已注册URL 是否可能已抓取黑名单 / 白名单的快速前置过滤缓存穿透防护分布式系统中的快速存在性预判6.6 “可能在”之后为什么常常还要查数据库因为布隆过滤器允许误判所以工程上常见流程是先查布隆过滤器若判定“不在”直接返回不存在若判定“在”再去数据库或哈希表做一次精确查询这样既降低了大量无效查询又把误判影响控制在最后一道精确检查上。6.7 为什么一般不支持删除因为一个 bit 位可能同时被多个元素共享。若把某个元素对应的位直接清零其他本来存在的元素也可能被误伤。若确实要支持删除通常需要改成计数型布隆过滤器让每个位不再只存0/1而是存计数值。但这样会带来额外空间成本。 避坑指南布隆过滤器不是精确集合。它适合做“前置过滤”“快速排除”不适合做需要严格准确结果的最终判定。七. 海量数据题怎么落地哈希切分 局部统计 哈希最有价值的地方之一是把原本完全装不下的一大堆数据切成很多能单独处理的小块。7.1 两个超大文件求交集若两个大文件都装不进内存直接整体建set或整体哈希都不现实。这时最自然的办法就是哈希切分。核心步骤如下文件 A 中的 queryHash(query) mod N写入 A0 ~ A(N-1)文件 B 中的 queryHash(query) mod N写入 B0 ~ B(N-1)分别处理 Ai 与 Bi在内存中求局部交集汇总最终结果这套方法成立的关键在于相同的 key一定会被同一个哈希函数切到同一编号的小文件里。所以只需要比较Ai和Bi不需要做跨文件全局比较。7.2 如果小文件仍然太大怎么办那就继续切。也就是说哈希分治可以递归进行直到单个分块能够在内存中完成精确处理。7.3 统计海量日志中的 Top K IP给一个超大日志文件每行一个IP想找出现次数最多的Top K思路依然类似按Hash(ip) % N把所有IP切到多个小文件保证同一个IP一定落到同一个小文件对每个小文件用map/unordered_map做精确计数从每个小文件提取局部高频项最后合并出全局Top K7.4 为什么“相同 IP 一定进同一小文件”这么关键因为只有这样局部计数才不会被分散。若同一个IP被拆到多个文件里局部统计结果就不完整全局合并也会出错。八. 学到这里应该建立怎样的整体框架 如果把这一整章内容压缩成一条主线可以这样理解哈希的目标让 key 和存储位置建立关联冲突不可避免真正要解决的是冲突后的定位效率主流方案开放定址 or 哈希桶C 封装重点KeyOfT、哈希仿函数、字符串特化、扩容重排、迭代器设计整数场景优先考虑位图允许误判场景优先考虑布隆过滤器海量数据场景用哈希做分治切分再做局部精确处理也就是说哈希从来不只是一个容器实现细节它更是一种非常强的空间换时间 分治切分思想。总结 哈希真正强大的地方不在于unordered_map这个类名本身而在于它提供了一种非常通用的建模方式把“全局查找问题”转化成“局部定位问题”。一旦 key 和位置之间建立了高质量的映射关系查找、判重、计数、分桶、切分这些问题都会变得更容易处理。围绕这条主线整章内容其实是在逐层展开用哈希函数建立映射用冲突处理机制维持可用性用哈希桶把容器封装成unordered_set/unordered_map用位图在整数场景下进一步压缩空间用布隆过滤器在可容忍误判时换取更高性价比用哈希切分去处理内存装不下的海量数据问题因此真正学会哈希之后得到的不只是一个容器实现能力而是一整套问题拆解思路能直接映射就直接映射冲突可控就用哈希整数范围小就上位图需要快速排除就上布隆过滤器数据过大就先哈希切分再局部精确处理。这也是为什么哈希在工程实践、面试题和底层容器设计里始终都是绕不开的一章。