参考链接：
https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/HashMap.md

https://thinkwon.blog.csdn.net/article/details/104588551

继承关系

继承了AbstractMap抽象类

参数

大小：size
容量：是2的整数倍，默认为16
负载因子：默认0.75
扩容阈值：16*0.75=12
树化阈值：8
链化阈值：6

构造方法

①指定负载因子
②指定容量
③指定负载因子和容量
④具有与指定映射相同的map

数据结构实现：

• <=JDK1.7：数组+链表（链表散列）

• >=JDK1.8：数组+链表+红黑树
  Node<K,V>[] table+Set<Map.Entry<K,V>> entrySet+
  Node

复杂度分析

add()：O(1)
get()：O(1)
remove()：O(1)

线程安全性

线程不安全

哈希函数比较：

• JDK1.7:

  4次位运算，5次异或运算（9次扰动）

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

• JDK1.8：

  1次位运算和1次异或运算（2次扰动）

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

插入过程(put)：

• 允许空键和空值
• 根据key值使用扰动函数得到hash值
  2. 使用(n-1)&hash获取插入位置
  3. 判断插入位置是否有同key冲突
  4. 同key覆盖，异key解决冲突
  5. 判断是否要进行树化（JDK1.8以上独有）

扩容机制（resize过程）

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) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
    }

• 先是巴拉巴拉获取旧的容量值，旧的阈值。
• 然后初始化新的容量值，新的阈值（都等于0）

第一个判断内：老容量>0

①先看旧的容量是不是要爆炸了，爆炸就设新容量为int的最大值（放弃治疗），然后resize 下班（返回老的table给你）
②旧容量没爆炸，再看扩容两倍后的容量爆炸没（这里的爆炸判断语句里悄悄把新容量设为了旧容量的2倍！），没爆炸还要看旧的容量是不是大于等于默认的容量，也就是说一你扩容后新容量不能爆炸，二你老容量比默认容量还小扩啥容啊，满足这两个条件才能赋新阈值为旧阈值的两倍。

第二个判断内（else if）：老容量<=0，老阈值>0

新容量等于旧阈值，舒服（为啥这样设计，看resize()函数前面的注释）

第三个判断内（else）：老容量<=0，老阈值<=0

那就是说老容量老阈值都是0啦！那新容量取默认容量值16，新阈值取默认容量值16乘以默认加载因子0.75,也就是12啦

第四个判断内：新的阈值==0

这个if也是看得我emmmmmmmmmmmm，从上面最前两个if语句都能发现经过第一或者第二个if语句下来的新阈值可能还没被赋值，而新容量一定被赋值了，然后这个if内的工作就是对新阈值进行赋值啦！它是怎样一个策略呢？
按理说新的阈值应该是新容量乘以负载因子，所以你就可以看到这个ft变量了，就判断，第一，你这个新容量有没有爆炸啊？第二你这个新阈值ft有没有爆炸啊，两个都没爆炸，好吧新阈值就是ft了，否则就取int的最大值了（放弃治疗）。
（看到这里真是不禁感叹代码设计者设计巧妙，代码可读性真是“一流”啊！）
（实际上在上面讲到的放弃治疗策略体现了对一些特殊情况的处理，也能体现代码设计的巧妙，篇幅有限）

后面就是一些重新分配存储位置，以及树化过程，请参考其他博主的博文！

只有在添加元素时才有机会触发树化函数，只有触发树化函数才有机会扩容，扩容每次都使新容量为旧容量的两倍；触发树化函数不一定会使原HashMap真正树化，而可能是单纯扩容。