学 HashMap 的时候，我被这几个设计细节惊到了
学 Java 以来，HashMap 是我听过最多、也最让我头疼的一个东西
真正开始啃源码的时候，我才发现 HashMap 的设计比我想的复杂得多，也巧妙得多。这篇就写写我从"会用"到"大概懂了"的整个过程。从一个新手的视角，把 HashMap 最核心的几个机制串一遍。
开始之前，Map 家族都有谁
学 HashMap 之前，我其实连 Map 这个概念都搞不太清楚。List 和 Set 我知道：List 是一排数据，Set 是一堆不重复的数据。但 Map 呢？它存的是一对一对的东西，每对有一个 key 和一个 value，你可以通过 key 找到对应的 value。
Java 里常见的 Map 实现有这么几个：
- HashMap：最常用的，基于哈希表，存键值对。它的问题是不保证顺序，也不安全。
- LinkedHashMap：HashMap 的小弟，多了个双向链表，能记住你插入的顺序，或者按访问顺序排。
- TreeMap：基于红黑树，key 会按大小排序。你可以用自然排序，也可以自己传个 Comparator。
- Hashtable：老前辈了，线程安全的，但因为它的方法全用 synchronized 包了一层，性能不太行，现在已经不怎么用了。
- ConcurrentHashMap：真正的线程安全选手，性能比 Hashtable 好得多，后面会单独讲。
一开始我记不住这么多，只知道最常用的就是 HashMap。但搞清楚它们之间的区别有个好处：面试的时候问"HashMap 和 Hashtable 有什么区别"这种问题，答案就藏在这里面。
而且说实话，日常开发 90% 的 Map 场景用 HashMap 就够了。剩下 10% 才需要考虑 LinkedHashMap 或者 ConcurrentHashMap。
HashMap 的底层到底长什么样
我之前以为 HashMap 里面就是一张简单的表，key 存一格，value 存一格，像 Excel 那样。
后来才知道完全不是这么回事。
JDK 1.7 的时候
在 JDK 1.7 及之前，HashMap 的底层结构是数组加链表。
怎么理解呢？你可以把数组想象成一排桶，每个桶有一个编号。你把一个键值对放进去的时候，HashMap 会根据 key 的哈希值算出一个数字，这个数字决定这个键值对应该丢到哪个桶里。
但问题来了：不同的 key 算出来的哈希值可能对应同一个桶。这就叫哈希冲突。
怎么办？那个桶里不止放一个元素，而是放一个链表。冲突了就把新的元素挂在链表的后面。
但这样有个问题：如果一个桶里的链表变得很长（比如几十个元素都挤到同一个桶里），那我要找某个 key 的时候，就得在这个链表里一个一个比，速度就慢下来了。链表查找的时间复杂度是 O(n)。
当时我还在想，那如果 key 特别多，链表特别长，HashMap 不就废了吗？这个担心是有道理的，所以 JDK 1.8 做了改进。
JDK 1.8 之后
JDK 1.8 把结构改成了数组加链表加红黑树。
核心变化是：当某个桶的链表长度达到一定阈值（默认为 8），而且整个数组的长度也达到 64 的时候，这个链表会转成一棵红黑树。红黑树查找的时间复杂度是 O(log n)，比链表的 O(n) 快了不少。
我第一次看到这个设计的时候，心想这思路挺聪明的：大多数情况下链表不长，用链表就够了，开销小；万一真的有很多 key 冲突到一起，就升级成红黑树补救一下。不搞一刀切。
不过有个条件我一开始忽略了：链表长度 ≥ 8 的时候，它不会立刻树化，还得看数组的长度有没有达到 64。如果数组长度还没到 64，它会先做扩容，把数组变大，让元素分散开，链表自然就短了。只有当数组长度也到 64 了，链表还是太长，才转为红黑树。
反过来，如果后面元素被删了，红黑树的节点数 ≤ 6 的时候，它又会退化回链表。这个 8 和 6 之间留了 2 的缓冲，避免了频繁地在链表和红黑树之间切换。
这个设计我当时琢磨了好一会儿才想通：它其实是个分级应对的策略：正常情况用链表，冲突严重了点扩容，扩容还不够再升级红黑树。
put 方法到底做了啥
先说说 put，就是往 HashMap 里存数据的时候会发生什么。
我第一次猜的是：直接算个位置，丢进去就完了。但看完源码发现步骤比我想象的多。
第一步：算位置
HashMap 先把 key 的 hashCode 拿过来，再做一次扰动处理（就是把 hashCode 的高位和低位做个异或），目的是让算出来的哈希值更均匀。然后通过(n - 1) & hash算出这个 key 应该放在数组的哪个位置。n 是数组的长度。
这里的&是位运算，比取模快得多。但有个前提：数组长度必须是 2 的 n 次方，后面会细说。
第二步：检查数组该位置是不是空的
如果算出来的那个位置是空的，太好了，直接 new 一个 Node 放进去就行。
这就是最简单的情况。
第三步：位置不为空，开始比较
如果那个位置已经有人占了，那就需要判断了。先看占位的这个 Node 和我们要放的 key 是不是同一个，比较哈希值和 equals。如果是同一个 key，就直接替换 value。
第四步：遍历链表或者红黑树
如果第一个节点不是我们要的 key，就看后面还有没有。如果这个桶里面是链表结构，就一个一个往后遍历，找到相同的 key 就替换值，没找到就在链表尾部追加。如果桶里面已经是红黑树了，就走红黑树的查找逻辑去找。
说到链表，我顺便提一句：JDK 1.7 的时候用的是头插法（新节点插到链表头部），JDK 1.8 改成了尾插法（插到尾部）。这是因为头插法在多线程扩容的时候可能产生环形链表，导致 get 的时候死循环。JDK 1.8 改成尾插法以后这个 bug 就没了。
第五步：检查要不要树化
如果刚才是在链表里追加了元素，追加完后 HashMap 会检查这个链表的长度是不是 ≥ 8 了，如果数组长度也 ≥ 64，就会把链表转成红黑树。
第六步：检查要不要扩容
最后，HashMap 会检查目前存了多少个元素（size）有没有超过容量 × 负载因子。如果超过了，就触发扩容，把数组变成原来的 2 倍，然后把老数据重新分配。
我当时看完这个流程，觉得最让我意外的是：一个看起来简单的 put 操作，背后竟然有这么多判断。但也正是因为这些设计，HashMap 才能在大部分情况下保持 O(1) 的性能。
get 方法怎么找到数据的
get 方法比 put 简单一些。
我还是会习惯性地先去找 getNode 方法，因为 get 本身只是调了一下 getNode。
过程大概是这样的：
- 先检查 table 数组有没有被初始化，数组长度是不是大于 0，算出来的那个位置是不是有节点。如果这些条件有一个不满足，直接返回 null。
- 检查位置上的第一个节点：如果哈希值和 key 都匹配上了，直接返回这个节点。
- 如果第一个不是，就看它有没有下一个节点。如果有，判断当前桶是链表还是红黑树：
- 链表：用 do-while 循环挨个比较 key，找到了就返回。
- 红黑树：走红黑树的查找算法去找。
- 如果整个走完都没找到，返回 null。
这个流程看完我最大的感受是：HashMap 在每次 get 的时候都先检查第一个节点，这个细节挺有实用性的：如果每个桶里的元素不多（这是大多数情况），第一个节点往往就是你要找的，一次比较就返回，不需要再去判断是链表还是树。
扩容机制，我觉得最巧妙的部分
HashMap 的扩容，我第一次看源码的时候没太看懂，后来画了几张图才弄明白。
什么时候扩容
当 HashMap 里的元素个数超过了容量 × 负载因子的时候，就会触发扩容。
比如默认容量是 16，负载因子是 0.75，那么当存到第 13 个元素的时候（16 × 0.75 = 12，也就是超过 12 个的时候），就会触发扩容。
怎么扩容
扩容分两步：
第一步：把数组扩大到原来的 2 倍。
第二步：把旧数组里的元素重新分配到新数组里。
关键就在这个第二步。
我原以为扩容就是把每个元素重新计算一遍哈希值，然后放到新数组对应的位置上去。
但 JDK 1.8 的 HashMap 没有这么做。
它利用了一个很巧妙的设计：因为新容量是旧容量的 2 倍，而容量始终是 2 的 n 次方，所以每个元素的新位置要么是原来的索引，要么是原来的索引 + 旧容量。
判断方法是看(e.hash & oldCap)的结果。如果结果是 0，就留在原位置；如果不是 0，就移动到"原位置 + oldCap"。
举个例子：旧容量是 16，某个 key 的 hash 值是 20，它在旧数组的位置是 20 & 15 = 4。扩容后新容量是 32，我们算一下 20 & 16，结果是 16，不是 0，所以它应该去的位置是 4 + 16 = 20。
我当时自己手算了一遍，发现确实是这样。灵感来源是：因为 2 倍扩容后，"n-1"的二进制低 n 位就多了一位（从 1111 变成 11111），所以新索引其实就是看 hash 值新增的那一位是 0 还是 1。是 0 就不动，是 1 就加 oldCap。
这个设计的妙处在于两点：
- 不需要重新计算 hash，省了一次哈希计算的开销。
- 能把旧数组里同一个桶的元素均匀分散到两个位置。因为 hash 值新增的那一位是 0 还是 1 可以认为是随机的，所以原来冲突的元素会被拆成两拨，分别放在"原位置"和"原位置 + oldCap"上。
我看明白这个之后，确实觉得这个设计很漂亮。一个简单的位运算，把扩容时最麻烦的两个问题一起解决了。
为什么容量必须是 2 的 n 次方
这个其实上面已经提到了：HashMap 里很多操作都依赖数组长度是 2 的 n 次方。我刚学的时候没太在意这个，觉得"是不是 2 的 n 次方能有多大区别"，后来仔细算了算才发现差别很大。
主要原因有三个：
1. 用位运算代替取模
HashMap 计算索引的核心公式是hash & (length - 1)。
当 length 是 2 的 n 次方时，这个位运算等价于hash % length。但位运算比取模快得多，位运算直接操作二进制位，而取模需要做除法。
如果 length 不是 2 的 n 次方，length - 1 的二进制就不是全 1 的形式，这个位运算就不等价于取模了。
2. 让索引分布更均匀
还是回到上面那个公式。当 length 是 2 的 n 次方时，length - 1 的二进制低 n 位全是 1（比如 length=16 时，15 的二进制是 1111），这样 hash 值的低 n 位每一位都能参与决定最终索引的位置。
如果 length 不是 2 的 n 次方，比如 length=15，length-1=14（二进制 1110），最后一位是 0。这意味着不管 hash 的最后一位是 0 还是 1，与运算的结果最后一位都是 0，所以索引的奇数位永远用不到，数组空间浪费了一半，碰撞概率也高了很多。
我当时看到这个例子的时候，心想这个设计约束确实是有道理的。不是 2 的 n 次方的话，损失太大了。
3. 扩容时不用重新计算 hash
这个上面扩容那节已经讲过了。正是因为容量一直是 2 的 n 次方，扩容时才能用hash & oldCap来判断新位置。
这三个原因是环环相扣的：为了让位运算生效，所以必须是 2 的 n 次方；因为必须是 2 的 n 次方，所以扩容时可以用位运算优化。整个设计是自洽的。
负载因子 0.75 为什么刚刚好
HashMap 默认的负载因子是 0.75。学到这里的时候我就好奇：为什么是 0.75？不是 0.5 或者 1？
负载因子的本质是：空间和时间之间的取舍。
- 如果负载因子太小（比如 0.5），HashMap 里用的桶还没装多少东西就开始扩容了。好处是冲突少，每个桶里的链表短，查得快。坏处是很多空间是空的，浪费内存。
- 如果负载因子太大（比如 1），HashMap 要把桶几乎装满才扩容。好处是空间利用率高。坏处是冲突变多，每个桶里的链表长，查得慢。
- 0.75 就是在空间和时间之间取了一个平衡点。在理想情况下，当负载因子是 0.75 时，HashMap 在时间性能和空间利用率上都能接受。
我从一本书上看到说，0.75 这个值是基于泊松分布算出来的。当负载因子是 0.75 时，链表长度超过 8 的概率非常低（小于千万分之一），所以正常情况下红黑树其实很少会触发生效，大多数时候链表就够了。这也解释了为什么 JDK 1.8 要把树化阈值设为 8：正常情况下链表长度几乎不会到 8，到了说明冲突已经很严重了，是时候升级了。
几个值得一提的小特性
HashMap 还有一些小细节，我当初看的时候觉得挺有意思的。
第一个是null 作为 key。如果你用 null 做 key，HashMap 的处理方式是：直接把 hash 值设成 0，然后放到 0 号桶里。所以 null key 只能有一个（因为每次都会覆盖到同一个桶），但 null value 可以有多个。
我当时问自己：如果我不给 key 传 null，调 get(null) 会怎么样？答案是：不会抛异常，因为 HashMap 明确处理了这种情况。不像 Hashtable，传 null 进去就直接抛 NullPointerException 了。
第二个是默认容量。HashMap 默认初始容量是 16，每次扩容变成原来的 2 倍。如果你在构造的时候指定了一个初始容量，HashMap 会把它调整成大于等于这个数的 2 的 n 次方。比如你传 10，它实际用的是 16；你传 30，它用 32。保证数组长度始终是 2 的 n 次方。
我之前有个问题：往 HashMap 里存 20 个元素，会扩容几次？答案是只扩一次。因为前 12 个元素不用扩，第 13 个触发扩容到 32，后面 7 个（第 14 到第 20 个）都在容量范围内。
怎么遍历一个 Map
最后说说遍历。Map 不像 List 那样直接用索引遍历，它有几种不同的方式。
我开始最常用的是增强 for 循环加 entrySet：
for(Map.Entry<String,Integer>entry:map.entrySet()){System.out.println(entry.getKey()+" -> "+entry.getValue());}这个写法最直接，能同时拿到 key 和 value。
如果只需要 key，可以用 keySet：
for(Stringkey:map.keySet()){System.out.println(key);}如果需要边遍历边删除元素，就得用迭代器：
Iterator<Map.Entry<String,Integer>>it=map.entrySet().iterator();while(it.hasNext()){Map.Entry<String,Integer>entry=it.next();if(someCondition){it.remove();}}这个和 List 的迭代器是同一个道理：只能在迭代器自己的 remove 方法里删，不能在循环里直接调 map.remove。
JDK 8 以后多了 Lambda 表达式和 forEach 方法，代码变得更短了：
map.forEach((key,value)->System.out.println(key+" -> "+value));还有 Stream API 的方式，如果你需要过滤或者做一些转换：
map.entrySet().stream().filter(entry->entry.getValue()>10).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue));这几种方式我平时用 entrySet 最多，偶尔用 forEach 和 Stream。迭代器通常只在需要遍历时删除元素的时候才用。
写在最后
写这篇东西的时候，我一直想着当初啃 HashMap 源码的自己。那时候看到 put 和 get 的源码，一行一行地对着文档看，好几处看了好几遍才看懂。
HashMap 给我的感觉是：它看起来是个简单的容器，但你越往里挖，越能发现设计者的用心。
数据结构从数组 + 链表演进到数组 + 链表 + 红黑树，扩容时用hash & oldCap来决定元素新位置，把容量设计为 2 的 n 次方来实现位运算代替取模，这些设计不是孤立的，它们互相配合，形成了一个有机的整体。
学完这些之后，我再去用 HashMap 的时候，感觉就不一样了。以前它就是"一个能放键值对的东西"，现在我知道它背后做了什么、为什么这么做。
当然，这篇讲的主要是 HashMap 单线程下的工作机制。它的线程安全问题、红黑树为什么不用平衡二叉树、equals 和 hashCode 怎么重写，这些话题也挺重要的，下篇再聊。
如果这篇文章让你对 HashMap 有了一点新的理解，那就够了。毕竟我也是这么一点点啃过来的。