HashMap

HashMap存储的时key-value格式的实例。
底层的存储结构是数组+链表格式。
单个实例的格式

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

一些成员变量

transient Node<K,V>[] table：底层存储结构
Set<Map.Entry<K,V>> entrySet：
size：记录了当前数量
threshold：临界值threshold = capacity * loadFactor,当size大于临界值就要扩容
loadFactor：负载因子，衡量HashMap满的程度，默认0.75f

还有一个capacity容量，不是成员变量，但很重要。

新建HashMap

 public HashMap(int initialCapacity, float loadFactor) 

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

无参构造函数，在第一次put数据的时候会进行扩容。

newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

上述构造函数新建时，并没有新建数组，对于前2个，只是设置了负载因子和临界值。
对于无参的构造函数，在第一次put数据时才会设置负载因子和临界值。
初始化数组都是在第一次put数据时。

存取原理

put方法

总体的流程就是，如果定位的table[index]为null，直接插入，如果index的key和要插入的相等（地址或者equals）那直接覆盖。如果不是就链表或红黑树遍历，遍历完再走上面流程。

put流程

https://www.cnblogs.com/LiaHon/p/11149644.html

1. 通过hash函数计算存储位置

 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. 判断table是否为null或长度为0，如果是，调用resize()方法进行扩容
3. 如果tabel[i]为null，直接构造Node插入
4. 如果tabel[i]不为null 判断key是否等于index处对应的key，如果相等或者equals方法相等，直接覆盖。
5. 否则如果是红黑树，插入
6. 链表的话判断长度是否大于等于8，是的话变为红黑树插入，否则链表 插入。

get方法

1. table为null，返回null
2. 计算hash值，定位到index，判断key是否相等或者equals是否相等，如果相等返回
3. 否则遍历，如果是TreeNode红黑树，如果是链表，链表遍历。

为什么需要负载因子：

因为map映射需要进行hash，如果负载因子是1的话，hash冲突概率变大。0.75是个经验值。
如果小了，空间利用率低，如果大了，链表长度过长或者红黑树高度过高。

默认长度为啥是16

经验值，保证是2的次幂就行（1 << 4; // aka 16）

为什么capatity大小都是2的幂？(真正的大小)

为了使用二进制完成取模运行，不用做进制转换，效率高。
hash函数
初始的阈值计算。

this.threshold = tableSizeFor(initialCapacity);

该方法是找到第一个比capacity大的2的次幂。
hash函数的原理还是取模
X % 2^n = X & (2^n – 1)
table中index的选择方式：i = (n - 1) & hash
因此：只要保证length的长度是2^n 的话，就可以实现取模运算了

https://www.cnblogs.com/hollischuang/p/12009172.html

扩容方式

扩容时机

第一次插入时扩容

        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

容量不够时扩容

        if (++size > threshold)
            resize();

容量不足时扩容的长度2倍

            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold

扩容是插入步骤：

1. 新建一个2倍数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
2. 重新计算index插入newTab[e.hash & (newCap - 1)] = e;

头插入尾插为啥形成环

头插入的话，扩容后，链表上实例的相对位置会发生变化。多线程环境下操作可能形成环。

线程安全相关

1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。