2. 哈希函数设计：哈希函数的作用、常见哈希函数、设计原则
好，咱们接着聊哈希表的核心——哈希函数。
说实话，哈希函数就是整个哈希表的灵魂。你想想看，哈希表为什么能实现 O(1) 的查找？说白了，就是靠哈希函数把任意大小的数据，映射到一个固定范围的数组下标上。这个映射做得好，哈希表就高效；做得不好，哈希表就退化成链表。
2.1 哈希函数到底在干什么？
哈希函数的作用，用一句话概括：把任意长度的输入，压缩成固定长度的输出。这个输出，我们通常叫它哈希值、散列值，或者直接叫它索引。
举个例子。假设你有一个数组，大小是 100。你想存一个学号 2024001 的学生信息。哈希函数就是负责把 2024001 这个数字，变成一个 0 到 99 之间的数。比如用最简单的取模：2024001 % 100 = 1。好，这个学生就放在数组下标为 1 的位置。
嗯，这里要注意：哈希函数不是加密。它不要求你能从哈希值反推出原始数据。它只要求两件事：
- 确定性：同一个输入，永远得到同一个输出。
- 均匀性：不同的输入，尽量均匀地分布在整个输出空间。
我在项目中遇到过一个问题：有个同事用了一个很简单的哈希函数，结果大量 key 都映射到了同一个桶里。查询速度从 O(1) 直接掉到了 O(n)。嗯，这就是哈希函数设计不好的典型后果。
2.2 常见的哈希函数
哈希函数有很多种，我挑几个最常用的给你讲讲。这些我都实际用过，踩过坑，也填过坑。
2.2.1 除留余数法
这是最简单、最常用的方法。公式就一行：
index = key % table_size比如 table_size = 16，key = 27，那么 index = 27 % 16 = 11。
但是！这里有个大坑。table_size 的选择非常关键。我个人习惯是：把 table_size 选为质数，或者至少是一个没有小质因数的数。
为什么？你想想看，如果 table_size = 16，而你的 key 全是偶数（比如 2, 4, 6, 8...），那么 2 % 16 = 2, 4 % 16 = 4, 6 % 16 = 6... 所有 key 都映射到了偶数下标上。奇数下标全空着。这均匀性就太差了。
我曾经在一个项目中，table_size 用了 1000，结果 key 全是 10 的倍数。你猜怎么着？所有 key 都映射到了 0, 10, 20, 30... 这些位置上。1000 个桶，只用了 100 个。后来我把 table_size 改成 997（质数），问题就解决了。
2.2.2 乘法哈希
乘法哈希是另一种经典方法。它的思路是：把 key 乘以一个常数，然后取小数部分，再乘以 table_size。
公式长这样：
index = floor(table_size * (key * A % 1))其中 A 是一个 0 到 1 之间的常数。Knuth 老爷子推荐用黄金分割比例的倒数：A ≈ 0.6180339887。
我个人觉得，乘法哈希的好处是：对 table_size 没那么敏感。不像除留余数法，table_size 选不好就出问题。乘法哈希即使 table_size 是 2 的幂，效果也还行。
不过说实话，乘法哈希在工程中用得不如除留余数法多。因为它的计算稍微复杂一点，而且现代 CPU 对取模运算做了大量优化，性能差距已经很小了。
2.2.3 MD5 / SHA 简介
MD5 和 SHA 属于密码学哈希函数。它们跟前面两种完全不是一个量级的东西。
简单说：
- MD5：输出 128 位（16 字节）的哈希值。曾经很流行，但现在已经被证明不安全了。我建议你别在安全相关的场景用 MD5。
- SHA 家族：SHA-1 输出 160 位，SHA-256 输出 256 位。SHA-256 目前还是安全的。
这些密码学哈希函数的特点是：计算慢、输出长、抗碰撞性强。它们不是为哈希表设计的。你想想看，哈希表只需要一个 32 位或 64 位的索引，你拿 SHA-256 算个 256 位的值出来，然后截断用，这不是杀鸡用牛刀吗？
不过，有一种场景我会用：当 key 是字符串，而且字符串很长的时候。比如你要缓存一个很大的 JSON 对象，直接用字符串做 key 太长了。这时候可以先算个 MD5，用 MD5 值做 key。虽然 MD5 不安全，但作为哈希表的 key，碰撞概率已经足够低了。
2.3 哈希函数的设计原则
讲了这么多，我总结几条设计原则。这些原则是我这些年写代码、读源码、踩坑总结出来的。
- 计算要快。哈希函数会被调用无数次。每次插入、查找、删除都要算一次。如果哈希函数本身很慢，那 O(1) 的复杂度就失去了意义。我见过有人用浮点数运算做哈希，那性能简直惨不忍睹。
- 分布要均匀。这是最核心的要求。哈希函数应该把 key 均匀地映射到整个数组空间。如果分布不均匀，冲突就会增多，性能就会下降。
- 确定性。同一个 key，不管什么时候调用，必须返回同一个哈希值。这个看起来是废话，但有些随机性的哈希函数确实存在。除非你有特殊需求，否则别用。
- 对输入敏感。输入稍微变化一点，输出应该完全不同。这叫「雪崩效应」。比如 "abc" 和 "abd" 的哈希值，应该天差地别，而不是只差 1。
- 尽量简单。不要为了追求完美而把哈希函数搞得太复杂。一个简单的除留余数法，配合一个质数大小的表，已经能解决 90% 的问题了。
2.4 知识体系一览
下面这张图，把哈希函数的核心知识点串起来了。你可以对照着看，心里有个全局观。
好了，哈希函数这块就讲到这里。记住一句话：好的哈希函数，是哈希表性能的基石。别在这上面偷懒，否则后面有你头疼的时候。
公众号:蓝海资料掘金营，微信deep3321