哈希函数算法

MrHe··2 min read

一提到“哈希”，很多人第一反应就是 HashMap。没错，但 HashMap 只是哈希思想的一种顶级应用。今天，我想带你回到原点，看看哈希这个思想是怎么一步步演化，并最终在计算机科学中变得如此重要的。这中间的每一步思维提升，都特别有意思。

场景一：最简单的需求，判断一个数在不在

假设现在我给你 1 亿个 int 类型的数，然后我再给你一个数，让你告诉我这个数在不在这 1 亿个数里。

解法一：暴力，永远的神

我的第一反应，也是最朴素的反应，就是遍历。

public boolean contains(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) {
            return true;
        }
    }
    return false;
}

这方法没毛病，简单直接。但问题也很明显，每次查询都要把整个数组扫一遍，时间复杂度是 O(N)。如果这 1 亿个数是固定的，但查询操作非常频繁，那每次都 O(N) 就太慢了，肯定有优化的空间。

解法二：先排序，再二分

暴力解法的痛点在于“无序”。如果数据是无序的，我们除了一个个看，别无他法。那如果我先让它变得有序呢？

我可以先对这 1 亿个数进行排序，比如用快排，时间复杂度 O(N * logN)。排序之后，每次查询我就可以用二分查找，时间复杂度降到了 O(logN)。

// 伪代码
// 1. Arrays.sort(arr); // O(N*logN) 的预处理
// 2. Arrays.binarySearch(arr, target); // O(logN) 的查询

这已经是个巨大的进步了！查询效率从“线性”级别提升到了“对数”级别。在数据量大的时候，这个差异是天壤之别。但是，还能不能更快？有没有可能做到 O(1) 查询？

解法三：空间换时间，哈希思想的雏形

O(1) 意味着我能一步到位，直接定位到某个位置，看看这个数在不在。这让我联想到了数组。数组的随机访问就是 O(1) 的，arr[i] 一下子就拿到了。

那我能不能准备一个巨大的布尔数组，比如叫 bucket，如果数字 x 存在，我就把 bucket[x] 设为 true。

// 假设数字都是正数且不大
boolean[] bucket = new boolean[MAX_VALUE]; 
// 预处理
for (int num : arr) {
    bucket[num] = true;
}

// 查询
public boolean contains(int target) {
    return bucket[target];
}

你看，查询是不是 O(1) 了？这就是最原始的“直接定址法”。我用数字本身作为地址（下标），直接去一个预设好的空间里找。这就是哈希思想的萌芽。

但问题又来了：

  1. 如果数字很大，比如 10^9，那我根本申请不了这么大的数组。

  2. 如果数字是负数，或者不是整数，比如字符串，那怎么办？

这两个问题，就催生了真正的哈希函数。

哈希函数（Hash Function）的核心作用就是映射。它负责把一个很大范围、或者不方便直接做下标的输入值（Key），转换成一个固定范围内的、可以做下标的输出值（哈希值/哈希地址）。

比如，我可以简单地用取模运算来把大数映射到小范围：hash(key) = key % ArraySize。

这样，不管 key 是 100 还是 10_0000_0100，只要我的数组大小是 1000，它们都会被映射到 0-999 这个范围内。

场景二：哈希冲突，一个无法回避的问题

当我使用 key % ArraySize 这种方式时，一个新的问题出现了：不同的 key 可能会得到相同的哈希值。比如 key1 = 7, key2 = 1007，如果数组大小是 1000，那么 7 % 1000 = 7，1007 % 1000 = 7。两个不同的数，被映射到了同一个位置。这就是哈希冲突（Hash Collision）。

冲突是不可避免的，因为你把一个大范围的数映射到一个小范围，必然会有多个数挤在一个位置上。那么，怎么解决冲突？这才是哈希表设计的精髓。

解法一：拉链法 (Chaining)

这是我最先想到的，也是 Java HashMap 采用的方法。思路很简单：既然一个位置可能要放多个元素，那我干脆不让这个位置只存一个元素了，我让它存一个“容器”，比如链表。

所有哈希到同一个位置的元素，都扔到这个位置的链表里。

  • 存入：计算 key 的哈希值，找到对应的数组下标。把 (key, value) 封装成一个节点，挂到这个下标对应的链表后面。

  • 查找：计算 key 的哈希值，找到对应的数组下标。遍历这个下标的链表，找到 key 相同的节点。

当链表长度很短时，查询效率接近 O(1)。但如果脸黑，所有 key 都哈希到同一个位置，那哈希表就退化成了一个链表，查询时间复杂度又回到了 O(N)。所以，一个“好”的哈希函数，必须能让数据尽可能地均匀分布，以避免这种情况。

解法二：开放地址法 (Open Addressing)

拉链法是“向外发展”（挂个链表），开放地址法则是“向内探索”。它的核心思想是：如果计算出的位置 i 已经被占了，那就按照某种规则去探测下一个空位。

  • 线性探测：如果位置 i 被占，就看 i+1，还被占就看 i+2，直到找到一个空位。缺点是容易产生“聚集”现象，一片连续的位置都被占了，导致探测时间变长。

  • 平方探测：如果位置 i 被占，就看 i+1^2, i-1^2, i+2^2, i-2^2... 这种方式能更好地打散聚集。

  • 二次哈希：准备两个哈希函数 h1 和 h2。如果 h1(key) 冲突了，就尝试 (h1(key) + 1 * h2(key)) % size，再冲突就尝试 (h1(key) + 2 * h2(key)) % size...

开放地址法的好处是不需要额外的链表结构，对 CPU 缓存更友好。但它实现起来更复杂，删除元素时也比较麻烦（不能直接删，要做个标记，否则会截断探测路径）。

解-N：一个好的哈希函数长啥样？

上面所有优化的前提，都是哈希函数本身要足够好。一个好的哈希函数应该具备两个基本特点：

  1. 高效性：计算速度要快。

  2. 均匀性：对任意 key，它计算出的哈希值都能等概率地分布在整个哈希空间，最大限度地减少冲突。

Java 的 String.hashCode() 就是一个经典的设计。它使用的计算公式是 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]。为什么选 31？因为 31 是个不大不小的质数，而且 31 * i 可以被虚拟机优化成 (i << 5) - i，位运算比乘法快。这些都是工程上的智慧。

场景三：思维升华，当内存极其有限时

现在，难度升级。我有 100 亿个黑名单 URL，每个 URL 平均 64 字节。现在给你一个 URL，判断它在不在黑名单里。要求：内存使用不能超过 1GB。

HashSet 肯定是不能用了。100 亿 * 64 字节，这得几百 GB 的内存，直接爆了。

解法一：磁盘方案（外排序/B+树）

内存不够，硬盘来凑。我可以把这 100 亿个 URL 存在文件里，然后通过外排序或者构建类似数据库索引（B+树）的方式来加速查询。但这势必导致大量的磁盘 I/O，查询速度肯定很慢。有没有纯内存的方案？

解-最终幻想：布隆过滤器 (Bloom Filter)

这时候，哈希思想就要出来救场了，而且是以一种极其巧妙的方式。布隆过滤器，你可以把它看作是哈希思想的“概率性”延伸。

它的思路是这样的：

  1. 我申请一个超大的位图（BitSet），比如 10G bits（注意是 bit，不是 Byte），大概就是 1.25GB，满足内存要求。初始时所有位都是 0。

  2. 我准备多个（比如 k=3 个）不同的、相互独立的哈希函数。

  • 加入黑名单：对于每个 URL，我用这 3 个哈希函数分别计算出 3 个哈希值。然后把这 3 个哈希值作为位图的下标，将对应的位都置为 1。 hash1(url) % size -> bit[i] = 1 hash2(url) % size -> bit[j] = 1 hash3(url) % size -> bit[k] = 1

  • 查询：对于一个要查询的 URL，同样用这 3 个哈希函数计算出 3 个哈希值 i, j, k。然后去看位图：

    • 如果 bit[i], bit[j], bit[k] 中有任意一个为 0，那么这个 URL 绝对不在黑名单里。因为如果它在，当初加入的时候肯定会把这三个位都置为 1。

    • 如果 bit[i], bit[j], bit[k] 全部都为 1，那么这个 URL 大概率在黑名单里。

为什么是“大概率”？因为这 3 个位被置为 1，可能是由其他多个 URL 共同作用的结果，恰好把这几个位置亮了。这就是“假阳性”（False Positive）。

布隆过滤器的特点：

  • 空间效率极高：它不存原始数据，只存哈希后的比特位信息。

  • 查询速度极快：几次哈希计算和内存访问，都是 O(k)，

  • 存在误判率：它返回“在”的时候，可能是不在的。但它返回“不在”的时候，一定是真的不在。

在黑名单过滤、爬虫 URL 去重、缓存穿透等场景，这种“宁可错放，不可漏过”的特性简直是神器。它可以用极小的代价过滤掉绝大部分的无效请求。

总结

从最简单的数组暴力查，到排序二分，再到用哈希思想做直接映射，然后为了解决地址冲突问题，发展出拉链法和开放地址法，并意识到一个好的哈希函数的重要性。最后，在内存受限的极端场景下，哈希思想又变身为布隆过滤器，用概率换空间。

整个过程，其实就是不断在时间、空间、准确率这三者之间做权衡和取舍。技术方案没有绝对的好坏，只有适不适合。理解哈希函数，不仅仅是会用 HashMap，更是理解这种“映射-冲突-权衡”的核心思想，这才是算法思维的乐趣所在。

  • #5zoi5bim5ye95pww