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）那直接覆盖。如果不是就链表或红黑树遍历，遍历完再走上面流程。
- 通过hash函数计算存储位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- 判断table是否为null或长度为0，如果是，调用resize()方法进行扩容
- 如果tabel[i]为null，直接构造Node插入
- 如果tabel[i]不为null 判断key是否等于index处对应的key，如果相等或者equals方法相等，直接覆盖。
- 否则如果是红黑树，插入
- 链表的话判断长度是否大于等于8，是的话变为红黑树插入，否则链表 插入。
get方法
- table为null，返回null
- 计算hash值，定位到index，判断key是否相等或者equals是否相等，如果相等返回
- 否则遍历，如果是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 的话，就可以实现取模运算了
扩容方式
扩容时机
第一次插入时扩容
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
扩容是插入步骤：
- 新建一个2倍数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; - 重新计算index插入
newTab[e.hash & (newCap - 1)] = e;
头插入尾插为啥形成环
头插入的话，扩容后，链表上实例的相对位置会发生变化。多线程环境下操作可能形成环。
线程安全相关
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
