一、HashMap 概述
java.util.HashMap<k,v> 集合 implements Map<k,v> 接口
HashMap 集合的特点：
1、HashMap 集合底层是哈希表：查询速度特别的快
JDK 1.8 之前：数组+单向链表
JDK 1.8 之后：数组+单向链表 | 红黑树（链表的长度超过8）：提高查询的速度
2、HashMap 集合是一个无序的集合，存储元素和取出元素的顺序有可能不一致
二、HashMap 存储自定义类型键值
HashMap存储自定义类型键值
Map集合保证key是唯一的：作为key的元素,必须重写hashCode方法和equals方法,以保证key唯一
三、遍历集合
参考 Map 集合的遍历方式：Map 遍历
四、HashMap 源码分析
1、hashCode 值
hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据映射到一个固定大小的序列上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。hash是具有唯一性且不可逆的，唯一性是指相同的“对象”产生的hash code永远是一样的。
2、Entry 数组
HashMap和Hashtable是散列表，其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个元素被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到了某个table[index]桶中。
使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。
（1）数组元素类型： Map.Entry
（2）初始容量：16
（3）扩容为原来的2倍
（4）那么 HashMap 是如何决定某个映射关系存在哪个桶的呢？
因为hash code是一个整数，而数组的长度也是一个整数，有两种思路：
①hash code值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算，不能保证均匀存放，可能会导致某些table[index]桶中的元素太多，而另一些太少，因此不合适。
②hash code值 & (table.length-1)，因为table.length是2的幂次方，因此table.length-1是一个二进制低位全是1的数，所以&操作完，也会得到一个[0,table.length-1]范围的值。
3、HashMap 中的散列函数 hash()
JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。
这里用 JDK1.8 的实例分析一下：
思考：那么，JDK1.8为什么要保留高16位呢？
因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时保留高16位的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。
4、如何解决冲突？
虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？
JDK1.8之间使用：数组+链表的结构。
JDK1.8之后使用：数组+链表/红黑树的结构。
5、JDK1.7里HashMap 中几个常量与变量是什么？
（1）默认数组容量
（2）默认加载因子
思考： loadFactor 设置为 0.1 与 0.9 有什么区别？
当 loadFactor 为 0.1 时，扩容太频繁
当 loadFactor 为 0.9时，会导致 table[index] 下面的链表会很长，查询速度会降低。
（3）加载因子
（4）阈值（临界值）
6、JDK 1.6 中HashMap 的构造方法是怎么样的？
图1
图2
可以看出 JDK1.6 中 table 数组初始化为了一个长度为 16 的空数组，默认加载因子为0.75，阈值为12。
6、JDK 1.7 中的 HashMap 的构造方法是怎么样的？
图1
图2
图3
可以从无参构造中看出，调用了有参的构造，但是有参的构造方法中并没有做什么，但是从上面的图三可以看出 table 数组初始化为了一个长度为0的长度为0的数组。
7、JDK 1.7 中的 put 方法
源码分析：
执行步骤：
（1）先判断table是否为空数组，如果是，先初始化长度为16的Entry 类型的数组，并且把threshold计算为12；
这里如果你手动指定了数组的capacity，那么如果这个capacity不是2的n次方，会自动纠正为2的n次方；
（2）如果key是null，特殊对待，key为null的映射关系的hash值为0,index也为0；
（3）key 不是 null，那么先计算hash(key)获得 hash 值
（4）再通过处理过的hash值&(table.length-1)计算index，决定是在table[index]，index在[0,table.length-1]范围内；
（5）判断table[index]桶下是否存在某个Entry的key与新的key的“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），如果是，用新的value替换原来的value；
（6）如果不存在，判断是否满足size达到阈值(threshold)并且table[index]不是null，如果是，先扩容；扩容会导致原来table中的所有元素都会重新计算位置，并调整存储位置；
（7）添加一个新的Entry对象至table[index]（注意，这个index也是重新计算过的）中，并且把当前table[index]下的所有元素都连接到新的Entry的next下。
（8）size++，元素个数增加
思考：
1、为什么要把数组的长度纠正为2的n次方？
① 后面算index = hash & table.length-1，这样才能保证[0,table.length-1]范围内
② 2的次方，根据它的散列算法，可以保证比较均匀的分散在它的数组的各个位置
2、扩容的条件是什么？
① size达到阈值threshold
② table[index]下面已经有映射关系，即不为空
8、JDK 1.8 中的 HashMap 的构造方法
可以看出，无参构造方法给加载因子赋值为0.75，其他的都为默认值。
9、JDK 1.8 中常量与变量
（1）_DEFAULT_INITIAL_CAPACITY_：默认的初始容量1<<4 (16)
（2）_MAXIMUM_CAPACITY_：最大容量 1 << 30
（3）static final float DEFAULT_LOAD_FACTOR = 0.75：默认加载因子 0.75
（4）static final int TREEIFY_THRESHOLD = 8; 默认树化阈值8，该阈值的作用是判断是否需要树化，树化的目的是为了提高查询效率；当某个链表的结点个数达到这个值时，可能会导致树化
（5）static final int MIN_TREEIFY_CAPACITY = 64;最小树化容量64，当某个链表的结点个数达到8时，还要检查table的长度是否达到64，如果没有达到，先扩容解决冲突问题
（6）static final int UNTREEIFY_THRESHOLD = 6;默认反树化阈值6，当删除了结点时，如果某棵红黑树的结点个数已经低于该值时，会把树重新变成链表，目的是减少复杂度
（7）Node<K,V>[] table：数组
（8）int size：记录有效映射关系的对数，也是Entry对象的个数
（9）int threshold：阈值，当size达到阈值时，考虑扩容
（10）double loadFactor：加载因子，影响扩容的频率
10、JDK 1.8 的 put 方法
源码分析：
（1）hash() 方法：使hashCode值更加散列
1 static final int hash(Object key) {
2 int h;
3 //如果key是null，hash是0
4 //如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或
5 // 即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
6
7 /*
8 index = hash & table.length-1
9 如果用key的原始的hashCode值 与 table.length-1 进行按位与，那么基本上高16没机会用上。
10 这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。
11 */
12 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
13 }
（2）putVal() 方法
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2 boolean evict) {
3 Node<K,V>[] tab; //数组
4 Node<K,V> p; //一个结点
5 int n, i;//n是数组的长度 i是下标
6
7 //tab和table等价
8 //如果table是空的
9 if ((tab = table) == null || (n = tab.length) == 0){
10 //n = (tab = resize()).length;
11 tab = resize();
12 n = tab.length;
13 /*
14 如果table是空的，resize()完成了
15 ①创建了一个长度为16的数组
16 ②threshold = 12
17 n= 16
18 */
19 }
20 //i = (n - 1) & hash ，下标 = 数组长度-1 & hash
21 //p = tab[i]
22 //if(p==null) 条件满足的话说明 table[i]还没有元素
23 if ((p = tab[i = (n - 1) & hash]) == null){
24 //把新的映射关系直接放入table[i]
25 tab[i] = newNode(hash, key, value, null);
26 //newNode（）方法就创建了一个Node类型的新结点，新结点的next是null
27 }else {
28 Node<K,V> e;
29 K k;
30 //p是table[i]中第一个结点
31 //if(table[i]的第一个结点与新的映射关系的key重复)
32 if (p.hash == hash &&
33 ((k = p.key) == key || (key != null && key.equals(k)))){
34 e = p;//用e记录这个table[i]的第一个结点
35 }else if (p instanceof TreeNode){//如果table[i]第一个结点是一个树结点
36 //单独处理树结点
37 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
38 }else {
39 //table[i]的第一个结点不是树结点，也与新的映射关系的key不重复
40 //binCount记录了table[i]下面的结点的个数
41 for (int binCount = 0; ; ++binCount) {
42 //如果p的下一个结点是空的，说明当前的p是最后一个结点
43 if ((e = p.next) == null) {
44 //把新的结点连接到table[i]的最后
45 p.next = newNode(hash, key, value, null);
46
47 //如果binCount>=8-1，达到7个时
48 if (binCount >= TREEIFY_THRESHOLD - 1){ // -1 for 1st
49 //要么扩容，要么树化
50 treeifyBin(tab, hash);
51 }
52 break;
53 }
54 //如果key重复了，就跳出for循环
55 if (e.hash == hash &&
56 ((k = e.key) == key || (key != null && key.equals(k)))){
57 break;
58 }
59 p = e;
60 }
61 }
62 //如果这个e不是null，说明有key重复，就考虑替换原来的value
63 if (e != null) { // existing mapping for key
64 V oldValue = e.value;
65 if (!onlyIfAbsent || oldValue == null){
66 e.value = value;
67 }
68 afterNodeAccess(e);
69 return oldValue;
70 }
71 }
72 ++modCount;
73
74 //元素个数增加
75 //size达到阈值
76 if (++size > threshold){
77 resize();//一旦扩容，重新调整所有映射关系的位置
78 }
79 afterNodeInsertion(evict);//什么也没干
80 return null;
81 }
（3）resize() 方法
1 final Node<K,V>[] resize() {
2 Node<K,V>[] oldTab = table;//oldTab原来的table
3 //oldCap：原来数组的长度
4 int oldCap = (oldTab == null) ? 0 : oldTab.length;
5
6 //oldThr：原来的阈值
7 int oldThr = threshold;//最开始threshold是0
8
9 //newCap，新容量
10 //newThr：新阈值
11 int newCap, newThr = 0;
12 if (oldCap > 0) {//说明原来不是空数组
13 if (oldCap >= MAXIMUM_CAPACITY) {//是否达到数组最大限制
14 threshold = Integer.MAX_VALUE;
15 return oldTab;
16 }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
17 oldCap >= DEFAULT_INITIAL_CAPACITY){
18 //newCap = 旧的容量*2 ，新容量<最大数组容量限制
19 //新容量：32,64，...
20 //oldCap >= 初始容量16
21 //新阈值重新算 = 24，48 ....
22 newThr = oldThr << 1; // double threshold
23 }
24 }else if (oldThr > 0){ // initial capacity was placed in threshold
25 newCap = oldThr;
26 }else { // zero initial threshold signifies using defaults
27 newCap = DEFAULT_INITIAL_CAPACITY;//新容量是默认初始化容量16
28 //新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12
29 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
30 }
31 if (newThr == 0) {
32 float ft = (float)newCap * loadFactor;
33 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
34 (int)ft : Integer.MAX_VALUE);
35 }
36 threshold = newThr;//阈值赋值为新阈值12，24.。。。
37
38 //创建了一个新数组，长度为newCap，16，32,64.。。
39 @SuppressWarnings({"rawtypes","unchecked"})
40 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
41 table = newTab;
42
43
44 if (oldTab != null) {//原来不是空数组
45 //把原来的table中映射关系，倒腾到新的table中
46 for (int j = 0; j < oldCap; ++j) {
47 Node<K,V> e;
48 if ((e = oldTab[j]) != null) {//e是table下面的结点
49 oldTab[j] = null;//把旧的table[j]位置清空
50 if (e.next == null)//如果是最后一个结点
51 newTab[e.hash & (newCap - 1)] = e;//重新计算e的在新table中的存储位置，然后放入
52 else if (e instanceof TreeNode)//如果e是树结点
53 //把原来的树拆解，放到新的table
54 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
55 else { // preserve order
56 Node<K,V> loHead = null, loTail = null;
57 Node<K,V> hiHead = null, hiTail = null;
58 Node<K,V> next;
59 /*
60 把原来table[i]下面的整个链表，重新挪到了新的table中
61 */
62 do {
63 next = e.next;
64 if ((e.hash & oldCap) == 0) {
65 if (loTail == null)
66 loHead = e;
67 else
68 loTail.next = e;
69 loTail = e;
70 }
71 else {
72 if (hiTail == null)
73 hiHead = e;
74 else
75 hiTail.next = e;
76 hiTail = e;
77 }
78 } while ((e = next) != null);
79 if (loTail != null) {
80 loTail.next = null;
81 newTab[j] = loHead;
82 }
83 if (hiTail != null) {
84 hiTail.next = null;
85 newTab[j + oldCap] = hiHead;
86 }
87 }
88 }
89 }
90 }
91 return newTab;
92 }
（4）newNode() 方法
1 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
2 //创建一个新结点
3 return new Node<>(hash, key, value, next);
4 }
（5）treeifyBin() 方法
1 final void treeifyBin(Node<K,V>[] tab, int hash) {
2 int n, index;
3 Node<K,V> e;
4 //MIN_TREEIFY_CAPACITY：最小树化容量64
5 //如果table是空的，或者 table的长度没有达到64
6 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
7 resize();//先扩容
8 else if ((e = tab[index = (n - 1) & hash]) != null) {
9 //用e记录table[index]的结点的地址
10 TreeNode<K,V> hd = null, tl = null;
11 /*
12 do...while，把table[index]链表变为红黑树
13 */
14 do {
15 TreeNode<K,V> p = replacementTreeNode(e, null);
16 if (tl == null)
17 hd = p;
18 else {
19 p.prev = tl;
20 tl.next = p;
21 }
22 tl = p;
23 } while ((e = e.next) != null);
24
25 if ((tab[index] = hd) != null)
26 hd.treeify(tab);
27 }
28 }
存储过程：
（1）先计算key的hash值，如果key是null，hash值就是0，如果为null，使用(h = key.hashCode()) ^ (h >>> 16)得到hash值；
（2）如果table是空的，先初始化table数组；
（3）通过hash值计算存储的索引位置index = hash & (table.length-1)
（4）如果table[index]==null，那么直接创建一个Node结点存储到table[index]中即可
（5）如果table[index]!=null，并且table[index]是一个TreeNode结点，说明table[index]下是一棵红黑树，如果该树的某个结点的key与新的key“相同”（hash值相同并且(满足key的地址相同或key的equals返回true)），那么用新的value替换原来的value，否则将(key,value)封装为一个TreeNode结点，连接到红黑树中。
（6）如果table[index]不是一个TreeNode结点，说明table[index]下是一个链表，如果该链表中的某个结点的key与新的key“相同”，那么用新的value替换原来的value，否则需要判断table[index]下结点个数，如果没有达到**TREEIFY_THRESHOLD****_(8)_**个，那么(key,value)将会封装为一个Node结点直接链接到链表尾部。
（7）如果table[index]下结点个数已经达到**TREEIFY_THRESHOLD(8)个，那么再判断table.length是否达到MIN_TREEIFY_CAPACITY(64)**，如果没达到，那么先扩容，扩容会导致所有元素重新计算index，并调整位置；
（8）如果table[index]下结点个数已经达到**TREEIFY_THRESHOLD(8)个并table.length也已经达到MIN_TREEIFY_CAPACITY(64)**，那么会将该链表转成一棵自平衡的红黑树，并将结点链接到红黑树中。
（9）如果新增结点而不是替换，那么size++，并且还要重新判断size是否达到threshold阈值，如果达到，还要扩容。
11、关于映射关系的 key 是否可以修改？
映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。
这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。
