很多人第一次接触哈希通常是从HashMap开始的。老师会告诉你HashMap 查询很快平均时间复杂度是 O(1)。然后你开始记map.put(key, value); map.get(key);但真正的问题是它为什么快如果一个HashMap里面已经放了几十万条数据为什么还能很快找到其中某一条想理解这个问题不能只停留在 API 层面而要从最基础的数组下标开始。一、先想一个最笨的查找方式假设现在有一个班级名单张三 李四 王五 赵六 陈七 ……现在问你王五在哪如果这些数据只是按顺序放在一个列表里你只能从头开始找第1个张三不是 第2个李四不是 第3个王五找到了数据量少的时候没什么问题。但如果有 100 万条数据呢最坏情况下你可能需要比较 100 万次。这就是典型的顺序查找。时间复杂度O(n)哈希想解决的就是能不能不一个个找而是直接算出数据大概放在哪里二、数组为什么查询这么快先看一个数组String[] users new String[10]; users[0] 张三; users[1] 李四; users[2] 王五;如果我要找users[2]计算机并不需要先看 users[0] ↓ 再看 users[1] ↓ 最后看 users[2]它可以直接定位。因为数组在内存中通常是一块连续区域。可以简单理解成数组首地址1000 users[0] → 1000 users[1] → 1008 users[2] → 1016 users[3] → 1024如果每个位置占 8 个字节那么元素地址 数组首地址 下标 × 元素大小所以访问users[2]计算机直接计算1000 2 × 8 1016然后直接去 1016 这个位置取数据。不需要搜索。这就是数组查询接近O(1)的根本原因。而哈希表的核心思想其实就是想办法把任意 Key转换成数组下标。三、哈希真正干了什么假设我们想存map.put(apple, 10); map.put(banana, 20); map.put(orange, 30);问题来了。数组下标只能是0 1 2 3 4但我们的 Key 却是apple banana orange怎么把字符串变成数组下标这时候就需要哈希函数。流程可以理解为Key ↓ Hash Function ↓ Hash值 ↓ 计算数组下标 ↓ 存入数组例如apple ↓ hashCode() ↓ 93029210 ↓ 计算下标 ↓ 2最后table[2] apple以后查询map.get(apple);再执行同样的计算apple ↓ 93029210 ↓ 下标2 ↓ 直接访问 table[2]所以它不需要扫描整个数组。这就是哈希查询快的核心原因。四、可以把哈希想象成“快递柜”一个很形象的例子。假设一个小区有 100 个快递柜。如果所有快递都堆在地上1000个快递你要找自己的快递只能一个个看名字。很慢。现在快递员设计了一套规则根据手机号 ↓ 计算一个数字 ↓ 决定放进哪个柜子比如13812345678 ↓ 某种计算 ↓ 柜子 37你来取快递的时候也按照同样规则算手机号 ↓ 37号柜于是直接去 37 号柜。哈希函数就是那个“决定放哪个柜子”的规则。数组就是那一排快递柜。五、但马上会出现一个问题哈希冲突假设只有 10 个柜子。但现在有几千个手机号。无论哈希函数设计得多好都有可能出现张三 → 3号柜 李四 → 7号柜 王五 → 3号柜张三和王五都算出了3这就叫Hash Collision哈希冲突。而且哈希冲突不是程序 Bug。它几乎是必然发生的。为什么因为输入空间非常大几乎无限种字符串但数组长度却有限16 32 64 128你要把大量 Key 映射到有限的位置就必然存在不同 Key 落到同一个位置的情况。六、那 HashMap 怎么解决冲突一种非常经典的方法就是链地址法。可以想象原本数组是table[0] table[1] table[2] table[3] table[4]如果张三 → table[2]那么table[2] → 张三后来王五 → table[2]发生冲突。那就不覆盖张三而是把它们连起来table[2] ↓ 张三 ↓ 王五再来一个赵六 → table[2]变成table[2] ↓ 张三 ↓ 王五 ↓ 赵六这就是为什么很多哈希表底层实际上可以理解为数组 链表七、这时候 HashMap 还是 O(1) 吗不一定。假设一个很差的哈希函数把所有 Key 都算到了同一个位置张三 ↘ 李四 ↓ 王五 → table[0] 赵六 ↑ 陈七 ↗最终table[0] ↓ 张三 ↓ 李四 ↓ 王五 ↓ 赵六 ↓ 陈七 ↓ ……这时候你找一个元素还是得顺着链表一个个找。时间复杂度可能退化成O(n)所以一个好的哈希函数非常重要。它希望做到让数据尽可能均匀地散落到整个数组中。这也是“Hash”这个词的本意之一打散。八、Java HashMap 为什么还有红黑树在 Java 8 以后HashMap并不只是数组 链表更准确地说是数组 链表 红黑树原因也很好理解。如果某个桶里的冲突数据越来越多table[3] ↓ A ↓ B ↓ C ↓ D ↓ E ↓ F ↓ ……链表查询效率会越来越差。所以当满足一定条件时Java 会把链表转换成红黑树。大致变成D / \ B F / \ / \ A C E G链表查询最坏可能接近O(n)而红黑树查询可以控制在O(log n)所以 HashMap 的底层设计本质上是在努力避免某一个桶里的数据太多导致哈希表失去“快速定位”的优势。九、HashMap 的数组下标到底怎么算为了方便理解可以先看一个简化版本。假设数组长度是16某个 Key 的哈希值是12345最直观的方法是12345 % 16得到9于是放到table[9]也就是index hash % length不过 Java 的HashMap做了进一步优化。当数组长度是 2 的幂时16 32 64 128可以使用位运算index (n - 1) hash;例如n 16 n - 1 15二进制15 0000 1111然后hash 0000 1111本质上就是取 Hash 值的低几位来决定数组下标。位运算速度很快。这也是为什么很多哈希表实现喜欢把数组容量设计成2的幂十、为什么 HashMap 还要扩容假设 HashMap 底层数组只有 4 个位置0 1 2 3现在放入越来越多的数据100条 1000条 10000条那么哈希冲突一定会越来越严重。就像原本只有 4 个快递柜却来了 1000 个快递。再好的分配算法也没用。所以 HashMap 会进行扩容。例如16 ↓ 32 ↓ 64 ↓ 128柜子变多之后数据可以重新分散。冲突自然会减少。十一、为什么不是等数组满了再扩容因为哈希表不能追求每个位置都塞满如果塞得太满冲突会越来越严重。所以 HashMap 会维护一个概念负载因子 Load Factor。可以简单理解成当前存了多少数据 ---------------- 数组容量JavaHashMap默认负载因子通常是0.75也就是说一个容量为16的 HashMap不会真的等放满 16 个元素才考虑扩容。而是在达到某个阈值后就进行扩容。目的只有一个用一些额外的内存空间换取更少的哈希冲突和更快的查询速度。这其实是计算机世界非常常见的一种思想空间换时间。十二、为什么 Key 一般不能随便修改这里还有一个很容易忽略的问题。假设一个对象User user new User(张三, 18);根据这个对象计算hash 123 ↓ 存进 table[11]后来你修改了参与hashCode()计算的数据user.name 李四;新的 Hash 可能变成456再查询的时候456 ↓ table[8]程序会去table[8]找。但这个对象实际上还躺在table[11]于是可能出现一种很奇怪的情况对象明明在 HashMap 里却找不到了。所以作为 Hash Key 的对象参与equals()和hashCode()的字段最好保持稳定。这也是为什么 Java 里String非常适合作为 HashMap 的 Key。因为 String 是不可变对象。十三、hashCode 相同两个对象就一定相同吗不一定。例如对象A → hashCode 9527 对象B → hashCode 9527它们完全可能是两个不同对象。所以 HashMap 判断 Key通常不是只看hashCode()还需要看equals()可以理解成两步第一步 hashCode ↓ 快速找到大概位置然后第二步 equals ↓ 确认到底是不是这个Key所以hashCode()负责快速定位equals()负责最终确认。这两个方法在哈希结构中通常是配合使用的。十四、为什么哈希查询平均是 O(1)现在整个逻辑就非常清楚了。普通查找从第一个开始 ↓ 一个个比较 ↓ 直到找到可能是O(n)而哈希表Key ↓ Hash ↓ 数组下标 ↓ 直接定位桶理想情况下只需要少量固定操作。数据从1000条增加到100万条并不意味着每次查询都必须多扫描几十万条数据。所以平均情况下HashMap 的put() get()都可以达到接近O(1)当然这个 O(1) 是建立在Hash 分布比较均匀数组容量合理冲突数量可控这些条件之上的。十五、真正理解哈希只需要抓住一条主线很多人学哈希时会被各种概念绕晕Hash hashCode HashMap 桶 链表 红黑树 负载因子 扩容 哈希冲突其实它们都围绕着同一个问题如何把一个原本需要“搜索”的问题变成一个可以“直接定位”的问题。整个 HashMap 的底层逻辑可以压缩成Key ↓ hashCode ↓ Hash计算 ↓ 数组下标 ↓ 找到桶 ↓ equals确认Key ↓ 返回Value而如果发生冲突数组 ↓ 链表 ↓ 冲突严重 ↓ 红黑树如果数据越来越多冲突增加 ↓ 扩容 ↓ 重新分散数据到这里HashMap 大部分设计其实已经串起来了。写在最后哈希真正厉害的地方不是它使用了什么特别神秘的算法。它背后的核心思想反而非常简单既然数组可以通过下标直接定位那我就想办法把任意 Key 转换成一个数组下标。于是有了Key → Hash → 下标 → 数组但现实中不同 Key 又可能算出相同的位置所以需要解决哈希冲突数据多了以后冲突又会增加所以需要扩容冲突严重以后链表查询又会变慢所以又引入红黑树。你会发现HashMap 的很多复杂设计并不是凭空出现的而是在“数组直接定位”这个最简单的思想上一层层解决现实问题演化出来的。理解了这一点再去看HashMap源码就不会只看到一堆hash、table、Node和位运算。你看到的其实是一整套非常经典的设计思想用哈希计算缩小搜索范围用空间换时间用合理的数据结构处理冲突。 深度理解哈希
很多人第一次接触哈希通常是从HashMap开始的。老师会告诉你HashMap 查询很快平均时间复杂度是 O(1)。然后你开始记map.put(key, value); map.get(key);但真正的问题是它为什么快如果一个HashMap里面已经放了几十万条数据为什么还能很快找到其中某一条想理解这个问题不能只停留在 API 层面而要从最基础的数组下标开始。一、先想一个最笨的查找方式假设现在有一个班级名单张三 李四 王五 赵六 陈七 ……现在问你王五在哪如果这些数据只是按顺序放在一个列表里你只能从头开始找第1个张三不是 第2个李四不是 第3个王五找到了数据量少的时候没什么问题。但如果有 100 万条数据呢最坏情况下你可能需要比较 100 万次。这就是典型的顺序查找。时间复杂度O(n)哈希想解决的就是能不能不一个个找而是直接算出数据大概放在哪里二、数组为什么查询这么快先看一个数组String[] users new String[10]; users[0] 张三; users[1] 李四; users[2] 王五;如果我要找users[2]计算机并不需要先看 users[0] ↓ 再看 users[1] ↓ 最后看 users[2]它可以直接定位。因为数组在内存中通常是一块连续区域。可以简单理解成数组首地址1000 users[0] → 1000 users[1] → 1008 users[2] → 1016 users[3] → 1024如果每个位置占 8 个字节那么元素地址 数组首地址 下标 × 元素大小所以访问users[2]计算机直接计算1000 2 × 8 1016然后直接去 1016 这个位置取数据。不需要搜索。这就是数组查询接近O(1)的根本原因。而哈希表的核心思想其实就是想办法把任意 Key转换成数组下标。三、哈希真正干了什么假设我们想存map.put(apple, 10); map.put(banana, 20); map.put(orange, 30);问题来了。数组下标只能是0 1 2 3 4但我们的 Key 却是apple banana orange怎么把字符串变成数组下标这时候就需要哈希函数。流程可以理解为Key ↓ Hash Function ↓ Hash值 ↓ 计算数组下标 ↓ 存入数组例如apple ↓ hashCode() ↓ 93029210 ↓ 计算下标 ↓ 2最后table[2] apple以后查询map.get(apple);再执行同样的计算apple ↓ 93029210 ↓ 下标2 ↓ 直接访问 table[2]所以它不需要扫描整个数组。这就是哈希查询快的核心原因。四、可以把哈希想象成“快递柜”一个很形象的例子。假设一个小区有 100 个快递柜。如果所有快递都堆在地上1000个快递你要找自己的快递只能一个个看名字。很慢。现在快递员设计了一套规则根据手机号 ↓ 计算一个数字 ↓ 决定放进哪个柜子比如13812345678 ↓ 某种计算 ↓ 柜子 37你来取快递的时候也按照同样规则算手机号 ↓ 37号柜于是直接去 37 号柜。哈希函数就是那个“决定放哪个柜子”的规则。数组就是那一排快递柜。五、但马上会出现一个问题哈希冲突假设只有 10 个柜子。但现在有几千个手机号。无论哈希函数设计得多好都有可能出现张三 → 3号柜 李四 → 7号柜 王五 → 3号柜张三和王五都算出了3这就叫Hash Collision哈希冲突。而且哈希冲突不是程序 Bug。它几乎是必然发生的。为什么因为输入空间非常大几乎无限种字符串但数组长度却有限16 32 64 128你要把大量 Key 映射到有限的位置就必然存在不同 Key 落到同一个位置的情况。六、那 HashMap 怎么解决冲突一种非常经典的方法就是链地址法。可以想象原本数组是table[0] table[1] table[2] table[3] table[4]如果张三 → table[2]那么table[2] → 张三后来王五 → table[2]发生冲突。那就不覆盖张三而是把它们连起来table[2] ↓ 张三 ↓ 王五再来一个赵六 → table[2]变成table[2] ↓ 张三 ↓ 王五 ↓ 赵六这就是为什么很多哈希表底层实际上可以理解为数组 链表七、这时候 HashMap 还是 O(1) 吗不一定。假设一个很差的哈希函数把所有 Key 都算到了同一个位置张三 ↘ 李四 ↓ 王五 → table[0] 赵六 ↑ 陈七 ↗最终table[0] ↓ 张三 ↓ 李四 ↓ 王五 ↓ 赵六 ↓ 陈七 ↓ ……这时候你找一个元素还是得顺着链表一个个找。时间复杂度可能退化成O(n)所以一个好的哈希函数非常重要。它希望做到让数据尽可能均匀地散落到整个数组中。这也是“Hash”这个词的本意之一打散。八、Java HashMap 为什么还有红黑树在 Java 8 以后HashMap并不只是数组 链表更准确地说是数组 链表 红黑树原因也很好理解。如果某个桶里的冲突数据越来越多table[3] ↓ A ↓ B ↓ C ↓ D ↓ E ↓ F ↓ ……链表查询效率会越来越差。所以当满足一定条件时Java 会把链表转换成红黑树。大致变成D / \ B F / \ / \ A C E G链表查询最坏可能接近O(n)而红黑树查询可以控制在O(log n)所以 HashMap 的底层设计本质上是在努力避免某一个桶里的数据太多导致哈希表失去“快速定位”的优势。九、HashMap 的数组下标到底怎么算为了方便理解可以先看一个简化版本。假设数组长度是16某个 Key 的哈希值是12345最直观的方法是12345 % 16得到9于是放到table[9]也就是index hash % length不过 Java 的HashMap做了进一步优化。当数组长度是 2 的幂时16 32 64 128可以使用位运算index (n - 1) hash;例如n 16 n - 1 15二进制15 0000 1111然后hash 0000 1111本质上就是取 Hash 值的低几位来决定数组下标。位运算速度很快。这也是为什么很多哈希表实现喜欢把数组容量设计成2的幂十、为什么 HashMap 还要扩容假设 HashMap 底层数组只有 4 个位置0 1 2 3现在放入越来越多的数据100条 1000条 10000条那么哈希冲突一定会越来越严重。就像原本只有 4 个快递柜却来了 1000 个快递。再好的分配算法也没用。所以 HashMap 会进行扩容。例如16 ↓ 32 ↓ 64 ↓ 128柜子变多之后数据可以重新分散。冲突自然会减少。十一、为什么不是等数组满了再扩容因为哈希表不能追求每个位置都塞满如果塞得太满冲突会越来越严重。所以 HashMap 会维护一个概念负载因子 Load Factor。可以简单理解成当前存了多少数据 ---------------- 数组容量JavaHashMap默认负载因子通常是0.75也就是说一个容量为16的 HashMap不会真的等放满 16 个元素才考虑扩容。而是在达到某个阈值后就进行扩容。目的只有一个用一些额外的内存空间换取更少的哈希冲突和更快的查询速度。这其实是计算机世界非常常见的一种思想空间换时间。十二、为什么 Key 一般不能随便修改这里还有一个很容易忽略的问题。假设一个对象User user new User(张三, 18);根据这个对象计算hash 123 ↓ 存进 table[11]后来你修改了参与hashCode()计算的数据user.name 李四;新的 Hash 可能变成456再查询的时候456 ↓ table[8]程序会去table[8]找。但这个对象实际上还躺在table[11]于是可能出现一种很奇怪的情况对象明明在 HashMap 里却找不到了。所以作为 Hash Key 的对象参与equals()和hashCode()的字段最好保持稳定。这也是为什么 Java 里String非常适合作为 HashMap 的 Key。因为 String 是不可变对象。十三、hashCode 相同两个对象就一定相同吗不一定。例如对象A → hashCode 9527 对象B → hashCode 9527它们完全可能是两个不同对象。所以 HashMap 判断 Key通常不是只看hashCode()还需要看equals()可以理解成两步第一步 hashCode ↓ 快速找到大概位置然后第二步 equals ↓ 确认到底是不是这个Key所以hashCode()负责快速定位equals()负责最终确认。这两个方法在哈希结构中通常是配合使用的。十四、为什么哈希查询平均是 O(1)现在整个逻辑就非常清楚了。普通查找从第一个开始 ↓ 一个个比较 ↓ 直到找到可能是O(n)而哈希表Key ↓ Hash ↓ 数组下标 ↓ 直接定位桶理想情况下只需要少量固定操作。数据从1000条增加到100万条并不意味着每次查询都必须多扫描几十万条数据。所以平均情况下HashMap 的put() get()都可以达到接近O(1)当然这个 O(1) 是建立在Hash 分布比较均匀数组容量合理冲突数量可控这些条件之上的。十五、真正理解哈希只需要抓住一条主线很多人学哈希时会被各种概念绕晕Hash hashCode HashMap 桶 链表 红黑树 负载因子 扩容 哈希冲突其实它们都围绕着同一个问题如何把一个原本需要“搜索”的问题变成一个可以“直接定位”的问题。整个 HashMap 的底层逻辑可以压缩成Key ↓ hashCode ↓ Hash计算 ↓ 数组下标 ↓ 找到桶 ↓ equals确认Key ↓ 返回Value而如果发生冲突数组 ↓ 链表 ↓ 冲突严重 ↓ 红黑树如果数据越来越多冲突增加 ↓ 扩容 ↓ 重新分散数据到这里HashMap 大部分设计其实已经串起来了。写在最后哈希真正厉害的地方不是它使用了什么特别神秘的算法。它背后的核心思想反而非常简单既然数组可以通过下标直接定位那我就想办法把任意 Key 转换成一个数组下标。于是有了Key → Hash → 下标 → 数组但现实中不同 Key 又可能算出相同的位置所以需要解决哈希冲突数据多了以后冲突又会增加所以需要扩容冲突严重以后链表查询又会变慢所以又引入红黑树。你会发现HashMap 的很多复杂设计并不是凭空出现的而是在“数组直接定位”这个最简单的思想上一层层解决现实问题演化出来的。理解了这一点再去看HashMap源码就不会只看到一堆hash、table、Node和位运算。你看到的其实是一整套非常经典的设计思想用哈希计算缩小搜索范围用空间换时间用合理的数据结构处理冲突。