1.HashMap数据结构

JDK1.7，HashMap由数组和链表组成；
JDK1.8，HashMap中增加了红黑树，在数据较多时，链表转化成红黑树；数据变少时退化成链表；

2.HashMap如何初始化

1.如果用户没有设置容器初始大小，hashMap什么都不做；
2.如果用户初始化的时候传入了容量设置，hashMap会做一些初始化操作，但是不会分配内存；

initialCapacity:初始设置的容器大小
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

loadFactor：加载因子当hashmap的大小达到caacity*loadFactor的时候执行resize操作；
 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
  }

通过移位运算计算出大等于cap的2次幂，作为hashMap的容量
    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;
    }

3.HashMap如何扩容

HashMap通过resize方法扩容
1.每次扩容时，hash数组长度扩大为原来的两倍；
2.初次初始化hash数组时，数组长度为threadshold的值；
3.第二次扩容时，数组长度为当前数组长度的2倍，上限是1<<30;
4.扩容完成了，会进行把数据放入新的hash数组，并进行结构重建；

4.HashMap插入元素的主要流程

1.计算key值的hash值；
2.table初始化检查：容量检查，扩容阈值更新，扩容后，数据迁移；
3.如果key值对应索引位没有数据，则直接新曾结点存入table节点中；否的话直接第4步；
4.如果当前节点只有一个元素直接替换，如果当前节点是红黑树，执行红黑树的插入操作，如果当前节点是链表，如果链表中存在key值和hash值都相同的元素则替换，否则采用头插法插入元素，如果当前链表的数据达到8个还进行树化操作。
5.至此HashMap的插入操作完成

5.HashMap什么时候转化为红黑树

1.在HashMap插入操作源码时，我们发现当table数组某一位置存储的元素达到8个转化成红黑树，并且hash表的长度达到64时，才开始执行树化。
2.hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换

6.HashMap 红黑树什么时候退化成链表

hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。

7.HashMap如果移除元素

1.计算出key值对应的Hash值，key穿null，hash值为0；
2.key的hash值与hash表的长度n-1做与运算，找到hash值的索引；
3.如果该索引对应位置只有一个元素，则检查key值和hash值是否相等，如果是则定位到待删除元素，如果该索引存储的是红黑树则执行红黑数查找，如果是链表则执行链表查找；
4.在第三步中，如果当前链表是红黑树，再删除元素后，还会执行红黑是否需要退化成链表的检查；