1、HashMap-底层数据结构

1、HashMap底层数据结构=数组+链表+红黑树。
2、HashMap字段属性有：
    /**
     * 序列化和反序列化时，通过该字段进行版本一致性验证
     */
    private static final long serialVersionUID = 362498820763181265L;
    /**
     * 默认 HashMap 集合初始容量为16（必须是 2 的倍数）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //左移4位，相当与2^4
    /**
     * 集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;//左移30位，相当于2^30
    /**
     * 默认的填充因子，与扩容有关
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
     */
    static final int TREEIFY_THRESHOLD = 8;
    /**
     * 当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
     * (JDK1.8新增)
     * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
     * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD=4 * 8
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
3、重要属性：
    /* ---------------- Fields -------------- */
    /**
     * 存储(位桶)的数组，在第一次使用时初始化，长度总是2的幂次方
     * 每一个Node本质都是一个单向链表
     */
    transient Node<K,V>[] table;
    /**
     * 保存缓存的entrySet()
     */
    transient Set<Map.Entry<K,V>> entrySet;
    /**
     * HashMap大小,它代表HashMap保存的键值对的多少
     */
    transient int size;
    /**
     * 记录集合被修改的次数,主要用于迭代器中的快速失败
     */
    transient int modCount;
    /**
     * 下一次HashMap扩容的大小: 调整大小的下一个大小值（容量*加载因子）。
     * 计算公式：capacity * load factor，这个值是当前已占用数组长度的最大值。
     */
    int threshold;
    /**
     * 存储负载因子的常量，计算HashMap的实时装载因子的方法为：size/capacity--table的长度length
     */
    final float loadFactor;

1-1、HashMap-底层数据结构-宏观-示意图

1-2、HashMap-底层数据结构-细分-示意图

1-3、HashMap-底层数据结构-单向链表实现

1、Node是单向链表，它实现了Map.Entry接口。链表查询时间复杂度：O(N)
    1-1、Node是一个静态内部类，一种数组和链表相结合的复合结构。
2、源代码：
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //构造函数：Hash值，键，值，下一个节点  
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true 
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

1-4、HashMap-底层数据结构-红黑树实现

1、实现了LinkedHashMap.LinkedHashMapEntry<K,V>，红黑树查询时间复杂度：O(logN)
    static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
        TreeNode<K,V> parent;  // 红黑树的根节点
        TreeNode<K,V> left; //左树
        TreeNode<K,V> right; //右树
        TreeNode<K,V> prev;    // 上一个几点
        boolean red; //是否是红树
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        /**
         * 返回当前节点的根节点
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
    ...
   }

1-5、HashMap-底层数据结构-hash值计算

1、Hash的计算实现：
    //将传入的参数key本身的hashCode与h无符号右移16位进行二进制异或运算得出一个新的hash值。
    //右移16位，是与HashMap的table数组下计算标有关系，当发生较大碰撞时也用树形存储降低了冲突。既减少了系统的开销。
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
2、hash函数Demo: 
    key.hashCode()                1111 1111 1111 1111 1111 0000 1010 1101
    key.hashCode() >>>16        0000 0000 0000 0000 1111 1111 1111 1111
   -------------------------------------------------------------------- ^
   ^异或运算后得：                 1111 1111 1111 1111 0000 1111 0101 0010

2、HashMap-构造方法

1、默认构造函数
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
2、指定容量大小和默认负载因子大小(0.75f)
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
3、指定容量大小和负载因子大小
    public HashMap(int initialCapacity, float loadFactor) {
        //指定的容量大小不可以小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //如果初始化容量大于2的30次方，则初始化容量都为2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //指定的负载因子不可以小于0或为Null
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
         // 设置"加载因子"
        this.loadFactor = loadFactor;
        // 设置"HashMap阈值"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
        this.threshold = tableSizeFor(initialCapacity);
    }
    /**
     * 返回大于等于initialCapacity的最小的二次幂数值。
     * >>> 操作符表示无符号右移，高位取0。
     * | 按位或运算
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
4、传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    /**
     * Implements Map.putAll and Map constructor
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

3、HashMap-存储机制-添加元素

1、源码分析：.put()方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
      * 
      * @param hash 索引的位置
      * @param key  键
      * @param value  值
      * @param onlyIfAbsent true 表示不要更改现有值
      * @param evict false表示table处于创建模式
      * @return
      */
    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为null或者长度为0，则进行初始化、
        //resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //得到该对象的保存位, hash & (length-1)运算等价于对 length 取模，也就是 hash%length。
        //但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。
        if ((p = tab[i = (n - 1) & hash]) == null)
            //tab[i] 为null，直接将新的key-value插入到计算的索引i位置
            tab[i] = newNode(hash, key, value, null); 
        else { //tab[i] 不为null，表示该位置已经有值了，需要做哈希冲突判断
            Node<K,V> e; K k;
            //检查第一个Node，判断p是不是要找的值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; //节点key已经有值了，直接用新值覆盖
            else if (p instanceof TreeNode) //该节点是红黑树结构
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {    //该节点是链表结构
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8，转换成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //treeifyBin方法中判断长度是否大于最小红黑树容量64,小于则继续扩容，大于则转为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    //key已经存在直接覆盖value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //此处不为空，表示链表中该位置有相同的key值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;//返回存在的Value值  
            }
        }
        ++modCount;
        //如果当前大小大于门限，则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    //空的方法实现， LinkedHashMap 会用到，LinkedHashMap 是继承的 HashMap，并且重写了该方法。
    afterNodeAccess(e);
    afterNodeInsertion(evict)
    ==>
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
2、.put()方法源码执行过程：
    2-1、判断键值对数组 table 是否为空或为null，否则执行resize()进行扩容；
    2-2、根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向2-6，如果table[i]不为空，转向2-3；
    2-3、判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向2-4，这里的相同指的是hashCode以及equals；
    2-4、判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向2-5；
    2-5、遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
    2-6、插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，进行扩容。
    2-7、如果新插入的key不存在，则返回null，如果新插入的key存在，则返回原key对应的value值（注意新插入的value会覆盖原value值）
3、.put()方法分析-问题思考：
    3-1、数组上有5个元素，而某个链表上有3个元素，问此HashMap的 size 是多大？
        3-1-1、只要是调用put() 方法添加元素，那么就会调用 ++size(这里有个例外是插入重复key的键值对，不会调用，但是重复key元素不会影响size),答案为7。
    3-2、
4、.put()方法

3-1、HashMap-添加元素-.put()方法-执行示意图

3-2、.treeifyBin()方法

1、.treeifyBin()方法用于hashMap链表长度达到8以后转红黑树前的预处理，当链表长度达到8以后判断表长度是否大于63的判断就是在这个方法里完成的，若表长度小于64，则不再进一步处理，仅仅调用resize()方法重新调整表。 2、若表长度大于等于64，则开始进行预处理，把原来长度达到8的单向链表转换成双向链表的形式，双向链表头结点为TreeNode hd;转成双向链表以后调用链表树形化方法treeify()把链表树形化。 3、详细分析：HashMap之TreeNode（红黑树）源码分析

    /**
        TreeNode：树节点，代表红黑树的一个节点，一个Node相当于链表的一个节点，next属性对应着下一个节点
        TreeNode是红黑树的同时也是一个单项链表：TreeNode不仅是红黑树，还是链表。继承了LinkedHashMap.Entry，而Entry继承了 HashMap.Node
    */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
    }
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //判断表长度是否大于64，如果不大于64则调用resize()方法重新调整表大小
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //定义树首节点、树尾节点
            TreeNode<K,V> hd = null, tl = null;
            //do.....while循环读取转换。直到链表最后一个元素
            do {
                //把当前节点转换为树节点
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)    //树尾节点为空，则表示链表没有根节点
                    hd = p;//将首节点(根节点)指向当前节点，hd 双向链表头元素
                else {//尾节点不为空，则构成一个双向链表结构
                    p.prev = tl;//将当前树节点的 前一个节点指向尾节点
                    tl.next = p;//尾节点的后一个节点指向当前节点
                }
                tl = p;//把当前节点设为尾节点
            } while ((e = e.next) != null); //否则开始尝试把单向链表转换转成双向链表
                if ((tab[index] = hd) != null)//把表index索引所在位置桶替换成刚刚建立的双向链表，然后判断是否null
                //树形化: 调用treeify()方法树形化刚刚的hd开头的双向链表
                hd.treeify(tab);//调用treeify()方法树形化刚刚的hd开头的双向链表
        }
    }
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
    //最终调用了
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    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;
        }
        //......
    }

4、HashMap-存储机制-扩容方法

1、扩容：.resize(),HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor）。
2、扩容方法源码：JDK1.7：jdk1.8之前是采用头插法(新链表与旧链表的顺序是反的)
    //参数 newCapacity 为新数组的大小
    void resize(int newCapacity) {
        Entry[] oldTable = table;//引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }
        Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;    
        for (Entry<K,V> e : table) {//遍历数组
            while(null != e) {
                Entry<K,V> next = e.next;
                //JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//重新计算每个元素在数组中的索引位置
                e.next = newTable[i];//标记下一个元素，添加是链表头添加
                newTable[i] = e;//将元素放在数组上
                e = next;//访问下一个 Entry 链上的元素
            }
        }
    }
3、扩容方法源码：JDK1.8：在1.8后采用尾插法,同时1.8的链表长度如果大于8就会转变成红黑树。
    //1、如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。
    //2、前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。
    3-1、源码分析：
        final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//原数组如果为null，则长度赋值0
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {    //如果原数组长度大于0
                if (oldCap >= MAXIMUM_CAPACITY) {    //数组大小如果已经大于等于最大值(2^30)
                    threshold = Integer.MAX_VALUE;    //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                    return oldTab;
                }
                //原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方    
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold，阀值扩大1倍
            }
            //旧阀值大于0，则将新容量直接等于就阀值 
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {//阀值等于0，oldCap也等于0（集合未进行初始化）
                newCap = DEFAULT_INITIAL_CAPACITY;    //数组长度初始化为16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    //阀值等于16*0.75=12
            }
            //计算新的阀值上限
            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;    //将当前表赋予table
            if (oldTab != null) {    //若oldTab中有值需要通过循环将oldTab中的值保存到新表中
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;    //元数据j位置置为null，便于垃圾回收
                        if (e.next == null)    //数组没有下一个引用,说明这个node没有链表.
                            //直接放在新表的e.hash & (newCap - 1)位置  
                            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;//记录下一个结点
                                //新表是旧表的两倍容量，实例上就把单链表拆分为两队，  
                      //e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对  
                                //原索引
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                //原索引+oldCap
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            //原索引放到新表bucket里
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                             //原索引+oldCap放到bucket里
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            //返回新表
            return newTab;
        }
    3-2、.resize()方法执行过程：
        1.判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
        2.若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小
            2.1. 若[2]的判定不成功，则继续判定 oldThr （代表 老表的下一次扩容量）大于0，若判定成功 则将oldThr赋给newCap作为新表的容量
            2.2 若 [2] 和[2.1]判定都失败,则走默认赋值 代表 表为初次创建
        3.确定下一次表的扩容量, 将新表赋予当前表
        4.通过for循环将老表中德值存入扩容后的新表中
            4.1 获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空
            4.2 若e的下面没有其他节点则将e直接赋到新表中的索引位置
            4.3 若e的类型为TreeNode红黑树类型
                4.3.1 分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
                4.3.2 通过Do循环 不断获取新旧索引的节点
                4.3.3 通过判定将旧数据和新数据存储到新表指定的位置
        5.最后返回值为 扩容后的新表。

5、HashMap-存储机制-查找元素

1、查找元素-通过key查找value: 通过 key 找到计算索引，找到桶位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回 null。
    1-1、源码分析：
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    //获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可。
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; /Entry对象数组  
        Node<K,V> first, e; //在tab数组中经过散列的第一个位置  
        int n; K k;
        // 找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //根据key计算的索引检查第一个索引: 判断条件是hash值要相同，key值要相同 
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                //匹配key值成功，则返回该值
                return first;
            //不是第一个节点，则继续检查first后面的节点
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)//遍历树查找元素，并返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //若上面判定不成功 则认为下一个节点为单向链表,通过循环匹配值
                do {
                    //遍历链表查找元素，找到key值和hash值都相同的Node
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //匹配成功后返回该值
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    1-2、.get()方法执行过程：    
        1-2-1.判定三个条件 table不为Null & table的长度大于0 & table指定的索引值不为Null
        1-2-2.判定 匹配hash值 & 匹配key值 成功则返回 该值
        1-2-3.若 first节点的下一个节点不为Null
            1-2-3-1 若first的类型为TreeNode 红黑树 通过红黑树查找匹配值 并返回查询值。
            1-2-3-2 若上面判定不成功 则认为下一个节点为单向链表,通过循环匹配值。
    1-3、.get()方法-小结：
        1-3-1、首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。
        1-3-2、hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。
2、查找元素-判断是否存在给定的 key 或者 value
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            //遍历桶，
            for (int i = 0; i < tab.length; ++i) {
                //遍历桶中的每个节点元素
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

6、HashMap-存储机制-删除元素

1、HashMap 删除元素首先是要找到 桶的位置，然后如果是链表，则进行链表遍历，找到需要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行平衡调节，注意，当红黑树的节点数小于 6 时，会转化成链表。
2、源码分析：
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //(n - 1) & hash找到桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        node = p;
        //如果桶节点存在下一个节点
        else if ((e = p.next) != null) {
            //节点为红黑树
        if (p instanceof TreeNode)
         node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//找到需要删除的红黑树节点
        else {
         do {//遍历链表，找到待删除的节点
             if (e.hash == hash &&
                 ((k = e.key) == key ||
                  (key != null && key.equals(k)))) {
                 node = e;
                 break;
             }
             p = e;
         } while ((e = e.next) != null);
        }
        }
        //删除节点，并进行调节红黑树平衡
        if (node != null && (!matchValue || (v = node.value) == value ||
                      (value != null && value.equals(v)))) {
        if (node instanceof TreeNode)
         ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
        else if (node == p)
         tab[index] = node.next;
        else
         p.next = node.next;
        ++modCount;
        --size;
        //为实现 LinkedHashMap 做准备的，是一个空方法实现，在 LinkedHashMap 中进行了重写，用来维护删除节点后，链表的前后关系。
        afterNodeRemoval(node);
        return node;
        }
        }
        return null;
    }

7、HashMap-线程安全性-分析

1、为什么说HashMap是线程不安全的?
    1-1、在并发的多线程使用场景中使用HashMap可能造成死循环。
    1-2、举例Demo: 可断点调试
        public class HashMapInfiniteLoop {  
            //map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
            private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
            public static void main(String[] args) {  
                map.put(5， "C");  
                new Thread("Thread1") {  
                    public void run() {  
                        map.put(7, "B");  
                        System.out.println(map);  
                    };  
                }.start(); 
                new Thread("Thread2") {  
                    public void run() {  
                        map.put(3, "A);  
                        System.out.println(map);  
                    };  
                }.start();        
            }  
        }

8、HashMap-其他方法-分析-.getOrDefault()方法

1、.getOrDefault()方法：jdk1.8引入，如果在Map中存在key，则返回key所对应的的value。如果 在Map中不存在key，则返回默认值。
2、源代码：
    // Map.getOrDefault(key，默认值)；
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }
3、举例Demo：
    .getOrDefault(Object key, V defaultValue)
    public class Demo {
        public static void main(String[] args) {
            Map<String, Integer> map = new HashMap<>();
            map.put("张三", 23);
            map.put("赵四", 24);
            map.put("王五", 25);
            String age= map.getOrDefault("赵四", 30);
            System.out.println(age);// 24，map中存在"赵四",使用其对应值24
            String age = map.getOrDefault("刘能", 30);
            System.out.println(age);// 30，map中不存在"刘能",使用默认值30
        }
    }
4、.getOrDefault(K V)方法中.getNode()方法，源代码：
    final HashMap.Node<K,V> getNode(int hash, Object key) {
        //定义变量
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
        //查看数据需要满足一下条件
            //1)数组不为空
            //2)数组长度>0
            //3)通过hash计算出该元素在数组中存放位置的索引,而且该索引处数据不为空null
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            //判断该数组索引位置处第一个是否为我们要找的元素 判断条件需要满足hash 和 key 相同
            // always check first node
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                //如果第一个就是我们要找的,直接返回即可
                return first;
            //如果第一个不是,我们需要循环遍历,然后找数据
            if ((e = first.next) != null) {
                //如果第1个的元素是红黑树类型的节点
                if (first instanceof HashMap.TreeNode)
                    //那我们需要调用红黑树的方法查找节点
                    return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
                //如果不是,则该为链表,需要遍历查找
                do {
                    //循环判断下一个节点的hash和key是否相同
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                    //更新e为下一个
                } while ((e = e.next) != null);
            }
        }
        //没找到返回Null
        return null;
    }

https://www.cnblogs.com/little-fly/p/7344285.html
https://segmentfault.com/a/1190000018520768
https://www.cnblogs.com/ysocean/p/8711071.html
https://www.jianshu.com/p/003256ce41ce
https://blog.csdn.net/qq_40574571/article/details/97612100
https://www.oracle.com/cn/database/technology/maps.html
https://www.cnblogs.com/mkfywj/p/5543600.html

Float.isNaN(loadFactor)
遍历树查找元素：.getTreeNode(hash, key)
如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办? 也就是说，
当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，
发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。 前面我们提到过，
哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。 
但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突，
那么冲突如何解决呢？哈希冲突的解决方案有多种。 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），
再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
https://www.yuque.com/lius/java/funwrx
https://www.yuque.com/moercheng/pkgur7/pgm06a
https://www.yuque.com/moercheng/pkgur7/cxu7md/edit#10.1.HashMap--1.7
https://www.yuque.com/moercheng/pkgur7/pwg92x/edit#fdc5b2e7