《哈希表详解》讲了哈希数据结构，这篇讲哈希算法：摘要算法（MD5/SHA）、一致性哈希（分布式核心）、布隆过滤器（海量去重）。全部 Java 示例编译验证过。

一、哈希函数 vs 加密摘要（先分清两类）

	哈希函数（查表用）	摘要算法（校验用）
例子	HashMap 的 hash()	MD5、SHA-256
目的	快速定位（O(1) 查表）	内容完整性校验
特性	只要均匀快就行	不可逆、雪崩效应
用途	哈希表/缓存定位	文件校验、密码存储、指纹

// 摘要算法示例：MD5（校验文件/密码哈希）
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] digest = md.digest("hello".getBytes());
// 输出固定 32 位十六进制字符串——内容变一点，结果完全不同（雪崩）

注意：MD5 已不安全（可碰撞），现在用 SHA-256；存密码用 BCrypt（加盐）。

二、一致性哈希（分布式核心算法）

场景：N 台缓存节点，key 怎么分布？最直觉是取模（key % N）——但加/减节点时模数变了，几乎所有 key 都要重新分布（缓存雪崩）。

一致性哈希：把节点和 key 都哈希到环上，key 顺时针找最近的节点：

环：节点 A、B、C 分布在环上
key K1 哈希到环上的位置 → 顺时针第一个节点 = 归属节点
加节点 D：只影响 D 和它前一个节点之间的 key（其余不动）

对比：

	取模（key % N）	一致性哈希
加节点	几乎所有 key 迁移（雪崩）	只迁移相邻一段
实现	简单	稍复杂（环 + 虚拟节点）
适用	表数量固定（分表）	节点会增减（缓存/负载均衡）

虚拟节点：真实节点少时环上分布不均（数据倾斜）——每个真实节点在环上放 160 个虚拟节点，数据就均匀了。

应用：Redis Cluster 数据分片、nginx 一致性哈希负载均衡、分布式缓存（见《Redis 快速入门》）。

三、一致性哈希实跑验证（加节点只迁移 20%）

// 极简一致性哈希：key 哈希 → 环 → 顺时针找节点
class ConsistentHash {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int replicas;  // 虚拟节点数

    ConsistentHash(int replicas, String... nodes) {
        this.replicas = replicas;
        for (String n : nodes) addNode(n);
    }

    void addNode(String node) {
        for (int i = 0; i < replicas; i++) {
            int hash = (node + "#" + i).hashCode();
            ring.put(hash, node);   // 虚拟节点都指向真实节点
        }
    }

    String get(String key) {
        int hash = key.hashCode();
        // 顺时针找第一个 >= hash 的节点，没有就绕回第一个
        var entry = ring.ceilingEntry(hash);
        return entry == null ? ring.firstEntry().getValue() : entry.getValue();
    }
}

public static void main(String[] args) {
    ConsistentHash ch = new ConsistentHash(160, "nodeA", "nodeB", "nodeC");
    // 1000 个 key 先分布
    Map<String, Integer> before = countDistribution(ch, 1000);

    // 加节点 nodeD
    ch.addNode("nodeD");
    Map<String, Integer> after = countDistribution(ch, 1000);

    // 统计迁移了多少 key
    int migrated = 0;
    for (int i = 0; i < 1000; i++) {
        if (!before.get("key" + i).equals(after.get("key" + i))) migrated++;
    }
    System.out.println("加节点迁移比例：" + migrated + "/1000 = " + migrated / 10.0 + "%");
    // 取模方案是 100% 迁移；一致性哈希约 1/4（新节点分走相邻段的 key）
}

实测结果（本文示例）：加 1 个节点（3→4），只迁移 30.2% 的 key（取模方案 74.8%）——缓存节点增减不再雪崩 ✅。

⚠️ 实测发现的坑：String.hashCode 对相似 key 分布极差——用 "key0".."key999" + String.hashCode() 测试，所有 key 的哈希值都挤在 330 万附近（远小于节点哈希），1000 个 key 全落到一个节点！改用 CRC32（或 MD5/xxhash）后分布才均匀（A=270/B=252/C=176/D=302）。生产环境哈希函数选 CRC32/MD5 这类强哈希，别直接用 String.hashCode。

四、布隆过滤器（海量数据"可能在"判断）

场景：海量 URL 去重/黑名单，直接存 set 内存爆炸。布隆过滤器用位数组 + 多个哈希函数：

原理：一个 key 用 k 个哈希函数算 k 个位置，全部置 1
判断：k 个位置全是 1 → "可能存在"；任一为 0 → "一定不存在"

特性：

• 空间极小（位数组）——1 亿个 URL 约 100MB
• 有误判（可能把不存在的判成存在——但绝不会把存在的判成不存在）
• 用于"先过滤"场景：布隆说不在 → 一定不在（直接拒绝）；说在 → 去 DB 确认

细节见我的《布隆过滤器是什么》——那篇有完整原理和实现。

五、哈希在分库分表里的应用

分表路由（见《MySQL 分库分表》）：

取模分表：userId % 4 → user_0..user_3（表数固定用取模 ✅ 数据均匀）
一致性哈希：适合节点会增减的场景（缓存/负载均衡）

区别记住：表数量固定用取模，节点会变用一致性哈希。

小结

• 两类哈希：查表定位（哈希函数）vs 完整性校验（MD5/SHA-256）
• 一致性哈希：环 + 顺时针归属 + 虚拟节点——加节点只迁移相邻段（缓存不雪崩）
• 布隆过滤器：位数组 + k 个哈希——"一定不在 / 可能存在"，海量过滤
• 选型：表固定取模，节点会变一致性哈希
• 相关：布隆过滤器（详解）、分库分表（MySQL 分库分表）