What is a key? A hash? A collision?什么是 key？什么是 hash？什么是冲突？

A key is a name. A hash is a number made from it. A collision is two names with the same number.key 是名字；hash 是由它算出来的编号；冲突是两个名字算出了同一个编号。

Short answer先给答案A key is the name you look things up by. A hash is a number computed from that key. A collision is two different keys that get the same number, so they share a bucket. HashMap answers a collision with a short list, and with a red-black tree once one bucket holds 8 items.key 是你用来查东西的名字；hash 是由这个 key 算出来的一个数字；冲突是两个不同的 key 算出了同一个数字，于是挤进同一个桶。HashMap 用一条短链处理冲突，桶里攒到 8 个就换成红黑树。

Basics基础HashMapHashMapmust know必背

01Key: the namekey：名字

A key is what you look things up by. map.put("apple", 5) — here the key is "apple", the value is 5.key 是你用来查东西的名字。map.put("apple", 5) 里，key 是 "apple"，value 是 5。

In Java, a key must have two methods that agree with each other: hashCode() and equals().Java 里 key 必须有两个互相配合的方法：hashCode() 和 equals()。

02Hash: the numberhash：编号

Think of it like this先这样想A cloakroom. You give a coat, you get a ticket with a number. The number tells the staff which shelf to use. The coat is the key, the number is the hash, the shelf is the bucket.寄存处：你交出外套，拿到一张带编号的票，编号告诉工作人员去哪个架子。外套＝key，编号＝hash，架子＝桶（bucket）。

hash = key.hashCode()          //  a number, like -1894770
index = (n - 1) & hash          //  which bucket: 0 .. n-1

The hash is not the memory address and not the value. It is only a number used to pick a bucket.hash 不是内存地址，不是 value，只是一个用来选桶的编号。

Java 8 also mixes the high bits into the low bits: (h = key.hashCode()) ^ (h >>> 16). If the high bits are all the same, some buckets would be overused.Java 8 还做了高低位混合 — (h = key.hashCode()) ^ (h >>> 16)。如果不混合，高位相同的 key 会挤在同一批桶里。

03Collision: the same number冲突：编号撞了

There are about four billion possible ints, but a HashMap has only 16 buckets at the start. Two different keys can easily get the same bucket. That is a collision.int 有四十亿种可能，但 HashMap 一开始只有 16 个桶，两个不同的 key 很容易落到同一个桶。这就是冲突。

A collision is not a bug. There are only three ways to handle it, and HashMap uses the first two:冲突不是 bug。处理冲突只有三种办法，HashMap 用了前两种：

Separate chaining — keep a short list in the bucket (what HashMap does for small counts).拉链法——桶里挂一条短链（HashMap 数量少时就这么做）
Treeify — when one bucket has 8 items, turn that list into a red-black tree (HashMap, Java 8+).树化——一个桶攒到 8 个，就把短链变成红黑树（Java 8+ 的 HashMap）
Open addressing — move to the next free bucket (ThreadLocalMap, not HashMap).开放寻址——往下一个空桶放（ThreadLocalMap 用这种，HashMap 不用）

04Why we must handle it为什么必须处理冲突

If every key landed in its own bucket, looking up would be one step: O(1). When many keys share one bucket, you must walk the list inside it: O(n) in the worst case.如果每个 key 都落在自己的桶里，查找就是一步 O(1)。当很多 key 挤在一个桶，就得在桶里顺着链走，最坏是 O(n)。

That is the whole reason for the 0.75 load factor and the 8-item treeify rule: keep buckets short.负载因子 0.75 和“8 个树化”这两条规则，目的都只有一个：让每个桶都很短。

05equals and hashCode must agreeequals 和 hashCode 必须一致

If two keys are equals(), they must have the same hashCode(). Otherwise the map puts the same key into two different buckets, and you will “lose” a value.如果两个 key equals() 为真，它们的 hashCode() 必须相同。否则同一个 key 会被放进两个不同的桶，你就会“丢”数据。

So when you write equals(), always write hashCode() too — use your IDE, it generates both.所以重写 equals() 时一定同时重写 hashCode()——让 IDE 一次生成两个就行。

→New words新词

key /kiː/ The name you look things up by.key：用来查东西的名字 ▶ hear it

hash /hæʃ/ A number computed from a key.hash：由 key 算出的编号 ▶ hear it

hashCode /hæʃ koʊd/ The Java method that gives that number.hashCode：给出这个编号的 Java 方法 ▶ hear it

bucket /ˈbʌkɪt/ One box of the array.桶：数组里的一格 ▶ hear it

collision /kəˈlɪʒn/ Two keys with the same bucket.冲突：两个 key 落进同一个桶 ▶ hear it

equals /ˈiːkwəlz/ The method that says two keys are the same.equals：判断两个 key 是否相同 ▶ hear it

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

✓Check yourself自测

What is the difference between a key, a hash and a bucket?key、hash、桶，三者有什么区别？
Two keys collide — what does HashMap do?两个 key 冲突了，HashMap 怎么处理？
Why must equals and hashCode agree?为什么 equals 和 hashCode 必须一致？

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

Answers参考答案

01Key: what you give. Hash: the number computed from it. Bucket: the box that number points to.key：你给的名字；hash：由它算出的编号；桶：编号指向的那一格。

02Put the new node at the end of that bucket's short list. When the list reaches 8 and capacity is at least 64, that bucket becomes a red-black tree.把新节点挂到该桶短链的末尾。链到 8 个、并且容量至少 64 时，这个桶变成红黑树。

03Otherwise two keys that are equals() can land in different buckets, and one value looks lost.否则两个 equals() 相同的 key 会落到不同的桶，其中一个值就像丢了。

Next: Lesson 5, Big O →下一课：第 5 课，复杂度 →