1 Hash算法
哈希函数的目标是计算key在数组中的下标。判断一个哈希函数的标准是：散列是否均匀、计算是否简单。
HashMap哈希函数的步骤：
对key对象的hashcode进行扰动
通过取模求得数组下标
扰动是为了让hashcode的随机性更高，第二步取模就不会让所以的key都聚集在一起，提高散列均匀度。
static final int hash(Object key) {
int h;
// 获取到key的hashcode，在高低位异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
也就是低16位是和高16位进行异或，高16位保持不变。一般的数组长度都会比较短，取模运算中只有低位参与散列；高位与低位进行异或，让高位也得以参与散列运算，使得散列更加均匀。
2 HashMap的数组长度
HashMap的默认数组长度的16，如果给于了初始长度，那么将计算出大于等于当前给定数组长度的最小2的幂次方的数，如果给定的数组长度超过MAXIMUM_CAPAC，则用MAXIMUM_CAPAC作为数组长度。
//创建 HashMap 时未指定初始容量情况下的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
规格化数组长度
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;
}
当给定初始长度时，会调用如上方法将HashMap的数组长度设置为2的幂次方。上面一连串的位移操作是为了把n的最高位1后面的位都变成1。这样就是得到一尾数连续为1的数，通过n+1操作就得到一个2的幂次方的数。
注意：
n=cap-1是为了当给的初始长度是2的幂次方时，让结果等于当前给定的初始长度。
3 HashMap定位
HashMap控制数组长度为2的整数次幂，好处是对hashcode进行求余运算和让hashcode与数组长度-1进行位与运算是相同的效果。能够快速定位Key所在的数组的位置，HashMap通过如下方法快速定位。
4 Hash扩容
HashMap每次扩容都使当前数组长度变成原数组长度的2倍（除最大容量外）。
如上（a）为原数组长度，（b）为扩容后的数组长度，可以看出，当扩容后数组原位置上的Key将落在新数组的原位置或原位置+原数组长度。所有扩容后数据的迁移就变得很高效了，只需要判断Key的Hash&原数组长度n就知道Key在扩容后的位置。
5 HashMap数据结构
//HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行 resize() 操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
/* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于 MIN_TREEIFY_CAPACITY ）导致的 hash冲突太多，则不进行链表转变为红黑树操作，转为利用 resize() 函数对 hashMap 扩容 */
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的装载因子默认为0.75，是为了权衡效率和空间。当装载因子越小时，Hash冲突就越小，但占用空间就越大。
JDK1.8HashMap引入了红黑树结构，当链表长度过长时，将链表转换为红黑树，提高链表查询效率。当链表长度大于等于8时，会把链表转换为红黑树。当链表长度等于小于等于6时，会把红黑树转换成链表。
为什么在8和6的时候转换？
因为当负载因子是0.75时，泊松分布中链表长度为8的概率已经很小了，为什么在6的时候转换为链表，一是因为6和8的概率相差较大，二是防止在8的时候对同一个元素平凡的添加和删除，导致链表在长度在8与7之间平凡转换导致效率低下。
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
链表转换成红黑树还有一个限制条件：
当链表要转换为红黑树时，首先要判断当前数组长度是否大于64，如果小于，就进行扩容。
为什么做这一个判读，是因为，数组长度较小时，如果链表长度能达到8，那么离数组扩容也不远了，所有先扩容，防止转换后在扩容，导致效率低下。
5.1Node节点
// Node<K,V> 类用来实现数组及链表的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //保存节点的 hash 值
final K key; //保存节点的 key 值
V value; //保存节点的 value 值
Node<K,V> next; //指向链表结构下的当前节点的 next 节点，红黑树 TreeNode 节点中也有用到
}
// TreeNode<K,V> 继承 LinkedHashMap.Entry<K,V>，用来实现红黑树相关的存储结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 存储当前节点的父节点
TreeNode<K,V> left; //存储当前节点的左孩子
TreeNode<K,V> right; //存储当前节点的右孩子
TreeNode<K,V> prev; // 存储当前节点的前一个节点
boolean red; // 存储当前节点的颜色（红、黑）
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
注意：
TreeNode还有prev，next两个引用，保留了双向链表的特性，在数组扩容时，方便红黑树的遍历。
5.2 put方法
//指定节点 key,value，向 hashMap 中插入节点
public V put(K key, V value) {
//注意待插入节点 hash 值的计算，调用了 hash(key) 函数
//实际调用 putVal（）进行节点的插入
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*根据 hash 值确定节点在数组中的插入位置，若此位置没有元素则进行插入，注意确定插入位置所用的计算方法为 (n - 1) & hash,由于 n 一定是２的幂次，这个操作相当于
hash % n */
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//说明待插入位置存在元素
Node<K,V> e; K k;
//比较原来元素与待插入元素的 hash 值和 key 值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//若原来元素是红黑树节点，调用红黑树的插入方法:putTreeVal
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);
//若链表上节点超过TREEIFY_THRESHOLD - 1，将链表变为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}//end else
if (e != null) { // 待插入元素在 hashMap 中已存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}//end else
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}//end putval
插入流程：
如果数组没有初始化就是初始化数组
定位数组中的位置，如果当前位置没有数据，就直接插入。
-
当前位置存在数据
如果是TreeNode直接插入
如果是Node，判断是否存在当前Key，如果存在则替换值，否则插入链表的尾部，然后判断是否需要转换成红黑树。
判断数组是否需要扩容。
注意：
JDK1.7使用头插，虽然效率高，但是在多线程下扩容会形成环。JDK1.8使用尾插，然后可以避免多线程形成环，但是数据会丢失，使用尾插是为了统计链表长度，判断是否需要转换为红黑树。
5.3 resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/*
1、resize（）函数在size > threshold时被调用。
oldCap大于 0 代表原来的 table 表非空， oldCap 为原表的大小，
oldThr（threshold） 为 oldCap × load_factor
*/
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*
2、resize（）函数在table为空被调用。
oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为
HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
或 HashMap(Map<? extends K, ? extends V> m)，导致 oldTab 为 null，oldCap 为0，
oldThr 为用户指定的 HashMap的初始容量。
*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
/*
3、resize（）函数在table为空被调用。
oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的 HashMap，所有值均采用默认值，
oldTab（Table）表为空，oldCap为0，oldThr等于0，
*/
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把 oldTab 中的节点 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//若节点是单个节点，直接在 newTab 中进行重定位
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//若节点是 TreeNode 节点，要进行 红黑树的 rehash 操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//若是链表，进行链表的 rehash 操作
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//根据算法 e.hash & oldCap 判断节点位置 rehash 后是否发生改变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// rehash 后节点新的位置一定为原来基础上加上 oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容流程：
-
首先确定新数组的大小
如果数组长度大于等于最大容量就不扩容
如果扩容后的数组大于等于最大容量，就让扩容后的数组长度设置为最大容量。
否则就是原来容量的2倍（这里没有解析初始化数组，数组初始化也会扩容）
-
创建新的数组，遍历的就的数据进行数组迁移
当前位置是TreeNode，则调用TreeNode的split方法
当前位置是Node，遍历链表，将链表放置在新数组的当前位置或者，当前位置+原数组长度的位置。
5.4 split方法
//这个函数的功能是对红黑树进行 rehash 操作
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//由于 TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//rehash 操作之后注意对根据链表长度进行 untreeify 或 treeify 操作
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}//end if
}//end split
注意：
由于TreeNode维持了双向链表的特征，所以数据迁移和单链表一样，将数据迁移到新数组的当前位置或这当前位置+原数组长度的位置。最后判断新链表长度，如果大于等于8则转换成红黑树，如果小于等于6转换成链表。当HashMap在删除节点时，不会判断长度，也不会将红黑树转换为链表。
