接下来会从以下几个方面介绍 HashMap 源码相关知识：
1、HashMap 存储结构
2、HashMap 各常量、成员变量作用
3、HashMap 几种构造方法
4、HashMap put 及其相关方法
5、HashMap get 及其相关方法
6、HashMap remove 及其相关方法
7、HashMap 扩容方法 resize()
介绍方法时会包含方法实现相关细节。
HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用ConcurrentHashMap。
一、HashMap 存储结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：
image.png
源码中具体实现如下：
// Node<K,V> 类用来实现数组及链表的数据结构
2 static class Node<K,V> implements Map.Entry<K,V> {
3 final int hash; //保存节点的 hash 值
4 final K key; //保存节点的 key 值
5 V value; //保存节点的 value 值
6 Node<K,V> next; //指向链表结构下的当前节点的 next 节点，红黑树 TreeNode 节点中也有用到
7
8 Node(int hash, K key, V value, Node<K,V> next) {
9 this.hash = hash;
10 this.key = key;
11 this.value = value;
12 this.next = next;
13 }
14
15 public final K getKey() { }
16 public final V getValue() { }
17 public final String toString() { }
18
19 public final int hashCode() {
20 }
21
22 public final V setValue(V newValue) {
23 }
24
25 public final boolean equals(Object o) {
26 }
27 }
28
29 public class LinkedHashMap<K,V> {
30 static class Entry<K,V> extends HashMap.Node<K,V> {
31 Entry<K,V> before, after;
32 Entry(int hash, K key, V value, Node<K,V> next) {
33 super(hash, key, value, next);
34 }
35 }
36 }
37
38 // TreeNode<K,V> 继承 LinkedHashMap.Entry<K,V>，用来实现红黑树相关的存储结构
39 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
40 TreeNode<K,V> parent; // 存储当前节点的父节点
41 TreeNode<K,V> left; //存储当前节点的左孩子
42 TreeNode<K,V> right; //存储当前节点的右孩子
43 TreeNode<K,V> prev; // 存储当前节点的前一个节点
44 boolean red; // 存储当前节点的颜色（红、黑）
45 TreeNode(int hash, K key, V val, Node<K,V> next) {
46 super(hash, key, val, next);
47 }
48 }
二、HashMap 各常量、成员变量作用
//创建 HashMap 时未指定初始容量情况下的默认容量
2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
3
4 //HashMap 的最大容量
5 static final int MAXIMUM_CAPACITY = 1 << 30;
6
7 //HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行 resize() 操作
8 static final float DEFAULT_LOAD_FACTOR = 0.75f;
9
10 //用来确定何时将解决 hash 冲突的链表转变为红黑树
11 static final int TREEIFY_THRESHOLD = 8;
12
13 // 用来确定何时将解决 hash 冲突的红黑树转变为链表
14 static final int UNTREEIFY_THRESHOLD = 6;
15
16 /* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于 MIN_TREEIFY_CAPACITY ）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用 resize() 函数对 hashMap 扩容 */
17 static final int MIN_TREEIFY_CAPACITY = 64;
//保存Node<K,V>节点的数组
2 transient Node<K,V>[] table;
3
4 //由 hashMap 中 Node<K,V> 节点构成的 set
5 transient Set<Map.Entry<K,V>> entrySet;
6
7 //记录 hashMap 当前存储的元素的数量
8 transient int size;
9
10 //记录 hashMap 发生结构性变化的次数（注意 value 的覆盖不属于结构性变化）
11 transient int modCount;
12
13 //threshold的值应等于 table.length * loadFactor, size 超过这个值时进行 resize()扩容
14 int threshold;
15
16 //记录 hashMap 装载因子
17 final float loadFactor;
三、HashMap 几种构造方法
//构造方法１，指定初始容量及装载因子
2 public HashMap(int initialCapacity, float loadFactor) {
3 if (initialCapacity < 0)
4 throw new IllegalArgumentException("Illegal initial capacity: " +
5 initialCapacity);
6 if (initialCapacity > MAXIMUM_CAPACITY)
7 initialCapacity = MAXIMUM_CAPACITY;
8 if (loadFactor <= 0 || Float.isNaN(loadFactor))
9 throw new IllegalArgumentException("Illegal load factor: " +
10 loadFactor);
11 this.loadFactor = loadFactor;
12 /* tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂，若指定初始容量为９，则实际 hashMap 容量为16*/
13 //注意此种方法创建的 hashMap 初始容量的值存在 threshold 中
14 this.threshold = tableSizeFor(initialCapacity);
15 }
16 //tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂
17 static final int tableSizeFor(int cap) {
18 int n = cap - 1;
19 n |= n >>> 1;// >>> 代表无符号右移
20 n |= n >>> 2;
21 n |= n >>> 4;
22 n |= n >>> 8;
23 n |= n >>> 16;
24 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
25 }
26 //构造方法２，仅指定初始容量，装载因子的值采用默认的 0.75
27 public HashMap(int initialCapacity) {
28 this(initialCapacity, DEFAULT_LOAD_FACTOR);
29 }
30 //构造方法３，所有参数均采用默认值
31 public HashMap() {
32 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
33 }
四、HashMap put 及其相关方法（hashMap 中比较重要的代码！！），介绍如下：
//指定节点 key,value，向 hashMap 中插入节点
2 public V put(K key, V value) {
3 //注意待插入节点 hash 值的计算，调用了 hash(key) 函数
4 //实际调用 putVal（）进行节点的插入
5 return putVal(hash(key), key, value, false, true);
6 }
7 static final int hash(Object key) {
8 int h;
9 /*key 的 hash 值的计算是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销*/
10 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
11 }
12
13 public void putAll(Map<? extends K, ? extends V> m) {
14 putMapEntries(m, true);
15 }
16
17 /*把Map<? extends K, ? extends V> m 中的元素插入到 hashMap 中,若 evict 为 false,代表是在创建 hashMap 时调用了这个函数，例如利用上述构造函数３创建 hashMap;若 evict 为true,代表是在创建 hashMap 后才调用这个函数，例如上述的 putAll 函数。*/
18
19 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
20 int s = m.size();
21 if (s > 0) {
22 /*如果是在创建 hashMap 时调用的这个函数则 table 一定为空*/
23 if (table == null) {
24 //根据待插入的map 的 size 计算要创建的 hashMap 的容量。
25 float ft = ((float)s / loadFactor) + 1.0F;
26 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
27 (int)ft : MAXIMUM_CAPACITY);
28 //把要创建的 hashMap 的容量存在 threshold 中
29 if (t > threshold)
30 threshold = tableSizeFor(t);
31 }
32 //判断待插入的 map 的 size,若 size 大于 threshold，则先进行 resize()
33 else if (s > threshold)
34 resize();
35 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
36 K key = e.getKey();
37 V value = e.getValue();
38 //实际也是调用 putVal 函数进行元素的插入
39 putVal(hash(key), key, value, false, evict);
40 }
41 }
42 }
43
44 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
45 boolean evict) {
46 Node<K,V>[] tab; Node<K,V> p; int n, i;
47 if ((tab = table) == null || (n = tab.length) == 0)
48 n = (tab = resize()).length;
49 /*根据 hash 值确定节点在数组中的插入位置，若此位置没有元素则进行插入，注意确定插入位置所用的计算方法为 (n - 1) & hash,由于 n 一定是２的幂次，这个操作相当于
50 hash % n */
51 if ((p = tab[i = (n - 1) & hash]) == null)
52 tab[i] = newNode(hash, key, value, null);
53 else {//说明待插入位置存在元素
54 Node<K,V> e; K k;
55 //比较原来元素与待插入元素的 hash 值和 key 值
56 if (p.hash == hash &&
57 ((k = p.key) == key || (key != null && key.equals(k))))
58 e = p;
59 //若原来元素是红黑树节点，调用红黑树的插入方法:putTreeVal
60 else if (p instanceof TreeNode)
61 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
62 else {//证明原来的元素是链表的头结点，从此节点开始向后寻找合适插入位置
63 for (int binCount = 0; ; ++binCount) {
64 if ((e = p.next) == null) {
65 //找到插入位置后，新建节点插入
66 p.next = newNode(hash, key, value, null);
67 //若链表上节点超过TREEIFY_THRESHOLD - 1，将链表变为红黑树
68 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
69 treeifyBin(tab, hash);
70 break;
71 }
72 if (e.hash == hash &&
73 ((k = e.key) == key || (key != null && key.equals(k))))
74 break;
75 p = e;
76 }
77 }//end else
78 if (e != null) { // 待插入元素在 hashMap 中已存在
79 V oldValue = e.value;
80 if (!onlyIfAbsent || oldValue == null)
81 e.value = value;
82 afterNodeAccess(e);
83 return oldValue;
84 }
85 }//end else
86 ++modCount;
87 if (++size > threshold)
88 resize();
89 afterNodeInsertion(evict);
90 return null;
91 }//end putval
/*读懂这个函数要注意理解 hash 冲突发生的几种情况
2 １、两节点 key 值相同（hash值一定相同），导致冲突
3 ２、两节点 key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突
4 ３、两节点 key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突
5 */
6 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
7 int h, K k, V v) {
8 Class<?> kc = null;
9 boolean searched = false;
10 TreeNode<K,V> root = (parent != null) ? root() : this;
11 //从根节点开始查找合适的插入位置（与二叉搜索树查找过程相同）
12 for (TreeNode<K,V> p = root;;) {
13 int dir, ph; K pk;
14 if ((ph = p.hash) > h)
15 dir = -1; // dir小于０，接下来查找当前节点左孩子
16 else if (ph < h)
17 dir = 1; // dir大于０，接下来查找当前节点右孩子
18 else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
19 //进入这个else if 代表 hash 值相同，key 相同
20 return p;
21 /*要进入下面这个else if,代表有以下几个含义:
22 1、当前节点与待插入节点 key 不同, hash 值相同
23 2、ｋ是不可比较的，即ｋ并未实现 comparable<K> 接口
（若 k 实现了comparable<K> 接口，comparableClassFor（k）返回的是ｋ的 class,而不是 null）
24 或者 compareComparables(kc, k, pk) 返回值为 0
(pk 为空 或者 按照 k.compareTo(pk) 返回值为０，
返回值为０可能是由于 ｋ的compareTo 方法实现不当引起的，compareTo 判定相等，而上个 else if 中 equals 判定不等)*/
25 else if ((kc == null &&
26 (kc = comparableClassFor(k)) == null) ||
27 (dir = compareComparables(kc, k, pk)) == 0) {
28 //在以当前节点为根的整个树上搜索是否存在待插入节点（只会搜索一次）
29 if (!searched) {
30 TreeNode<K,V> q, ch;
31 searched = true;
32 if (((ch = p.left) != null &&
33 (q = ch.find(h, k, kc)) != null) ||
34 ((ch = p.right) != null &&
35 (q = ch.find(h, k, kc)) != null))
36 //若树中存在待插入节点，直接返回
37 return q;
38 }
39 // 既然ｋ是不可比较的，那我自己指定一个比较方式
40 dir = tieBreakOrder(k, pk);
41 }//end else if
42
43 TreeNode<K,V> xp = p;
44 if ((p = (dir <= 0) ? p.left : p.right) == null) {
45 //找到了待插入的位置，xp 为待插入节点的父节点
46 //注意TreeNode节点中既存在树状关系，也存在链式关系，并且是双端链表
47 Node<K,V> xpn = xp.next;
48 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
49 if (dir <= 0)
50 xp.left = x;
51 else
52 xp.right = x;
53 xp.next = x;
54 x.parent = x.prev = xp;
55 if (xpn != null)
56 ((TreeNode<K,V>)xpn).prev = x;
57 //插入节点后进行二叉树的平衡操作
58 moveRootToFront(tab, balanceInsertion(root, x));
59 return null;
60 }
61 }//end for
62 }//end putTreeVal
63
64 static int tieBreakOrder(Object a, Object b) {
65 int d;
66 //System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较
67 if (a == null || b == null ||
68 (d = a.getClass().getName().
69 compareTo(b.getClass().getName())) == 0)
70 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
71 -1 : 1);
72 return d;
73 }
五、HashMap get 及其相关方法 (重点！！)
public V get(Object key) {
2 Node<K,V> e;
3 //实际上是根据输入节点的 hash 值和 key 值利用getNode 方法进行查找
4 return (e = getNode(hash(key), key)) == null ? null : e.value;
5 }
6
7 final Node<K,V> getNode(int hash, Object key) {
8 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
9 if ((tab = table) != null && (n = tab.length) > 0 &&
10 (first = tab[(n - 1) & hash]) != null) {
11 if (first.hash == hash && // always check first node
12 ((k = first.key) == key || (key != null && key.equals(k))))
13 return first;
14 if ((e = first.next) != null) {
15 if (first instanceof TreeNode)
16 //若定位到的节点是 TreeNode 节点，则在树中进行查找
17 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
18 do {//否则在链表中进行查找
19 if (e.hash == hash &&
20 ((k = e.key) == key || (key != null && key.equals(k))))
21 return e;
22 } while ((e = e.next) != null);
23 }
24 }
25 return null;
26 }
final TreeNode<K,V> getTreeNode(int h, Object k) {
2 //从根节点开始，调用 find 方法进行查找
3 return ((parent != null) ? root() : this).find(h, k, null);
4 }
5
6 final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
7 TreeNode<K,V> p = this;
8 do {
9 int ph, dir; K pk;
10 TreeNode<K,V> pl = p.left, pr = p.right, q;
11 //首先进行hash 值的比较，若不同令当前节点变为它的左孩子或者右孩子
12 if ((ph = p.hash) > h)
13 p = pl;
14 else if (ph < h)
15 p = pr;
16 //hash 值相同，进行 key 值的比较
17 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
18 return p;
19 else if (pl == null)
20 p = pr;
21 else if (pr == null)
22 p = pl;
23 //执行到这儿，意味着hash 值相同，key 值不同
24 //若k 是可比较的并且k.compareTo(pk) 返回结果不为０可进入下面elseif
25 else if ((kc != null ||
26 (kc = comparableClassFor(k)) != null) &&
27 (dir = compareComparables(kc, k, pk)) != 0)
28 p = (dir < 0) ? pl : pr;
29 /*若 k 是不可比较的 或者 k.compareTo(pk) 返回结果为０则在整棵树中进行查找，先找右子树，右子树没有再找左子树*/
30 else if ((q = pr.find(h, k, kc)) != null)
31 return q;
32 else
33 p = pl;
34 } while (p != null);
35 return null;
36 }
七、HashMap 扩容方法 resize()
构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时
总结：区别于jdk1.7，put方法：
下面简单说下添加键值对put(key,value)的过程：
1、判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；
2、根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入3
3、判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理(jdk1.7只有链表冲突处理)
4、如果同一个数组位置上冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，treeifyBin首先判断当前hashMap的长度，如果不足64，只进行 resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
参考source:
https://my.oschina.net/u/2307589/blog/1800587
https://www.cnblogs.com/little-fly/p/7344285.html
