Jdk1.8中，HashMap底层基于数组、链表、红黑树实现
不同的key计算出相同的hash值得到数组相同位置的索引，就发生hash冲突，形成链表
当数组长度大于默认值的0.75就发生扩容，
链表转换红黑树的必要条件： 链表长度大于8，数组长度大于等于64
红黑树虽然查询速度快，但是占用空间是链表的2倍，链表长度小的时候，整个遍历也不会消耗太多时间

//定义hashmap的时候给定数组初始长度，默认16
Map<Integer, Integer> map = new HashMap<>(64);

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8; (jdk1.8以后才有)
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 负载因子
    final float loadFactor;
}

红黑树：
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
特点：
1.每个节点要么是红色，要么是黑色。
2.根节点必须是黑色
3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。如果有删除或者插入节点,使用左旋和右旋;

HashMap提供了4个构造函数：

HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
HashMap(Map<? extends K, ? extends V> m)：传入一个map以构造一个新的map，使用默认加载因子（0.75）。

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

HashMap 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;
    //判断table是否为空，为空就进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果通过hash值取模得到的桶为空，则直接把新生成的节点放入该桶
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//以下为该桶不为空的逻辑
        Node<K,V> e; K k;
        //判断桶的第一个元素的key值是否相同（hash值相同，且能equals）
        //如果相同，则返回当前元素（函数末尾进行统一处理）
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        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);
                    //插入之后，检查是否达到了转成红黑树结构的标准
                    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;
                p = e;
            }
        }
        //处理相同元素的情况
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //如果onlyIfAbsent为ture，则在oldValue为空时才替换
            //否则直接替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//修改次数+1
    //map的size加1，然后判断是否达到了threshold，否则进行扩容
    //threshold由Node[] table的长度及loadFactor控制
    if (++size > threshold)
        resize();
    //执行回调函数
    afterNodeInsertion(evict);
    return null;
}

Put 总结：

1 判断存放元素的数组是否为空， 为空就初始化容量，默认长度为16

2 计算key的hash值 ，

3 用公式key的hash值%数组长度16得到元素在数组中的索引位置

4 判断该数组索引上是否有元素，如果没有，创建一个Node节点，放到这个位置，tab[i] = newNode

5 如果索引有元素了，就是hash冲突了，判断老数据类型，两种情况 链表还是红黑树，

6 如果是红黑树就走红黑树的流程 是链表就走链表的流程

7 链表需要判断当前节点的下一个节点是否为NULL 为NULL 就设置进去，还要判断节点是否大于8，大于8需要转换成红黑树，

8如果不为NULL 就一直遍历 直到下一个节点为NULL，遍历过程中如果找到相同的key,直接退出遍历，把新的key返回，最后会判断key是否为Null,不为NULL，就把value 覆盖 旧值 最后才是判断数组是否需要扩容

①判断当前桶是否为空，空的就需要初始化数组（resize（） 中会判断是否进行初始化）。
②根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
③如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
④如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
⑤如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
⑥接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
⑦如果在遍历过程中找到 key 相同时直接退出遍历。
⑧如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
⑨最后判断是否需要进行扩容。

---

Get底层代码：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果table不为空，则再进行查询操作
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        //先检查第一个元素是否key相同
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //如果为红黑树结构，则走红黑树的查询逻辑
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {//否则遍历链表
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Get总结：

1 判断存放元素的数组是否为空， 为空则不再查询，返回NULL

2 计算key的hash值

3 用公式key的hash值%数组长度16得到元素在数组中的索引位置

4 判断当前位置的数据类型是红黑树还是链表

5 红黑树就以红黑树的二分查找就行查询返回

6 链表就需要遍历，找到相同的key就返回 遍历完没有找到就返回Null

---

为什么要用到数组、链表、红黑树这些结构？
1、数组长度是16，每个元素都是key-value结构， 元素存储到75%（0.75负载因子）进行 2倍扩容。
2、存储元素的算法是 hash(key) % 16 根据key进行hash计算得到的值来对数组长度16 取模，余数作为元素在数组中的存储索引位置。
3、链表为了解决Hash冲突 , 不同的key进行 hash计算可能hash值一样，那么计算出来的存储索引位置也一样，这叫hash冲突，HashMap使用链表的方式来解决Hash冲突，就是在当前索引位置的元素上向下拖一个链表。
4、红黑树是为了提高查询速度了，因为链表过长，查询速度会很慢，红黑树能提高查询速度 ，当链表长度达到 8 且数组长度大于64 变成 红黑树，当链表长度 小于 6 变成链表。

---

链表和红黑树在什么情况下转换的？
1、链表元素超过8时且数组长度大于等于64，会自动转化成红黑树；元素小于等于6时，树结构还原成链表形式
2、红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；
链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
3、选择6和8的原因是，中间有个差值7可以防止链表和树之间频繁的转换。
假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。