仔细想想你其实每天都在跟哈希打交道——HashMap里存键值对是哈希HashSet里去重是哈希重写equals()时 IDE 唠叨着让你一并重写hashCode()是哈希下载文件后比对的 MD5 校验值是哈希登录时密码不是明文存储而是加密成一串乱码也是哈希Git 每一次 commit 那串看不懂的十六进制 ID 还是哈希甚至你们公司 Redis 集群把数据均匀分到不同机器上——背后站着的依然是哈希。你熟练地使用着这些工具但真要你解释一句哈希到底是什么它凭什么能让查找变得这么快你可能就卡壳了。这篇文章就是来帮你捅破这层窗户纸——从最朴素的原理出发一路讲到 HashMap 源码、一致性哈希和布隆过滤器让你对这位最熟悉的陌生人真正知根知底。一、先别急让我们从一只指纹说起在正式进入 Java 源码之前我想先问你一个问题如果让你在一本 1000 页的字典里快速找到某个单词你会怎么做你肯定不会从第一页开始逐页翻——那得翻到地老天荒。更聪明的做法是字典本身就有索引比如侧面的 ABCD 标签你先根据首字母定位到大致的页码区间再在这个小区间里精确查找。这个根据首字母快速定位的过程本质上就是哈希Hash。哈希就是把一个任意长度的输入通过某种算法映射成一个固定长度的输出。这个输出就像数据的指纹——独一无二理想情况下、短小精悍让你能通过它快速定位到原始数据。用更生活化的例子来说图书馆索书号每本书都有一个索书号你不需要遍历整个图书馆直接根据索书号就能找到书架位置。身份证号14 亿人每人一个 18 位的身份证号这就是一种哈希编号。文件 MD5你下载文件时经常看到的MD5 校验值就是一种哈希。下载完比对一下就知道文件有没有被篡改。好了概念讲完了。下面我们上硬菜。二、哈希函数好的哈希函数长什么样上面的例子中取首字母计算 MD5生成索书号这些操作都是由哈希函数(Hash Function)完成的。2.1 哈希函数的三好学生标准一个优秀的哈希函数必须同时满足三个条件特性含义大白话确定性同样的输入永远得到同样的输出张三算出来是 3 号柜子不能下次算成 7 号高效性计算速度要快如果算一次哈希要 1 秒钟再好的算法也白搭均匀性输出尽可能均匀分布不能让所有人都挤在 1 号柜子前面排队2.2 一个最简单的哈希函数// 最简单的哈希取模 public int hash(String key, int tableSize) { int sum 0; for (char c : key.toCharArray()) { sum c; // 把每个字符的 Unicode 值加起来 } return sum % tableSize; // 取模保证落在 [0, tableSize-1] 范围内 }这个函数能用吗能用。但好吗不好。比如abc和cba算出来的哈希值完全一样因为字符和相同这就叫哈希冲突。哈希冲突不可避免。好的哈希函数不是没有冲突而是让冲突尽可能少、尽可能均匀。就像天底下没有不吵架的夫妻但好的婚姻能让吵架次数少、伤感情程度低——哈希函数也是这个道理。三、Java 世界里的哈希hashCode()与equals()的结婚契约终于到了 Java 的主场。在 Java 中一切哈希的起点是两个方法hashCode()和equals()。它们是Object类自带的方法所有 Java 对象都继承了它们。3.1 每个对象都有指纹public class Object { public native int hashCode(); // 返回对象的哈希值默认是内存地址的某种映射 public boolean equals(Object obj) { return (this obj); // 默认比较内存地址 } }3.2 改写命运的结婚契约当你决定让自定义对象可以被放进HashMap的 Key 中时你就必须遵守hashCode()和equals()之间的契约——我管它叫结婚契约铁律一如果a.equals(b) true那么a.hashCode()必须等于b.hashCode()。铁律二如果a.equals(b) falsea.hashCode()可以相等也可以不相等相等的叫冲突不相等的是理想情况。铁律三同一个对象多次调用hashCode()在equals()用到的字段没变的情况下必须返回相同值。违反契约的后果是什么来看一段车祸现场public class Student { private String name; public Student(String name) { this.name name; } Override public boolean equals(Object o) { if (this o) return true; if (!(o instanceof Student)) return false; return Objects.equals(name, ((Student) o).name); } // 注意重写了 equals()但忘了重写 hashCode() } // 车祸现场 MapStudent, Integer scores new HashMap(); scores.put(new Student(小明), 90); // 你期望拿到 90实际拿到的却是 null Integer score scores.get(new Student(小明)); System.out.println(score); // null 为什么呢因为虽然两个Student对象equals返回true但它们的hashCode()不同默认用内存地址所以HashMap去不同的桶里找当然找不到。记住重写equals()就必须重写hashCode()。这俩就像筷子——少一只你能吃饭吗能用但你得用手而面试官会因为这个把你挂掉。3.3 标准写法public class Student { private String name; private int age; Override public boolean equals(Object o) { if (this o) return true; if (!(o instanceof Student)) return false; Student student (Student) o; return age student.age Objects.equals(name, student.name); } Override public int hashCode() { return Objects.hash(name, age); // Java 7 一行搞定 } }现代 Java 项目中直接用 Lombok 的EqualsAndHashCode注解或者用 IDEA 自动生成一般不需要手写。但面试时你得能手写出来。四、哈希冲突——当两个不同的人拿到了同一个储物柜号码前面我们说了哈希冲突是不可避免的。那么冲突发生了怎么办业界主要有两种方案。4.1 链地址法Separate Chaining核心思想每个桶不只放一个元素而是放一个链表或红黑树。冲突的元素串在同一个桶后面。数组索引: [0] - 张三 - 李四 - null ← 桶0里挂了两个元素冲突了 [1] - null ← 这个桶空的 [2] - 王五 - null ← 这个桶只有一个元素这就是 JavaHashMap采用的方式。4.2 开放地址法Open Addressing核心思想每个桶只放一个元素。如果目标桶被占了就按某种规则去找下一个空桶。线性探测往后走一步看看下一个桶空不空二次探测往后走 1²、2²、3²... 步双重哈希用第二个哈希函数计算步长Java 的ThreadLocal中的ThreadLocalMap用的就是开放地址法线性探测。4.3 两种方案对比维度链地址法开放地址法实现数组链表/红黑树纯数组内存需要额外存储指针全部在数组内缓存友好删除简单从链表移除复杂不能直接置空扩容阈值可以超过 100%通常 ≤ 70%代表HashMapThreadLocalMap五、HashMap 源码深度拆解——Java 面试的必考题如果说数据结构面试有一道必考题那一定是 HashMap。下面的内容建议你收藏面试前拿出来温习。5.1 数据结构全景图┌─────────────────────────────────────────────────────────┐ │ HashMap │ │ │ │ table (NodeK,V[]) │ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │...│n-1│ │ │ └─┬─┴───┴─┬─┴───┴───┴───┴───┴───┘ │ │ │ │ │ │ │ └──→ Node → Node (链表长度≤8) │ │ │ ↓(树化) │ │ │ TreeNode ↔ TreeNode (红黑树长度8) │ │ │ │ │ └──→ null (空桶) │ └─────────────────────────────────────────────────────────┘5.2 核心常量为什么是 8 和 0.75看源码前先记住这几个魔法数字static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认容量 16 static final float DEFAULT_LOAD_FACTOR 0.75f; // 负载因子 static final int TREEIFY_THRESHOLD 8; // 链表转红黑树阈值 static final int UNTREEIFY_THRESHOLD 6; // 红黑树退化为链表阈值 static final int MIN_TREEIFY_CAPACITY 64; // 最小树化容量面试高频问题来了为什么负载因子是 0.75这是时间和空间的折中设太大如 0.9空间利用率高但哈希冲突概率飙升查找效率下降。设太小如 0.5冲突少、查找快但一半空间浪费了。0.75 是经过大量实验验证的甜点值在时空之间取得了最佳平衡。为什么树化阈值是 8根据泊松分布在负载因子为 0.75 的情况下一个桶中元素个数达到 8 的概率约为0.00000006亿分之六。也就是说正常情况下几乎不可能出现需要树化的场景——如果真的出现了说明你的hashCode()写得有问题或者有人在故意构造哈希碰撞攻击。树化本质上是一种防御机制。为什么退化阈值是 6 而不是 8如果退化阈值也设为 8当元素个数在 7→8→7 之间反复横跳时链表和红黑树会频繁转换开销巨大。设成 6 相当于加了一个缓冲区避免震荡。5.3 哈希扰动函数不是简单取模那么简单// JDK 1.8 HashMap 的 hash() 方法 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }为什么要做h ^ (h 16)这个扰动因为计算桶下标用的是(n - 1) hash等同于取模运算但只对 2 的幂次有效。当n比较小比如初始容量 16时n - 1的二进制只有低 4 位是 1n 16: n - 1 15 0000 0000 0000 1111如果不做扰动只有hashCode的低 4 位参与运算高位完全被忽略——冲突率会高得离谱。扰动函数把高 16 位和低 16 位异或让高位也参与进来哈希更均匀。5.4 put() 方法全流程final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; // 1. 如果 table 为空先扩容懒初始化 if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 2. 计算桶下标如果桶为空直接放 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { // 3. 桶不为空分三种情况处理 NodeK,V e; K k; // 3a. 第一个节点就是目标直接命中 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; // 3b. 桶里是红黑树走树的插入逻辑 else if (p instanceof TreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); // 3c. 桶里是链表遍历链表 else { for (int binCount 0; ; binCount) { if ((e p.next) null) { // 走到末尾插入新节点 p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) // 长度≥8转红黑树 treeifyBin(tab, hash); break; } if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) break; // 找到了相同key p e; } } // 4. 如果找到了相同的 key覆盖旧值 if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; return oldValue; } } // 5. 检查是否需要扩容 if (size threshold) resize(); return null; }用一张流程图总结put的全过程put(key, value) │ ▼ 计算 hash(key)确定桶下标 index │ ▼ 桶为空──是──▶ 直接放入新节点 │ 否 │ ▼ 桶内第一个节点就是要找的 key──是──▶ 覆盖 value │ 否 │ ▼ 桶内是红黑树──是──▶ 走树的插入逻辑 │ 否是链表 │ ▼ 遍历链表 - 找到相同 key → 覆盖 value - 走到末尾 → 插入新节点 → 检查是否需要树化 │ ▼ size threshold──是──▶ 扩容5.5 扩容机制为什么容量总是 2 的幂JDK 1.8 的扩容是一次优雅的重哈希过程final NodeK,V[] resize() { // ... 省略部分代码 NodeK,V[] oldTab table; int oldCap (oldTab null) ? 0 : oldTab.length; int newCap oldCap 1; // 新容量 旧容量 × 2 // 遍历旧数组 for (int j 0; j oldCap; j) { NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null; if (e.next null) // 只有一个元素直接放新位置 newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode) // 红黑树走 split 逻辑 ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { // 链表拆成两条 // 核心技巧用 hash oldCap 判断元素在新数组中的位置 // 结果为 0位置不变 (j) // 结果为 1位置变成 j oldCap // ...拆分逻辑 } } } }为什么容量始终保持 2 的幂三个好处位运算替代取模hash (n-1)等价于hash % n但快得多。扩容时元素位置规律扩容后元素要么在原位置要么在原位置 旧容量处。不需要重新计算哈希。配合扰动函数让哈希分布更均匀。5.6 JDK 1.7 vs JDK 1.8 的演进特性JDK 1.7JDK 1.8数据结构数组 链表数组 链表 红黑树插入方式头插法新节点插在链表头部尾插法新节点插在链表尾部扩容死链⚠️ 多线程扩容可能形成环形链表CPU 100%✅ 修复不会成环哈希扰动4 次扰动1 次扰动高16位异或低16位面试时主动提 JDK 1.7 头插法导致的死循环问题绝对是加分项。六、一致性哈希——当哈希遇上分布式到目前为止我们聊的都是单机环境。现在把视角拉远如果你的数据量大到一台机器装不下需要用多台机器组成集群哈希还能用吗6.1 普通哈希取模的翻车现场假设你有 3 台 Redis 服务器用最简单的策略路由数据int serverIndex hash(key) % 3; // 3台机器取模决定去哪台看起来没问题。直到有一天你加了一台新机器——原来hash(user:1001) % 3 2 → 去 2 号机器 现在hash(user:1001) % 4 1 → 去 1 号机器 ← 找不到了几乎所有 Key 的路由都变了。这意味着什么缓存全部失效所有请求直接打到数据库——俗称缓存雪崩。这是个能让运维半夜起来加班的问题。6.2 一致性哈希的环形魔法一致性哈希用一个Hash 环0 ~ 2³²-1来解决这个问题核心规则把服务器节点也哈希到环上数据的 Key 同样哈希到环上从 Key 的位置顺时针走遇到的第一个节点就是目标服务器6.3 增加/删除节点的影响增加节点前Key1、Key2、Key3 都路由到 Server B 增加节点后只有 Key2 切换到了新节点 Server CKey1 和 Key3 不受影响只影响环上相邻的一小段数据而不是全部。这就是一致性哈希的核心优势。6.4 虚拟节点——让雨露均沾成为现实一致性哈希有一个隐患如果节点太少哈希环上的分布可能极不均匀有的节点分到海量数据有的节点闲出屁。解决方案是虚拟节点Virtual Node每个物理节点在环上映射为多个虚拟节点。物理节点 Server A → 虚拟节点 A#1, A#2, A#3 ... A#150 物理节点 Server B → 虚拟节点 B#1, B#2, B#3 ... B#150虚拟节点越多分布越均匀。这也是 Dubbo、Nginx、Memcached 等中间件中一致性哈希的通用做法。// 带虚拟节点的一致性哈希示意 public class ConsistentHash { private final TreeMapInteger, String ring new TreeMap(); // 用TreeMap实现环 private final int virtualNodes; // 每个物理节点的虚拟节点数 public ConsistentHash(int virtualNodes, ListString servers) { this.virtualNodes virtualNodes; for (String server : servers) { addNode(server); } } private void addNode(String server) { for (int i 0; i virtualNodes; i) { String virtualNodeName server # i; int hash getHash(virtualNodeName); ring.put(hash, server); } } public String getServer(String key) { int hash getHash(key); // 顺时针找最近的节点 Map.EntryInteger, String entry ring.ceilingEntry(hash); if (entry null) { entry ring.firstEntry(); // 超过最大值回到环的起点 } return entry.getValue(); } }七、布隆过滤器——用空间换时间的极致艺术7.1 一个真实场景你的公司做了一个新闻 App。为了不让用户看到重复的新闻每次推荐前你都要判断这篇文章用户看过没。你不可能每次都去数据库查——那会让数据库直接歇菜。你也不可能把所有已读文章ID存到内存——用户量大了之后内存分分钟爆炸。这时候布隆过滤器Bloom Filter就登场了。7.2 核心原理布隆过滤器是一个概率型数据结构它告诉你两件事这个元素一定不存在 → 100% 确定这个元素可能存在 → 有一定误判概率布隆过滤器的结构 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 初始化全部为0 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 添加元素 Java hash1(Java) 2 ──▶ 第2位置1 hash2(Java) 5 ──▶ 第5位置1 hash3(Java) 7 ──▶ 第7位置1 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 查询 Java 检查第2、5、7位 → 都是1 → 可能存在 ✅ 查询 Python 检查第1、4、6位 → 第4位是0 → 一定不存在 ❌7.3 Java 实现基于 Redis// 使用 Guava 的布隆过滤器 import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; BloomFilterString filter BloomFilter.create( Funnels.stringFunnel(Charset.defaultCharset()), 1000000, // 预计插入数量 0.01 // 期望误判率 1% ); filter.put(user:1001:article:5001); // 标记为已读 if (filter.mightContain(user:1001:article:5002)) { // 可能存在有 ≤1% 概率误判去数据库二次确认 } else { // 一定不存在放心推荐给用户 }布隆过滤器的妙处在于用极小的空间远小于存储全部 ID 所需的内存换取了一定不存在这个确定性的答案。在缓存穿透防护、垃圾邮件过滤、网页去重等场景中堪称神器。八、哈希应用全景图——不止是 HashMap哈希的应用远比大多数人想象的要广泛。来快速过一遍应用场景哈希的作用代表技术快速查找O(1) 时间复杂度HashMap、HashSet数据校验检测数据是否被篡改MD5、SHA-256负载均衡将请求均匀分配到服务器一致性哈希Nginx、Dubbo去重判断用极小内存判断是否存在过布隆过滤器数据分片数据库/缓存水平拆分分库分表路由密码存储不可逆加密BCrypt、Argon2防篡改区块链、Git commit IDSHA-1Git、SHA-256区块链秒杀去重防止用户重复下单Redis Lua 脚本九、面试高频题——手写与实践9.1 你能手写一个简单的 HashMap 吗面试中可能被问到这里给出一个简化版public class SimpleHashMapK, V { static class NodeK, V { final K key; V value; NodeK, V next; Node(K key, V value) { this.key key; this.value value; } } private NodeK, V[] table; private int size; private static final int DEFAULT_CAPACITY 16; private static final float LOAD_FACTOR 0.75f; SuppressWarnings(unchecked) public SimpleHashMap() { table (NodeK, V[]) new Node[DEFAULT_CAPACITY]; } public void put(K key, V value) { int index indexFor(key); NodeK, V head table[index]; // 查找是否已存在 for (NodeK, V e head; e ! null; e e.next) { if (e.key.equals(key)) { e.value value; // 覆盖 return; } } // 头插法插入新节点 NodeK, V newNode new Node(key, value); newNode.next head; table[index] newNode; if (size table.length * LOAD_FACTOR) { resize(); } } public V get(K key) { int index indexFor(key); for (NodeK, V e table[index]; e ! null; e e.next) { if (e.key.equals(key)) { return e.value; } } return null; } private int indexFor(K key) { return (key.hashCode() 0x7fffffff) % table.length; // 取正再取模 } SuppressWarnings(unchecked) private void resize() { NodeK, V[] oldTable table; table (NodeK, V[]) new Node[oldTable.length 1]; size 0; for (NodeK, V head : oldTable) { for (NodeK, V e head; e ! null; e e.next) { put(e.key, e.value); // 简单做法rehash reinsert } } } }9.2 面试必问题清单以下问题建议你在面试前都能对答如流HashMap 的底层数据结构是什么→ 数组 链表 红黑树为什么用红黑树而不是 AVL 树→ 红黑树插入删除的旋转次数更少适合频繁修改的场景AVL 树查找略快但旋转开销大适合读多写少HashMap 的扩容机制→ 容量翻倍、rehash、链表拆分高位/低位两条链为什么 HashMap 线程不安全→ 数据覆盖、1.7 死循环、size 不准确hashCode()和equals()的关系→ 对象相等则 hashCode 必相等反之不必然什么是哈希冲突如何解决→ 链地址法、开放地址法一致性哈希的原理和优势→ Hash 环 顺时针查找增减节点只影响相邻数据布隆过滤器的原理和应用场景→ 多哈希 位数组用于缓存穿透防护、去重十、总结从哈希看计算机科学的权衡之美回顾整篇文章你会发现一个反复出现的主题权衡Trade-off。负载因子 0.75时间 vs 空间的权衡树化阈值 8正常场景性能 vs 极端场景防御的权衡链地址法 vs 开放地址法灵活性 vs 缓存友好的权衡布隆过滤器准确性 vs 内存占用的权衡一致性哈希数据均匀性 vs 扩缩容成本的权衡哈希之所以成为计算机科学中最广泛应用的技术之一正是因为它完美体现了没有银弹只有权衡的工程哲学。学技术既要学是什么概念也要学怎么用API更要学为什么设计原理。三者缺一不可。希望这篇文章能帮你打通哈希的任督二脉在面试和工作中游刃有余。