hash函数和布隆过滤器

作者

1.Hash函数

1. 选择 Hash 的两个核心标准

图中列出了两点，这是衡量一个哈希算法好坏的金标准：

  • 计算速度快 (High Performance):

    • 在 Redis、Nginx 或高频交易系统中，每一秒可能有百万次哈希计算。

    • MD5 是为了安全设计的，计算繁琐。而 MurmurHash 这类算法是为了速度设计的，它们利用位运算（异或、移位、乘法），在现代 CPU 上快得惊人。

  • 强随机分布性 (Avalanche Effect / Distribution):

    • 这指的是雪崩效应：输入哪怕只改动 1 个 bit，输出的哈希值应该发生巨大的、不可预测的变化。

    • 分布越均匀，哈希冲突（Collision）就越少，哈希表查询就越接近 O(1)。

2. 三大网红算法详解 (面试/工程必备知识)

这三个名字在高性能计算领域如雷贯耳：

(1) MurmurHash (尤其是 MurmurHash2/3)

  • 地位： 它是工业界事实上的标准。

  • 特点： 极快，分布极好。

  • 谁在用：

    • Redis：字典（Dict）结构默认使用 MurmurHash2。

    • Java：Guava 库、Jedis。

    • 大数据：Hadoop, Elasticsearch, Kafka, Cassandra。

  • 场景： 当你不知道选什么时，闭眼选 MurmurHash 通常没错。

(2) CityHash

  • 出身： Google 开发。

  • 特点： 专门针对处理字符串进行了优化。它利用了现代 CPU 的指令集特性，在处理长字符串时，通常比 MurmurHash 更快。

  • 场景： 类似于 ClickHouse 这样的高性能数据库，或者需要大量处理文本哈希的场景。

(3) SipHash

  • 出身： Jean-Philippe Aumasson 和 Daniel J. Bernstein 设计。

  • 核心卖点： 安全 (Security)，防范 Hash Flooding Attack（哈希洪水攻击）。

    • 背景： 以前很多语言（如 Python 2, Java 7）用简单的哈希算法。黑客可以精心构造几百万个不同的字符串，但它们的哈希值完全一样（冲突）。如果黑客把这些数据发给服务器，服务器的哈希表会退化成一个巨大的链表，CPU 飙升到 100%，导致拒绝服务（DoS）。

  • 谁在用：

    • Python 3.4+ 的字典。

    • Rust 的 HashMap 默认就是 SipHash。

    • Go map 的实现也参考了类似的思路。

  • 场景： 面向公网的 Web 服务，必须防止恶意攻击者通过哈希冲突搞垮你的服务器。

2.操作流程

虽然这两个词看起来很简单，但在底层实现（比如 C++ 的 std::unordered_map 或 Java 的 HashMap）中，它们涉及了一系列精密的步骤。

结合你前面发的关于“Hash 函数”和“负载因子”的图片，以下是这两个流程的标准工业级实现逻辑：

1. 插入流程 (Insert)

当你执行 map["key"] = value; 时，后台发生了什么？

  1. 计算哈希值 (Calculate Hash):

    • 调用哈希函数（比如 MurmurHash），将你的 Key（如字符串 “apple”）转换成一个巨大的整数 hash_code。

  2. 定位桶索引 (Map to Bucket Index):

    • 将 hash_code 对数组长度取模（index = hash_code % array_size），算出它应该放在数组的第几号格子里（这个格子叫 Bucket/桶）。

  3. 处理冲突 (Handle Collision) —— *关键步骤*:

    • 检查： 看看这个格子里是不是已经有别人了？

    • 如果为空： 直接把 Key-Value 放进去。

    • 如果不为空（发生哈希冲突）：

      • 拉链法 (Chaining): 像 C++ STL 那样，把新元素挂在这个格子的链表后面（或者红黑树上）。

      • 开放寻址法 (Open Addressing): 往后找下一个空位插进去。

  4. 检查负载因子 (Check Load Factor):

    • 插入完成后，算一下 当前元素总数 / 数组长度。如果超过阈值（如 0.75），触发扩容（Rehash），把所有数据搬到更大的新数组里。

2. 搜索流程 (Search)

当你执行 auto it = map.find("key"); 时，后台发生了什么？

  1. 计算哈希值 (Calculate Hash):

    • 必须使用和插入时完全相同的算法，对 Key 再次计算哈希值。

  2. 定位桶索引 (Map to Bucket Index):

    • 同样通过取模，直接“空降”到对应的数组格子上。这一步是 O(1) 的，非常快。

  3. 遍历比对 (Traversal & Comparison):

    • 找到了格子不代表找到了数据（因为可能有哈希冲突）。

    • 必须在这个格子的链表（或红黑树）中，逐个比较 Key 是否完全相等（调用 operator== 或 equals()）。

    • 这就是为什么自定义类做 Key 时，既要写 Hash 函数，也要重载 == 运算符。

  4. 返回结果:

    • 如果比对成功，返回 Value。

    • 如果链表走完了还没对上，说明 Key 不存在。

3.冲突

1. 冲突产生原因 (Cause of Conflict)

  • 原理： 哈希表的本质是将“无限”的输入空间（比如所有可能的字符串），映射到“有限”的输出空间（数组下标）。

  • 现象：

    • Key A (“Apple”) 经过哈希计算 -> Index 5

    • Key B (“Banana”) 经过哈希计算 -> Index 5

    • 这两个完全不同的 Key 抢占了同一个坑位，这就是冲突。

2. 负载因子 (Load Factor)

  • 图中标注它用于 “描述冲突激烈程度”。

  • 逻辑：

    • 就像一辆公交车，如果只有 1 个人（负载因子低），随便坐，几乎不会有人抢同一个位置。

    • 如果车上已经坐了 90 人（负载因子高），新上来一个人，很容易发现想坐的位置已经被占了，不得不去寻找其他位置或挤在一起。

  • 结论： 负载因子越高，冲突概率呈指数级上升，性能下降越快。

3. 解决冲突 (Resolve Conflict) —— 核心重点

既然冲突不可避免，工程上必须有方案来处理它。主流方案主要有两种：

方案 A：链地址法 (Chaining / Open Hashing)

  • 这是最常用的方案（C++ STL std::unordered_map 和 Java HashMap 都在用）。

  • 原理： 数组的每个格子里存的不是数据本身，而是一个链表的头指针。

    • 如果 Index 5 被占了，新来的元素就挂在 Index 5 的链表后面。

    • 如果链表太长（比如 Java 8 中超过 8 个），为了防止查询变慢，链表会自动进化成红黑树，将查询复杂度从 O(n) 优化回 O(\log n)。

  • 优点： 简单，对高负载因子的容忍度较高。

  • 缺点： 链表指针跳跃，对 CPU 缓存（Cache）不友好。

方案 B：开放寻址法 (Open Addressing / Closed Hashing)

  • 这是高性能库（如 Google Abseil, Python Dict）常用的方案。

  • 原理： 数组里只存数据，不存指针。如果 Index 5 被占了，我就按规则去找下一个空位。

    • 线性探测 (Linear Probing): 看看 Index 6 空不空？不空看 Index 7…

    • 二次探测 (Quadratic Probing): 跳着找，防止数据扎堆。

  • 优点： 数据都在数组里，内存连续，CPU 缓存命中率极高，速度极快。

  • 缺点： 非常依赖负载因子。一旦满了，性能会雪崩式下跌（通常负载因子到 0.5 或 0.6 就要扩容）。

4.布隆过滤器

第一部分：布隆过滤器 (Bloom Filter)

1. 核心口诀

“说存在，不一定存在；说不存在，一定不存在。”

2. 核心参数与权衡

笔记中列出了 n, p, m, k 四个变量，它们的关系是互相制约的：

  • n (数据量): 你要存多少个元素。（这是前提，不能动）

  • p (误判率): 你能容忍多大的误差？（越小越好，但代价是空间越大）

  • m (位图大小): 内存占用。

  • k (Hash函数个数): 计算成本。

面试考点：

  • 如果 m (空间) 给定，n 增加，p (误判率) 会怎么变？ -> 变大（因为坑位更挤了）。

  • k (Hash次数) 是不是越多越好？ -> 不是。k 太少误判率高；k 太多会拖慢速度，且更容易把位图填满（导致误判率反而上升）。

3. 为什么不支持删除？

笔记里提到了“计数无法回溯”。

  • 通俗解释： 就像很多人共用一把钥匙（Hash 映射的位），如果你因为 A 离开了就把钥匙扔了（置为 0），那么 B、C、D 也回不了家了。

  • 扩展知识： 如果非要支持删除，可以使用 Counting Bloom Filter (计数布隆过滤器)，把 Bit 变成 Counter（计数器），但空间消耗会变成原来的 3-4 倍。

4. 代码解析：双重哈希优化 (Double Hashing)

笔记末尾的代码片段其实是布隆过滤器中生成 k 个 Hash 位置的经典优化写法：

// 这是一个非常经典的优化：不需要真去找 k 个不同的哈希函数
// 只需要 2 个哈希值 (hash1, hash2)，就能模拟出 k 个位置
uint64_t hash1 = MurmurHash2_x64(key, len, Seed); 
uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1));
​
for (i = 0; i < k; i++) 
{
    // 公式：Hash_i = (Hash1 + i * Hash2) % m
    Pos[i] = (hash1 + i*hash2) % m; 
}

  • 为什么要这样做？ 计算一次 MD5 或 MurmurHash 是有成本的。如果 k=10，真的算 10 次哈希会很慢。这种利用线性探测公式的方法，只需要算 2 次哈希，就能生成足够随机的 k 个位置，性能极高。

第二部分：分布式一致性 Hash (Consistent Hashing)

1. 解决什么问题？

普通 Hash (hash(key) % node_count) 的致命缺陷是：当节点数量变化（扩容/缩容/宕机）时，几乎所有数据的映射关系都会改变，导致缓存雪崩。

一致性 Hash 将其变为：只有一小部分数据需要迁移。

2. 核心机制

  • 哈希环： 把 0 到 2^{32}-1 想象成一个闭合的圆环。

  • 落点： 服务器 IP 和 数据 Key 都 Hash 到这个环上。

  • 寻址： 数据 Key 顺时针找遇到的第一台服务器。

3.虚拟节点 (Virtual Nodes)

虽然笔记里没写，但这在面试和实际应用中是必须提到的：

  • 问题： 如果服务器很少（比如只有 2 台），它们在环上可能靠得很近，导致大部分数据都压在其中一台机器上（数据倾斜）。

  • 解决： 给每台物理机器分配 100~200 个“分身”（虚拟节点），均匀撒在环上。这样既解决了数据倾斜，又能让雪崩时流量均匀分摊给剩余机器。

总结：实战中的应用链条

这两个技术通常是配合使用的，特别是在处理 高并发缓存架构 时：

  1. 请求进来 -> 布隆过滤器（快速判断 Key 是否存在？如果不存，直接返回，拦截缓存穿透）。

  2. 如果存在 -> 一致性 Hash（计算该 Key 应该去哪个 Redis 节点取数据，解决分布式存储与扩容）。

  3. 取数据 -> 返回结果。

如果需要进一步了解如何确定具体的 m 和 k 值，可以直接使用 hur.st/bloomfilter 网站计算。

问题一：分布式一致性 Hash 增加或者删除节点怎么进行数据迁移？

这个问题考察的是你对一致性 Hash 核心价值（最小化迁移）的理解。

1. 核心原理：顺时针“接管”

在一致性 Hash 环中，数据是存储在它顺时针方向遇到的第一个节点上的。

2. 场景 A：增加节点 (Add Node) —— 数据拆分

假设环上原本有节点 Node A 和 Node B。数据 K_1 落在 A 和 B 之间，所以归 B 管。

  • 操作： 现在在 A 和 B 之间新加入一个 Node C。

  • 影响范围： 只有 A 到 C 之间的数据 会受到影响。

  • 迁移步骤：

    1. Node C 上线。

    2. 扫描 Node B（也就是 C 的顺时针后继节点）的数据。

    3. 将原本属于 A~C 范围内的 Key（哈希值 < C 的位置），从 Node B 迁移到 Node C。

    4. Node B 上剩下的数据（C~B 范围）保持不变。

  • 结论： 只需要从“下一个节点”那里分担一部分数据过来，其他节点无感知。

3. 场景 B：删除节点 (Remove Node) —— 数据合并

假设 Node C 宕机或被移除。

  • 操作： Node C 离开环。

  • 影响范围： 原本 Node C 负责的所有数据。

  • 迁移步骤：

    1. 找到 Node C 的顺时针后继节点 Node B。

    2. 将 Node C 上的所有数据全部迁移（或备份恢复）到 Node B 上。

  • 结论： 它的负载全部压到了它的下一个节点身上。

4. 进阶考点：虚拟节点 (Virtual Nodes)

面试时只答上面两点是不够的，必须提到 虚拟节点。

  • 痛点： 如果物理节点少，增加/删除一个节点会导致某个节点压力突然激增（数据倾斜）。

  • 解决方案： 实际迁移时，我们操作的是虚拟节点。

    • 增加一台物理机器 = 在环上随机撒入 100 个虚拟节点。

    • 这意味着这台新机器会从环上 现有的所有机器 手里都“抢”一点数据过来。

    • 结果： 数据迁移是均匀的，全集群共同分担，不会导致某一台机器被打挂。

问题二：只用 2GB 内存，在 20 亿个整数中找到出现次数最多的数

这是一道典型的 “分治法 (Divide and Conquer) + Hash” 题目。

1. 问题分析

  • 数据量： 20 亿个整数 (int)。

  • 存储空间： 20 \times 10^8 \times 4 \text{ Bytes} \approx 8 \text{ GB}。

  • 限制： 内存只有 2GB。

  • 矛盾： 无法一次性把 8GB 数据全部加载到内存中进行排序或建立哈希表。

2. 错误解法

  • 位图 (BitMap)： 位图只能判断“在不在”（0/1），无法统计“出现多少次”。

  • 直接 HashMap： 20 亿个整数如果都不一样，HashMap 光是存 Key 就爆内存了。

3. 标准解法：Hash 分流 (Hash Split)

核心思想： 大事化小。利用哈希函数的确定性，把相同的数字赶到同一个小文件里。

步骤 1：哈希取模拆分 (Partition)

  • 遍历这 20 亿个整数。

  • 对每个数 num 计算哈希并取模：file_index = hash(num) % 16（或者取 100，1000 都可以，确保每个小文件小于 2GB）。

  • 将 num 写入到对应的临时文件 data_0.txt … data_15.txt 中。

  • 原理： 相同的数，算出来的哈希值一定一样，模 16 也一定一样。所以所有相同的数都会进入同一个小文件。

步骤 2：分别统计 (Local Count)

  • 依次将每个小文件加载到内存（因为文件拆小了，比如 500MB，内存放得下）。

  • 使用 std::unordered_map<int, int> 统计该文件中每个数出现的频率。

  • 找出当前这个小文件中出现次数最多的数（局部冠军），记为 (local_num, local_count)。

  • 清空内存，处理下一个文件。

步骤 3：归并比较 (Global Max)

  • 维护一个全局变量 max_num 和 max_count。

  • 每处理完一个小文件，就拿它的“局部冠军”和全局冠军 PK。

  • if (local_count > max_count) { max_num = local_num; max_count = local_count; }

  • 处理完所有文件后，max_num 就是最终答案。

4. 极端情况 (Skew/倾斜)

  • 追问： 如果这 20 亿个数里，有 19 亿个都是数字 “1”，那么 hash(1) % 16 会导致其中一个小文件特别大（还是超过 2GB），怎么办？

  • 解法： 在处理小文件时，如果发现文件大小依然超过内存阈值，就换一个哈希函数，对这个小文件进行二次拆分 (Re-hash)，直到能放入内存为止。

发表评论