目录结构
一、面试常见问题
二、基本常量属性
三、构造方法
四、节点结构
       4.1 Node类
       4.2.TreeNode
五、put方法
       5.1 key的hash方法
       5.2 resize() 扩容方法
六、get方法

一、面试常见问题

Q1: HashMap底层数据结构是什么？

jdk1.7是数组+链表； jdk1.8 采用数组+ 链表+红黑树

Q2:为什么要引入红黑树，有什么优势，解决什么问题？

红黑树的引入是为了提高查询效率，哈希冲突可以减少（元素key均匀散列程度和通过扩容）,不可避免，
如果冲突元素较多，会导致链表过长，而链表查询效率是O(n), 当链表长度超过8后，且数组长度(length)超过64才转化为红黑树, 这点易忽略（后源码证明）,
不是链表长度一超高8个就将其树化为红黑树，此时扩容解决冲突效果更好。（注：红黑树的特性需要了解掌握）

Q3: 在一条链表上新增节点，什么方式插入？

1.8 是尾插法，1.7是采用头插法，为什么1.7需要头插法？头插法效率高？

Q4：放入HashMap中元素需要什么特性？

需要重写hashCode和 equals()方法 ，不重写会有什么问题？

Q5: HashMap是线程安全的吗？你列举其他线程安全的，特性？

不是, 因为它的方法没有同步锁，HashTable 是线程安全的，每个方法有加synhronized关键字，线程安全，但也会导致效率变低；
一般多线程环境使用 ConcurrentHashMap，其原理是采用了分段锁机制，每一段（Segment）中是一个HashMap，每个Segment中操作是加锁的，
即保证线程操作某一个Segment是排他的，但不同线程在不同Segment是可以同时操作的，即保证了线程安全，又提高了并发效率。
（此处不详细展开ConcurrentHashMap，面试问题是环环相套的，好的面试官会步步引导，目的是为了全面考察面试者的技术水平）。

Q6: 1.7中 HashMap存在什么问题？

在多线程环境下，1.7中Map可能会导致cpu使用率过高，是因为存在环形链表了，HashMap中 链表是单链表结构，怎么会有环？
是链表中元素指向下一个元素的指针next,指向了前面的元素，导致了环，所以在遍历链表时，
程序一直死循环无法结束。在多个线程放置元素时，resize()方法中导致(后源码证明)。

Q7: 1.8是先插入新值再判断是否扩容，还是先扩容在插入新值？

1.8是先插入元素，在判断容量是否超过阈值，扩容，1.7是先扩容再插入新值

Q8: HashMap是延迟初始化？

是的，创建的Map对象，如果有指定容量大小，会记录下来;没有指定会使用默认16，在第一次put元素时才初始化数组，1.7，1.8都是如此，可以节省内存空间。

Q9: HashMap允许放置空键(null)，空值(null)吗？

允许放置，null 键是放置在数组第一个位置的，因此在判断某个key是否存在时，不能通过该get() 方法获取value为null判断，
这时键值对可能是 null:null,此时是存在Node对象的，可以通过containsKey(key)判断 ，key为null，Node对象不为null,如下图1所示

对比HashTable ,HashTable 不允许 null键，null值.

Q10 ：简要讲述一下HashMap放置元素过程，即put()方法。

put方法流程如下图2所示

二、基本常量属性

//默认初始容量 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/**
 *最大容量，如果在构造函数中指定大于该值，会使用该值作为容量大小，2^30
 */static final int MAXIMUM_CAPACITY = 1 << 30;/**
 * 默认加载因子75%，好比地铁满载率，受疫情影响地铁满载率不超过30%
 * 1,加载因子设置较大，随着数组中元素装的越多，发生的冲突的概率越大，即对应的链表
 * 越长，影响查找效率。
 * 2，加载因子设置较小，元素很容易达到设定的阈值，发生扩容操作，数组空间还有很大部分          
 * 没有利用上，造成空间浪费。
 * 因此在时间与空间上的权衡考虑
 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/**
 * 树化阈值：在链表元素超过8个了，将链表转化为红黑数结果，提高查找效率
 */static final int TREEIFY_THRESHOLD = 8;/**
 * 取消树化阈值：在红黑树中节点数量小于6个，将其转化为链表结构
 */static final int UNTREEIFY_THRESHOLD = 6;/**
 * 最小树化容量,容易忽视
 * 链表树化红黑树条件：
 * 1，链表中元素数量超过(>)8个;
 * 2, 满足map中元素个数(size)大于等于64否则会先扩容，扩容对解决hash冲突更有效。 
 */static final int MIN_TREEIFY_CAPACITY = 64;

三、构造方法

//传有初始容量和加载因子1.HashMap(int initialCapacity, float loadFactor)//有初始容量，加载因子默认2.HashMap(int initialCapacity)//初始容量, 加载因子默认3.HashMap()//传递的一个Map子集4.HashMap(Map<? extends K, ? extends V> m)

四、节点结构

• 1.数组和链表节点对象为HashMap内部类 Node.

• 2.红黑树节点 TreeNode，继承LinkedHashMap.Entry , 而 Entry继承Node,因此 TreeNode 实际是 Node孙子.

• 3.Node类,重写了hashCode和 equals方法，记录了当前key, value, key的hash值，以及指向后一个元素指针.

4.1 Node类

//实现Map集合的Entry类static class Node<K,V> implements Map.Entry<K,V> {    //记录当前节点key的hash
    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;
    }    public final K getKey()        { return key; }    public final V getValue()      { return value; }    public final String toString() { return key + "=" + value; }    //重写了hashcode 
    public final int hashCode() {        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;        return oldValue;
    }     //重写了equals
    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;
    }
}

4.2.TreeNode

什么是红黑树？特点？

性质1. 节点是红色或黑色.

性质2. 根节点是黑色.

性质3.所有叶子都是黑色.（叶子是NUIL节点）

性质4. 每个红色节点的两个子节点都是黑色.（从每个叶子到根的所有路径上不能有两个连续的红色节点）

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点.

// 继承LinkedHashMap.Entry  继承>> HashMap.Nodestatic final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;    // needed to unlink next upon deletion//颜色是否为红色boolean red;

五、put方法

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);
}

5.1 key的hash方法

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

hash(key)方法：

1.hashMap支持 key 为null,放在数组索引为0的位置

2.为了保证key的hash值分布均分、散列，减少冲突

 (h = key.hashCode()) ^ (h >>> 16)

等于 key的hash值 异或于 其hash值的低 16位

例："水果"的 hashCode()

h = 11011000000111101000

h>>>16=00000000000000001101

两者异或，不同为1，相同为0

1101 10000001 11101000 ^ 
0000 00000000 00001101 ---------------------- 
1101 10000001 11100101

put核心方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;    if ((tab = table) == null || (n = tab.length) == 0)       //1，数组为空，初始化操作，此处resize() 待解析1
        n = (tab = resize()).length;    if ((p = tab[i = (n - 1) & hash]) == null)     /**2,通过key的计算出的hash值与数组长度-1与运算，算出在数组下标位置
       * 若该位置为空则创建新节点封装元素值，放在该位置
       */
        tab[i] = newNode(hash, key, value, null);    else {      // 若数组下标位置已经有值
        Node<K,V> e; K k;        //3,首先判断数组位置两个key是否相同，e用来指向存在相同key的节点。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;        else if (p instanceof TreeNode)  //4，key不相同的情况下，判断数组该下标位置连接的是链表还是树节点
 //若是树结构，就将该值放入树中(放入树中操作，也会遍历树判断是否存在相同的key的节点，若无相同会以新节点插入树中)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        else {        //数组该下标位置只有1个节点或者链表：这里统一为链表形式
            for (int binCount = 0; ; ++binCount) {                if ((e = p.next) == null) {                //5，没有找到相同key的元素，在链表后插入新节点
                    p.next = newNode(hash, key, value, null);                /**此处为什么要>=7,因为bincount从0开始递增，当bincount=7时，
                *此时for循环执行了7次，加上新增加的节点，以及数组下标位置节点
                *共7+1+1= 9了，即该数组下标位置链表长度大于8了,需要转化为红黑树
                */
                 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);                    break;
                }                //遍历链表比较判断是否存在两个key相同元素
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;  //有上面 e= p.next,这里 p有重新被赋值为e，即继续遍历链表下一个元素    
                p = e;
            }
        }        // 存在相同的key的元素，可能在数组、链表、树上 
        if (e != null) { // existing mapping for key
            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)       //6，覆盖旧值，返回旧值，也可设置仅仅当旧value存在，不为null情况才覆盖原值
                e.value = value;
            afterNodeAccess(e);            return oldValue;
        }
    }    //修改次数+1
    ++modCount;    //7,判断整个map中元素个数是否大于阈值，大于则扩容，由此可见是先插入元素再判断容量大小是否扩容，区别1.7先扩容再插入新值
    if (++size > threshold)
        resize();    //该方法为空，不用理会
    afterNodeInsertion(evict);    return null;
}

5.2 resize() 扩容方法

该方法有个比较有意思的是将旧数组的元素移到扩大为原来容量2倍的新数组中时，原来数组中链表需要进行拆链，非常巧妙，下见。

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    //1,原来数组容量>0情况
    if (oldCap > 0) {        //如果数组容量已经为最大值了 2^30,那就仅仅是将扩容阈值修改
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;            return oldTab;
        }        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)   //1.1 如果原来数组容量>=16,且其2倍小于最大容量(oldCap<<1 等价于 oldCap*2^1）
    // 阈值也扩容为原来2倍  
            newThr = oldThr << 1; // double threshold
    }    else if (oldThr > 0) // initial capacity was placed in threshold
     //1.2 什么情况数组容量=0，阈值>0呢？
     //创建HashMap，指定了数组初始容量cap，会将其转换为大于等于cap的最小的2的幂次方的数赋值给threshold,这里即将数组容量赋值
         newCap = oldThr;    else {         // zero initial threshold signifies using defaults
     //1.3原来数组容量和阈值都为0，即常用的无参构造方式，使用默认容量大小
     //阈值根据容量和负载因子算出   
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }    //2,newThr = 0情况出现在1.1中，没满足条件扩大为原来2倍
    if (newThr == 0) {        float ft = (float)newCap * loadFactor;   //小于最大容量，则用容量和加载因子乘积，否则为 Integer最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;    //3,创建新数组对象
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;    //4,原数组对象不为空，需要将原数组元素移到新数组中
    if (oldTab != null) {       //遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;            //数组下标位置有元素
            if ((e = oldTab[j]) != null) {        //直接把该下标位置链表(或红黑树)取出来，1个元素也当做链表看待，原数组该位置置空，只要我们拿着链表头节点/树根节点(e)就行
                oldTab[j] = null;                if (e.next == null)              //该位置只有1个元素，直接与新数组长度hash，确定位置放入新数组
                    newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof TreeNode)                 //该位置是一颗红黑树，迁移到新数组
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                else { // preserve order
     //5，重点解析：这里将原数组链表拆分为2条链表放入新数组，那它是怎么拆的呢？
    // loHead,loTail(lo 理解为low缩写)分别记录放在新数组下标小的那一条链表的头节点和尾结点,
    // 同理hiHead，hiTail(hi理解为 hight缩写)放在新数组下标大的位置
                    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-1)求得是数组下标，e.hash & oldCap 
       // 是为了获取比oldCap-1更高的那位一是0还是1，是0的就留在原位，是1的话需要增加oldCap。这里不易理解，下面详解
                        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;
}

扩容拆链过程分析：

#1,扩容前位置23&15= 7 0001 0111
 &0000 1111---------0000 0111#2,扩容后位置 
23&31= 230001 0111
 &0001 1111---------0001 0111/**因为每次扩容都是old数组长度的2倍，那么在要计算在扩容后新数组位置，
那么只需要关心key的hash值左边新增计算的那位是0还是1，如上未扩容前23与15与运算，只需关心低4位值，高位无论其是否有1，与运算后都会为0; 而扩容后，15变为31，那么key的hash值影响计算结果位由4位变为5位，
因此 e.hash & oldCap的结果就是获取新增的位置，000X 0000,即X的值，0或者1；
0运算结果不变，放在原位，1与运算结果会增加一个原数组长度。
*/

如下图3所示：

7 & 7=70000 01110000 0111----------23 & 7=70001 01110000 0111----------31 & 7=70001 11110000 0111----------15 & 7=70000 11110000 0111#可见第4位(从右向左)为1的有15，31，扩容后位置：原有下标+原数组长度

拆链位运算实现的巧妙：

1,扩容迁移原有数组中的元素，不用再重复计算原有元素key的hash值，提高效率.

2,扩容后拆链，会将链表长度缩短，减少hash冲突，提高查找效率.

六、get方法

根据键值对中的键（key）获取值

public V get(Object key) {
    Node<K,V> e;    //获取节点赋值给e,e！=null, 返回该键值对的value值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

下见方法：getNode(int hash, Object key)

final Node<K,V> getNode(int hash, Object key) {   //传入的hash值与put方法一样的方法，相同规则计算key的hash值
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {        //1，获取数组下标位置的第一个节点，first
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && 
            key.equals(k))))            //2，检查是否为相同的key,是直接返回该节点对象；不是则遍历下一个节点
            return first;        if ((e = first.next) != null) {            //3,下一个节点存在，需判断是红黑树，还是链表
            if (first instanceof TreeNode)              //3.1红黑树则遍历树获取是否存在与该key相同的节点
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);            do {               //3.2 链表则依次遍历，查找相同的key，找到则返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;
            } while ((e = e.next) != null);
        }
    }    //数组为空，或者没有找到返回空
    return null;
}

道阻且长，且歌且行！ 每天一小步，踏踏实实走好脚下的路，文章为自己学习总结，不复制黏贴，就是想让自己的知识沉淀一下，也希望与更多的人交流，如有错误，请批评指正！