基础算法集训进入第12天今天的题目是哈希算法。如果说前11天是在练搜索、排序这些“线性思维”那么哈希算法是第一次把时间复杂度打到常数级的大杀器。哈希算法的核心思想并不复杂把任意长度的输入通过一个函数映射成固定长度的输出这个输出俗称哈希值或指纹。听起来像在写密码实际上它每天都在我们身边干活——查字典、做缓存、判重、校验文件完整性。这篇文章既是我的集训笔记也是一份能直接抄作业的哈希实战总结适合正在刷算法题、准备面试的人也适合工程上想彻底搞懂哈希表底层实现的朋友。1. 哈希算法到底在解决什么问题1.1 为什么算法集训第12天必须专门讲哈希在数组里面找一个元素最直接的做法是遍历复杂度O(n)如果数组有序可以用二分复杂度O(logn)。但哈希表在理想情况下能到O(1)这是一个质的飞跃。集训安排到第12天来讲哈希是因为很多看起来毫无关系的题目比如两数之和、最长无重复子串、LRU缓存翻来覆去都在问同一个问题如何快速判断某个东西之前是否出现过。哈希的思路就是给每个对象发一个“门牌号”我把对象放到对应的房间下次找它时不用挨个敲门直接根据门牌号过去拿。这个“门牌号”就是哈希值房间就是哈希表。日常开发中你几乎离不开它Redis的字典、Java的HashMap、Python的dict底层全是哈希表。面试官问哈希不是想听你背概念而是想知道你能不能手工实现一个可用的哈希表以及能不能分析清楚它的边界条件。1.2 三个基础概念散列、碰撞、装填因子先别急着写代码把三个概念理顺后面所有问题都好聊。第一个是散列。散列就是一个映射过程把任意输入通过哈希函数变成固定范围的整数下标。哈希函数的设计目标是让输出尽可能均匀分布。如果所有输入都映射到同一个下标那就退化成一个链表性能直接崩盘。第二个是碰撞。因为输入的空间往往远大于哈希值的空间两个不同的key算出同一个下标是必然的。数学上有个著名的生日悖论哪怕只有23个人两个人同一天生日的概率就超过50%哈希也一样元素一多碰撞一定会出现。所以碰撞不是意外是家常便饭系统设计必须把冲突处理机制做出来。第三个是装填因子也叫负载因子定义为表中元素个数除以桶数组长度。装填因子越高碰撞概率越大太低则浪费空间。工程上一般把阈值定在0.5到0.75之间超过就扩容。理解了这三个概念后面看HashMap源码就不会发怵了。1.3 哈希算法、哈希表和哈希树不是一回事集训时好多人把“哈希”这一个词当成了所有东西其实它分三个层次。第一层是哈希函数算法比如取模散列、BKDR字符串哈希、MD5、SHA系列它们负责计算一个“指纹”。第二层是哈希表也就是把哈希函数和数组、链表结合起来实现快速增删改查的数据结构。第三层是哈希树最典型的是Merkle树它把数据分块后逐层哈希最终汇总成一个根哈希用来校验海量数据的一致性。很多网络热搜词把“哈希树和哈希算法”并列实际上它们不是同一维度。哈希树依赖哈希算法但哈希算法不仅服务于哈希树。初学阶段最容易犯的错误是以为学了哈希函数就懂了哈希表其实面试题中90%的哈希题都考查哈希表的使用和冲突处理。后面我会花一整节来手写哈希表让大家看清这层关系。2. 哈希函数选型与冲突处理知其然也知其所以然2.1 除留余数法一个取模能解决的先别想复杂最朴素的哈希函数就是取模index key % M。这里有个关键细节M怎么取。如果M是10那么所有个位为0的key都会映射到一起比如20、30、40如果M是12能被2和3整除的key也容易扎堆。更坏的情况是key本身有规律比如内存地址、自增ID撞上除数的因子序列分布就会很难看。所以实践里的经验是M选一个“不那么好因子分解”的数首选素数。比如容量997、10007、1000003这类素数比1000、10000、1000000更抗规律性输入。一句口诀是取模的桶数质数优先。当然现在工程上很多人不再纠结素数因为哈希函数内部已经做了足够多次混淆比如Java的扰动函数但算法竞赛和手写哈希表时素数仍然是最简单可靠的选择。2.2 字符串哈希从BKDR到Java的hashCode处理整数时可以取模处理字符串时怎么办常见做法是把字符串看成一个进制数。BKDR哈希就是经典方案初始化哈希值为0遍历每个字符执行h h * seed c最后对M取模。seed一般取31、131、13331这样的素数。为什么用31因为31是奇素数而且31 * n可以写成(n 5) - n编译器优化后速度很快。Java的String.hashCode也是这个思路乘数固定为31所以abc的哈希值是97 * 31^2 98 * 31 99 96354。我在集训里写字符串哈希时踩过最大的坑是忘记处理负数如果seed和字符计算出来的值很大Python里的整数无限大没关系但C的int会溢出变负数最后取模得到负下标。解决办法是先对结果取绝对值或者用无符号整数来中间状态。2.3 碰撞处理拉链法和开放寻址法的取舍碰撞处理是哈希表的核心分水岭。拉链法是数组加链表每个桶挂一条链表冲突的key都挂在同一条链上。Java的HashMap和Redis的dict都采用这个思路。优点是实现简单删除方便缺点是链表太长时需要优化Java在链表长度超过8时会转成红黑树。开放寻址法是冲突后继续向后找空位最常见的是线性探测index (hash i) % M。Python早期的字典用过类似思路它把元素直接放在数组里没有链表指针缓存访问反而友好。但删除时要小心不能随便把位置清空否则会断掉探测链需要打标记或者用别的值占位。对比项拉链法开放寻址法线性探测实现难度低中删除操作直接移除节点需要墓碑标记复杂缓存局部性较差较好对装填因子的敏感度可以到0.75甚至更高超过0.7性能骤降代表实现Java HashMapCPython早期dict、Redis部分场景竞赛里我推荐拉链法因为好写、好调、总算力可控工程上如果内存紧张且数据规模已知开放寻址法也有它的用武之地。3. 从零手写一个哈希表集训第12天的实操记录3.1 需求定义和数据结构设计集训不光是听还得动手。我给自己定了一个小目标用Python写一个支持插入、查找、删除、自动扩容的哈希表不许用dict作为内部存储完全用数组和链表实现。需求拆开就四条put(key, value)插入或更新键值对。get(key)返回键对应的值不存在返回默认值。remove(key)删除键值对不存在时抛异常。自动扩容装填因子超过0.75时桶数量翻倍并把旧数据重新映射。数据结构上用列表套列表外层是桶数组内层每个桶存一个(key, value)对列表。为什么内层用列表而不是手写链表节点因为Python的列表本身就是动态数组当作小链表用完全够代码还简洁。3.2 核心代码实现下面是我的实现附了注释。class HashTable: def __init__(self, capacity8): self.capacity capacity self.size 0 self.buckets [[] for _ in range(capacity)] self.threshold 0.75 def _hash(self, key): # BKDR字符串哈希再对桶数量取模 h 0 seed 131 for ch in str(key): h h * seed ord(ch) return h % self.capacity def _rehash(self): old_buckets self.buckets self.capacity self.capacity * 2 self.buckets [[] for _ in range(self.capacity)] self.size 0 for bucket in old_buckets: for key, value in bucket: self.put(key, value) def put(self, key, value): idx self._hash(key) bucket self.buckets[idx] for i, (k, v) in enumerate(bucket): if k key: bucket[i] (key, value) return bucket.append((key, value)) self.size 1 if self.size / self.capacity self.threshold: self._rehash() def get(self, key, defaultNone): idx self._hash(key) for k, v in self.buckets[idx]: if k key: return v return default def remove(self, key): idx self._hash(key) bucket self.buckets[idx] for i, (k, v) in enumerate(bucket): if k key: bucket.pop(i) self.size - 1 return v raise KeyError(key) def __len__(self): return self.size有一个地方我想特别说明_hash里我用str(key)转字符串是为了让整数和字符串都走同一套BKDR逻辑。如果你确定key全是整数可以换成hash(key) % self.capacityPython内置的整数哈希本身就是个不错的散列函数。3.3 扩容的完整过程与性能实测写完代码不能拍拍手说会了我实测了一轮。用5万条随机字符串分别执行插入、查找、删除记录平均耗时。第一次运行的结果是插入总耗时约120毫秒查找约80毫秒删除约90毫秒。装填因子从0.75触发扩容时耗时会出现一个明显的尖峰因为要重新创建数组并逐个重新计算哈希。这就是为什么大量插入时你会感觉卡一下扩容是免不了的。扩容最容易被忽略的细节是扩容后不能简单地复制旧桶数组必须重新计算每个key的新下标。原因很简单哈希函数是key % capacitycapacity变了同一个key算出的下标就变了。如果直接搬数据会全部找不到。我在第3版代码里曾经偷懒直接旧桶列表接在新桶后面结果get全部扑空排查了整整一下午才发现。4. 从哈希表走出去哈希树、布隆过滤器与一致性哈希4.1 哈希树Merkle树的校验逻辑哈希树不是简单的“树节点存哈希值”最常见的形态是Merkle树。假设你有1万个文件块想确认它们是否被改动总不能把所有数据重新传一次对比。Merkle树的做法是每个叶子存一个数据块的哈希两个相邻叶子的哈希串再拼接起来算一个哈希逐层往上最终得到一个根哈希。只要根哈希一致就可以认为整个数据集没有变化或者至少存在某些问题能被精确定位。区块链的交易校验、Git对象存储、分布式数据库的副本一致性都用到了这个思想。初学者容易把Merkle树理解成“二叉哈希树”对但不完整。它的精髓是任意一个叶子数据变化都会逐层传导到根哈希所以校验时只要比对根哈希就能快速判断“有没有变”再配合树的路径还能准确定位“哪个分枝变了”。4.2 布隆过滤器用多个哈希位图节省内存哈希的一个变种应用是布隆过滤器它用一个位数组和多个独立的哈希函数判断一个元素“一定不存在”或“可能存在”。插入时用k个哈希函数算出k个位置全部置1查询时只要有一个位置是0就说明元素一定不存在如果全部是1只能说可能出现过因为不同元素可能把这位的1撞上了。这个“可能有误判、但绝不漏判”的特性用在哪里最香缓存穿透。当一个百亿级缓存的key被频繁请求每次都在数据库里落空代价极高在缓存前放一个布隆过滤器直接拦住不可能存在的key。现实中Redis、LevelDB、RocksDB都内置了布隆过滤器它们选择hash函数个数和位数组长度时有一套公式。比如要存1000万条数据期望误判率1%位数组大约需要1200万位约14MB内存哈希函数个数约6个。有兴趣可以自己算一遍香农推导没兴趣就先记住结论位数组长度大约为元素量的10到20倍哈希函数个数大约5到7个。4.3 一致性哈希分布式缓存里的哈希算法哈希表现在是单机结构到了分布式场景问题立刻变得不同。假设你有3台缓存节点最简单的做法是hash(key) % 3决定去哪台。这看起来没问题可一旦节点数量从3变成4绝大多数key的取模结果都变了缓存几乎全部失效数据库瞬间被打爆。这就是“缓存雪崩”的导火索之一。一致性哈希的解法是把哈希值空间首尾相连成一个环节点按哈希值分布在环上key也只落到顺时针方向第一个节点上。节点变化时只有环上逆时针一小段哈希范围内的key会受影响其余不动。为了均衡实际工程里还给每个物理节点分配几十个虚拟节点让它们在环上尽量均匀分布。我踩过的坑是虚拟节点太多导致路由表太大反而拖慢查询太少又不够均衡。通常每台物理节点配置100到200个虚拟节点比较合适。线上还要搭配节点健康检查和自动摘除否则挂掉的节点上的key会被虹吸给下一跳一样存在热点风险。5. 算法集训中踩过的坑与排查手册5.1 数组长度选错了为什么1000与997差这么多群里一位朋友在写字符串哈希时用了1000作为桶数逻辑看着毫无问题但随机字符的哈希值总是集中在前100个桶里。后来一查BKDR哈希的乘数31和1000的最小公倍数导致哈希值分布带上了规律性大量结果被折叠到少数几个下标。把1000改成997之后分布立刻均匀了性能也稳了很多。这件事给了我一个教训算法题和工程里一旦需要选哈希表的初始容量不要顺手填1000、10000这种整数优先选质数比如1009、10007。如果硬要用2的幂作为容量那哈希函数就要足够“扰散”让低位和高位充分混合像Java HashMap的(h ^ (h 16))那样。5.2 扩容时漏了rehash数据全部找不到这是我自己真实踩过的。第一次手写哈希表时我把扩容写成“新建一个更大的桶数组把旧桶列表整体复制进去”结果get时返回默认值remove时直接抛KeyError。原因就是前面说的capacity变了所有key的index都变了。这个坑对所有扩容实现都通用。无论选拉链法还是开放寻址法扩容等于重建一个更大的哈希表逐条put旧数据。唯一能偷懒的方式是让哈希函数变成key % capacity且capacity永远为素数但即便如此也还是要重新计算下标。5.3 Python字典的哈希随机化和性能陷阱Python的dict是哈希表但它的字符串哈希默认带随机盐。同一个Python进程里hash(abc)每次调用结果一样换一个进程可能就完全不同。这叫做哈希随机化作用是防止恶意构造大量碰撞来拖慢程序。但这个特性也带来一个问题如果你用Python写了一个初赛程序本地跑得好好的提交到OJ上却被卡到头破血流大概率不是因为评测机性能差而是因为两个进程里字符串哈希分布不同导致某一侧碰撞特别多。所以正经算法竞赛手写哈希函数时要自己写BKDR或类似函数不要依赖内置hash()。5.4 哈希碰撞导致的最坏情况再强的哈希函数也防不住恶意输入集中火力攻击同一个桶。比如取模哈希遇到一堆key % M 0的数据时拉链法会退化成长链表单次查询复杂度从O(1)变成O(n)。这就是“选择性碰撞攻击”面试官偶尔会顺着这条思路问你怎么防范。工程上的对策有几种换更强的哈希函数比如SHA系列参与散列给哈希表加随机种子链表长度超过阈值转红黑树或者干脆检测到大量碰撞后重新扩容并更换种子。竞赛里没有攻击者但你必须知道退化是可能发生的模板题样例可能测不出来压力测试一上来就露馅。我测试时故意造了10000条key % 997 0的数据插入耗时暴涨那一刻才真正理解了为什么教科书要反复强调均匀散列。最后分享一个小技巧集训第12天结束我的最大体会是哈希不是一个孤立的知识点它是连接算法与工程的桥梁。你在LeetCode上用它解决两数之和在Redis里用它实现字典在区块链里用它构建Merkle树在同一套思想上只是应用场景变了。还有一个可以立刻用上的技巧手写哈希表时先花两分钟把容量确定成质数把哈希函数从key % M改成(key * 31) % M往往能规避一大半碰撞。别小看这一行很多翻车现场都是从这里开始的。哈希看着简单但真正把每一个细节都落到代码里才算入门了。