HashMap的数据结构
(JDK1.8为例)
如图
先知道三个概念
table：存储HashMap节点信息，是个数组
slot：hash槽，即table[i]
bullet：hash桶，相同hash槽上所有元素的集合
这张图有点像一张二维表。HashMap的数据结构采用是分而治之的思想，按照一定的规则将数据一排排存放，查找的时候先找到数据在哪一排，然后在从这排数据挨个找。提高效率。
那么每一排的数据是怎么存放的。以链表的形式存储的，并且满足一些条件时，链表会转化为红黑树。当然，红黑树也会再变成链表。
HashMap简单来说是底层数据结构是数组+链表+红黑树的组合，
数组记录着每一列的位置，链表和红黑树表示列上元素的排列规则。
在源码中，用table表示数组，代码如下
transient Node<K,V>[] table;
Node是HashMap的内部类，是链表上的节点。里面的元素有hash值，键值对以及指向下一个节点的next指针，代码如下：
static class Node<K,V> implements Map.Entry<K,V>{
final int hash;
final K key;
V value;
Node<K,V> next;
}
HashMap几个重要的元素
默认初始化值16
在创建HashMap时，如果没有指定具体的值，初始化默认是16，即创建的数组的长度，代码如下
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
最大容量，即HashMap能创建的最大容量，能创建的数据的最大长度，代码如下
static final int MAXIMUM_CAPACITY = 1 << 30
负载因子，HashMap的扩容参数之一，浮点类型。默认0.75，代码如下
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表转化阈值，在jdk1.8后，当Hash桶的元素个数增加，大于等于8时，会转化为红黑树，代码如下
static final int TREEIFY_THRESHOLD = 8;
红黑树转化阈值。当Hash桶的元素个数减少，小于等于6时，会变回链表，代码如下
static final int UNTREEIFY_THRESHOLD = 6;
最小的树形化阈值。只有当HashMap的数组长度超过这个数值时，链表才允许转化的树。
因此，链表转化为树的条件有两个1：HashMap数组长度超过64，2:链表上的元素大于等于8了
代码如下
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的扩容过程
1.为什么扩容？
HashMap的设计思想是分而治之。如果没有指定初始化容量值，那么HashMap在初始化时会创建一个容量为16的数组。我们可以理解为创建了一个有16列的队伍。然后每插入一个元素，先算出这个元素在第几列，如果该列没有元素，就排上去。如果该列已经有元素了，就插到最后一个元素的后面。那么下次需要找出该元素，只需先找到该元素所在的列，然后再从该列中寻找。提高效率。但是，毕竟只有16列的队伍，随着插入元素的增多，列上的元素也有越来越多，那么其实到后面会很影响查询效率。所以。这时候就需要扩容，即把数组的个数进行扩充。HashMap每次会将数组扩容为之前的两倍。
2.什么时候进行扩容？
jdk1.8源码中，扩容的方法名是resize()
final Node<K,V>[] resize() {
//....
}
HashMap在这些时候进行扩容：
1）第一次put的时候，即第一次插入元素的时候。
当我们创建一个HashMap对象的时候，其实HashMap并没有初始化数组。我们可以看下HashMap的构造方法：
//无参构造方法
public HashMap() {
//指定负载因子为默认的负载因子，即0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//两个参数构造方法
//指定初始容量initialCapacity 指定负载因子loadFactor
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);
}
//一个参数构造方法
//调用两个参数的构造方法，初始容量为自己指定，负载因子用默认的DEFAULT_LOAD_FACTOR,即0.75f
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
可以看出HashMap的构造方法主要是初始化一些成员量。而当需要往hashMap插入第一个元素的时候，就需要进行第一次扩容了，毕竟创建对象只是指定成员量，没有实际的空间装东西嘛。代码如下
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
这里调用了resize()，其实就是扩容了。
在resize()方法里
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
这里创建了大小为newCap的Node数组。如果没有指定初始化大小，那么newCap等于DEFAULT_INITIAL_CAPACITY(16)。如果指定了大小，那么newCap等于tableSizeFor(int cap)计算得来的值
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;
}
}
2)当元素个数大于threshold时
if (++size > threshold)
resize();
threshold是扩容的阈值。第一次的域值是初始化容量*负载因子，按照默认的情况，就是16乘以0.75，为12。
可以看出是当第十二个元素插入完成后，进行扩容。在扩容的过程中，会将阈值扩充为之前的两倍。按照默认的情况下，会变成24，也就是说当第二十四的元素插入完成后，会再进行扩容
3）还有一种情况，也会进行扩容，就是当链表上的元素大于8，但是因为数组个数还没到达64嘛，无法转化为红黑树，这时候，也会进行扩容
这个是在treeifyBin方法中，treeifyBin是将链表转化为红黑树的方法。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
能进入这个方法，说明链表的长度满足大于8的要求了，但是在方法内部有这一层判断，如果tab即数组的长度小于MIN_TREEIFY_CAPACITY，就是64的时候，那么不转红黑树了，也会进行扩容
3.怎么扩容
扩容简单来说就是做了两件事。1：创建一个新数组，原来的两倍大。2：把旧数组的元素放入到新数组中
看看resize()方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//oldTab :老数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap :老数组的长度
int oldThr = threshold; //老扩容阈值
int newCap, newThr = 0; //newCap新数组长度，初始为0。newThr 新扩容阈值，初始为0
//如果老数组长度为0(说明不是第一次扩容)
if (oldCap > 0) {
//如果老数组长度大于扩容最大值，没法扩容，直接返回oldTab老数组
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果把老数组的长度增加两倍还是小于最大值 并且老数组长度大于初始长度值
//这个分支比较经常进啦
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 扩容阈值增加两倍
}
//如果老扩容阈值大于0，把新数组的长度设置为老扩容阈值
//什么时候进这个分支。就是老数组为空，且初始的话的时候指定了默认初始值DEFAULT_INITIAL_CAPACITY
else if (oldThr > 0)
newCap = oldThr;
else { // 这里就是无参构造初始化，第一次扩容时
newCap = DEFAULT_INITIAL_CAPACITY;//长度为默认初始化值16
//阈值为负载因子乘以默认初始化值 为 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//上面的执行完后，如果新的扩容阈值还是0，那么赋值，其实就是有参构造方法初始化，第一次扩容时会进来
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//再把扩容阈值赋值给全局变量threshold，下次扩容时赋值给老扩容阈值时用
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//经过上面的判断，新数组的长度newCap终于被确定出来，两倍长度，然后创建一个新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//再把引用指向全局变量table数组（真正使用的）
table = newTab;
//上面说是第一件事：创建一个新的数组，长度为两倍
//============================我是分割符================================
//下里说第二件事：把旧数组的元素放入新的数组里
//resize最后返回的是newTab，所有接下来的操作其实是对newTab进行操作的
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//创建Node节点e，这个起到临时存储的作用，
//后面都是先将oldTab[i]指向e,然后将oldTab[i]置为null
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//e.next为null，说明该下标的位置只有一个节点
//重新计算插入的新数组的下标 e.hash&(newCap - 1)，
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //如果已经是树节点了
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //单独用树节点的方法处理
else { // 最后就是链表结构的情况
//声明了5个变量
Node<K,V> loHead = null, loTail = null; //低位头 低位尾 节点
Node<K,V> hiHead = null, hiTail = null; //高位头 高位尾 节点
//低位：0到oldCap-1 高位：oldCap到newCap-1
Node<K,V> next;
//遍历链表
do {
next = e.next;//next用于临时存储节点
//和原来旧数组的位置是一样的（用lo存储新链表）
if ((e.hash & oldCap) == 0) {
if (loTail == null)//尾节点为空，说明链表为空
loHead = e; //指向头节点
else
loTail.next = e;//否则放在链表最后一个
loTail = e;/然后再把e指向尾节点
}
else { //如果位置和旧数组的不一样（用hi存储新链表）
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//最后将分别将lo链表和hi放在指定的位置
if (loTail != null) {
loTail.next = null;//现将尾节点的next节点置为空
newTab[j] = loHead;//放在和原来下标一样的位置
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;//放在原下标加上oldCap的位置
}
}
}
}
}
return newTab;
}