之前已经分析过了一版1.7版本的HashMap，这里主要是来分析一下1.8HashMap源码。
一、HashMap数据结构
HashMap 是一个利用散列表（哈希表）原理来存储元素的集合，是根据Key value而直接进行访问的数 据结构。
-
在 JDK1.7 中，HashMap 是由 数组+链表构成的。
-
在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成
数组: 优势：数组是连续的内存，查询快（o1 ）劣势：插入删除O(N) 链表: 优势：不是连续的内存，随 便插入（前、中间、尾部）插入O(1) 劣势：查询慢O(N)。
二、HashMap源码深度解析
2.1 成员变量与内部类
// 默认数组容量，16，左移4位既16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量，左移30位，即2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 当链表的值小于6红黑树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 做红黑树转换的hashmap容量大小，如果前面单个链表个数大于8，但是hashmap容量小于64则直接扩容不做红黑树转换
static final int MIN_TREEIFY_CAPACITY = 64;
// hashmap得数组，中间状态数据
transient Node<K,V>[] table;
// 用来存放缓存、中间状态数据
transient Set<Map.Entry<K,V>> entrySet;
// hashmap的实时数据
transient int size;
// 用来记录hashmap中K-V的修改次数
transient int modCount;
// 扩容临界值
int threshold;
// 负载因子
final float loadFactor;
// 具体存放数据的地方，JDK 1.7之前存放的是Entry，JDK1.8之后存放的是node节点
static class Node<K,V> implements Map.Entry<K,V> {
// hash值
final int hash;
// key值
final K key;
V value;
// 下一个节点指针
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.2 HashMap构造器
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}使用默认构造函数时，在put之前和之后分别debug以上变量信息对比看看。
第一次put之后：
接下来我们使用自定义初始化参数验证：
在有参数构造时，最终tableSizeFor。
/**
* 带参数的初始化其实threshold就是调用这个函数
* 其实这里最主要的作用就是将cap转成n的指数倍
* 首先将n转成2进制，右移再和自己取或，相当于把里面所有的0变成1
* 最终的目的，找到>=n的，1开头后面全是0的数，例如n整数为17，那么二进制为10001 -1 =10000，经过不断右移或自己，那么高位都会变成了11111
* 最后n的值就为：11111+1=100000，对应的整数值就是32
*/
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;
}总结：
- 无参数构造时，容量为16，因子=0.75，第一次插入数据时，才会初始化table阈值等信息。
- 有参构造函数，会取大于但是最接近你容量的2的指数倍。
- 无论哪种构造方式，扩容阈值最终都是=容量*因子。
2.3 HashMap插入方法
1）先了解以下流程图。
2）关于key做hash值的计算
当我们调用put方法添加元素的时候，实际是调用了其内部的putVal方法，第一个参数需要对key求hash值。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
然后我们来看下hash是怎么取值的。
static final int hash(Object key) {
int h;
// hash 扰动
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}图解：
结论：使用移位异或运算做第二次扰动，不是直接使用hashcode。
3）核心逻辑：
/**
* onlyIfAbsent:true不更改现有值
* evict：fakse表示table为创建状态
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 临时变量，tab=数组，p=插槽的指针，n=tab的长度,i为数组下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 数组是否为null或者size长度=0,第一次put的时候初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化数组or扩容
n = (tab = resize()).length;
// 寻址，后续会将具体源码
if ((p = tab[i = (n - 1) & hash]) == null)
// 获取得到的坐标为空，则直接新的node放在插槽上
tab[i] = newNode(hash, key, value, null);
else {
/**
* 如果存在有值那么说明存在hash碰撞了，需要追加成链表了
* e：是否找到与当前key相同的节点，找到说明是更新，null说明是新key插入
* k:临时变量，查找过程中的key在这里暂存
*/
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 如果第一个正好是相同的
e = p; // 将p赋值给e，要注意此时还没有覆盖，只是单单的标记到了e，标记找到相同key的节点。
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);
// 一直遍历到最后判断找不到存在一样的key，那么直接插入到末尾，并且这里会判断是否需要转换成红黑树，内部会判断时候数据大小是否大于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; // 遍历的过程如果找到一样的，那么赋值给e
p = e;
}
}
if (e != null) { //如果e是非空的，那么说明前面循环中找到了一个跟当前key相同的值
V oldValue = e.value;
// 判断是否需要覆盖
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 用来标记修改次数
++modCount;
// 判断当前大小是否超过阈值，如果超过则做扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}4）寻址计算
接着上面说的 i = (n - 1) & hash]，这个寻址计算，我们来看下下面的例子：
其实在上面已经说到过了，我们的hash值是去hashcode然后跟本身右移16做异或运算得到最终扰动之后的hash值，然后这里跟对应的数组长度做与运算，hashcode不会超长了吗，我们来看下面的例子：
其实可以看得到，其实就是拿hashcode的对应数组长度的低位做运算，hashcode超出那部分就不要了。
就是不管你算出来的hash是多少，超出tab长度的高位会被抹掉，低位是多少就是你所在的槽的位置，也就是对应table的下标。
这里可能有人会问了，为什么不做取模运算，取模也会保证不会超出来数组长度，其实这里做位运算的效率比取模运算是要高非常多的！！！！
2.4 hashmap扩容方法
看下图：
核心源码resize方法：
/**
* 这个方法包含了初试化以及扩容的方法
*/
final Node<K,V>[] resize() {
// 原先的数组
Node<K,V>[] oldTab = table;
// 原数组长度，如果没有初始化那么就是0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 原扩容临界点
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 如果原值就已经到达上线，不扩容直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
/**
* 如果还没到上限，那么就重新计算新容量，注意这里还是没有开始迁移数据
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 原数组长度左移一位，其实就是*2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // HashMap(int initialCapacity, float loadFactor)初始化的时候调用
newCap = oldThr;
else { // HashMap() 初始化的时候调用，注意前面验证过了，是在第一次put的时候调的
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;
// 以上各种操作就是各种容量相关值的计算，下面是计算之后重新迁移数据
@SuppressWarnings({"rawtypes","unchecked"})
// 按照新容量来创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果原数据不为空，则开始迁移数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 遍历数组
Node<K,V> e; // 临时变量，记录的是当前指向的node节点
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 方便gc
if (e.next == null) // 不存在下一个节点，既只有一个节点，那么直接复制到新数组的索引下即可
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 如果是树节点，拆成两拼到新table上
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
/**
* 如果是链表那么则拆成两个链表
* loHead：低位链表
* hiHead：高位链表
* 在上面我们说过了，其实我们是拿数组长度对应的hashcode的低位做与运算来得到对应的数组下标
* 现在数据扩容了两倍，就是就是多拿了一位hashcode对应高位来做运算，如果运算结果为0，那么代表hashcode的高一位为0，那么这node节点迁移到新数组上则是在低位
* 如果返回的是1，那么代表高位的是1，则迁移到新数组上面去这个节点应该是在高位
* 其实这也是为什么hashmap是2倍扩容的原因。
*/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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;
newTab[j + oldCap] = hiHead; // 高位，原数据下标+原数组长度
}
}
}
}
}
return newTab;
}总结：
- 扩容就是将旧表的数据迁移到新表。
- 迁移过去的值需要重新计算hashcode，也就是他存储位置
- 如果计算位置，采用低位链表和高位链表，如果位置下面的e.hash&oldCap等于0，那么它对应的就是低位链表，也就是数据位置保持不变。
- e.hash & old不等于0就是要重写计算他的位置，也就是j+oldCap，就是高位链表位置。 例如原数组长度为16,16的二进制为：10000，原先计算hash是拿hashcode & （16-1）就是参与运算的二进制就是，1111，然后现在拿16来做与运算，就是判断原先的key的高一位是否是0，还是1，如果是1，那么与运算返回的结果就不是0，那么这个位置就是应该放在高位链表，否则表示这个key的原先的hashcode的高一位数为0，然后与运算返回的结果就是0，则应该放在低位链表。
2.5 HashMap获取方法
![[算法] 优先算法(三):滑动窗口(上)](https://img-blog.csdnimg.cn/direct/e0d3ec96d2184852a603e610ac17d3ca.jpeg#pic_center)
