HashMap在jdk1.8是数组+链表+红黑树实现，当链表的节点树大于等于8的时候，会把链表转成红黑树，
当触发扩容的时候，会把树变成2棵树,如果树的节点不够UNTREEIFY_THRESHOLD = 6，就会退化成链表
允许存放null值，也可以插入null值
扩容机制是
默认增长的长度是 旧长度 << 1 也就是是原来的2倍
默认长度是 1 << 4
默认的load_factor = 0.75f
阀值 threshold = 长度 * load_factor 下一次扩容的阀值
是先插入在扩容，还是扩容再插入？
在第一次插入的时候进行初始化，会执行初始化数组，和分配新的threshold，之后是插入再判断 size > threshold
put(k key,V value) 插入元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
//h >>> 16 获取 key.hashCode()高位16位
// key.hashCode() 异或高位16位，让hash分布均衡
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//这里的主要逻辑
//先判断是否是第一次进这个方法，判断条件(tab = table) == null || (n = tab.length)
//如果是 则需要初始化table，执行resize()进行初始化
//如果不是第一次进，那根据(n - 1) & hash公式，计算出需要插入到table数组的哪一个位置
//如果计算出来的位置是个空位置，则直接tab[i] = newNode(hash, key, value, null)
//如果计算出来的位置不是一个空值（这里用p来表示这个不是空值的元素）
//如果p元素的hash值和key值都和插入的元素一样，则说明插入的元素已经存在，可能只是值不一样
//如果p元素的hash值和key值和插入的元素不一样，则需要判断这个p是否是树元素
//如果p是个树元素，则((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)，进行红黑树插入
//如果p元素的hash值和key值和插入的元素不一样，p又不是一个树元素，则只能是链表元素了
//如果p元素是链表元素
//那就循环p对应的链表，直到找到一个空的位置
//如果循环的次数，已经大于等于7，刚好找到位置，
//也就是准备插入第8个元素的时候，会先把需要插入的元素插入链表 p.next = newNode(hash, key, value, null)
//然后进行链表转换成红黑树 treeifyBin(tab, hash); 结束循环
//如果循坏的过程中找到一个节点的ash值和key值和插入的元素一样
//则直接结束循坏，说明链表里已经存在需要插入的元素，只是值可能不一样
//最后在上面的操作后，是找到的元素，就会根据条件 if (!onlyIfAbsent || oldValue == null)
//put的时候 onlyIfAbsent=false //如果为true，则不更改现有值
// 把需要插入的元素的值覆盖找到元素的值即可
//忘了，size++ modCount++ 当然还需要判断是否需要扩容 if (++size > threshold) resize（）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; //hashmap存放元素的array
Node<K,V> p; //指的是通过key的hashcode计算出来的tab数组下标对于的node
int n;//这里指的是tab的长度
int i;
if ((tab = table) == null || (n = tab.length) == 0) //如果是第一次put,会进行初始化
n = (tab = resize()).length; //tab = resize()进行初始化
//获取这个key的可以保存的数组下标,如果这个这个位置为空，说明没人占
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//直接创建newNode，放进tab[i]
else { //获取的这个位置有人占
Node<K,V> e;
K k; //插的key
//如果占位置的节点的key和插入的key的一样，后面就只需要改这个节点的值就行
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //已存在，后面就只需要改这个节点的值就行
//判断这个占位置的节点是否是树节点（红黑树）
else if (p instanceof TreeNode)
//那就是红黑树的插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//那占位置的节点一顶是链表节点
else {
//来一个死循环
for (int binCount = 0; ; ++binCount) {
//如果占位置的节点的下一个位置为空
//记得e = p.next，已经被赋值
if ((e = p.next) == null) { //p的下一个节点是个空节点，那就直接插入
//直接把数据放进这个空的位置，也即是p.next，后插法
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD = 8
//binCount是0开始的 所以TREEIFY_THRESHOLD - 1
//也就是插入第8个的时候
//当链表的元素大于等于TREEIFY_THRESHOLD，treeifyBin(tab, hash)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//满足树形化容器要求最小值64
treeifyBin(tab, hash);
break;//推出循环
}
//如果在链表里面找到，则只需要改值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //把游标指向p的下一个元素
}
}
//说明存在旧值的key与要插入的key"相等"
if (e != null) { // existing mapping for key
V oldValue = e.value;
//是允许覆盖值，oldValue==null，设置值
//因为e可能已存在的，所以设置旧值即可
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//没有实现
return oldValue;
}
}
++modCount;//修改次数+1
if (++size > threshold) //判断是否需要扩容
resize();//扩容
afterNodeInsertion(evict);//没有实现
return null;
}
//put的时候 root.putTreeVal(this, tab, hash, key, value)
//这里意思是
//从根节点开始循环
//根据节点的hash值大小，判断需要插入的位置，
//如果hash值一样，则判断是否key一样，key一样直接返回(插入的值已经存在)
///如果hash值一样,key不一样，根据key的comparableTo比较大小，
//没有实现comparable ，如果是第一次进来，会遍历整一个树，判断需要插入的节点是否已存在
//最后使用System.identityHashCode(a)进行比较，
//System.identityHashCode(a) 无论给定对象的类是否覆盖hashCode()，
//返回给定对象与默认方法hashCode()返回的相同哈希代码。空引用的哈希码为零
//最后根据比较的结果dir来决定，当dir<=0 p = p.left 否则p = p.left
//如果p==null 则说明有位置插入，这里就是进行x = map.newTreeNode(h, k, v, xpn),然后就是关系绑定
// TreeNode<K,V> xp = p; Node<K,V> xpn = xp.next x = map.newTreeNode(h, k, v, xpn)
//如此绑定关系
//先确定树的关系 dir<=0? xp.left = x: xp.right = x
//后确定双向链表的关系 xp->x->xpn xp<-x<-xpn
//如果p！=null 说明没有插入的位置，继续循坏查找
//返回值插入返回null 找到返回找到的节点
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this; //获取根元素
for (TreeNode<K,V> p = root;;) {
int dir;
int ph; // p.hash
int K;
int pk;//p,key
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;//put进来的元素，已经在树里面找到，直接返回
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//获取不到k的比较器
if (!searched) { //是否已搜索
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q; //从p节点遍历完左右节点，发现了
}
dir = tieBreakOrder(k, pk); //获取内存地址比较返回的值
}
TreeNode<K,V> xp = p;
//p = p.left or p.right
//根据dir，需要插入到左边还是右边，p的左边和右边是否有位置，没有继续循环
if ((p = (dir <= 0) ? p.left : p.right) == null) { //新的节点，可以插入的位置
// 上面 TreeNode<K,V> xp = p; p = p.left or p.right
//xpn = xp.next
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x; //小于在左
else
xp.right = x;//大于在右
//修复关系 xp->x->xpn xp<-x<-xpn
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//修复树 balanceInsertion
//调整根元素，如果根元素改变，数组保存新的根元素moveRootToFront
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
//寻找策略
//先根据节点的hash值进行比较
//如果hash值一样，比较key值是否相等
//如果hash值一样，key值不想等，那就判断是否是单子节点，p = 单子节点，继续寻找
//如果hash值一样，key值不想等，两个子节点，那就根据两个子节点的key进行比较，要求key实现了comparable
//如果hash值一样，key值不想等，两个子节点，key没有实现comparable，那就先递归查找右边子节点树，找不到则寻找左节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) //大于找左边
p = pl;
else if (ph < h) //小于找右边
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; //找到就返回
//p.hash == h 是等于的 ,那就判断是否是单子节点，继续循环
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
//p.hash == h 是等于的 两个子节点
//如果key实现了comparable接口或者是string ,Integer等实现了comparable的自然顺序的key，
//则按照comparable比较大小进行左右的选择
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//p.hash == h 是等于的 两个子节点
//key没有实现comparable接口或者不是是string ,Integer等实现了comparable的自然顺序的key
//递归查找右边
else if ((q = pr.find(h, k, kc)) != null)
return q;
else //如果右边找不到，只能找左边，继续找
p = pl; //左边
} while (p != null);
return null;
}
//把链表变成红黑树
//tab =hashmap存放元素的array
//hash =key计算出来的hash
//主要逻辑
//tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY
//先判断tab数组有没有初始化或者长度64不够64，没满足条件则初始化或者扩容 resize()
//根据index = (n - 1) & hash 计算出hash 存放到tab数组的下标，然后取出 e = tab[index]
//如果e不等于空 则遍历e对应的链表
//遍历中把链表Node 变成 TreeNode TreeNode<K,V> p = replacementTreeNode(e, null)
//最后以链表的第一个元素调用 treeify(tab);
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n;//等于数组长度
int index; //hash 对于tab数组的下标
Node<K,V> e;//hash的头部节点
//tab 还没初始化，或者初始化了，但是长度不满足树形化容器要求最小值
//MIN_TREEIFY_CAPACITY = 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//扩容
//n = tab.length
//tab[index = (n - 1) & hash] 取出这个hash的头部节点
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null;//头节点
TreeNode<K,V> tl = null;//子节点
do {
//拷贝头部元素的属性，创建成TreeNode
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);//遍历链表
//头部元素设置为hd 不等于null==》 hd.treeify(tab);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
//创建
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
//tab =hashmap存放元素的array
//this = hd 头部元素,现在只是一个双向链表
//这里的逻辑是遍历链表
//如果没有根元素，那么设置根元素 root == null x.parent = null; x.red = false; root = x;
//如果存在根节点，那么就遍历树，从根元素开始
//先根据节点的hash值进行比较
//如果hash值一样，比较key值是否相等
///如果hash值一样,根据key的comparableTo比较大小，
//如果key没有没有实现comparable，最后使用System.identityHashCode()进行比较，
//System.identityHashCode(a) 无论给定对象的类是否覆盖hashCode()，
//返回给定对象与默认方法hashCode()返回的相同哈希代码。空引用的哈希码为零
//最后根据比较的值 绑定关系 dir <= 0 ? p.left : p.right
// TreeNode<K,V> xp = p; x.parent = xp; dir <= 0 ? xp.left = x ：xp.right = x;
//绑定关系后就需要保证红黑树没有违反规则，则调用balanceInsertion
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//x = hd
//next = x.next
//遍历的是列表
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
//左右节点都是null
x.left = x.right = null;
//如果不存在根节点
if (root == null) {
x.parent = null; //x的parent设置为空
x.red = false; //红黑树的根节点是黑色。
root = x; //设置x 为根节点
}
else { //如果存在根节点，也即是不是根节点怎么放
K k = x.key; //取出需要处理的节点x的key
int h = x.hash;///取出需要处理的节点x的hash
Class<?> kc = null; //
//死循环
//TreeNode<K,V> p = root
//遍历的是树呢
for (TreeNode<K,V> p = root;;) {
int dir; //记录p节点和x节点的hash值比较状态 大于-1 小于1
int ph; //节点hsah值
K pk = p.key; //取出节点的key
if ((ph = p.hash) > h) //p节点的hash值> x节点的hash值
dir = -1; //大于设置状态-1
else if (ph < h) //p节点的hash值 < x节点的hash值
dir = 1; //小于设置状态-1
//这里就是等于的意思了
//kc = comparableClassFor(k) ==>x的class
//dir = compareComparables(kc, k, pk) ==>x,p的比较值
//kc = null,
//comparableClassFor(k),获取x的key的类型，
//如果是实现了comparable的就返回x的key的类型，否则返回null，见下面函数分析
//compareComparables,通过 comparable 获取比较的值，没有实现comparable，
//或者p的key的class和x的class 不一样，返回0，见下面函数分析
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//使用默认的hashcode进行相减,见下面函数分析
dir = tieBreakOrder(k, pk);
//xp = 节点p
TreeNode<K,V> xp = p;
//p > x = -1
//p = 大于 p.left 小于p.right
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//记得xp等于之前的p 进来if p= p.left or p.right 设置x的爸爸是xp
x.parent = xp;
if (dir <= 0) // p > x = -1
xp.left = x; //大于是左边
else
xp.right = x;//小于是右边
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
//如果x的Class是" Class C implements Comparable "的形式，则返回x的Class，否则为null。
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) { //是否实现了Comparable
Class<?> c; //x的class 对象
Type[] ts, as;
Type t;
ParameterizedType p;
//如果是字符串
if ((c = x.getClass()) == String.class) // bypass checks
return c; //返回字符串的class
// c.getGenericInterfaces()对象表示的类或接口直接实现的接口的{@code Type}
//主要是判断c实现的Comparable的泛型类型是否是c的类
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
//kc =null
//k x的key
//x p的key
//比较k x key的值通过 Comparable的compareTo
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
//a 指的是 x的key
//b 指的是 p的key
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
//通过x的key的class的类名，string.compareTo(p的key的class的类名)
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
//调用System.identityHashCode(a)
//，System.identityHashCode方法是java根据对象在内存中的地址算出来的一个数值，
//不同的地址算出来的结果是不一样的，跟默认的方法 hashCode() 返回的代码
//根据上面定义的 p>x = -1
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
//插入平衡
//root 数节点
//x x节点
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; //插入节点设置为红色，这样不会违法红黑树的，每条路径的黑色节点数都是一样的
//xp x.parent
//xpp xp.parent
//xppl xpp.left
// xppr xpp.right
//从x节点，不断的循环到root接点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//x是根节点
if ((xp = x.parent) == null) { //说明是根节点
x.red = false; //红黑树根节点是黑色。
return x; //直接返回根节点
}
//
//x的父节点是黑色 xpp = xp的父节点（x的爷爷是null）
//或者xp就是根节点，或者xp的颜色是黑色，就直接返回来
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//x的父亲 == x的爷爷的左儿子
if (xp == (xppl = xpp.left)) {
//x的爷爷有右儿子，也即是x的叔叔节点，x的叔叔节点是红色
//红黑树插入情景1 x的父节点p是个红色，x的叔叔节点sib是红色
//处理是设置p,sib的颜色为黑色，x的爷爷节点Y设置为黑色，把当前的节点X = 爷爷节点Y 继续循环
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;//把叔叔节点改成黑色
xp.red = false; //父节点改成黑色
xpp.red = true; //爷爷节点改成和红色
x = xpp; //把x变成爷爷
}
//没有叔叔节点，或者叔叔节点是黑色
else {
//红黑树插入情景2 如果x是右节点，x的父节点是红色，叔叔节点是黑色，或者没有叔叔节点
//处理是 把x= x. parent 然后以x. parent进行左旋
if (x == xp.right) {
//左旋，看下面分析了
//x = xp 把x变成x的父亲
//左旋之后xp就变成了x的左节点了
root = rotateLeft(root, x = xp);
//之前x = xp 把x变成x的父亲
//(xp = x.parent) == null 相等说明 x（一开始的x） 的父亲就是根节点
//xpp = xp.parent xpp = x（一开始的x）的祖父
//xp = x.parent xp不可能等于null，他等于之前x
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//情景3 如果x是左节点，x的父节点是红色，x的叔叔节点是黑色，或者没有叔叔节点
//处理是 让x的父节点设置为黑色，x的爷爷节点设置为红色，右旋
//，xp也不是null 是红色
if (xp != null) {
xp.red = false; //变成黑色
if (xpp != null) { //祖父也不是空的
xpp.red = true; //变成红色
//以祖父进行右旋
root = rotateRight(root, xpp);
}
}
}
}
//x的父亲 == x的爷爷的右儿子，镜像的
else {
//x爷爷有左儿子（叔叔节点）并且它还是红色
if (xppl != null && xppl.red) {
xppl.red = false; //左叔叔变成黑色
xp.red = false;//爸爸变成黑色
xpp.red = true;//父亲红色
x = xpp;//把x 变成爷爷节点
}
//x爷爷没有左儿子（叔叔节点）或者 左叔叔节点是黑色
else {
//如果x是父节点的左节点，三点一条线，需要平衡
if (x == xp.left) {
//以父节点右旋一下
//x = xp
root = rotateRight(root, x = xp);
//(xp = x.parent) == null 相等说明 x（一开始的x） 的父亲就是根节点
//xpp = xp.parent xpp = x（一开始的x）的祖父
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//x（一开始的x）的爷爷不是空的
if (xp != null) {
xp.red = false;///x（一开始的x）的爷爷设置为黑色
if (xpp != null) { //x（一开始的x）的祖父不等于null
xpp.red = true; //x（一开始的x）的祖父设置为红色
//左旋
root = rotateLeft(root, xpp);
}
}
}
}
}
}
//左旋
//根节点
//p节点
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r; //p节点的右节点 r = p.right
TreeNode<K,V> pp;
TreeNode<K,V> rl;
//r = p.right
if (p != null && (r = p.right) != null) {
//rl = p.right = r.left
//p的左孙子也是p的右儿子
//r1 等于 p的左孙子
if ((rl = p.right = r.left) != null)
rl.parent = p; //p的左孙子的爸爸变成p
//p的父亲也是r的父亲
//pp = p的父亲
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;//如果pp==null,那就说明r就是root了，root节点为黑色
else if (pp.left == p) //把r变成p的左儿子
pp.left = r;
else
pp.right = r; ////把r变成p的右儿子
r.left = p;
p.parent = r;
}
return root;
}
//右旋，看下面的图理解
//主要逻辑就是 l的右节点lr成为p的左节点 l成为p的父节点， p成为l的右节点
//先判断p节点 和 p节点的左节点l不能是空的 p != null && (l = p.left) != null
//处理p跟lr的关系
//lr = p.left = l.right； lr.parent = p; l的右节点成为的做节点
//处理p.parent跟l的关系
//pp = l.parent = p.parent == null 说明 l就是根节点 所以设置为黑色
//pp.right = l; pp.right = l;
//处理l跟p的关系
// 主要逻辑 l.right = p; p.parent = l; p成为l的右子节点
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//l = p.left
if (p != null && (l = p.left) != null) {
//(lr = p.left = l.right
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
//tab 数组
//这里的逻辑是
//如果 root != null && tab != null && (n = tab.length) > 0
//根据 (n - 1) & root.hash 计算出存放这个hash的tab的下标，根据下标取出这个元素first
//如果元素first 不等于传进来的root，那就说明树的根节点因为删除和调整已经发生改变，需要修复
//主要是修复关系
//举例子 1->2->3->4->5 原来tab[i] = 1 传进来的root = 3
//那么先让tab[i] = 3
//然后调整链表的位置 需要调整的位置 2->3->4 记得是双向的 2<-3<-4 变成 1->2->4->5 1<-2<-4<-5
//最后 3->1->2->4->5 记得是双向的3<-1<-2<-4<-5
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;//等于长度
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;//计算出头节点的下标
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //取出tab中的根元素
if (root != first) {//判断根元素有没有改变
Node<K,V> rn;
tab[index] = root;//设置新的根节点
TreeNode<K,V> rp = root.prev; //根节点的上一个节点，链表
//rn = root.next
if ((rn = root.next) != null)//说明新的根节点的下一个节点不是null
((TreeNode<K,V>)rn).prev = rp; //rp ->rn rp<-rn
if (rp != null)
rp.next = rn; //rp ->rn
if (first != null)//
first.prev = root; //first的上一个是root root<-first
root.next = first; //下一个节点是first root->first
root.prev = null; //根节点的上一个节点肯定是null的
}
assert checkInvariants(root);//断然检测
}
}
//检测树是否正确
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red) //三个红色
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
get(key) 根据key 获取值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first;
Node<K,V> e;
int n;
K k;
//first = tab[(n - 1) & hash] 找到根节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果查找的就是根节点，那就是first，返回first
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;
}
//根据hash和key获取树节点
//逻辑是parent== null 就是根 this 不是 root()
final TreeNode<K,V> getTreeNode(int h, Object k) {
//parent是空 root（） 否则this
return ((parent != null) ? root() : this).find(h, k, null);
}
//this 就是 调getTreeNode的节点
//逻辑就是一直找p.parent 知道p.parent== null
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
//p = r.parent
if ((p = r.parent) == null)
return r; //r就是根节点
r = p; //继续找
}
}
//寻找策略
//先根据节点的hash值进行比较
//如果hash值一样，比较key值是否相等
//如果hash值一样，key值不想等，那就判断是否是单子节点，p = 单子节点，继续寻找
//如果hash值一样，key值不想等，两个子节点，那就根据两个子节点的key进行比较，要求key实现了comparable
//如果hash值一样，key值不想等，两个子节点，key没有实现comparable，那就先递归查找右边子节点树，找不到则寻找左节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) //大于找左边
p = pl;
else if (ph < h) //小于找右边
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; //找到就返回
//p.hash == h 是等于的 ,那就判断是否是单子节点，继续循环
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
//p.hash == h 是等于的 两个子节点
//如果key实现了comparable接口或者是string ,Integer等实现了comparable的自然顺序的key，
//则按照comparable比较大小进行左右的选择
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//p.hash == h 是等于的 两个子节点
//key没有实现comparable接口或者不是是string ,Integer等实现了comparable的自然顺序的key
//递归查找右边
else if ((q = pr.find(h, k, kc)) != null)
return q;
else //如果右边找不到，只能找左边，继续找
p = pl; //左边
} while (p != null);
return null;
}
remove(key) 根据key 删除值
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//删除
//hash 需要删除的hash
//需要删除key
//value //matchValue 为ture=时使用
//matchValue 如果为true，只在值相等时删除 false
//movable 如果为false，则在移除时不移动其他节点 true
//这个方法逻辑是
//(tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null
//上面的条件都要成立才可以玩
//需要删除的元素的hash 和key 是否和 p = tab[index = (n - 1) & hash] 是一样的？
//如果是 那p就是需要删除的元素，node = p;
//如果不是，继续判断 p 是否是树元素
//如果p 是树元素 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 根据红黑树去找
//如果p 不是树元素，那就是链表元素了，循坏变量p对应的链表，找出hash 和key和需要删除的元素一样的节点 node = e;
//如果 node != null && !matchValue // remove的时候matchValue 是false
//如果成立 先判断找到的节点node是否是树节点 ，如果是 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable)
//如果找到的节点node是根节点 tab[index] = node.next;//链表节点没有设置 prev ,所以不设置
//如果找到的节点node既不是树节点，也不是根节点，那就是链表节点 p.next = node.next; //链表节点没有设置 prev ,所以不设置
//
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab;
Node<K,V> p;
int n;
int index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;//根节点
//e = p.next
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//是树节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//链表类型
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; //找到
break;//退出
}
p = e;//p 等于e的上一个元素
} while ((e = e.next) != null);
}
}
//如果为true，只在值相等时删除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
//红黑树删除节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //根节点
tab[index] = node.next; 设置根节点为node的下一个
else
p.next = node.next; //p->node的下一个元素
++modCount;//修改次数+1
--size;//元素-1
afterNodeRemoval(node);//没有实现
return node; //返回需要删除的节点
}
}
return null;
}
//根据hash和key获取树节点
//逻辑是parent== null 就是根 this 不是 root()
final TreeNode<K,V> getTreeNode(int h, Object k) {
//parent是空 root（） 否则this
return ((parent != null) ? root() : this).find(h, k, null);
}
//this 就是 调getTreeNode的节点
//逻辑就是一直找p.parent 知道p.parent== null
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
//p = r.parent
if ((p = r.parent) == null)
return r; //r就是根节点
r = p; //继续找
}
}
//寻找策略
//先根据节点的hash值进行比较
//如果hash值一样，比较key值是否相等
//如果hash值一样，key值不想等，那就判断是否是单子节点，p = 单子节点，继续寻找
//如果hash值一样，key值不想等，两个子节点，那就根据两个子节点的key进行比较，要求key实现了comparable
//如果hash值一样，key值不想等，两个子节点，key没有实现comparable，那就先递归查找右边子节点树，找不到则寻找左节点
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) //大于找左边
p = pl;
else if (ph < h) //小于找右边
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; //找到就返回
//p.hash == h 是等于的 ,那就判断是否是单子节点，继续循环
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
//p.hash == h 是等于的 两个子节点
//如果key实现了comparable接口或者是string ,Integer等实现了comparable的自然顺序的key，
//则按照comparable比较大小进行左右的选择
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//p.hash == h 是等于的 两个子节点
//key没有实现comparable接口或者不是是string ,Integer等实现了comparable的自然顺序的key
//递归查找右边
else if ((q = pr.find(h, k, kc)) != null)
return q;
else //如果右边找不到，只能找左边，继续找
p = pl; //左边
} while (p != null);
return null;
}
//movable 如果为false，则在移除时不移动其他节点
//这里的逻辑是
//先判断 tab == null || (n = tab.length) == 0 //tab 不是空的，或者长度大于0
//设置关系 pred->node->succ 改成 pred->succ pred<-succ 链表阶段的删除操作 next，prev
//没有根节点，或者根节点右节点是null,左节点是null 左节点的左节点是null
//直接退化成为链表 first.untreeify(map)
//如果删除节点有两个节点
//第一步，首先判断这个节点是否有右节点
//因为能进这个if肯定是有右节点的
//循环它的右子节点的左节点，直到最后一个左节点就是这个节点的后继节点 while ((sl = s.left) != null)
//最后是调整关系，把p和s的位置调换，如果s 存在右节点那replacement = p的右节点sr，否则replacement=p
//单节点 replacement = pl; replacement = pr；
//没有节点 replacement = p;
//如果是有节点的 就要先p.left = p.right = p.parent = null; 再balanceDeletion
//没节点的balanceDeletion 再 p.parent = null; pp.left = null; pp.right = null;
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0) //tab 不是空的，或者长度大于0
return;
int index = (n - 1) & hash;//删除元素的hash
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//根节点
TreeNode<K,V> root = first;
TreeNode<K,V> rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, //删除节点的下一个
TreeNode<K,V> pred = prev;//删除节点的上一个
//-------------------------------链表阶段的删除操作--------------------------------
//设置关系 pred->node->succ 改成 pred->succ pred<-succ
if (pred == null)//没有上一个节点，那就是根节点
tab[index] = first = succ;//那就是根节点的下一个节点成为根节点
else
pred.next = succ; //删除节点的上一个的下一个节点=删除节点的下一个
if (succ != null) //删除节点的下一个不是空
succ.prev = pred; //删除节点的下一个的上一个元素为删除节点的上一个
//-------------------------------删除操作--------------------------------
//根元素是空直接返回
if (first == null)
return;
//如果root.parent不是空，那就找根元素
if (root.parent != null)
root = root.root();
//没有根节点，或者根节点右节点是null,左节点是null 左节点的左节点是null
//直接退化成为链表 first.untreeify(map)
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small //设置新的根节点
return;//返回
}
//
TreeNode<K,V> p = this; //需要删除的节点
TreeNode<K,V> pl = left;//需要删除的节点的左节点
TreeNode<K,V> pr = right;//需要删除的节点的右节点
TreeNode<K,V> replacement;//替换删除的元素
if (pl != null && pr != null) {
//存在两个子节点
//二叉树的后继节点的寻找方法
//第一步，首先判断这个节点是否有右节点
//情景1 ：存在右节点，那么它的后继节点就是它的右子树的最小值，
//循环它的右子节点的左节点，直到最后一个左节点就是这个节点的后继节点
//不存在右节点，那么就要根据这个节点和父节点的关系来确定了
//情景2 ：如果，这个节点是父节点的左子节点，那么这个节点的后继节点就是父节点
//情景3 ：如果，这个节点是父节点的右节点，那么就要向上循环这个节点的祖先节点，直到找到一个祖先节点是个左节点，
//那么这个左节点的父节点就是这个节点的后续节点
//这个if里面，只符合情景1
//第一步，首先判断这个节点是否有右节点
//因为能进这个if肯定是有右节点的
//循环它的右子节点的左节点，直到最后一个左节点就是这个节点的后继节点 while ((sl = s.left) != null)
//最后是调整关系，把p和s的位置调换，如果s 存在右节点那replacement = p的右节点sr，否则replacement=p
TreeNode<K,V> s = pr;
TreeNode<K,V> sl;
while ((sl = s.left) != null) //s =p的右边树节点，最小的那一个节点
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors //p和后续节点s交换颜色
TreeNode<K,V> sr = s.right; //后续节点的右节点
TreeNode<K,V> pp = p.parent; //p的父节点
if (s == pr) { // s 就是 p的右节点
//p.left = p.right = p.parent
p.parent = s; //p.parent = s
s.right = p; //s.right = p
}
else { //s 不是 p的右节点
//绑定p.parent = sp 也就是s的parent
TreeNode<K,V> sp = s.parent; //sp = 后续节点的父节点
if ((p.parent = sp) != null) { //p.parent = sp
if (s == sp.left) //左节点
sp.left = p;
else
sp.right = p; //右节点
}
//绑定s.right
if ((s.right = pr) != null)
pr.parent = s;
}
//这里绑定 p的left 和 p的left
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
//绑定s.left
if ((s.left = pl) != null)
pl.parent = s;
//这里绑定 s.parent 是 pp（p.parent）
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
//如果后续节点有一个右节点
if (sr != null)
replacement = sr; //replacement就是右节点
else
replacement = p; //replacement后续节点
}
//单节点，p的左节点不是空，则replacement就是左节点
else if (pl != null)
replacement = pl;
//单节点，p的右节点不是空，则replacement就是右节点
else if (pr != null)
replacement = pr;
//没有子节点，那replacement就是自己了
else
replacement = p;
if (replacement != p) { //不是没有子节点节点的
//replacement替换掉p
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement; //直接就是根节点
else if (p == pp.left) //p是左元素，则replacement也是左元素
pp.left = replacement;
else
pp.right = replacement; //p是右元素，则replacement也是右元素
//清除掉p //prev next 上面已经删掉
p.left = p.right = p.parent = null;
}
//如果 p.red是真的不需要调整，黑色才balanceDeletion(root, replacement)
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//没有子节点的需要清除关系
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent; //获取p的父节点
p.parent = null;//清空p的父节点引用
if (pp != null) { //不是存在父节点
if (p == pp.left) //p是左元素，则清空pp的左元素
pp.left = null;
else if (p == pp.right)//p是右元素，则清空pp的右元素
pp.right = null;
}
}
if (movable)//remove 传进来的是false //不执行
moveRootToFront(tab, r);
}
//由树变了链表
//遍历树，遍历过程中 TreeNode->Node Node<K,V> p = map.replacementNode(q, null);
//设置节点的next 返回根节点
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null); // TreeNode->Node
if (tl == null)
hd = p;
else
tl.next = p; //设置节点的next
tl = p;
}
return hd;// 返回根节点
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
//红黑树4个场景
//逻辑
//第一步，就是判断x是不是空，又或者是不是等于根节点 是直接返回
//判断x的父节点xp ==null ,是那说明，x就是根节点 设置x为黑色 返回x
//判断x是不是红色，是红色就会设置为黑色，直接返回根节点，
//为什么呢，因为红色设置为黑色不就是弥补p的黑色吗，所以直接返回
//下面的代码主要是红黑色的删除调整情况
//情景1： 如果x的兄弟节点sib是个红色节点，那么设置sib为黑色，x的父节点p 为红色，然后以p为中心进行左旋
//情景2： 如果x的兄弟节点sib 的两个左右子节点都是黑色，那么设置sib为红色，x = x.parent
//情景3： 如果x的兄弟节点的右节点是个黑色，x的兄弟节点的左节点是个红色，
//那么设置sib为红色，x的兄弟节点的左节点为黑色，以sib为中心进行右旋
//情景4： 如果x的兄弟节点右节点是个红色，左节点任意颜色
//那么 x的父节点设置为黑色，x的兄弟节点的颜色设置为x的父节点的颜色，x的兄弟节点的右节点设置为黑色，以x的父节点为中心进行左旋
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
//判断x是不是空，又或者是不是等于根节点
if (x == null || x == root)
return root;
//判断x的父节点xp ==null ,是那说明，x就是根节点 设置x为黑色 返回x
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//判断x是不是红色，是红色就会设置为黑色，直接返回根节点，
else if (x.red) {
x.red = false;
return root;
}
//判断x是左节点还是右节点
else if ((xpl = xp.left) == x) {
//判断x的兄弟节点是不是不是空，并且是个红色
//-----------情景1-------------
if ((xpr = xp.right) != null && xpr.red) {
//设置x的父节点为红色，x的兄弟节点为黑色，以x的父节点左旋
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;//获取新的兄弟节点
}
//如果没有兄弟节点，则想x = x的父节点
if (xpr == null)
x = xp;
//-----------情景1-------------
else {
//如果有兄弟节点
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
//如果x的兄弟节点的左右节点都是黑色 或者不存在左右节点 设置x的兄弟节点为红色 ，x = x.parent
//-----------情景2-------------
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
//-----------情景2-------------
else {
//如果x的兄弟节点的右节点是黑色，或者没有右节点
//-----------情景3-------------
if (sr == null || !sr.red) {
if (sl != null) //如果存在x的兄弟节点的左节点
sl.red = false; //设置x的兄弟节点的左节点为黑树
xpr.red = true;//设置x的兄弟节点sib为红色
root = rotateRight(root, xpr);//以x的兄弟节点sib为中心，进行右旋，sib左节点顺时针旋转，让sib左节点成为sib的父节点，sib为右节点
xpr = (xp = x.parent) == null ? //sib = 右旋后x的兄弟节点
null : xp.right;
}
//-----------情景3-------------
//-----------情景4-------------
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red; //将x父节点颜色 赋值给 x的兄弟节点
if ((sr = xpr.right) != null)//如果存在x的兄弟节点的右节点
sr.red = false;// 将x兄弟节点sib的右子节设为黑色
}
if (xp != null) {
xp.red = false;// 将x父节点设为黑色
root = rotateLeft(root, xp);;//对x的父节点进行左旋
}
//-----------情景4-------------
x = root;//设置x为根节点 调整完毕退出循环
}
}
}
else { // 下面的跟上面的是一个对称关系
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
扩容 分析
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; //记录旧的table.length
int oldThr = threshold;//记录旧的扩容因子
int newCap, newThr = 0;
//说明是已经初始化
if (oldCap > 0) {
//旧的已经是最大容量了 返回旧容量
//static final int MAXIMUM_CAPACITY = 1 << 30;
if (oldCap >= MAXIMUM_CAPACITY) { //如果table.length大于等于最大容量
threshold = Integer.MAX_VALUE;//threshold = Integer.MAX_VALUE
return oldTab; //返回旧的oldCap，没法再大了
}
//newCap = oldCap << 1
//newThr = oldThr << 1
//static final int MAXIMUM_CAPACITY = 1 << 30 = 1073741824 ;
//static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16; 默认的初始容量-必须是2的幂。
//oldCap << 1 翻一倍 1 << 4 = 16 <= newCap = 旧的长度 * 2 < 1 << 30
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold //设置为触发下一次调整大小的值 newThr = oldThr * 2
}
//new HashMap(initialCapacity) 会设置this.threshold
else if (oldThr > 0) // initial capacity was placed in threshold 初始容量设置为threshold
newCap = oldThr; //触发下一次调整大小的值
//new HashMap()
else { // zero initial threshold signifies using defaults 零初始阈值表示使用默认值
newCap = DEFAULT_INITIAL_CAPACITY; //使用默认值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//触发下一次调整大小的值
}
//计算 newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//ft = 触发下一次调整大小的值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
//当符合条件时newThr = ft ，不符合条件 Integer.MAX_VALUE
}
threshold = newThr; //threshold = newThr
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建一个新的数组
table = newTab; // table = newTab
if (oldTab != null) { //oldTab != null
for (int j = 0; j < oldCap; ++j) { //遍历旧数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { //元素不是空 e = oldTab[j]
oldTab[j] = null;//把oldTab[j] =null
if (e.next == null) //e没有下一个节点
//直接在新的数组里面根据e.hash & (newCap - 1) 计算新的位置存放
newTab[e.hash & (newCap - 1)] = e;
//判断e是否是个树节点
else if (e instanceof TreeNode)
//进行树节点的拷贝
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
/**
* 测试目的：理解HashMap发生resize扩容的时候对于链表的优化处理：
* 初始化一个长度为8的HashMap，因此threshold为6，所以当添加第7个数据的时候会发生扩容；
* Map的Key为Integer，因为整数型的hash等于自身；
* 由于hashMap是根据hash &（n - 1）来确定key所在的数组下标位置的，因此根据公式 m（m >= 1）* capacity + hash碰撞的数组索引下标index，可以拿到一组发生hash碰撞的数据；
* 例如本例子capacity = 8， index = 7，数据为：15，23，31，39，47，55，63；
* 有兴趣的读者，可以自己动手过后选择一组不同的数据样本进行测试。
* 根据hash &（n - 1）， n = 8 二进制1000 扩容后 n = 16 二进制10000， 当8的时候由后3位决定位置，16由后4位。
*
* n - 1 : 0111 & index resize--> 1111 & index
* 15 : 1111 = 0111 resize--> 1111 = 1111
* 23 : 10111 = 0111 resize--> 10111 = 0111
* 31 : 11111 = 0111 resize--> 11111 = 1111
* 39 : 100111 = 0111 resize--> 100111 = 0111
* 47 : 101111 = 0111 resize--> 101111 = 1111
* 55 : 110111 = 0111 resize--> 110111 = 0111
* 63 : 111111 = 0111 resize--> 111111 = 1111
*
* 按照传统的方式扩容的话那么需要去遍历链表，然后跟put的时候一样对比key，==，equals，最后再放入新的索引位置；
* 但是从上面数据可以发现原先所有的数据都落在了7的位置上，当发生扩容时候只有15，31，47，63需要移动（index发生了变化），其他的不需要移动；
* 那么如何区分哪些需要移动，哪些不需要移动呢？
* 通过key的hash值直接对old capacity进行按位与&操作如果结果等于0，那么不需要移动反之需要进行移动并且移动的位置等于old capacity + 当前index。
*
* hash & old capacity（8）
* n : 1000 & index
* 15 : 1111 = 1000
* 23 : 10111 = 0000
* 31 : 11111 = 1000
* 39 : 100111 = 0000
* 47 : 101111 = 1000
* 55 : 110111 = 0000
* 63 : 111111 = 1000
*
* 从下面截图可以看到通过源码中的处理方式可以拿到两个链表，需要移动的链表15->31->47->63，不需要移动的链表23->39->55；
* 因此扩容的时候只需要把loHead放到原来的下标索引j（本例j=7），hiHead放到oldCap + j（本例为8 + 7 = 15）
*
* @param args
————————————————
版权声明：本文为CSDN博主「青元子」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u010890358/article/details/80496144
*/
//这里分析得真好，谢谢大佬
//我这里总结一下
//e.hash & (newCap - 1) 不管你e.hash是什么值 ，在计算下标的时候，控制你在那个地方的是(newCap-1)
//而newCap 是个2的n次方，这是个很特别的数，这个数减1 二进制必定是长这样子的 111（8-1）,1111（16-1）,11111（32-1）,11111（64-1）等
//比如8 二进制是 111，那么下面举例子说明
// e.hash 的二进制 = 01001010111010101011011 我不知十进制是什么值，但无所谓，(newCap - 1) 二进制是 111
//01001010111010101011011
// &
//00000000000000000000111
// =
//00000000000000000000011
//结果下标就是 11 十进制是3，你看，不管你的e.hash是什么，下标必定在111的范围内，所以e.hash真正参加计算的只是后三位而然
//扩容
//当容量不够进行扩容时，把数组的长度扩大到 oldCap << 1; 记得oldCap是个2的n次方 这里举例oldCap=8
//00000000000000000001000
// << 1 (意思是位向左移动一位，右边补0)
//00000000000000000010000
//最后结果转十进制等于16 上面我们数组存了一个元素01001010111010101011011 那他怎么处理呢，还是一样的处理
//01001010111010101011011
// &
//00000000000000000001111 （16-1）
//00000000000000000001011
//结果下标就是 1011 十进制是11，你看，不管你的e.hash是什么，下标必定在1111的范围内，所以e.hash真正参加计算的只是后四位而然
//举例 oldCap=8 newCap=16
//a元素的分析 a元素的hashcode的二进制 = 01001010111010101011011
//011（元素二进制的后三位） & 111（oldCap-1） = 0011 未扩容时
//1011（元素二进制的后四位） & 1111（newCap-1） = 1011 扩容后
//b元素的分析 b元素的hashcode的二进制 = 01001010111010101010011
//011（元素二进制的后三位） & 111（oldCap-1） = 0011 未扩容时
//0011（元素二进制的后四位） & 1111（newCap-1） = 0011 扩容后
//根据上面的数据进行如下分析
//第一个结论，(oldCap-1)的二进制比（newCap-1）的二进制 少一位1
//第二个结论，在进行下标计算时 ，元素的hashcode的二进制真正有用到的位置
//未扩容，后三位
//扩容后，后四位
//第三个结论，计算出来的下标
//a元素 未扩容的下边跟扩容后的下边相差一个1000
//b元素 未扩容的下边跟扩容后的下边相等
//仔细观察a,b元素的二级制
//a 01001010111010101011011
//b 01001010111010101010011
//你会惊讶的发现，a和b只是倒数第四位不一样，a 是1，b是0
//然而 计算出来的下标结论是
//a元素 未扩容的下边跟扩容后的下边相差一个1000
//b元素 未扩容的下边跟扩容后的下边相等，也即是位置不会发生改变
//这里已经说明，第四位是0和1，对于计算下标有着天大的影响
//那现在来分析(e.hash & oldCap) oldCap = 8
//a元素 1011（元素二进制的后四位 & 1000 = 1000
//b元素 0011（元素二进制的后四位 & 1000 = 0000
//先提出一个问题为什么是& oldCap 不是其他呢
//oldCap的二级制是多少 1000 发现了什么吗 它的倒数第4位是个1
//根据上面的分析，第四位是0和1，对于计算下标有着天大的影响
//元素的第四个位置是0，那么位置不变
//元素的第四个位置是1，那么位置改变
//而oldCap是一个2的n次方的数，2的n次方的数是很有规律的，10（2） （100）4 （1000）8 （10000）16 等
//0111 (oldCap-1) 未扩容后
//1111 (newCap-1) 扩容后
//1000 oldCap 未扩容后
//10000 newCap 扩容后
//因为1000的第四位是1 而且1000后三位是0,在参与&运算时，只会比较第四位，其他位都是0
//所以(e.hash & oldCap) == 0 就知道 e.hash的第四位是0，否则就是1
//所以明白了为什是oldCap了吗
//至于为什么新的位置是旧的位置是旧的位置+旧的长度
//第三个结论 如果第四个位置是1，未扩容的下边跟扩容后的下边相差一个1000，这个1000熟悉不，不就是oldCap吗？
if ((e.hash & oldCap) == 0) {
//第一条链表
// 第一次
// loTail
// loHead
// 1
// 第二次
// loTail
// loHead
// 1 -> 2
//第三次
// loTail
// loHead
// 1 -> 2 -> 3
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; //第二条链表的位置是 旧的长度位置+旧的位置j
}
}
}
}
}
return newTab;
}
//((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
for (TreeNode<K,V> e = b, next; e != null; e = next) { //遍历这棵树
next = (TreeNode<K,V>)e.next;
e.next = null;
//判断e.hash是否需要移动位置
// 第一次
// loTail
// loHead
// 1
// 第二次
// loTail
// loHead
// 1 -> 2
//第三次
// loTail
// loHead
// 1 -> 2 -> 3
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;
}
}
if (loHead != null) {
//static final int UNTREEIFY_THRESHOLD = 6
//调整大小的时候，如果树的节点数少于6，会进行树的退化
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);
}
}
}
//由树变了链表
//遍历树，遍历过程中 TreeNode->Node Node<K,V> p = map.replacementNode(q, null);
//设置节点的next 返回根节点
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null); // TreeNode->Node
if (tl == null)
hd = p;
else
tl.next = p; //设置节点的next
tl = p;
}
return hd;// 返回根节点
}
//tab =hashmap存放元素的array
//this = hd 头部元素,现在只是一个双向链表
//这里的逻辑是遍历链表
//如果没有根元素，那么设置根元素 root == null x.parent = null; x.red = false; root = x;
//如果存在根节点，那么就遍历树，从根元素开始
//先根据节点的hash值进行比较
//如果hash值一样，比较key值是否相等
///如果hash值一样,根据key的comparableTo比较大小，
//如果key没有没有实现comparable，最后使用System.identityHashCode()进行比较，
//System.identityHashCode(a) 无论给定对象的类是否覆盖hashCode()，
//返回给定对象与默认方法hashCode()返回的相同哈希代码。空引用的哈希码为零
//最后根据比较的值 绑定关系 dir <= 0 ? p.left : p.right
// TreeNode<K,V> xp = p; x.parent = xp; dir <= 0 ? xp.left = x ：xp.right = x;
//绑定关系后就需要保证红黑树没有违反规则，则调用balanceInsertion
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//x = hd
//next = x.next
//遍历的是列表
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
//左右节点都是null
x.left = x.right = null;
//如果不存在根节点
if (root == null) {
x.parent = null; //x的parent设置为空
x.red = false; //红黑树的根节点是黑色。
root = x; //设置x 为根节点
}
else { //如果存在根节点，也即是不是根节点怎么放
K k = x.key; //取出需要处理的节点x的key
int h = x.hash;///取出需要处理的节点x的hash
Class<?> kc = null; //
//死循环
//TreeNode<K,V> p = root
//遍历的是树呢
for (TreeNode<K,V> p = root;;) {
int dir; //记录p节点和x节点的hash值比较状态 大于-1 小于1
int ph; //节点hsah值
K pk = p.key; //取出节点的key
if ((ph = p.hash) > h) //p节点的hash值> x节点的hash值
dir = -1; //大于设置状态-1
else if (ph < h) //p节点的hash值 < x节点的hash值
dir = 1; //小于设置状态-1
//这里就是等于的意思了
//kc = comparableClassFor(k) ==>x的class
//dir = compareComparables(kc, k, pk) ==>x,p的比较值
//kc = null,
//comparableClassFor(k),获取x的key的类型，
//如果是实现了comparable的就返回x的key的类型，否则返回null，见下面函数分析
//compareComparables,通过 comparable 获取比较的值，没有实现comparable，
//或者p的key的class和x的class 不一样，返回0，见下面函数分析
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//使用默认的hashcode进行相减,见下面函数分析
dir = tieBreakOrder(k, pk);
//xp = 节点p
TreeNode<K,V> xp = p;
//p > x = -1
//p = 大于 p.left 小于p.right
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//记得xp等于之前的p 进来if p= p.left or p.right 设置x的爸爸是xp
x.parent = xp;
if (dir <= 0) // p > x = -1
xp.left = x; //大于是左边
else
xp.right = x;//小于是右边
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
右旋
image.png
左旋
image.png
网友评论