How does HashMap work?HashMap 是怎么工作的？

01One sentence一句话

Say this first先说这句

A HashMap is a box of small boxes. You give it a key, and it gives you back a value very fast. Inside, it uses an array. Each box in the array is called a bucket. When two keys fall into the same bucket, they stand in a line.HashMap 是一个装着小盒子的盒子：给它 key，它很快还你 value。底层是一个数组，数组里每一格叫一个桶。两个 key 落进同一个桶时，就排成一队（链表）。

01bThe whole thing in nine sentences九句话讲清楚（零基础版）

1. It is a box: you give it a name (key), it gives back the thing (value) — fast.它是个盒子：给它一个名字（key），它很快把对应的东西（value）还给你。
2. Inside is a row of numbered boxes: an array of 16 buckets, numbered 0–15.里面是一排带编号的格子，共 16 个，编号 0–15。这排格子就叫数组。
3. When you put something, it computes a number from the key. That number is the hash.放东西时，它拿 key 算出一个数字，这个数字叫 hash。
4. The hash picks a bucket. Next time you look up the same key, it picks the same bucket — no searching.用 hash 选格子。下次用同样的 key 来拿，还是同一个格子——不用一格格找，所以快。
5. Two different keys can get the same bucket. That is a collision. The fix: put them in a line inside that bucket.两个不同的 key 可能选中同一个格子，这叫冲突。办法：在这个格子里挂一条队伍。
6. Looking up a key in a line means comparing names one by one — until the name matches.格子里是队伍时，就顺着队伍一个一个比名字，比到为止。
7. When one line reaches 8 items, the line becomes a red-black tree, so a lookup takes only a few steps.某一格排到 8 个时，这条队伍变成红黑树——查东西只要几步。
8. At 75% full, the array doubles from 16 to 32, and items are re-split. No hash is recomputed.装到 75% 满时，数组从 16 格扩成 32 格，东西重新分一遍；技巧是不用重算 hash。
9. It is not thread-safe: two threads writing at once can overwrite each other. Use ConcurrentHashMap.它线程不安全：两个线程同时写会互相覆盖、丢数据。并发里用 ConcurrentHashMap。

If all nine are clear, you can already answer this question in an interview. The rest is detail.这九句都清楚，这道题你已经会答了。剩下的都是细节。

02What is inside里面是什么

Outside, it looks like a table of names and values:从外面看，是一张“名字 → 值”的表：

Inside, it is an array of buckets. A bucket has three possible states: empty, a short line, or a tree.从里面看，是一个桶数组。一个桶只有三种状态：空、短链、树。

03How put worksput 的六步

1. Make the table — the first put creates the array with 16 buckets.建表——第一次 put 才创建 16 格数组。
2. Compute the hash — (h = key.hashCode()) ^ (h >>> 16), mixing high bits into low bits.算 hash——(h = key.hashCode()) ^ (h >>> 16)，把高位混进低位。
3. Find the bucket — index = (n - 1) & hash; because n is a power of two this equals hash % n, but faster.定位桶——index = (n - 1) & hash；因为 n 是 2 的幂，这等价于 hash % n，但更快。
4. Empty bucket? — put a new node there. Done.桶是空的？——放一个新节点，结束。
5. Not empty? — same key → replace the value; different key → go to the end of the line; at 8 items the bucket may become a tree.不空？——key 相同就覆盖 value；不同就挂到链尾；到 8 个可能树化。
6. Too full? — if size > capacity × 0.75, double the array.太满了？——超过 容量 × 0.75 就扩容一倍。

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;                  // 1. create the array
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);     // 2. empty bucket
else {
    if (p.hash == hash && (p.key == key || key.equals(p.key)))
        e = p;                                    // 3. same key: replace
    else if (p instanceof TreeNode)
        e = ((TreeNode) p).putTreeVal(...);   // 4. bucket is a tree
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);  // 5. add at the end
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);                 //    line too long: tree
                break;
            }
            if (e.hash == hash && (e.key == key || key.equals(e.key))) break;
            p = e;
        }
    }
    if (e != null) { V old = e.value; e.value = value; return old; }
}
++modCount;
if (++size > threshold) resize();                 // 6. too full: grow
return null;

04Why resize is cheap为什么扩容不贵

From 16 to 32, an item has only two possible places: where it is, or where it is + 16. One bit decides:从 16 扩到 32，每个元素只有两种去处：原位，或者原位 + 16。看一位就够：

if ((e.hash & oldCap) == 0)  keep the item at index i
else                          move it to index i + oldCap

So HashMap does not recompute every hash. It splits each bucket into two short lines.所以不用重算每个 hash，只是把每个桶拆成两条短链。

05Two numbers: 0.75 and 8两个数字：0.75 和 8

06Why it is not thread-safe为什么线程不安全

Two threads call put at the same time: both read size, both write it back — one update is lost. In JDK 7, two resizes at once could bend a list into a circle and get would spin forever.两个线程同时 put：都读到 size、都写回——丢掉一次更新。JDK 7 里两个线程同时扩容，甚至能把链拧成环，get 就永远转不出来。

So in a web application I use ConcurrentHashMap: it locks only the bucket being changed.所以 Web 应用里我用 ConcurrentHashMap：它只锁正在改的那个桶。

Long version: Lesson 7.完整版：第 7 课。

07Go deeper, one idea at a time再往下学，一次一个概念

• Lesson 1: What is an array?第 1 课：什么是数组
• Lesson 2: What is a linked list?第 2 课：什么是链表
• Lesson 3: What is a tree? Red-black tree?第 3 课：什么是树、红黑树
• Lesson 4: key, hash, collision第 4 课：key、hash、冲突
• Lesson 5: O(1), O(n), O(log n)第 5 课：O(1)、O(n)、O(log n)
• Lesson 6: HashMap methods in real code第 6 课：HashMap 方法与真实用法
• Lesson 7: Why it is not thread-safe第 7 课：为什么线程不安全

08Interview script面试话术（60 秒）

Four steps, always in this order: structure → collision → resize → limits.四步，顺序固定：结构 → 冲突 → 扩容 → 边界。

1. Structure: an array of buckets, O(1) lookup.结构：一个数组，每格一个桶，平均 O(1)。
2. Collision: same bucket → list → tree at 8.冲突：同一个桶 → 链表；8 个转红黑树。
3. Resize: over 0.75 × capacity → double, no hash recompute.扩容：超过容量 0.75 翻倍，不重算 hash。
4. Limits: not thread-safe → ConcurrentHashMap.边界：线程不安全 → 用 ConcurrentHashMap。

Say this, 60 seconds照这段说，60 秒

HashMap is an array of buckets. To put a value, it computes the key hash code, uses it to pick a bucket, and stores the entry there, so a lookup is O(1) on average.HashMap 底层是一个数组，每一格叫一个桶。放数据时先用 key 的 hashCode 算出 hash，用 hash 定位到桶，所以查找平均是 O(1)。

If two keys land in the same bucket, that is a collision: the bucket keeps a linked list. When a list reaches 8 entries and the array has at least 64 buckets, the list becomes a red-black tree, and lookup drops from O(n) to O(log n).如果两个 key 落到同一个桶，就是哈希冲突：桶里挂一条链表。链表到 8 个、并且容量至少 64 时，会转成红黑树，查找从 O(n) 降到 O(log n)。

When the number of entries passes capacity times 0.75, the array doubles. Because the capacity is a power of two, every entry either stays where it is or moves by the old capacity, so no hash is recomputed.元素超过容量 × 0.75 时扩容一倍。因为容量是 2 的幂，每个元素要么留在原位、要么挪到「原位 + 旧容量」，所以不用重算 hash。

It is not thread-safe: two threads putting at once can lose data. So for shared mutable state I use ConcurrentHashMap, and I keep plain HashMap for read-only dictionaries and grouping.它线程不安全，多线程同时 put 会丢数据，所以共享可变状态我用 ConcurrentHashMap；只有只读的字典和分组统计我才用 HashMap。

Last line, and make it yours — pick one of these from your own projects:最后一句，换成你自己的项目（选一条你说得出口的）：

• Selling machines / satellite stations: ConcurrentHashMap<String, Channel> holds 300+ online devices.智能售货机 / 卫星地面站：用 ConcurrentHashMap 管 300+ 台在线设备的连接和状态。
• News ranking: count views in a local ConcurrentHashMap, flush to a Redis sorted set every minute.热搜榜：本地 ConcurrentHashMap 先计数，每分钟刷进 Redis 有序集合算排名。
• Order system: index multi-platform orders by platform order id, and cache the status dictionary.订单系统：按平台单号建索引做去重匹配，状态字典放只读 Map 里缓存。
• Data reporting: the form engine carries dynamic fields in Map<String, Object>, stats by groupingBy.数据报送：模板化表单用 Map<String, Object> 承载动态字段，统计用 groupingBy。

Before you memorise anything: play the 5-minute bucket game — you will feel the collision, the resize and the tree.背之前先手过一遍：玩 5 分钟装桶小游戏——冲突、扩容、树化，手上过一遍就记住了。

09Eight follow-ups八个必答追问

10Three things not to say三句别说

• I read the source code — one question and it shows.「我看过源码，我背过 putVal」——一追问就露。
• I tuned the load factor to 0.5 — they will ask for your benchmark data.「我把 loadFactor 调成 0.5 优化过」——会问你要压测数据。
• HashMap is thread-safe — that ends the interview.「HashMap 是线程安全的」——直接出局。

When you truly do not know: say what you guess, then say you will check the source. Honest plus a direction beats making it up.真不会的时候：说你的推测，再说回去查源码确认。诚实 + 有方向，比你硬编好得多。

→New words新词

Click ▶ hear it for real people on YouGlish; 🔊 for the computer voice.点 ▶ hear it 听真人发音（YouGlish）；点 🔊 听电脑朗读。

✓Check yourself自测

1. Explain the whole thing in 60 seconds, in English.用英文把整件事讲 60 秒。
2. Where does the bucket index come from?桶的位置是怎么算出来的？
3. Why does resize not recompute the hash?为什么扩容不用重算 hash？
4. What would you say if I ask “then why not always use ConcurrentHashMap?”如果我问“那为什么不干脆一直用 ConcurrentHashMap”，你怎么答？

Answer out loud first. Only then open the answers below.先自己出声答，再看下面的答案。