一.源码大纲
1.了解红黑树原理（可翻看上一个文章，[红黑树原理分析](数据结构红黑树添加、修改原理分析 - 简书 (jianshu.com)
)）
2.对hashmap源码进行详细解析。
二.代码解析
1.原理分析
hashmap原理图
在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。当一个值中要存储到Map的时候会根据Key的值来计算出他的hash，通过哈希来确认到数组的位置，如果发生哈希碰撞就以(单向)链表的形式存储，但是这样如果链表过长来的话，HashMap会把这个链表转换成红黑树来存储。
1.2 hash冲突(hash碰撞)
根据key（键）即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经被占用了。这就是所谓的hash冲突。
1.3 hashmap的初始
- 首先我们看一下hashmap中成员变量:
//当桶(bucket)上的结点数大于8时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
//桶中结构转化为红黑树对应的数组长度最小的值
static final int MIN_TREEIFY_CAPACITY = 64;
//集合的初始化容量为16，初始化容量一定是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//集合最大容量的上限是：2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存储元素的数组，长度必须是2的n次幂
transient Node<K,V>[] table;
//存放元素的个数，注意这个不等于数组的长度。
transient int size;
//HashMap被改变的次数
transient int modCount;
//临界值 当实际大小(容量*负载因子)超过临界值时，会进行扩容
int threshold;
//存储负载因子的常量
final float loadFactor;
//默认的构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定容量大小的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
指定“容量大小”和“加载因子”的构造函数
initialCapacity: 指定的容量
loadFactor:指定的加载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//判断初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超过MAXIMUM_CAPACITY，会将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判断负载因子loadFactor是否小于等于0或者是否是一个非数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果满足上述其中之一，则抛出非法的参数异常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
/*
tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次幂。
但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写：
this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。
但是，请注意，在jdk8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算
*/
this.threshold = tableSizeFor(initialCapacity);
}
/**
Returns a power of two size for the given target capacity.
返回比指定初始化容量大的最小的2的n次幂
*/
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;
}
1.3.1 为什么初始化容量必须为2的n次方
1.为了提高效率使用&位运算符取代了%运算，取模算法hash%length ,hashmap将其优化成位运算hash&(length-1)，但hash%length等于hash&(length-1)的前提是length是2的n次幂
1.3.2红黑树与链表之间关键成员变量
当这个链表的的长度大于8的时候并且数组的长度大于64的时候，则将单链表转化为红黑树，如果链表的长度大于8，但是数组的长度小于64的时候，此时并不会把单链表转化为红黑树，而是对数组进行扩容，再对数据重新排列。
当红黑树的长度小于6的时候，则会把红黑树转换为单链表。
/**
* 链表转为红黑树的临界值，必须大于2且最少为8
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树退化为链表的临界值
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 链表转红黑树的最小容量
*/
static final int MIN_TREEIFY_CAPACITY = 64;
1.4 hashmap核心代码put()方法分析
- hashmap的put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//获取当前key的hashCode值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个是java8的散列扰动函数，用于优化散列效果。通过它获取hash值
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)
//如果未初始化，调用resize方法 进行初始化
n = (tab = resize()).length;
//通过 & 运算求出该数据（key）的数组下标并判断该下标位置是否有数据
//（n-1&hash= hash%n;对hashcode取模，获取当前hashcode在数组中的位置
if ((p = tab[i = (n - 1) & hash]) == null)
//如果没有，直接将数据放在该下标位置
tab[i] = newNode(hash, key, value, null);
//该数组下标有数据的情况
else {
Node<K,V> e; K k;
//判断该位置数据的key和新来的数据是否一样
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果一样，证明为修改操作，该节点的数据赋值给e,后边会用到
e = p;
//判断是不是红黑树
else if (p instanceof TreeNode)
//如果是红黑树的话，进行红黑树的操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//新数据和当前数组既不相同，也不是红黑树节点，证明是链表
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//判断next节点，如果为空的话，证明遍历到链表尾部了
if ((e = p.next) == null) {
//把新值放入链表尾部
p.next = newNode(hash, key, value, null);
//因为新插入了一条数据，所以判断链表长度是不是大于等于8
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;
}
}
//判断e是否为空（e值为修改操作存放原数据的变量）
if (e != null) { // existing mapping for key
//不为空的话证明是修改操作，取出老值
V oldValue = e.value;
//一定会执行 onlyIfAbsent传进来的是false
if (!onlyIfAbsent || oldValue == null)
//将新值赋值当前节点
e.value = value;
afterNodeAccess(e);
//返回老值
return oldValue;
}
}
//计数器，计算当前节点的修改次数
++modCount;
//当前数组中的数据数量如果大于扩容阈值
if (++size > threshold)
//进行扩容操作
resize();
//空方法
afterNodeInsertion(evict);
//添加操作时 返回空值
return null;
}
当前方法分为两种情况，如果下标下没有值，直接放入值，如果下表下有值，对值进行判断，当出现key值相同的，直接覆盖，当链表小于8时，直接添加，当链表大于8的时候进行单链表转换红黑树的操作。
final void treeifyBin(Node < K, V > [] tab,int hash)
{
int n, index;
Node < K, V > e;
// 这块就是我们上面提到的，不一定树化还可能只是扩容。主要桶数组容量是否小于64 MIN_TREEIFY_CAPACITY
//如果数组的容量小于64的时候，不进行转换红黑树，而是进行扩容
if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if((e = tab[index = (n - 1) & hash]) != null){
// 又是单词缩写；hd = head (头部)，tl = tile (结尾)
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);
}
}
判断当前数组的容量是否大于64如果小于64,对当前数组进行扩容操作。如果当前容量大于64，把单项链表转化为双向链表，并把双向链表放置到当前列表的位置，调用treeify方法进行红黑树的转换。
/**
* 参数为HashMap的元素数组
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null; // 定义树的根节点
// 遍历遍历双向链表，x指向当前节点、next指向下一个节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next; // 下一个节点
x.left = x.right = null; // 设置当前节点的左右节点为空
// 如果还没有根节点,设置当前点为根节点,红黑树变化规则root节点变黑
if (root == null) {
x.parent = null; // 当前节点的父节点设为空
x.red = false; // 当前节点的红色属性设为false（把当前节点设为黑色）
root = x; // 根节点指向到当前节点
}
// 如果已经存在根节点了
else {
K k = x.key; // 取得当前链表节点的key
int h = x.hash; // 取得当前链表节点的hash值
Class<?> kc = null; // 定义key所属的Class
// 从根节点开始遍历，寻找插入点，此遍历没有设置边界，只能从内部跳出
for (TreeNode<K,V> p = root;;) {
// GOTO1
//两值比较大小，判断插入方向。
int dir, ph; // dir 标识方向（左右）、ph标识当前树节点的hash值
K pk = p.key; // 当前树节点的key
if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
dir = -1; // 标识当前链表节点会放到当前树节点的左侧
else if (ph < h)
dir = 1; // 右侧
/*
* 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较
* 如果当前链表节点的key实现了comparable接口，并且当前树节点和
链表节点是相同Class的实例，那么通过comparable的方式再比较两者。
* 如果还是相等，最后再通过tieBreakOrder比较一次
*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
/*
* 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧位置，继续遍历找位置。
* 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧位置，继
续遍历找位置
*/
//如果左边或者右边不为空的话，循环下一个节点继续找寻插入点
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//获取到插入点，插入数据
x.parent = xp;
if (dir <= 0)
xp.left = x; //插入到左边
else
xp.right = x;//插入到右边
//插入后通过红黑树原理，平衡当前树，
root = balanceInsertion(root, x);
break;
}
}
}
}
// 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
// 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
moveRootToFront(tab, root); // 单独解析
}
当前过程，首先，对双向链表进行循环操作，如果root没有把当前节点设置为root节点，如果root节点存在，从root节点开始对比，当前值需要插入到左边，还
是右边，找到当前值的插入点，插入当前值，对当前值进行红黑树平衡操作
/**
* 红黑树插入节点后，需要重新平衡
* root 当前根节点
* x 新插入的节点
* 返回重新平衡后的根节点
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; // 新插入的节点标为红色
/*
* 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
* xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
*/
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 父节点不为空
// 如果父节点为黑色,不进行平衡操作，直接平衡。
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
// 如果父节点是爷爷节点的左孩子
if ((xppr = xpp.right) != null && xppr.red) {
// 如果右叔叔不为空 并且 为红色
//为红黑树的叔红现象，进行变色处理
xppr.red = false; // 右叔叔置为黑色
xp.red = false; // 父节点置为黑色
xpp.red = true; // 爷爷节点置为红色
x = xpp;
// 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点
}
else {
// 如果右叔叔为空 或者 为黑色
// 如果当前节点是父节点的右孩子，左旋后变成，左边节点,进行红黑树的变色，右旋处理
if (x == xp.right) {
root = rotateLeft(root, x = xp); // 父节点左旋
xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
}
if (xp != null) { // 如果父节点不为空
xp.red = false; // 父节点 置为黑色
if (xpp != null) { // 爷爷节点不为空
xpp.red = true; // 爷爷节点置为 红色
root = rotateRight(root, xpp); //爷爷节点右旋
}
}
}
}
else
{ // 如果父节点是爷爷节点的右孩子
if (xppl != null && xppl.red) {
// 如果左叔叔是红色
xppl.red = false; // 左叔叔置为 黑色
xp.red = false; // 父节点置为黑色
xpp.red = true; // 爷爷置为红色
x = xpp;
// 运行到这里之后，就又会进行下一轮的循环了，将爷爷节点当做处理的起始节点
}
else { // 如果左叔叔为空或者是黑色
if (x == xp.left) { // 如果当前节点是个左孩子
root = rotateRight(root, x = xp); // 针对父节点做右旋
xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
}
if (xp != null) { // 如果父节点不为空
xp.red = false; // 父节点置为黑色
if (xpp != null) { //如果爷爷节点不为空
xpp.red = true; // 爷爷节点置为红色
root = rotateLeft(root, xpp); // 针对爷爷节点做左旋
}
}
}
}
}
}
流程:
- 当节点为root节点的话，修改为黑色，直接平衡不需要操作。
- 当节点的父亲节点为黑色的时候，直接平衡不需要操作。
- 当父节节点(红色)为左节点的时候，叔叔节点为红色，父节点，和叔叔节点变为黑色，父节点的父亲节点点变为红色，已当前祖父节点为当前节点进行第二次循环判断。
- 当父亲节点为左节点，叔叔节点为黑色或者不存在的时候，如果当前节点为父亲节点的右孩子，进行以父节点进行左旋转，当前节点变为父亲节点，父亲节点变为当前节点，把父亲节点变为黑色，父节点的父亲节点(祖父节点变为红色)，以祖父节点进行右旋，得到平衡。
5.当父亲节点为右节点情况与左节点相反。
/**
* 节点左旋
* root 根节点
* p 要左旋的节点
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) { // 要左旋的节点以及要左旋的节点的右孩子不为空
if ((rl = p.right = r.left) != null) // 要左旋的节点的右孩子的左节点 赋给 要左旋的节点的右孩子 节点为：rl
rl.parent = p; // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
// 将要左旋的节点的右孩子的父节点 指向 要左旋的节点的父节点，相当于右孩子提升了一层，
// 此时如果父节点为空， 说明r 已经是顶层节点了，应该作为root 并且标为黑色
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p) // 如果父节点不为空 并且 要左旋的节点是个左孩子
pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
else // 要左旋的节点是个右孩子
pp.right = r;
r.left = p; // 要左旋的节点 作为 他的右孩子的左节点
p.parent = r; // 要左旋的节点的右孩子 作为 他的父节点
}
return root; // 返回根节点
}
/**
* 节点右旋
* root 根节点
* p 要右旋的节点
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) { // 要右旋的节点不为空以及要右旋的节点的左孩子不为空
if ((lr = p.left = l.right) != null) // 要右旋的节点的左孩子的右节点 赋给 要右旋节点的左孩子 节点为：lr
lr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子，孩子还没有答应，这一步孩子也认了爹】
// 将要右旋的节点的左孩子的父节点 指向 要右旋的节点的父节点，相当于左孩子提升了一层，
// 此时如果父节点为空， 说明l 已经是顶层节点了，应该作为root 并且标为黑色
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子
pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹，爹还没有答应，这一步爹也认了孩子】
else // 要右旋的节点是个左孩子
pp.left = l; // 同上
l.right = p; // 要右旋的节点 作为 他左孩子的右节点
p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子
}
return root;
}
左旋，右旋方法，可以看上一篇红黑树分析，理解原理，当前方法理解与源码关联不大，不做解释。[红黑树原理分析](数据结构红黑树添加、修改原理分析 - 简书 (jianshu.com)
)）
//进行双向链表的调整 ，经过左旋，或者右旋操作后，双向链表的头节点可能发生了变化。需要把根节点放到链表头节点
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//拿到tab的数组下标
int index = (n - 1) & root.hash;
//保存原始的双向链表
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 头节点是否发生了改变
if (root != first) {
Node<K,V> rn; //root的下一个元素，为了后续的双向链表的指向做工作
tab[index] = root; //将树结构覆盖原来的值
TreeNode<K,V> rp = root.prev; // root的前继 为了root断开链表进行操作
if ((rn = root.next) != null) //如果root后继不为空,说明root 节点处于中间 需要对root进行断开链表操作
((TreeNode<K,V>)rn).prev = rp; //将root的后继指向root的前继
if (rp != null) //rp！=null 说明root有前继
rp.next = rn; //root前继的后继指向root的后继 这样root就移除了双链表。相当于从链表中删除了root节点
if (first != null) //原来的双向链表不为空 进行头插法插入root
first.prev = root;
root.next = first;
root.prev = null; //前继置为空 完成头插法插入，root成为链表头节点
}
assert checkInvariants(root);
}
}
当前方法：如果当前的root不等于以前放置在数组中的双向链表的根节点的时候，在双向链表中删除root;把root的后继，与root的前驱进行关联，在使用头插法，把root插入的以前first的前面，最后把root放入当前的数组的位置中。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
// 记录Map当前的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 记录Map允许存储的元素数量，即阈值（容量*负载因子）
int oldThr = threshold;
// 声明两个变量，用来记录新的容量和阈值
int newCap, newThr = 0;
// 若当前容量不为0，表示存储数据的数组已经被初始化过
if (oldCap > 0) {
// 判断当前容量是否超过了允许的最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 若超过最大容量，表示无法再进行扩容
// 则更新当前的阈值为int的最大值，并返回旧数组
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
}
// 若不满足上面的oldCap > 0，表示数组还未初始化，
// 若当前阈值不为0，就将数组的新容量记录为当前的阈值；
// 为什么这里的oldThr在未初始化数组的时候就有值呢？
// 这是因为HashMap有两个带参构造器，可以指定初始容量，
// 若你调用了这两个可以指定初始容量的构造器，
// 这两个构造器就会将阈值记录为第一个大于等于你指定容量，且满足2^n的数（可以看看这两个构造器）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 若上面的条件都不满足，表示你是调用默认构造器创建的HashMap，且还没有初始化table数组
else { // zero initial threshold signifies using defaults
// 则将新容量更新为默认初始容量（10）
// 阈值即为（容量*负载因子）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 经过上面的步骤后，newCap一定有值，但是若运行的是上面的第二个分支时，newThr还是0
// 所以若当前newThr还是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;
// 创建一个记录新数组用来存HashMap中的元素
// 若数组不是第一次初始化，则这里就是创建了一个两倍大小的新数组
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
// 将新数组的引用赋值给成员变量table
table = newTab;
// 开始将原来的数据加入到新数组中
if (oldTab != null) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
HashMap.Node<K,V> e;
// 若原数组的j位置有节点存在，才进一步操作
if ((e = oldTab[j]) != null) {
// 清除旧数组对节点的引用
oldTab[j] = null;
// 若table数组的j位置只有一个节点，则直接将这个节点放入新数组
// 使用 & 替代 % 计算出余数，即下标
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 若第一个节点是一个数节点，表示原数组这个位置的链表已经被转为了红黑树
// 则调用红黑树的方法将节点加入到新数组中
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 上面两种情况都不满足，表示这个位置是一条不止一个节点的链表
// 以下操作相对复杂，所以单独拿出来讲解
else { // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
resize()方法总结下来就是，第一部分进行newCap新容量的计算，进行新的newThr扩容阈值的计算;下来对以前数组中的树进行差分,如果为一个值，直接放入新的列表，如果为红黑树，对红黑树进行拆分，进行插入操作，如果为单项列表，则对单项列表进行拆分，因为数组的长度发生了变化，hash&(newCap-1)的位置也会发生相应的变化，所以需要进行差分处理。
关于resize()方法链表拆分问题分析
resize方法中的最后一部分，是将原数组中的一条链表的节点，放入到扩容后的新数组中，而这一部分相对来说比较难理解。首先我们得知道是怎么实现的，然后再来逐句分析代码。首先，我们得知道一个结论，那就是：原数组中一条链表上的所有节点，若将它们加入到扩容后的新数组中，它们最多将会分布在新数组中的两条链表上。
链表拆分图
那这个结论是怎么来的呢？我们先说左边第一个节点，它的hash值是2，转换成二进制就是0010，而容量为2^3 == 8，通过num % 2^n == num & (2^n - 1)这个公式，我们知道2与容量8的余数是2 & （8 - 1） == 0010 & 0111 == 0010。任何数与0111做与运算（&），实际上就是取这个数二进制的最后三位。而扩容之后，容量变成了2^4 == 16，这时候，取模就是与16-1 == 15做与运算了，而15的二进制是1111，我们发现，1111与之前的0111唯一的区别就是第四位也变成了1（以下说的第几位都是从右往左）。而2 & 15 == 0010 & 1111 == 0010，和0010 & 0111 结果是一样的。为什么？因为0010的第四位是0，所以从0111变成1111，并不会对计算结果造成影响，因为0和任何数做与运算，结果都是0。所以扩容后，2这个节点，还是放在数字下标为2的位置。我们在来看看剩下的三个数：
hash值为10，转换成二进制1010，1010的第四位为1，所以 1010 & 0111 != 1010 & 1111
hash值为18，转换成二进制10010，10010的第四位为0，所以 10010 & 0111 == 10010 & 1111
hash值为26，转换成二进制11010，11010的第四位为1，所以 11010 & 0111 != 11010 & 1111
所以扩容后，余数是否发生改变，实际上只取决于多出来的那一位而已，那一位只有两种结果：0或者1，所以这些节点的新下标最终也只有两种结果。而多出来的那一位是哪一位呢？8转换成二进制是1000，而从8扩容到16，取余的数从0111变成了1111，多出的这个1刚好在第四位，也就是1000中，唯一一个1所在的位置；16的二进制是10000，扩容成32后，取余的数从1111变成11111，在第五位多出了一个1，正好是10000的1所在的位置。所以我们可以知道，扩容后，节点的下标是否需要发生改变，取决于旧容量的二进制中，1那一位。所以容量为8，扩容后，若节点的二进制hash值的第四位为0，则节点在新数组中的下标不变；若为1，节点的下标改变，而且改变的大小正好是+8，因为多出了最高位的1，例如1010 & 0111 = 0010，而1010 & 1111 = 1010，结果相差1000，也就是旧容量的大小8；所以若下标要发生改变，改变的大小将正好是旧数组的容量。
我们如何判断hash值多出来的那一位是0还是1呢，很简单，只要用hash值与旧容量做与运算，结果不为0表示多出的这一位是1，否则就是0。比如说，容量为8（二进制1000），扩容后多出来的是第四位，于是让hash值与1000做与运算，若hash值的第四位是1，与1000做与运算后结果就是1000，若第四位是0，与1000做与运算后就是0。好，下面我们来看看代码吧：
// 创建两个头尾节点，表示两条链表
// 因为旧链表上的元素放入新数组中，最多将变成两条链表
// 一条下标不变的链表，一条下标+oldCap
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;
// 循环遍历原链表上的每一个节点
do {
// 记录当前节点的下一个节点
next = e.next;
// 注意：e.hash & oldCap这一步就是前面说的判断多出的这一位是否为1
// 若与原容量做与运算，结果为0，表示将这个节点放入到新数组中，下标不变
if ((e.hash & oldCap) == 0) {
// 若这是不变链表的第一个节点，用loHead记录
if (loTail == null)
loHead = e;
// 否则，将它加入下标不变链表的尾部
else
loTail.next = e;
// 更新尾部指针指向新加入的节点
loTail = e;
}
// 若与原容量做与运算，结果为1，表示将这个节点放入到新数组中，下标将改变
else {
// 若这是改变下标链表的第一个节点，用hiHead记录
if (hiTail == null)
hiHead = e;
// 否则，将它加入改变下标链表的尾部
else
hiTail.next = e;
// 更新尾部指针指向新加入的节点
hiTail = e;
}
} while ((e = next) != null);
// 所有节点遍历完后，判断下标不变的链表是否有节点在其中
if (loTail != null) {
// 将这条链表的最后一个节点的next指向null
loTail.next = null;
// 同时将其放入新数组的相同位置
newTab[j] = loHead;
}
// 另一条链表与上同理
if (hiTail != null) {
hiTail.next = null;
// 这条链表放入的位置要在原来的基础上加上oldCap
newTab[j + oldCap] = hiHead;
}
至此hashmap的所有关键代码分析完毕，其余代码大家可自行分析
喜欢的话给个赞呗
网友评论