1. 散列函数到底在“散”什么——写代码前必须想清楚的问题如果你用过哈希表八成经历过一种诡异场景插入数据时一切正常一到查找就频繁命中冲突链表被拉得老长查一次要遍历几十个节点。我第一次遇到这个问题是给一批学号建索引的时候。当时偷懒直接取了个模结果因为表长选得不好同模的学号全挤到一个桶里查找效率从 O(1) 退化成了 O(n)。后来把教科书翻出来老老实实把散列函数的几种构造方法捋了一遍才发现这根本不是玄学而是一套非常具体的选型逻辑。散列函数干的事说白了就是一句话给你要存的每个关键字算出一个数组下标。这个数组呢就是哈希表也叫散列表。你往表里放数据、从表里取数据都靠这个函数定位。所以散列函数的设计质量直接决定了哈希表的查找效率。那什么样的散列函数算好教科书上写的是三条计算简单、地址分布均匀、冲突尽量少。这仨不是并列关系而是有先后顺序的。我个人的理解是首先要保证计算开销足够小因为每条记录插入和查找都要调用一次散列函数其次才是分布均匀因为分布越均匀冲突就越少每个桶的数据量就越平均最后才是各种边界情况下的稳定性。这里补充一个概念冲突。哪怕你的散列函数设计得再好因为关键字的总量通常远大于地址空间两个不同的关键字算到同一个地址是必然会发生的事。构造散列函数的目标不是消灭冲突——那是做不到的——而是尽量让冲突次数少、分布均匀为后面的冲突处理策略留出操作空间。常见的冲突处理有链地址法、开放定址法这些它们和散列函数是两套独立设计但又互相影响。本文聚焦在散列函数本身冲突处理只会在相关位置带一句。构造散列函数的经典方法就是标题里列的那六种直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。这六种方法不是互相排斥的实际工程里经常组合使用。比如先用随机数法得到一个中间值再对 p 取模或者先折叠再取平方的中间位。下面逐个展开每种方法我都会讲清楚三件事它为什么这么做、适合什么场景、有什么坑。2. 直接定址法最朴素的线性映射只适合“连续编号”类数据2.1 公式长什么样直接定址法大概是六种方法里最没“技术含量”的一种公式也最简单H(key) key或者更通用一点H(key) a × key b其中 a 和 b 是常数。这里 a 一般取 1 或一个很小的正整数b 用来做偏移。比如员工编号从 1001 开始你要把地址映射到从 0 开始的数组那就让 b -1001即 H(key) key - 1001。这样编号 1001 的员工的记录就存在数组下标 0 的位置编号 1002 存在下标 1以此类推。2.2 它真正的优势不可能发生冲突很多人看不上直接定址法觉得它太简单。但它的优势是其他方法比不了的它是六种方法里唯一能做到“零冲突”的。因为关键字和地址是一一对应的线性关系每个关键字唯一地占据一个地址不存在两个不同关键字映射到同一个地址的可能。而且它的计算开销是常数级的一次乘法和一次加法就完了比取模、平方、折叠这些操作都要快。在关键字本身就是连续整数、或者可以线性映射成连续整数的场景里直接定址法就是最优解。我举一个实际例子。学校机房的上机座位编号一般是“楼栋号 楼层 序号”这种形式比如 3 号楼 2 层 15 号机编号就是 3215。如果这些编号本身是连续分配的座位总数正好能映射到一个固定大小数组那你完全可以用座位编号直接做数组下标不用任何处理。2.3 直接定址法的致命短板直接定址法的短板一句话总结就是“太挑数据了”。它要求关键字集合的分布范围小且连续或者即使不连续跨度也不能太大。假设你有 5 万个学生学号从 20230001 到 20239999但实际注册用户只有 5 万人。如果用直接定址法H(key) key - 20230000数组就需要开到 9999 个位置实际只用了大约一半空间浪费严重。如果学号是从 20200001 到 20259999跨度变成好几万浪费就更大。更极端一点如果关键字不是整数比如字符串形式的用户名“zhangsan”“lisi”直接定址法完全没法用。所以我在实际项目里直接定址法用得非常少。它更适合一种情况你知道关键字的取值范围并且这个范围不会比实际记录数大太多。如果你拿不准就别用直接定址法考虑后面几种。2.4 使用直接定址法的几个注意点用直接定址法时有几个细节容易被忽略。一个是 a 和 b 的选择要保证“地址不越界”。比如 H(key) key 时关键字的取值范围必须落在 0 到表长减 1 之间。另一个是关键字如果出现负数要注意取绝对值或做偏移。还有一点当关键字不是整数而是字符类型时可以先把字符编码转换成整数再套公式比如 C 语言里字符有 ASCII 码姓名首字母可以转成 65~122 之间的数但这种转换后的范围往往不连续直接用直接定址法会浪费空间更适合后面的方法。3. 数字分析法数据全部已知时让关键字自己告诉你取哪几位3.1 思路来源统计每一位的“信息量”数字分析法的出发点很朴素既然所有关键字都是预先知道的那我就逐个看看每个关键字里各位数字的分布情况挑出那些“变化大、重复少”的位组合起来当作哈希地址。为什么这样做有效你想很多真实场景里的关键字是有规律的。比如学号前几位通常表示入学年份同一个年级的同学这部分完全相同中间位可能是学院代码或专业代码也就有限的几个取值只有最后几位才是真正区分每个学生的序号。如果直接拿整个学号做散列高位那部分信息全是一样的相当于是“无效信息”。但如果把不同的位拆开来看尾号那几位的变化最丰富拿它做地址分布自然均匀。这有点像做数据分析时的“特征选择”思路——把冗余的特征丢掉留下区分度最高的特征。3.2 一个完整的操作过程假设现在有 8 个关键字是我以前给学生作业编号时用过的一批11340 12367 13398 14339 15370 16311 17342 18303第一步列出所有关键字按位拆开统计每一位上各数字出现的次数。这个例子是 5 位数我们可以逐位统计第 1 位全是 1完全没变化。第 2 位1、2、3、4、5、6、7、8 各出现一次分布非常均匀。第 3 位3、3、3、3、3、3、3、3全是 3没变化。第 4 位4、6、9、3、7、1、4、0基本都不同分布好。第 5 位0、7、8、9、0、1、2、3除 0 出现两次外其他各一次分布也好。第二步挑出分布均匀的位。第 2 位、第 4 位、第 5 位合适。如果我们需要三位地址直接取这三个位拼起来得到12 23 33 43 53 63 73 83等一下这里我拼的是第 2、4、5 位第一个数字 11340第 2 位是 1第 4 位是 4第 5 位是 0拼出来是 140。以此类推11340 → 140 12367 → 267 13398 → 398 14339 → 439 15370 → 570 16311 → 611 17342 → 742 18303 → 803你也可以选择把挑出来的位直接相加或组合形成一个地址值。重点是选择哪几位是由数据本身的分布决定的而不是拍脑袋定下来的。3.3 数字分析法的局限关键字必须是静态的数字分析法最大的问题是它要求所有关键字都预先知道并且在运行期间不再变化。因为一旦有新的关键字插入原来统计出来的“均匀位”可能就不均匀了。比如上例里如果后面插进来一条学号 12345第 5 位就变成了 0、7、8、9、0、1、2、3、5数字 0 出现两次分布不再像原来那么理想但还能接受。但如果是一次性插入几百条原来挑出来的位数可能就不再是最优选择。所以数字分析法最适合的场景是“静态关键字集合”比如编译原理里的符号表所有变量名在编译前就已经确定再比如数据字典里的枚举值映射字典构建后不再增删。对于频繁插入、删除的动态场景数字分析法不太好用因为你得不停地重新统计分布。另外还有一个隐含前提关键字本身必须是数字或者能方便地拆成数字位。字符串类型的关键字如果想用数字分析法需要先做一次字符到数字的编码转换但转换后的分布信息不一定能很好地保留原关键字的特征。4. 平方取中法先平方再截取中间位把数据差异“搅匀”4.1 为什么要先平方平方取中法的操作也很简单先把关键字平方然后取平方结果里的中间几位作为地址。关键问题是为什么要取“中间几位”而不是最高位或最低位这里面的道理值得好好说。一个数乘以它自己的时候结果的每一位都会受到原数多个位数的影响。比如 1234 的平方1234 × 1234 1,522,756最后一位 6 只由原数的个位 4 决定最前面的 1 只由原数的最高位 1 决定。但中间那几位比如百位和千位上的数字是原数各个位数交叉相乘加总后进位得到的几乎跟原数每一位都有关系。也就是说平方之后中间几位把整个关键字的信息都“揉”进去了相当于做了一次均匀化处理。这和随机数发生器里“先放大后截取”的思路一模一样。如果只取最高位或最低位那跟直接用原数的某一部分没区别信息量不够分布也不均匀。平方取中法的精妙之处就是用一次平方运算把低位和高位的差异都扩散到中间位。4.2 到底取哪几位怎么定假设哈希表长 m 1000需要三位地址。那计算过程就是将关键字平方。观察平方后的位数。取中间的三位。以 1234 为例平方后是 1522756共 7 位。中间三位从第 3 位到第 5 位是 227。那么地址就是 227。再试一个关键字 2048平方后是 4194304共 7 位中间三位是 943。这里有个细节如果平方后位数是偶数中间两位怎么取比如 9876 的平方是 975353768 位数。中间两位按从高位往低位数的第 4、5 位是 35。这时候系统中必须约定一个统一的规则比如“取中间偏左的两位”或“取中间偏右的两位”只要全系统一致就行。我习惯统一取从第 (位数/2 - 1) 位开始的两位避免实现上的歧义。4.3 平方取中法的适用场景平方取中法适合关键字位数中等、预先不知道关键字分布、又希望地址分布尽量均匀的场景。它不需要像数字分析法那样预先掌握全部数据也不依赖关键字是否为连续编号所以适用面比前两种广不少。一个实际例子是内存缓存里用短字符串做键。字符串先被转换成哈希初始值这个初始值往往是一个很大的整数直接用这个整数做地址可能超出数组范围。这时候可以对这个大整数做平方取中把地址压缩到目标范围内同时尽量保持分布均匀。4.4 避坑平方运算溢出平方取中法最大的坑是溢出。你是不是觉得只是个平方运算能有多大问题可如果不注意数据类型溢出会悄悄发生导致平方结果错误取出来的地址也是错的排查起来非常隐蔽。C 语言里 int 通常是 32 位最大值约 21 亿。如果关键字是 10 万左右平方后就是 100 亿一个 int 根本装不下必须用 long long。如果关键字是字符串转换出的哈希值那原值可能达到几百万甚至几十亿平方后更是天文数字普通 64 位整数都可能兜不住。所以用平方取中法之前一定要估算一下关键字的量级。如果关键字达到百万级平方结果是 10 的 12 次方就必须用 uint64_t 这类类型或者采用变通方案先对关键字取小一点的模再平方牺牲一点均匀度换取不溢出。这块建议在实现时加一个断言或者溢出检查别等线上出了问题再追。5. 折叠法关键字太长就拆成几段相加注意两种折法不一样5.1 什么时候该想到折叠法直接定址法太挑数据数字分析法要求静态集合平方取中法怕关键字太大。那如果关键字本身就是个超长数字比如 18 位的身份证号、11 位的电话号码平方后位数得翻倍很容易溢出怎么办这时候就轮到折叠法出场了。折叠法的思路是把一个很长的关键字拆成几段等长的数字然后把这几段数字相加得到的新数字就作为地址或地址的一部分。它相当于“先压缩、再组合”压缩了几位数的长度组合过程又把各段的特征都保留了下来所以分布比直接用低位更好。5.2 移位折叠和边界折叠折叠法有两种常见实现移位折叠和边界折叠区别只在叠加时的方向。先说移位折叠。假设电话号码是 436-555-4601我们把它拆成三位一段436、555、460、1。注意这里最后一段只有一位说明分段后允许有一小段是不满位的处理时直接参与加法即可。然后把这些段相加436 555 460 1 1452取后三位 452就是哈希地址。如果表长是 4 位就用 1452或者处理一下进位。再看边界折叠。同样这段号码从中间折过去把相邻的段反向排列再相加。具体做法是436 倒过来看还是 436因为它本身是回文段555 倒过来还是 555但 460 倒过来是 064。也可以这样理解把数字写在纸上从某一段开始整体折返像折纸一样。这样叠加的结果是436 555 064 1 1056取后三位 056作为地址。边界折叠和移位折叠的结果不一样这是正常的。两种方法没有绝对的优劣关键是边界折叠能进一步打乱顺序性关键字的规律性。如果关键字是连续编号比如 100001、100002、100003移位折叠的地址也会呈现连续规律这时候边界折叠效果更好。所以实际用的时候如果测试移位折叠冲突较多可以试试边界折叠。5.3 折叠法叠加时的两个边界问题第一个问题各段相加后超过了地址位数进位怎么处理。比如上面 436 555 460 1 1452如果我只想要三位地址是直接取低三位 452还是把最高位 1 再和低位相加形成“进位折叠”两种做法都有人用。直接取低位简单直接但会把高位的部分信息丢掉进位折叠即把 452 1 453能多保留一点信息。如果表长是 3 位我更推荐进位折叠因为它多了一点点“随机化”效果。第二个问题分段长度怎么定。一般按表长的量级来定。比如表长在 1000 左右就按三位分段表长在 10000 左右就按四位分段。分段太短折叠后地址范围可能不够分段太长起不到压缩作用。还有个经验是分段最好和表长的位数一致或稍长一点这样叠加后的值能覆盖整个地址空间不会集中在某个区间。折叠法的整体适用面也挺宽。它不要求关键字是连续编号也不要求预先知道全部数据只要关键字是数字且位数比较长就行。对电话号码、身份证号、银行账号这类场景折叠法配合除留余数法一起用效果通常不错。6. 除留余数法工程最常用但那个 p 才是决定命运的参数6.1 公式和它为什么最常用除留余数法的公式简单得不能再简单H(key) key mod p这里的 p 通常是一个小于等于哈希表长 m 的质数或不包含小于 20 的质因子的合数。这个方法的优点是通用性极强不管关键字多大、是整数还是字符串转换来的数值一次取模运算就能得到一个合法的表内地址。计算开销也小现代 CPU 对整数取模有专门的指令常数时间完成。也正因为取模操作通用又廉价工程实线里绝大多数散列函数最后一步都会用一个除留余数法收尾。即便是复杂一点的散列算法比如用随机数法或平方取中法先算一个中间值最后也常常对这个中间值取模把结果压到目标范围内。所以与其说除留余数法是一个独立的方法不如说它是散列函数设计的“基础设施”。6.2 为什么 p 要选质数不能选 2 的幂这是一个特别值得展开的点。前面我提到自己早年吃过亏就是因为表长选了 2 的幂。这里把原因讲透。假设哈希表表长 m 16p 取 16那么key mod 16 实际等价于取 key 的二进制低 4 位key 的高位部分全部被丢弃了如果关键字是连续编号比如 100、101、102……那它们的低 4 位会周期性地重复一共只有 16 种组合。也就是说不管你有多少个关键字最终都会被分到这 16 个桶里冲突概率可想而知。如果换成质数 p 17那就完全不同了。因为 17 和二进制的各个位之间没有整除关系key mod 17 的结果不会简单地落在某几位上而是各个位的信息都被“搅”进了结果里。对于连续关键字取模结果在 0 到 16 之间来回跳动分布会均匀很多。选 p 的一般原则是取一个不大于表长 m 的最大质数并且这个质数不要太接近 2 的幂也不要太接近 10 的幂。比如 m1000p 可以取 997m10000可以取 9973。这样能避免关键字在十进制或二进制下的周期性结构直接反映到地址上。6.3 举个例子算一遍假设表长 m 13p 取 13质数关键字依次是25, 31, 44, 58, 69, 72, 85计算25 mod 13 12 31 mod 13 5 44 mod 13 5 ← 冲突 58 mod 13 6 69 mod 13 4 72 mod 13 7 85 mod 13 7 ← 冲突可以看到14 个关键字对 13 取模必然出现冲突因为地址空间只有 13 个。但分布总体上是分散的。如果换成 p 12非质数那么25 mod 12 1 31 mod 12 7 44 mod 12 8 58 mod 12 10 69 mod 12 9 72 mod 12 0 85 mod 12 1 ← 和 25 冲突冲突次数不一定更多但 p 是偶数时所有偶数关键字取模后只能得到偶数地址奇数关键字只能得到奇数地址这会直接浪费一半的地址空间。所以偶数绝对不能选。6.4 除留余数法和表长 m 的关系除留余数法的输出范围是 0 到 p-1。如果 p m那地址空间只用了 p 个位置表的后 m-p 个位置永远空着。所以 p 一般取“小于等于 m 的最大质数”让地址空间和表长接近减少空间浪费。如果 m 本身就是质数最简单直接 p m。实际工程里的另一个经验是哈希表的装载因子元素个数 / 表长建议控制在 0.7 左右。装载因子太高无论散列函数多好冲突都会明显增多太低空间浪费。确定了装载因子再决定表长 m最后才选 p这是一条固定的设计链路。7. 随机数法看着不靠谱其实有严格的确定性要求7.1 核心思路用“伪随机”代替“解析计算”随机数法的公式是H(key) random(key)这里的 random 不是一个真正的随机数生成器而是一个以 key 为种子seed的伪随机数生成函数。说白了就是给定 key用一套固定的算法算出一个看起来没有规律、但实际上确定性的数值来。很多人第一次听到“随机数法”都会觉得奇怪散列函数要求稳定可复现同一个 key 每次调用必须返回同一个地址用随机数是不是搞错了其实没有。伪随机数生成器的特点是同样的种子永远产生同样的序列。你把 key 当作种子那么每次对同一个 key 调用随机数法得到的结果一定一样不同 key 得到的结果在统计意义上接近均匀分布。它本质上是用一个更复杂的非线性函数替换前面那些方法里的“数学公式”仅此而已。7.2 随机数法的适用场景随机数法在教科书里出现频率不高但在实际工程里有它独特的价值。一是关键字长度参差不齐时。比如你存的是各种长度的字符串短的可能只有一个字符长的可能有几十个字符直接用取模、折叠等方法处理长度差异会导致某些长度的关键字映射到同一个区域。伪随机函数能较好地把不同长度的输入都“搅匀”。二是防御性场景。如果有人恶意构造关键字专门攻击你散列函数的弱点比如知道你的 p 之后构造一堆 key mod p 都等于同一个值那哈希表就退化成了链表。这时候如果用带随机性的散列函数攻击者无法提前预知结果就能有效规避这类风险。很多语言的标准库在哈希表实现里都加入了这种随机化处理比如用进程启动时生成的随机种子。三是当关键字不是数值时。比如结构体对象作为 key你需要先把对象转成一个整数种子再用随机数法生成地址。C 的 std::hash、Python 的 hash() 底层都有一部分这类思想。7.3 用随机数法要注意的两件事第一伪随机数生成器的质量直接决定了散列效果。普通的 rand() 函数在线性同余法下低位周期性明显直接拿它取模后果很严重。如果代码里要用随机数法最好选择高质量的伪随机算法比如 xorshift、splitmix64 这类或者直接用加密库里的伪随机函数。业界常见做法是用 splitmix64 做默认散列种子生成器它简单、快速、均匀度好。第二确定性必须贯穿始终。同一个 key 在同一进程内多次计算必须得到同一个地址。这意味着不能依赖 time()、getpid() 这类每次运行都会变化的值作为散列函数的一部分。如果需要“每次启动都不同的随机化散列”那必须把随机种子保存在进程启动时的一次性初始化里之后所有调用都用同一个种子否则数据一存一取就对不上了。8. 六种方法放一张表里怎么选——附我的实测检验方法8.1 六种方法横向对比前文逐个拆解完了这里用一张表把六种方法的关键信息收拢起来方便你做选型对照。方法基本操作最大优点主要限制典型场景直接定址法H(key)a×keyb零冲突、速度最快关键字必须连续或范围小连续编号、枚举值数字分析法取分布均匀的若干位地址分布可以做到很均匀需要预先知道全部关键字且静态静态符号表、字典平方取中法平方后取中间几位均匀化效果好不依赖数据分布大关键字平方易溢出中等长度整数的通用散列折叠法分段后叠加适合超长关键字压缩效果好分段规则和进位处理需统一电话号码、身份证号除留余数法key mod p通用性最强开销小p 的选择直接影响冲突率绝大多数哈希表实现随机数法伪随机函数生成抗人为构造适配异质输入依赖高质量伪随机算法字符串散列、安全场景这张表不是死的。实际工程里最常见的是组合使用比如先用随机数法或平方取中法处理关键字得到一个中间整数最后用除留余数法收尾。我自己写缓存模块的时候惯用套路是“散列 取模”两段式设计前半段分散差异后半段压缩范围效果比单用任何一种都稳定。8.2 一个更实用的选型决策思路如果面试或者做项目时拿不准该用哪种方法可以按下面这个顺序快速决策先看关键字是不是连续整数且范围不大——是就直接定址法不是再看关键字集合是不是预先全部已知且固定——是可以优先试数字分析法如果关键字是整数而且不太大平方取中法是个通用选择如果关键字位数很长折叠法更合适如果关键字是字符串或需要防御恶意输入随机数法更稳妥如果哪种都拿不准就用除留余数法先兜底再根据实测冲突率调 p。8.3 我的实测方法不靠感觉用数据说话最后分享一个我非常推荐的验证方式也是我每次设计完散列函数后必做的三件事。第一统计桶长度的最大值和方差。构造一组具有代表性的数据包括连续编号、随机数、周期性编号三组插入到哈希表里然后统计每个桶链表的长度。好的散列函数桶长的最大值不要超过平均装载因子的 2~3 倍。如果出现某个桶特别长说明散列函数有偏向优先怀疑 p 的选择和关键字特征的相关性。第二对连续关键字做专项测试。连续关键字是散列函数最容易暴露问题的一类数据因为它们在天然结构上可能和取模、取中位等方法产生共振。拿 1 到 10000 连续插入观察冲突次数是否明显高于随机数据。第三测试负载因子对冲突的影响。在同一散列函数下分别装入 30%、50%、70%、85% 的关键字记录冲突曲线。如果 70% 之前冲突增长平缓85% 时突然变陡这是正常的如果 50% 就开始陡增说明散列函数分布不够均匀。这一步能帮你决定哈希表什么时候该扩容。我在实际中还有一个习惯每次调整散列函数后同时跑一遍“顺序插入”和“乱序插入”两组测试。因为有些散列函数对插入顺序敏感顺序插入时冲突少乱序插入时冲突暴涨这种函数在工程里稳定性不行。踩过几次坑之后我的体会是散列函数设计不复杂但很容易被低估。直接定址法适合简单场景数字分析法适合静态集合平方取中法适合中等长度的整数折叠法适合超长数字除留余数法通用但 p 要认真选随机数法特殊场景下很能打。真正的难度不在于背下这六种方法而在于面对实际数据时能根据特征快速排除掉不合适的方案再用统计手段验证剩下的方案是不是真的稳。