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;
}
