如果你第一次翻开《算法笔记》胡凡、曾磊第4.2节大概率会被“散列”这个名词劝退——说实话我第一次看的时候也差点跳过去觉得这又是一个数学味很重的概念。但后来刷题刷多了才反应过来这一节其实是全书写得最“实用”的地方之一散列Hash说人话就是“用一个设计好的函数把不好直接比较、不好定位的数据映射成一个方便存储和访问的整数然后用数组下标去干活”。这篇内容不打算复述教材而是站在“读完了4.2节并且拿它去解了一堆题”的角度把散列的来龙去脉、代码写法、冲突处理、实战场景和踩坑经历一次讲透。无论你是刚翻开这本书的竞赛入门选手还是刷LeetCode想补基础这篇都能给你省下不少摸索时间。1. 散列到底在解决什么问题先看一道经典题1.1 暴力查找的困境先来一道几乎所有算法书都会用的入门题给出N个正整数再给出M个询问每次询问一个数x判断x在这N个正整数中是否出现过。N和M都可以到10^5级别。如果你老老实实对每个询问都遍历一遍原数组复杂度是O(NM)。N和M各是10^5的时候总操作量是10^10绝大多数OJ一秒跑不完运气好也要几十秒。这就是所谓的“超时”——不是程序写错了是算法本身太慢了。这时候自然有人会想能不能开一个大数组比如a[100000]让a[x] 1表示x出现过a[x] 0表示没出现过预处理的时候遍历一遍原数组把对应下标置1查询的时候直接看a[x]是不是1。这样一来预处理的复杂度是O(N)每个查询是O(1)整体变成O(NM)。这个想法就是散列最朴素的原型。你不用管它叫什么名字先记住这个“直接用值当下标”的动作。1.2 《算法笔记》4.2节是怎么串这条线的《算法笔记》4.2节的安排很有意思它没有上来就讲哈希表的完整结构而是从“空间换时间”的直观思路切入然后逐渐展开散列函数、冲突处理、字符串散列。这样做的最大好处是你不需要先学一堆数据结构就能立刻用散列思想解题。等你以后学到哈希表、unordered_map会发现底层不过是这节内容的工程化变体。书里先讲的是“直接定址法”也就是刚才那个a[x]的思路。接着讲“除留余数法”应对“x太大、直接开数组开不下”的情况。然后就自然地引出冲突问题——两个不同的key算出了同一个下标怎么办。最后专门讲字符串的散列因为刷题时最常见的不是数字而是字符串的统计、判重、映射。这节内容不多但串起了散列的完整思维链。我建议你读的时候不要把目光只停在“能用map搞定”的舒适区里而是跟着书里的思路把底层原理过一遍。后面的题你会回来感谢这个决定的。2. 从暴力到O(1)散列的精髓是空间换时间2.1 直接定址法最简单也最容易被忽视先说说直接定址法。它的定义不复杂如果key是整数而且范围不大直接令H(key) key或者H(key) key - a其中a是一个偏移常量让散列值落在数组下标范围内。举个例子统计一次考试中0到100分每个分数出现了多少次。开一个int cnt[101]读到分数s就cnt[s]。这不算什么高级操作但它就是散列。很多人学了“正规”散列之后反而忘了这种最原始的玩法觉得“这不是数组吗算什么散列”其实它的本质就是“以key本身作为存储位置”是散列思想中最直接、最高效的形态。在竞赛和面试里直接定址法的出场率远比你想象的高。比如判断一个字符串里有没有重复字符最简单的方法就是开一个bool vis[256]遍历字符时把ASCII码对应的位置标记一下。这比排序、比set都要快得多。2.2 从bool数组到计数数组直接定址法有两种常见用法很多人一开始分不清。第一种是“有没有”开bool数组。比如判断某个数是否出现过出现过置true。第二种是“有几个”开int数组。比如统计每个数字出现的次数读到一次就。这两种用法的差别就在数组类型上但解决的问题完全不同前者是存在性判重后者是频次统计。// 存在性判重 bool vis[100000]; for (int i 0; i n; i) { cin x; vis[x] true; } // 频次统计 int cnt[100000] {0}; for (int i 0; i n; i) { cin x; cnt[x]; }在刷题时很多题表面上是“统计出现次数”实际上考察的就是这个最简单的散列思想。我见过不少人一上来就写map其实一个数组就解决了而且快一个数量级。2.3 空间换时间到底换的是什么直接定址法能成立的前提是key的取值范围不能太大。比如key是0到10^7之间的整数开一个int a[10000000]占40MB内存大部分OJ都能接受。但如果key是0到10^9开数组就是4GB直接内存爆炸。这就是散列的第一性原理空间换时间。你想查询O(1)就得腾出一块和key取值范围相当的内存当“舞台”。如果取值范围太大直接定址法不划算这时候才需要设计更紧凑的散列函数把大范围的key压缩到一个可控的数组或表里。所以散列函数的作用本质上是在“空间开销”和“冲突概率”之间找平衡。很多人学散列只记住了“O(1)”忽略了它背后的代价。真到了内存受限的题目里你就会发现散列不是银弹它需要你根据数据范围做取舍。这个认知比记住几个函数重要得多。3. 散列函数怎么设计从数字到字符串3.1 除留余数法模数怎么选当key的范围太大直接开数组不现实时最常见的做法是除留余数法H(key) key % mod让散列值落在0到mod-1之间然后开一个大小为mod的数组。这里有个很容易被忽略的细节mod怎么选书里的建议是mod取一个小于等于表长数组长度的素数。为什么是素数因为如果mod是合数那取模的分布会不均匀。举一个直观的例子如果mod 12那么所有偶数key取模后只能是偶数下标所有3的倍数key取模后也只能是3的倍数下标很多槽位永远不会被用到冲突自然就多了。而素数能和大多数key的公因子都变成1分布更均匀。实际竞赛里常把mod设成10^5 3、10^5 7、10^9 7这种素数。一方面是够大另一方面素数的取模特性让分布更均匀。如果你偷懒随便设一个mod等遇到特殊构造的数据散列值就会大量撞车程序整体退化到时候哭都来不及。3.2 字符串hash把字符串变成26进制数字符串本身不是整数不能直接当下标。最常见的思路是把字符串看成是一个k进制的数然后把它转成十进制整数。比如一串只包含小写字母的字符串就可以看成26进制数A到Z对应0到25然后从左到右逐位转换。int hashFunc(char S[], int len) { int id 0; for (int i 0; i len; i) { id id * 26 (S[i] - a); } return id; }这个函数的本质就是“进制转换”空串的值是0每次读入一个字符就把已有的值乘以进制再加新字符的值。比如abc的处理过程就是(0 * 26 0) * 26 1 1再乘26加2 28。整个过程和把123从十进制转换成整数一模一样只是进制从10换成了26。理解这一点字符串hash就不难了。如果字符串里既有大写字母、又有小写字母和数字可以把字符集扩大到62位大写A-Z对应0-25小写a-z对应26-51数字0-9对应52-61然后用62进制转换。代码逻辑完全相同只是换字母表。3.3 hash值怎么存int与long long的溢出问题字符串一长id就会变得非常大。26进制的abcdefghij就已经超过int范围了如果字符串再长一点连long long都扛不住。这个问题有两条路可以走。第一条是取模每算一步都对某个素数取模hash值永远控制在可控范围。代价是不同字符串可能算出同一个hash值也就是碰撞。第二条是用unsigned long long自然溢出让乘法超过64位时自动截断相当于对2^64取模。这种写法在竞赛里很常见因为大多数时候碰撞概率足够低而且写起来简洁。// 取模版 const int MOD 1000000007; int hashFunc(string s) { int id 0; for (char c : s) id (1LL * id * 26 (c - a)) % MOD; return id; } // 自然溢出版 typedef unsigned long long ull; ull hashFunc(string s) { ull id 0; for (char c : s) id id * 26 (c - a); return id; }我的建议是平时练习用取模版更安全、可控参加竞赛图省事可以用自然溢出版。但无论如何你都要知道hash的碰撞是“概率事件”而不是“绝对不会发生”。后面我会专门讲碰撞带来的坑。4. 冲突处理线性探测、平方探测与链地址法的取舍4.1 冲突不可避免那就处理它哪怕散列函数设计得再好只要数组长度有限两个不同key就可能算出同一个下标。这背后是鸽笼原理N1个鸽子放进N个笼子至少有一个笼子有两只鸽子。当插入的数据量接近表长时冲突几乎必然发生。很多人初学散列时会天真地想那我让数组开得足够大不就行了但数组开得再大只要数据量超过表长冲突照样会出现只是时间早晚的问题。所以冲突处理不是“要不要做”的问题而是“怎么做”的问题。《算法笔记》4.2节主要讲了三种线性探查法、平方探查法、链地址法。我来逐个拆解并说说哪些适合面试手写、哪些适合竞赛。4.2 线性探查法Linear Probing线性探查的核心思路很简单如果hash值对应的槽位已经被占了就往后一个一个找直到找到空位。查找时也同理从hash值位置开始往后找直到找到目标或者遇到空位。int table[MAXSIZE]; void insert(int key) { int idx key % MAXSIZE; while (table[idx] ! EMPTY) { idx (idx 1) % MAXSIZE; // 线性往后走 } table[idx] key; } bool search(int key) { int idx key % MAXSIZE; while (table[idx] ! EMPTY) { if (table[idx] key) return true; idx (idx 1) % MAXSIZE; } return false; }这实现起来几乎没有门槛但有一个很容易踩的坑删除。如果你把一个槽位直接置空那后面那些因为冲突而往后挪的元素就“断链”了——查找的时候明明元素还在却因为中间出现一个空位而提前终止。正确的做法是给槽位打“已删除”标记而不是真删。这个坑我当年考试时踩过一次印象深刻。4.3 平方探查法Quadratic Probing线性探查有个明显问题一旦某一片区域满了新来的元素会一直往后挤形成“聚集”让冲突区域越来越大。平方探查就是为了缓解这个问题第i次探测不是往后走i步而是走后i²步。具体来说如果H(key)位置被占就依次尝试(H(key) 1²) % T、(H(key) 2²) % T……直到找到空位。这样即使一群元素都映射到同一个区域它们的探测路径也会迅速分散开不容易形成连续拥堵。平方探查的缺点是它并不能保证只要表里有空位就一定能找到。当表长或探测次数不合适时可能会陷入循环理论上永远找不到空位。在实际写代码时通常会把探测步数限制在表长以内或者选一个合适的表长来规避这个问题。4.4 链地址法拉链法链地址法的思路完全不同每个数组下标不再是存一个元素而是挂一条链表。冲突的元素都放在同一个下标的链表中。查找时先算下标再沿着链表顺序找。vectorint table[MAXSIZE]; void insert(int key) { int idx key % MAXSIZE; table[idx].push_back(key); } bool search(int key) { int idx key % MAXSIZE; for (int x : table[idx]) { if (x key) return true; } return false; }拉链法的优点非常突出实现简单、删除容易链表删节点就行不需要打标记、对表长度不那么敏感。C STL里的unordered_map底层用的就是链地址法的工程化版本。所以如果你理解了拉链法再去看unordered_map的复杂度保证会非常有感觉。4.5 三种方法怎么选我自己刷题的经验是手写散列表的场景其实很少大多数时候用STL容器就够了。但如果面试或考试要求手写开放定址法线性、平方更容易被考察因为它在连续数组上操作概念清晰、代码短。拉链法适合真正需要频繁删除的场景。一个容易被忽略的事实是开放定址法和拉链法的性能差异在数据量接近表长时会急剧放大。开放定址法在表快满时冲突率会指数级上升而拉链法只在链表变长时线性退化。所以如果你在实现一个长时间运行的数据结构拉链法通常更稳。但在竞赛里的临时数组开放定址法完全够用。5. 实战用散列思想啃下几类高频题目5.1 统计N个字符串中每个字符串的出现次数这道题几乎是字符串散列的标配。给N个字符串每个串由小写字母组成问每个串出现几次。如果你用map复杂度是O(N × L × logN)L是字符串长度如果用散列先把字符串hash成一个整数再开一个计数数组或unordered_map复杂度就是O(N × L)。#include iostream #include unordered_map using namespace std; int main() { int n; cin n; unordered_mapstring, int cnt; for (int i 0; i n; i) { string s; cin s; cnt[s]; } // 输出出现次数超过1次的字符串 for (auto [s, c] : cnt) { if (c 1) cout s c endl; } return 0; }如果你理解了字符串hash的原理就会明白unordered_map的key虽然不是整数但底层做的其实是同一件事把字符串映射成一个hash值再放进哈希表。学散列之前你只是会用API学完之后你才能判断这个API什么时候效率高、什么时候会退化。5.2 两数之和散列最经典的活用LeetCode第一题“两数之和”是散列思想在“记忆化”上的典型应用。题目给一个数组和一个目标值target要求找出两个数使它们的和等于target。暴力是O(N²)而用散列表边遍历边查可以做到O(N)。核心思路是遍历到每个数x时检查target - x是否已经在哈希表里。如果在就找到了答案如果不在就把x存进哈希表供后面的数查询。vectorint twoSum(vectorint nums, int target) { unordered_mapint, int pos; // 存“值 - 下标” for (int i 0; i nums.size(); i) { int need target - nums[i]; if (pos.count(need)) { return {pos[need], i}; } pos[nums[i]] i; } return {}; }这题的关键不在代码而在于“为什么要存之前见过的数”。散列的O(1)查询让“记住历史”变得几乎没有成本所以你可以在一次遍历中完成原本需要两重循环的事。这种“边遍历边用散列表记录状态”的套路在很多题里都会用到值得形成肌肉记忆。5.3 判断数组是否存在重复元素判断一个数组里有没有重复元素常规做法是排序后检查相邻元素O(N log N)。如果用散列unordered_set可以做到O(N)遍历时把元素加入集合如果发现当前元素已经在集合里说明有重复。bool hasDuplicate(vectorint nums) { unordered_setint seen; for (int x : nums) { if (seen.count(x)) return true; seen.insert(x); } return false; }这题看起来简单但它引出了一个很重要的思考什么时候用排序什么时候用散列如果题目还要求你输出重复元素出现的次数排序后扫一遍和散列统计都行但如果数组很大、内存紧张排序可能更划算因为不需要额外开辟一个哈希表。学会在“时间O(N) 空间O(N)”和“时间O(N log N) 空间O(1)”之间权衡才是核心能力。5.4 散列思想还能去哪排序、去重与查找散列思想不止体现在“哈希表”这一个数据结构里。桶排序就是散列思想在排序领域的体现把数值映射到桶下标再按桶输出。位图bitset也用类似思路只是压缩到了一个bit表示一个值。布隆过滤器更是把散列思想用到了极致用多个hash函数来快速判断“某个元素一定不存在”或“可能存在”。把这些串起来看你会发现散列不仅是一节教材内容而是一种通用的思维框架遇到一个难处理的对象就想办法把它映射成一个好处理的位置或数字。这个思路在并查集、字典树、后缀数组里都能看到影子。所以我在读4.2节时最大的收获不是记住了某个函数而是建立了这种“映射”的思维习惯。6. 我踩过的散列坑与刷题建议6.1 取模冲突导致的随机WA有一道题我至今印象深刻。题目里的key范围是0到10^9我当时图省事直接用key % 100000当下标没有处理冲突。结果程序运行结果时对时错改了半天才发现大量不同的key映射到了同一个下标后来的数据把前面的覆盖了判断结果就变成了“随机正确”。这个坑的本质是取模只是在压缩空间不代表冲突消失了。如果你没有用开放定址或拉链法兜底那取模后相同位置的不同key就会互相覆盖逻辑彻底乱掉。所以我现在的习惯是数据范围不超过10^7时优先用直接定址法最安全。数据范围大、但可以用unordered_map时直接用STL。必须手写散列时一定选好冲突处理策略而不是只写一个取模。6.2 负数下标和数组越界字符串hash的时候如果你处理的是“大写字母小写字母数字”的混合串很容易把字符映射成负数然后下标越界。比如取char和某个字母的差值如果字母表顺序处理得不小心下标会跑到负数区域去。解决方法有两个一是统一字母表顺序确保所有映射值都非负二是给hash值加偏移比如加一个固定的大常数。另一个容易踩的坑是数组开小了把表长设成10^5结果字符串的数量也是10^5几乎每次插入都要冲突。数组一定要比实际数据量稍大一些宁可多开一点也不要卡着边界。6.3 字符串hash在极限数据下的碰撞字符串hash最常见的问题是进制取得太小。比如有人图省事把字符串当作“ascii码相加”来hash那ab和ba会算出同一个值因为加法不区分顺序。还有人用1进制也就是每个字符都当成1那长度相同的字符串全部会碰撞基本等于没hash。正确的做法是选一个至少等于字符集大小的进制。纯小写字母取26大小写数字混合取62。如果还不放心可以取131、13331这种更大的基数碰撞概率会进一步下降。在特别关键的场景比如判重结果需要绝对准确我建议用双hash用两个不同的模数分别算一次两个hash值都相同才认为是同一个字符串。这能把碰撞概率降到几乎可以忽略不计的程度。6.4 刷题路线建议如果你正在跟着《算法笔记》学我建议按这个顺序巩固散列先用直接定址法做几道统计题比如PAT乙级的统计字符、统计数字题把“a[x]”这种操作练熟。然后做字符串hash题。自己写一遍26进制转换的hash函数再换成62进制体会进制对碰撞的影响。接下来手写一遍线性探测和链地址法感受两种冲突处理方式的代码差异。不用练习太多两道题就够。最后才是用unordered_map做几个综合题比如两数之和、字母异位词分组理解STL容器和手写散列的边界在哪里。练习量不需要特别大但每一步都要真的手写而不是看一眼答案。散列属于那种“一看就懂、一写就错”的知识点只有亲手调过冲突、改过越界你才算真正掌握。等到后续学到哈希表、设计哈希集合、实现LRU之类的题目时4.2节打下的底子会帮你省下大量时间。