本篇讲讲集合中代码最长，使用最广的Map类。以HashMap为例讲解JDK 1.8下的源码。为什么不先讲与List相似的Set，等看完本篇文章再去看HashSet的源码就明白了。
（一）HashMap基础
前两篇文章重点讨论了线性存储的集合List，List的每个单元存放某种类型的元素。HashMap属于散列存储的集合，以Key，Value键值对的形式存储元素。存储和访问都是通过Key生成对应的hash值进行插入或访问。
HashMap除了常用的构造方法，增加与访问元素方法外，另一个重要的方法是其扩容时调用的resize()和transfer()方法，这两个方法是HashMap线程不安全，造成并发死锁的直接原因，Chuck在接受阿里电话面试时就被问到这一点，当时没有答上来，三面就被刷掉了。后来用了一个两个小时的时间通读源码和多篇博文才搞清楚。该知识点将在之后的文章中专门讨论集合类线程安全时加以讲解。
（二）HashMap源码讲解
依旧是从定义讲起：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
这种继承关系想到ArrayList，继承AbstractList，实现List，Cloneable和Serializable接口。与之类似，HashMap所实现的Map接口是Map类集合的祖先，定义了remove()，put()，size()等Map通用方法，AbstractMap是一个抽象类，其中的普通方法有containsKey()，get()，size()等，但其中大多数方法在HashMap中是被重写了。
HashMap中Key，Value键值对的每个元素都是Map接口中中Entry接口实现类类的一个对象实例。Map接口中的Entry接口定义了一系列抽象方法，如getKey()，getValue()，equals()，hashCode()，comparingByValue()，comparingByKey()等，HashMap中通过内部类Node实现Entry定义如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
Key和Value是键值对，hash是通过hash函数计算出的哈希值，通过它可以查到元素在集合中的位置从而添加或访问。next属性可以看出HashMap中存在链式存储的结构。其实往后看会发现HashMap中不仅含有链式结构，在链表长度达到一定值后还会采用树结构存储，这样访问效率将会由O(n)降为O(logn)。
HashMap中定义个几个常量，对HashMap的控制起着至关重要的作用。
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
DEFAULT_INITIAL_CAPACITY：默认初始大小，在未指定初始大小构造时采用。注意是16不要和ArrayList的10搞混了。
MAXIMUM_CAPACITY：集合最大大小，一般达不到这么大。
DEFAULT_LOAD_FACTOR：默认的负载因子为0.75，负载因子
= 当前实际规模 / 集合规模，当该值大于负载因子是便会触发resize()函数，调整集合大小。
TREEIFY_THRESHOLD、UNTREEIFY_THRESHOLD和MIN_TREEIFY_CAPACITY：都与链表转二叉树操作有关。
那么HashMap中的元素究竟是存放在哪？以什么样的方式存储？这就又涉及以下属性：
transient Node<K,V>[] table; //Node数组，存放元素
transient Set<Map.Entry<K,V>> entrySet; //Set用于存储Map中的Entry
transient int size; //记录数组规模
transient int modCount; //记录Map被操作的次数
int threshold; //扩容阀值 = 数组大小 * 负载因子
final float loadFactor; //负载因子
重点注意table数组，键值对的存储通过hash函数对Key进行hash，确定其在数组的那个位置，然后以链表或者二叉树的方式存储。
在存储是存入键值对通过hash函数对Key进行hash，再通过hash值确定其在数组中的位置。
//hash计算过程为取Key的hashCode ^ (Key的hashCode >>> 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash()只是求得一个hash值，具体在table数组的哪个位置需要在putVal方法中确定，在老版本的jdk中，该部分有一个专门的方法名为indexFor，确定数组下标的公式是将hash()中求得的hash值&(table.length - 1)。在新版本的jdk中，计算所在位置的方法不变，只不过取消了indexFor()函数，计算过程在put操作中进行。
每每分析集合类，务必要分析其put方法，因为put方法最能体现集合的存储逻辑，HashMap的存储方法如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
直接踢皮球给putVal()方法，源码如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table为空时初始化，也就是之前提到的第一次插入元素时初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //创建新的数组并获取长度
//刚刚提到的计算元素在数组中位置的方式
//若当前位置未存任何元素，直接创建新的节点插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { //若当前节点存在
Node<K,V> e; K k;
//判断table[i]首个节点是否等于，相等则覆盖当前Value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //若当前节点已经是树结构存储
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //直接在树中插入键值对
else { //table[i]已存在，且是链式存储
for (int binCount = 0; ; ++binCount) {
//遍历到链表尾添加新的Node节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判断链表长度是否大于8，大于则转换树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//其实到这里出入就结束了，但put操作返回节点原先的值，此处需要获取oldValue并返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put函数大致的思路为：
①对key的hashCode()做hash，然后再计算index;
②如果没碰撞直接放到bucket里；
③如果碰撞了，以链表的形式存在buckets后；
④如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
⑤如果节点已经存在就替换old value(保证key的唯一性)
⑥如果bucket满了(超过load factor*current capacity)，就要resize。
HashMap允许存储Key为null的键值对，那么对于Key值为null的键值对HashMap是如何做到存储的呢？通过前文的hash()方法中当Key == null时返回值为0，转到putVal()方法中，确定在数组数组中的位置通过hash值 & (table.length - 1)的方式，当hash值为0时，所得值也为0，故Key为null的键值对一定存放在table[0]处。
在put操作过程中，多次出现resize()函数，该函数的作用是第一次put操作时初始化数组和当元素个数大于阀值时对table进行扩容。在JDK 1.8之前的版本中，该方法和transfer()方法协同使用，而在JDK 1.8起合并为一个方法。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//这部分操作是检测数组是进行初始化操作还是扩容操作，并对数组的大小，阀值等进行更新。
if (oldCap > 0) { //当前数组大小不为0，故进行扩容操作
//若数组大小超过最大限度，则不进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} //否则将数组大小设为当前大小的2倍，同时更新阀值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} //当阀值不为0，大小为0时，将大小设为阀值（不知道为什么会有这种情况）
else if (oldThr > 0)
newCap = oldThr;
else { //将大小和阀值设为默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//按上述参数设置新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//以下操作是将原数组元素添加到新数组中，只发生在扩容操作时
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize()操作在JDK 1.8中有较大改进，但同之前版本一样，会产生并发死锁问题，该问题会在之后讲解并发情况下使用集合时进行详细解读。
JDK 1.8为了加快查询速度，采用了红黑树结构进行存储，红黑树是一种特殊的二叉平衡树，至于太详细的Chuck也不太懂，在此给出一些红黑树的特性，如果面试官问到可以说一说：
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是NIL节点）。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续
的红色节点)
性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
Chuck到网上找了一些HashMap常见的面试题，总结一下，希望能有帮助：
1.什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着
Entry(hash, key, value, next)对象。
2.你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它
调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用
情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，
它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果
发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java8中，如果一个
bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
3.你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位
置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
4.你知道hash的实现吗？为什么要这样实现？
在JDK 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：
(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在
bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大
的开销。
5.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用
hash方法。
关于Java集合的小抄中是这样描述的：
以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶，Entry用一个next属性实现多个Entry以单向链表存
放，后入桶的Entry将next指向桶当前的Entry。
查找哈希值为17的key时，先定位到第一个哈希桶，然后以链表遍历桶里所有元素，逐个比较其
key值。
当Entry数量达到桶数量的75%时(很多文章说使用的桶数量达到了75%，但看代码不是)，会成倍
扩容桶数组，并重新分配所有原来的Entry，所以这里也最好有个预估值。
取模用位运算(hash & (arrayLength-1))会比较快，所以数组的大小永远是2的N次方，你随便
给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
iterator()时顺着哈希桶数组来遍历，看起来是个乱序。
6.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类
(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大
小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法
找到新的bucket位置
7.你了解重新调整HashMap大小存在什么问题吗？
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重
新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会
反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在
头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。
因此在并发环境下，我们使用CurrentHashMap来替代HashMap
