Context
关于 HashMap, 有一件事儿一直很困惑，，在『Redis 核心历险』中是这样被提到的:
Redis 的字典相当于 Java 语言中的 HashMap，它是无序字典，内部存储了很多键值对。实现结构上与 Java 的 HashMap 也是一样的，都是”数组 + 链表”二维结构。第一维的 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。
嗯，第一句没啥问题，，然而”数组 + 链表”什么鬼？还有 hash 碰撞。。作者并没有详细解释这儿，应该默认是每个 Java 开发者都知道的知识点了。然而我却在这儿卡壳了，心慌慌。。趁着周末赶紧补补课。事实证明，这波补课是很有效果的，在这本书后边的内容中，hash 还将会一直出现。
Hash
在 Wiki 中的定义为:
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
用我自己的话来说就是，，为数据创建指纹摘要，通过该摘要就可以找到原始数据。我觉得更多的场景是为相对大的数据创建摘要。假如有个 hash()，可以为任意数据生成一个32位的摘要。那么我们在互联网下载文件的时候，有的网站会在下来链接处给出该文件的 hash 值，等用户下载完成之后，通过 hash() 对该文件提取摘要，将两个 hash 值，进行对比。如果结果一样，说明文件在下载过程中没有被篡改。
那倘若我们对数字 1 进行 hash()，那应该也会得到一个长度为 32 位的摘要，但这时候还能叫『摘要』么？我感觉是不太合适的。
HashMap
OK，back to the point..关于 Hash 我们需要知道👇
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。
按我之前不成熟的想法，，HashMap 中为什么要放链表？直接放数据对象不就够了么。。原因就是当我们通过 get(key) 方法从 HashMap 中获取对象的时候，理论上这个 key 对应的 hash 值和某个 whateverKey 对应的 hash 值是一样的(即，散列碰撞)，，因为『如果两个散列值相同，两个输入值很可能是相同的，但也可能不同(即，key 和 whateverKey)』。此时我们可以通过 key 和 whateverKey 都可以获取到对应的数据对象。如此，为了解决散列碰撞带来的问题，我们需要在 HashMap 中将两个‘key’都指向同一个数据对象，而在 HashMap 中的链表就是用来维护这些‘key’的。下面，我们试着读读 HashMap 源码。
HashMap 的 DOC 注释
1 |
|
put() 方法
1 | public V put(K key, V value) { |
get() 方法👇
1 | public V get(Object key) { |
remove() 方法
1 | public V remove(Object key) { |
entrySet() 方法
1 | /** |
到这里之后是有点儿懵的，，因为 entrySet0() 方法中第一行代码，entrySet在 HashMap 中是这样声明的：👇1
private transient Set<Map.Entry<K,V>> entrySet = null;
之后在其他地方没有明确对其进行赋值的代码，然鹅我们在 Test 类进行 for(Map.Entry<String,String> m: map.entrySet()) 循环时，entrySet明明是有值的。那么 map.entrySet() 到底是在什么时候进行赋值的呢？！这个问题困扰了我很久，在 HashMap 显式继承的 AbstractMap 类和实现的 Map<K,V> 接口中，也没有找到答案。出门遛了一圈，突然想到了 Test 类被编译之后的 class 文件！！然后用 JD-JUI 反编译之后，终于有些发现了：👇1
2// class 文件反编译之后的 forEach 循环
for (Iterator i$ = map.entrySet().iterator(); i$.hasNext(); localEntry = (Map.Entry)i$.next())
👆我们可以看到，虽说用的是 forEach 循环，但在编译之后还是通过 Iterator 迭代器进行遍历的。首先初始条件 Iterator i$ = map.entrySet().iterator()，我们可以看到 map.entrySet() 返回的是一个 Set<Map.Entry<K,V>>，所以其 iterator() 是 Set 接口实现类的 iterator() 方法。我们继续看 entrySet0() 方法的第二行代码，在 entrySet 为空的情况下，会初始化一个新的 Set<Map.Entry<K,V>> 对象，即 new EntrySet()，我们看看 EntrySet 类：👇
1 | private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { |
<<<<<<<<<<<< 2019-04-02.update
上个月末的时候，花了一个晚上更新了下简历，但并没有到处去投，只是对外可见。陆陆续续开始有公司接触，其中还接到一个电话面试，，是某外包公司的。突如其来的电话面试，有点仓促，但好在前端时间也一直在看书恶补。其中有个很基础的问题，，『简单说下 Java 集合框架各容器类之间的关系』。多亏了学习 『Redis 核心历险』时，对 LinkedList 多看了一眼，也经受住了超越妹妹的考验。当中面试官特地提到 Map 和 Collection 有没有关系? 可以确定是肯定有关系，但有什么关系呢？没有答上来。。那时还没有整理 HashMap 这篇文章，只有 LinkedList。其实在整理这篇文章时也没找到两者之间的关系，因为 interface Map<K,V> 与 interface Collection<E>并没有直接的继承关系。。这时候需要感谢的是『码出高效 Java 开发手册』了，平时把这本书放在了床头，睡前会翻一翻从此再无失眠，并没有从第一张开始读，而是直接挑了最薄弱的数据结构与集合这一章。
OK，下面来说说 Map 和 Collection 的关系！在书中是这样描述的: 👇
在数据元素的存储、查找、修改和遍历中，Java 中的 Map 类集合都与 Collection 类集合存在很大的不同。它是与 Collection 类平级的一个接口，在集合框架图上，它有一条微弱的依赖线月 Collection 类产生联系，那是因为部分方法返回 Collection 视图，比如 values() 方法返回的所有 values 的列表
我们先看 Map 接口的 values() 方法：👇1
2// Map 接口类
Collection<V> values();
非常明显，，说到values()方法，肯定会想到 keySet() 和 entrySet() ，毕竟这三个方法在 HashMap 迭代的时候可是肩并肩的~👇1
2
3// Map 接口类
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();
我们再看看，这三个方法在 HashMap 中的实现~ 👇1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44// values 方法
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
// Values 类，AbstractCollection 类实现类了 Collection 接口
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
// keySet 方法
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
// KeySet 类，abstract class AbstractSet<E> 继承了 AbstractCollection<E> 实现了 Set<E>，而抽象类 AbstractCollection 和 Set 接口 都继承了 Collection 接口。
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
// 至于 entrySet() 方法，我们在分析 HashMap 的 forEach 循环时已经挖过源码了。EntrySet 类与 KeySet 类一样，都继承了 AbstractSet 抽象类。
