《面试王者系列》HashMap 之 原理篇
HashMap是我们实际工作中用得最多的一个集合之一了，也是面试必考点之一，它涵盖了基础数据结构、哈希算法、扩容机制等等，它既有广度也有深度，能很好的验证一个开发者对编程基础的掌握程度。
当年我学习了很多的基础数据结构和算法，但怎么使用，场景在哪里？很迷茫。后来看了HashMap的原理后，发现它就是这些基础数据结构和哈希算法非常经典的应用场景。
原理简介
HahsMap的数据结构由数组 + 链表和红黑树 组成
每个存储在HashMap里的数据，都是以key、value这种键值对的形式存储在链表或者红黑树里的
它的核心就是利用key计算出来的hash值和数组的长度进行取模，来确定数据在数组中的位置
如果这个位置已经存在数据，说明出现哈希冲突了，就会在对应位置上形成一条链表
如果某一个位置的哈希碰撞很多，链表太长是会影响查询效率的，所以链表长度达到一个阈值之后，会转成红黑树来提高查询效率
最后就是扩容了，数据越多，数组里空格的地方也就越少，也越容易发生哈希冲突
所以当数据总数达到一个阈值之后，就会触发扩容，每次扩容，都是原来的2倍
数据结构
HashMap的数据结构由数组 + 链表组成，在链表达到一定长度后，会转成红黑树，这是JDK8之后新增的特性，目的是解决链表太长导致的效率问题。
为什么是数组+链表的结构？
数组搭配hash取模的效率是最高的，o(1)的时间复杂度
但是哈希算法会有哈希冲突的问题
链表就是来解决这个问题的，当出现哈希冲突，会在数组的对应位置形成一条链表
链表源码
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //keyd的hash值
final K key; //键
V value; //值
Node<K,V> next; //下一条数据
...
}
红黑树源码
其实 LinkedHashMap.Entry 还是继承于 HashMap.Node，所以TreeNode也是Node的子类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
成员变量
成员变量源码（加了注释）
/** HashMap数据存放的地方 */
transient Node<K,V>[] table;
/** 迭代器，用于遍历数据 */
transient Set<Map.Entry<K,V>> entrySet;
/** 实际数据总数 */
transient int size;
/** 变更次数，用于判断是否在迭代过程中变更了数据 */
transient int modCount;
/** 扩容阈值 */
int threshold;
/** 自定义的扩容负载因子 */
final float loadFactor;
基本规则
1、HahsMap默认初始容量是16
2、HahsMap最大容量是2的30次方，也就是1073741824
3、HahsMap默认的扩容负载因子是0.75
4、HahsMap链表和红黑树互相转换的规则：
（1、链表长度达到8，且集合容量达到64时才会转红黑树
（2、链表长度达到8，但集合容量还没有达到64时，不会转红黑树，但会执行扩容的操作
（3、红黑树长度退回到6，会转成链表
5、HahsMap每次扩容都是在当前容量的基础上*2，也就是扩容两倍。且容量一定是2的n次幂， 也是就是2、4、8、16、32、64、128、256 .......
规则常量源码（加了注释）
/** 初始容量 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 最大容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 初始负载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 转成红黑树的链表长度阈值 */
static final int TREEIFY_THRESHOLD = 8;
/** 红黑树退回链表的阈值 */
static final int UNTREEIFY_THRESHOLD = 6;
/** 链表转成红黑树的容量阈值 */
static final int MIN_TREEIFY_CAPACITY = 64;
构造函数 & 如何保证容量是2的n次方
构造函数源码解析
/** 可自定义容量和扩容负载因子的构造函数 */
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);
}
/** 可自定义容量的构造函数 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 无参构造函数 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 带默认值的构造函数 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
如何保证容量是2的n次方
使用无参构造器和默认值构造器的情况下，容量肯定是2的n次方
因为默认的容量是16，之后每次扩容，都是扩容2倍，所以一定是2的n次方
但是当使用了自定义容量的构造器，HashMap还怎么保证容量还是2的n次方呢
答案在这个构造函数上
在这个构造函数里，有这样一行代码 this.threshold = tableSizeFor(initialCapacity);
有点懵对不对，这是设置的threshold是扩容阈值，和容量有什么关系？
别急，我们先看tableSizeFor()方法，上代码
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的n次方的数值
举个栗子，当输入一个10，这个方法会返回16，输入25，会返回32，依此类推
关键的地方到了！HashMap的扩容和初始化，都是在resize()里完成的，在put()方法第一次被调用的时候，会调用resize()初始化容量。
如上图，如果我们使用的是自定义容量的构造器，在初始化容量时可以大致分成4步
第1步：设置oldThe = threshold
第2步：还记得吗？在构造器里已经设置了threshold = tableSizeFor(initialCapacity)，所以此时else if (oldThr > 0) 这个条件是符合的 ，然后把初始容量newCap 设置为 oldThe，到这里，是不是都串起来了......，构造器里当时看着很迷的操作，其实是为了在这里设置初始容量用的。
第3步：设置threshold真正的数值，也就是threshold = 容量 * 自定义负载因子
最后一步，按容量newCap长度创建数组，赋值给table，初始化操作完成
怎么计算数组下标的？
分三步：
1、通过key拿到hashcode
2、通过hashcode计算hash值，这里加上了高16位异或低16位的扰动函数，目的是减少哈希碰撞几率。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
3、通过取到的 hash 值，和 容量长度-1 进行 位与& 运算，得到数组下标
table[hash & (table.length - 1)]
拓展知识：
其实hash & (table.length - 1) 等同于 hash % table.length
使用 & 替代 % 是因为位运算比 取余% 运算符快很多
但hash & (table.length - 1) 等同于 hash % table.length有一个前提，就是容量的长度必须是2的n次方，这也是为什么容量必须是2的n次方的原因。
get() 获取数据
定位数据
通过key计算出来的hash值，和容量长度-1进行位与运算& 得到数组下标，通过这个下标，获取到数据对象，这个数据对象可能是链表或者树，需要按照不同的结构来进行遍历或检索。
判断key是否符合条件
遍历过程中，会对比 hash值 和 equals() ，两项都一致，就认为符合条件
源代码解析
public V get(Object key) {
Node<K,V> e;
// 通过传入的key，计算出 hash 值，然后匹配Node
// 匹配到，返回value，否则返回null
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 获取Node的核心方法
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 通过hash & table.length-1计算数组下标，然后获取数组这个位置的链表。
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 先判断第一条数据是否符合条件
// 判断规则：hash值一致 和 equals()对比一致
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 第一条不符合条件，判断是链表还是树，然后按照不同的结构来遍历匹配
if ((e = first.next) != null) {
// 红黑树的遍历与匹配
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 链表的遍历与匹配
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
put() 添加数据
懒汉式初始化容量
HashMap初始化工作是在put()阶段段完成的，在新增数据前，先判断是否需要初始化，如果还未初始化，则调用resize()方法进行初始化。（也可以理解为第一次添加数据时，才进行初始化的操作）
添加数据
和get()方法一样，通过key计算出的hash值和数组长度进行取模运算，得到数组下标
如果这个位置没有数据，直接创建一个Node放在这个下标位置即可
如果已经存在数据，说明哈希冲突了，根据这个位置数据对象的结构（它们可能是链表或者树），来进行遍历或者检索是否存在相同key的数据，存在则修改value，不存在则插入链表尾部或者添加到树上
转 红黑树 和 扩容 的时机
当新增数据时，还会判断对应下标位置的链表长度是否达到8，且容量也达到64，满足这俩条件时，会把链表转成红黑树。如果链表长度达到8，但容量没有达到64，就扩容两倍。最后判断数据总数是否达到扩容的阈值，达到了就进行扩容。
Tip：红黑树的长度在退回到6的时候，会转回链表。
源代码解析
public V put(K key, V value) {
// 1、通过传入的key计算hash值和调用核心的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;
// 2、判断数组有没有被初始化，没有则调用扩容的方法进行初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 3、容量长度-1 和 hash 进行 位与运算&，得到数组下标和这个位置的数据
if ((p = tab[i = (n - 1) & hash]) == null)
// 4、如果这个位置没有数据，直接创建一个链表放到这个下标位置，然后执行到步骤9
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 5、如果有数据，说明哈希冲突了，先看这个位置第一条是否匹配key，匹配就执行步骤8修改
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 6、第一条不匹配，且数据对象是树，检索这个key是否已经存在，不存在则添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 7、第一条不匹配，且数据对象是链表，遍历这个key是否已经存在，不存在就插入链表尾部
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 7.1 遍历到链表尾了，没有相同的key，就插入链表尾部
p.next = newNode(hash, key, value, null);
// 7.2 链表长度达到阈值，执行转红黑树的方法，里面会判断容量是否达到64和扩容
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;
}
}
// 8、5-6-7如果匹配到了相同key的数据，替换value，返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 9、是添加而不是修改数据的情况时，modCount+1，然后判断是否达到阈值，达到即进行扩容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* 链表转红黑树的方法
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组容量没有达到64，扩容即可
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
为什么JDK8要优化成使用尾插法？
JDK7的时候，使用的是头插法，JDK8以后，优化成了尾插法
因为头插法，在多线程并发扩容的时候，可能会出现环形链表的情况
到了JDK8，改成了使用尾插法，第一可以避免环形链表的发生，第二尾插法扩容时不会改变数据在链表中的顺序。
拓展知识
JDK7的扩容核心代码
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历旧数组
for (Entry<K,V> e : table) {
// 遍历链表
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算在新数组里的下标位置
int i = indexFor(e.hash, newCapacity);
// 头插法，旧数组的数据迁移到新数组后，顺序会倒过来
e.next = newTable[i];
newTable[i] = e;
// 继续向后遍历，直到next=null
e = next;
}
}
}
举个栗子
原数组下标1的地方存储着 A和B两条数据
我们假设，在扩容后，A和B会存储在新数组下标2的位置
然后有2个线程同时进入到transfer()方法里，t1 和 t2
t1 执行到 while(null != e) { 这个循环内，CPU时间片用完了，挂起，此时e=A
t2 开始执行，第一轮遍历到A，把A放到新数组下标3的位置，第二轮遍历到B，由于使用的是头插法，所以B会插在A的前面，顺序也就变成了 B -> A
这个时候，t2的CPU时间片结束，挂起
t1 继续执行，注意了，执行到这行代码的时候 e.next = newTable[i]; ，此时的newTable[i]已经被t2线程设置成 B ，而B.next又是A，一个环，就这样形成了
由于此时还在while循环体内，t1线程会进入死循环
resize() 扩容 & 初始化容量
扩容
有两种情况会触发扩容
一种是在put()添加数据时，size 大于扩容阈值，会触发扩容
还有一种也是在put()添加数据时，key对应位置上的链表长度达到8，但是容量却没有达到64，也会触发扩容，目的是通过扩容的方式，减小这个位置再次发生哈希冲突的几率。
容量小于最大值MAXIMUM_CAPACITY = 1 << 30，才进行扩容，而且每次扩容都是在原基础上*2，这样能保证扩容后，容量也是2的n次方。
如果容量已经达到最大值，就不进行扩容了，但是会把threshold(扩容阈值)设置成int最大值，此时扩容阈值会比容量大，之后put()新数据，因为size > threshold条件不满足，也就不会触发扩容了。
扩容本质上是创建一个容量更大的数组，然后把原数组的数据迁移到新数组里面
但由于数组长度变大，原数组里的数据在新数组里，不一定还是原来那个位置了
扩容前，容量是 8 ，算出来的下标是0
扩容后，容量是 16，算出来的下标是9
这明显不一样了，所以迁移数据时，得重新hash定位到新数组对应的位置上。
容量初始化
容量初始化分两种，默认初始化和自定义初始化
-
默认初始化：实例不是通过自定义容量和负载因子的构造器创建的，此时容量会设置为16，扩容阈值会设置成16 * 0.75；
-
自定义初始化：实例是通过自定义容量和负载因子的构造器创建的，初始化容量 = 自定义容量向右最近的一个2的n次方值，例如定义的是10的容量，实际上这个实例默认容量会是16。
源代码解析
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 当前容量长度 > 0 时，说明容量已经初始化过，可以进行扩容，
if (oldCap > 0) {
// 当前容量达到最大值，就不扩容了，但是得把扩容阈值设置成int最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没有达到最大容量，把新的容量值设置为 当前容量*2
// 如果扩容前的容量是大于16的，新的扩容阈值也*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 使用了自定义容量和负载因子的构造器，在进行容量初始化时，会命中此if条件
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始容量 = oldThr即可
newCap = oldThr;
// 默认的容量初始化
else { // zero initial threshold signifies using defaults
// 容量等于默认值16
newCap = DEFAULT_INITIAL_CAPACITY;
// 扩容阈值等于 16*0.75
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当使用了自定义容量和负载因子的构造器，在进行容量初始化是，会命中此if条件
if (newThr == 0) {
// 初始化扩容阈值=最新容量*自定义负载因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 扩容，创建一个新数组，容量等于上面计算出来的newCap
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 非初始化容量时
if (oldTab != null) {
// 遍历旧数组，把里面的数据重新hash到新数组中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 位置j只有一条数据的，直接hash计算出下标，放到新数组中对应的位置即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 位置j是红黑树，按红黑树的规则进行重新计算和设置在新数组的位置
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 位置j是链表而且这个链表length > 1，遍历进行迁移
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 = 0 表示不需要改变位置
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);
// 不需要改变位置的，index还是使用原来的
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 需要改变位置的，使用 原位置 + 原容量长度 的位置即可
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
转载自:https://juejin.cn/post/7195402758118178871