最近在闲暇时刻仔细查看了HashMap的代码，对于一些不常用的方法如iterator,spliterator等以及树节点的部分做了仔细阅读，对于不好理解的部分做了较为详细的注释，对于简单理解的部分没有做注释。
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import sun.misc.SharedSecrets;
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
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;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
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;
}
// 比较地址，比较key，比较value
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;
}
}
// 这里翻译为高位扩展至低位
// >>> 16代表无符号右移，即将低16位去掉
// ^ 异或操作
// 如果原hashcode > pow(2,16)，异或操作后可能和原hashcode不同
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 树节点判断位置时，如果key的hash相同，但是并不equals，会通过该方法判断key是否实现了compareable接口
// 如果实现了compareable，会使用compare来判断位置
static Class<?> comparableClassFor(Object x) {
// 是否实现Compareable接口
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // String类型直接通过验证，难不成是因为String用到的比较多
return 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) && // 参数类型的基本类型为Compareable
(as = p.getActualTypeArguments()) != null && // 参数类型存在
as.length == 1 && as[0] == c) // type arg is c // 参数类型存在且和自己的类型相同。注意，若是实现的Compareable接口的参数类型不是自身类型，也不会使用compare来判断位置
return c;
}
}
}
return null;
}
/**
树节点中有用到此方法
如果实现了compareable，通过此方法来判断位置
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
// 如果cap是2的整次幂则返回cap，如果cap不是2的整次幂，则返回大于该整数的最小的2的整次幂
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;
}
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
// 结构修改的次数，会在使用迭代器时做判断
// 若是HashMap修改的次数和迭代器构造时的expectModCount不同，那么不能使用此迭代器，迅速抛错
transient int modCount;
// 使用该值来判断是否进行扩容
// 该值 = 容量 * 负载系数
// 例如：如果长度为8的数组，Node数量达到 8 * loadFactor 后就会进行扩容
int threshold;
// 负载系数。也就是当桶的数量达到总数量的负载系数时会自动扩容
final float loadFactor;
// 指定初始容量和加载因子
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);
}
// 添加一个Map到该HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//在putAll操作时可能会走下面这步骤，其实就算这里不扩容下面的操作还是会扩容。不明白为什么在这里放一句
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
// 返回键值对数量
public int size() {
return size;
}
// 是否包含键值对
public boolean isEmpty() {
return size == 0;
}
// 返回对应键的值
// 这里要注意，返回的null可能是该键对应的值就是null，可以使用containsKey来判断键值是否存在
public V get(Object key) {
Node<K,V> e;
// 这里使用了hash方法，经过hash可能和key的hashcode不同
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
// first 对应的是链表的头结点
// 使用&运算来求余
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 查询节点时比较的是Node的hash和key，即便是相同的hash若是key不同也会是不同的节点
// 这里要注意"key相同"这个概念，若是重写了key的equals方法，也可能导致key看起来不同但实际是相同的
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);
// 遍历链表找到对应的Node
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
// 是否包含该key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
// 如果没有就插入，如果有就更新
// 返回值为null或者原来的值
public V put(K key, V value) {
// 这里使用了hash方法，可能导致hashcode变化
return putVal(hash(key), key, value, false, true);
}
/**
* 如果没有就插入，如果有就更新
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, 不改变原来的值
* @param evict if false, 表示table还没创建.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果数组是空的，先创建数组
// resize操作时，若是在new HashMap时指定了容量，那么数组长度为容量(容量cap一定为2的某次幂)，但是threshold会变为 cap*loadfactor
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 这里使用了与运算求余
// 通过求余定位到数组中的位置
// 如果该位置为空，直接生成一个新的Node放在该位置
if ((p = tab[i = (n - 1) & hash]) == null)
// 这里生成Node时将hash传了进去，这里要注意，这个hash和Node的hashcode()返回的hash并不一样，做判断操作时一般都使用传入的hash
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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) {
if ((e = p.next) == null) {
// 链表中不存在，在链表末尾添加新节点
p.next = newNode(hash, key, value, null);
// 如果超过了TREEIFY_THRESHOLD就转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 根据hash判断，若是hash相同并且key相同代表该键存在，修改该键对应的值为新值
// 这里要注意，如果只是hash相同但是key不相同也会生成新的Node。而不是修改Node
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 沿着链表向后遍历
p = e;
}
}
// 如果Node存在，并且onlyIfAbsent为false,修改节点的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 为其他子类准备的回调方法
afterNodeAccess(e);
return oldValue;
}
}
// 操作次数+1
++modCount;
// 如果Node数超过了负载容量则扩容。负载容量 = 容量 * 负载因子
if (++size > threshold)
resize();
// 为其他子类准备的回调
afterNodeInsertion(evict);
return null;
}
// 扩容数组，返回新的数组
// 若数组不为空，将容量变为原来的二倍
// 原位置上的Node节点或者保持位置不变，或者移动到新数组的[index+oldLength]位置
// 位置上的链表分为两部分，保持原位置不变或者挂载到新数组的[index+oldLengh]位置
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果无后续节点，直接将该节点散列到新的数组
newTab[e.hash & (newCap - 1)] = 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;
// 这里为什么使用&比较
// 是因为oldCap肯定是2的整次幂，也就是说它的二进制位只有最高位是1，其余都为0。
// &运算的特点，1&1=1,1&0=0,0&0=0
// 所以使用e.hash & oldCap == 0 的概率就是一个数的某一位为1的概率，这个概率接近50%
// 其实达到的效果就是将链表一半的数据hash到新数组的[j+oldCap]位置
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) {
// 将尾节点的next置空
loTail.next = null;
// 将原链表的一部分放到新数组的 [原位置]
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 将原链表的一部分放到新数组的 [原位置 + oldCap]。因为数组是原来的二倍
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
// 链表转换为红黑树
// 转换的是数组的某个节点处的链表
// 这里注意，转换后的红黑树也保存了链表的逻辑结构，并且是双链表的逻辑结构
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 容量太小直接扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd为链表的头结点
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为链表的头结点，因此是将整个链表构造为红黑树
// 构造完成后会将树的根节点放在数组的原位置
hd.treeify(tab);
}
}
// 添加别的map
// 这里要注意，若是添加的key有和原map相同的，那么将会修改这个key对应的值
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
// 删除对应的键值，返回原值
// 返回结果是null有两种情况，可能该键值不存在，也可能该键对应的值就是null
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 删除键值
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue 是否需要判断value相等
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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, 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都是链表的头结点
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
// 这里遍历链表，p是node的前驱节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
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);
// 这里p是node的前驱节点
else if (node == p)
// 相等表示node就是数组位置上的第一个节点，即链表的头结点，直接将后继节点放在数组的位置上作为第一个节点
tab[index] = node.next;
else
// 若果不是，将后继节点作为前驱节点的后继节点
p.next = node.next;
// 操作数量+1
++modCount;
// node数量-1
--size;
// 回调函数
afterNodeRemoval(node);
return node;
}
}
return null;
}
// 将Node数组清空
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
// 是否包含特定的值
// 即便是转换成了树，也包含了双链表结构，因此遍历时只需要按照链表结构遍历即可
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
// 生成一个set，内部主要是使用iterator
// 这个和list不同，是在运行时才去找下一个
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
// 操作该类时要小心，因为它会反应到HashMap
// 例如remove操作也会删除掉HashMap中的键值对
// 不支持add操作，因为他们继承了AbstractCollection但是没有覆盖add方法
final class KeySet extends AbstractSet<K> {
// 使用外部类的size
public final int size() { return size; }
// 若是和外部类相同的方法，使用 父类.this
public final void clear() { HashMap.this.clear(); }
// 构造迭代器
public final Iterator<K> iterator() { return new KeyIterator(); }
// 这个contains和HashMap的containsKey是相同的
public final boolean contains(Object o) { return containsKey(o); }
// 和删除键值对效果相同
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 生成一个可以操作部分节点的iterator
public final Spliterator<K> spliterator() {
// 初始化时fence为-1
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
// 根据数组和链表的数据结构遍历
// 转换成树后仍然保留了链表结构
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// 数组结构
for (int i = 0; i < tab.length; ++i) {
// 链表结构
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// 返回所有值
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
// 类似KeySet和ValueSet
// 不使用set而直接使用collection是因为value可能有重复的
// 使用效果是相同的，remove方法等也会删除HashMap的数据
// 不能使用add等方法，因为没有覆盖父类方法
// 可以发现这里面没重写remove方法，但是最终调用了 HashIterator 的remove方法，也是删除了HashMap中的键值对
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
// 生成一个可以操作部分节点的iterator
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// 返回所有键值对，和上面的KeySet和Values相同
// 方法的实现都是类似的
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
// 这里删除时也比较了value，即key和value全部相同时才会删除
return removeNode(hash(key), key, value, true, true) != null; // 倒数第二个参数代表也比较value
}
return false;
}
//
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
// 这里遍历是按照数组和链表的数据结构来遍历
// 转换为树后也保留了链表的结构
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// 覆盖原来的一些方法
// 返回对应的node的值，若是node为空返回默认值
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
// 若果键值对不存在则插入，如果存在则不修改原来的值
// 这个方法可以这样使用 if(evalue = map.putIfAbsent(evalue)) ...
@Override
public V putIfAbsent(K key, V value) {
// 倒数第二个参数为true代表键值对存在时不修改原来的值
return putVal(hash(key), key, value, true, true);
}
// 如果key和value都相同，则删除对应键值对
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
// 根据key和value修改对应的键值对的值为新值
// 修改成功返回true，若是键值对不存在或者value不相同，返回false
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
// 根据key查询Node，若是Node存在将值修改为value，返回原来的value。若是Node不存在，返回null
// 这里注意，返回null时不一定是Node不存在，也可能oldValue本来就是null
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
// 如果不存在则添加，如果存在则不修改
// 这个和putIfAbsent作用相似，但是提供了一个生成value的function
// 由于这里可能插入新的Node，因此有可能resize和转换树
// 这里注意，若是size已经达到了threshold，使用这个方法插入节点并不会造成resize，会在下一次调用这个方法时才会resize
@Override
public V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
// 判断是否需要转换树
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
// 如果数组是空的或者容量大于阈值进行扩容
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
// 查找Node
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
V oldValue;
if (old != null && (oldValue = old.value) != null) {
afterNodeAccess(old);
return oldValue;
}
}
// 生成值
V v = mappingFunction.apply(key);
if (v == null) {
return null;
} else if (old != null) {
old.value = v;
afterNodeAccess(old);
return v;
}
else if (t != null)
// 添加到树中
t.putTreeVal(this, tab, hash, key, v);
else {
// 添加到链表
// 这里注意，这里是将新节点添加到链表的头部
// 和putVal不同，putVal是将新节点添加到链表的尾部
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
// 这里size加1后并没有判断是否resize
afterNodeInsertion(true);
return v;
}
// 如果有则修改，如果没有则不添加
// 如果修改后的值是null，那么会将原Node删除
public V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node<K,V> e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
// 删除原Node
removeNode(hash, key, null, false, true);
}
return null;
}
// 有则修改，没有则添加
// 结合上面两个方法的特点
// 添加的新节点是链表的头结点，添加完成后不会计算是否resize，如果修改后的值为null,将原Node移除
@Override
public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
// 判断是否扩容
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
// 查找Node
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
V oldValue = (old == null) ? null : old.value;
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
// 移除原Node
removeNode(hash, key, null, false, true);
}
else if (v != null) {
if (t != null)
t.putTreeVal(this, tab, hash, key, v);
else {
// 放在链表的头部
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
// size+1后没判断是否扩容
afterNodeInsertion(true);
}
return v;
}
// 如果有则修改，如果没有则添加
// 提供了一个原value和新value的function，可以使用这两个值构建新值
// 若是有则使用function生成的value替换，若是没有则直接使用新value替换
// 结合上面两个方法的特点
// 添加的新节点是链表的头结点，添加完成后不会计算是否resize，如果Node存在，且function生成的值为null,将原Node移除
@Override
public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
// 是否扩容
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
// 定位节点
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
// Node存在
if (old != null) {
V v;
if (old.value != null)
v = remappingFunction.apply(old.value, value);
else
v = value;
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
// function生成的value为null，直接移除
removeNode(hash, key, null, false, true);
return v;
}
if (value != null) {
if (t != null)
// 添加到树中
t.putTreeVal(this, tab, hash, key, value);
else {
// 添加到链表头部
tab[i] = newNode(hash, key, value, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
// size+1后没有进行resize判断
afterNodeInsertion(true);
}
return value;
}
// 根据数组和链表的结构遍历键值对
// 转换成树之后也保留了链表的结构
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
// 根据数组和链表结构遍历数组，根据function(k,v)生成新的value替换原来的value
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Node<K,V>[] tab;
if (function == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
e.value = function.apply(e.key, e.value);
}
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
// 浅拷贝，返回一个和该HashMap相同键值对的副本
// 这里要注意，若value是对象类型，原HashMap的改变可能会导致副本HashMap的改变
@SuppressWarnings("unchecked")
@Override
public Object clone() {
HashMap<K,V> result;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize();
result.putMapEntries(this, false);
return result;
}
// These methods are also used when serializing HashSets
// 序列化时会用到
final float loadFactor() { return loadFactor; }
// 返回数组长度，这个值一定大于Node的数量
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}
// 序列化，序列化时会写入容量，大小和所有键值对
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets); // 写入数组长度
s.writeInt(size); // 写入Node数量
internalWriteEntries(s); // 写入键值对，这里很简单就是遍历键值对逐个写入，顺序就是遍历每个数组桶的链表
}
/**
* 反序列化
* 因为忽略了原HashMap的capacity，所以新生成的HashMap结构可能变化了，数组长度可能小于原HashMap
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// 根据write的顺序，依次读取
s.defaultReadObject();
reinitialize();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
s.readInt(); // 忽略了原HashMap的数组长度
int mappings = s.readInt(); // 读入Node数量
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
// 这里当计算的长度小于default时，使用默认值
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
// Check Map.Entry[].class since it's the nearest public type to
// what we're actually creating.
SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// 逐个读取键值对，放入新的HashMap
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
/* ------------------------------------------------------------ */
// 各种迭代器
// 这些迭代器主要是使用nextNode()来控制next，达到迭代的效果
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
// 这个值是为了判断和HashMap的modCount是否相等
// 若是不相等说明原HashMap改变了，不能使用迭代器，迅速抛错，即fast-fail
int expectedModCount; // for fast-fail
// 在迭代开始后，index应该是next的下一个
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
// 当前Node在数组中的位置
index = 0;
if (t != null && size > 0) { // advance to first entry
// 找到第一个不是null的Node，这个Node就是第一个next
do {} while (index < t.length && (next = t[index++]) == null);
}
}
// 是否迭代完成
public final boolean hasNext() {
return next != null;
}
// 这里仍然是按照数组加链表的结构遍历的，找到下一个不是null的值
// 但是这里的遍历写法和其他不太相同，链表在外部，数组遍历在内部
// 可以将迭代器想象成一个整体的链表结构，还是单链表
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 链表结构
if ((next = (current = e).next) == null && (t = table) != null) {
// 遍历数组结构
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
// 移除当前Node
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
// 同时改变HashMap的modCount和当前Iterator的expectedModCount
expectedModCount = modCount;
}
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
/* ------------------------------------------------------------ */
// 各种 spliterators
// spliterator 是将 iterator分成几部分来并行处理
/**
可以这样使用
do{
new Thread(new MyRunnable(spliterator,"thread"+ index++)).start();
}while((spliterator = spliterator.trySplit())!=null); // 这里trySplit()后生成了新的对象，对其他线程内部的spliterator不影响
这样的效果是将HashMap中的键值对分成了几部分，多个线程同时处理
因为每个线程处理的是所有键值对的一部分，互相之间不会有影响，因此没有多线程通信和加锁的问题
但是在处理的过程中若是修改HashMap，例如使用map.put()，会抛出ConcurrentModificationException。和iterator相同，这个是通过modCount来判断的
如果HashMap散列的不均匀，可能起不到什么效果，因为spiterator划分的是数组，并不是将所有节点放到一起划分，而数组上可能有很长的链表。
这里还有一个小花活。由于默认的加载因子是0.75，因此默认加载因子的情况下，Node数组的后面四分之一长度是空的。
使用spliterator时是从后向前划分，第一个spliterator是数组后面的1/2，由于最后的1/4是空的，因此处理时只有数组的1/2到3/4的部分，
因此一般情况下第一个spliterator和第二个spliterator处理的都是数组的1/4长度的节点(不考虑链表部分)
*/
static class HashMapSpliterator<K,V> {
final HashMap<K,V> map;
Node<K,V> current; // current node 当前Node
int index; // current index, modified on advance/split 当前索引
int fence; // one past last index 上一个索引
int est; // size estimate 估计数量，这个数量在经历过trySplit后变得不准确
int expectedModCount; // for comodification checks
HashMapSpliterator(HashMap<K,V> m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getFence() { // initialize fence and size on first use
int hi;
// 初始化的fence为-1，经历过trySplit后fence发生变化
if ((hi = fence) < 0) {
HashMap<K,V> m = map;
est = m.size;
expectedModCount = m.modCount;
Node<K,V>[] tab = m.table;
// 只要不是第一次调用fence都是大于等于0的
hi = fence = (tab == null) ? 0 : tab.length;
}
return hi;
}
public final long estimateSize() {
getFence(); // force init 如果是第一次则将est置为table.length
return (long) est;
}
}
static final class KeySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<K> {
KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public KeySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; // 这里的lo开始时是0，即index为0。因为index会在trySplit方法中改变，若是不调用trySplit，即在当前的spliterator遍历到末尾
return (lo >= mid || current != null) ? null :
new KeySpliterator<>(map, lo, index = mid, est >>>= 1, // index 在这里发生了变化，变成了低位，但是这里的低位对应的下一个spliterator的高位，forEach时将从这个index开始遍历
expectedModCount);
}
public void forEachRemaining(Consumer<? super K> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
// 这里为什么不用hi = getFence()呢，在tryAdvance中就是使用的getFence()
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi && // 先将index赋给遍历位，即从index开始遍历，注意这里的index对应的是下一个spliterator的高位，因此无缝连接
(i = index) >= 0 && (i < (index = hi) || current != null)) { // index 在这里发生了变化，变为了高位，因为遍历完肯定是在高位。不明白为什么这么着急将index置为高位
Node<K,V> p = current;
current = null;
// 按照链表加数组的结构遍历
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.key);
p = p.next;
}
} while (p != null || i < hi); // 这里可以发现spliterator是按照数组角标划分的，因此遇到哈希散列不均匀的情况也无能为力
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
// 类似于iterator的hasNext，迭代处理
/**
可以这样使用
while(spliterator.tryAdvance(item->{
// action...
})){
}
*/
public boolean tryAdvance(Consumer<? super K> action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<K,V>[] tab = map.table;
// 相对forEach来说简化了，就是简单的将index逐步遍历到fence
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
// 根据数组和链表结构遍历
while (current != null || index < hi) {
if (current == null)
current = tab[index++]; // 这里是逐步加index的，而forEach是直接将index赋值高位
else {
K k = current.key;
current = current.next;
action.accept(k); // 这里也很奇怪，为什么要在处理完action后才进行异常判断
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
// 按照Spliterator中对characteristics的定义，在多次调用trySplit时要保证每次的characteristics都相同才能使用
// 但是HashMap应该不是这样用，因为它在trySplit时做了est>>>1操作，几乎是减半。
// 因此在第一个spliterator时反应了SIZED和DISTINCT特性，但是经历过trySplit后只剩下了DISTINCT属性。
// 因为key是不重复的，所以有DISTINCT特性。而value是可以重复的，因此ValueSpliterator没有DISTINCT特性。
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
}
// 和KeySpliterator相同，处理的是value
static final class ValueSpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<V> {
ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public ValueSpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer<? super V> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Node<K,V> p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.value);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer<? super V> action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<K,V>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
V v = current.value;
current = current.next;
action.accept(v);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
}
}
// 和KeySpliterator相同，处理的是键值对
static final class EntrySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<Map.Entry<K,V>> {
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
// 分为一部分
public EntrySpliterator<K,V> trySplit() {
// 这里可能将fence变为 (index+fence)/2，这样在调用forEachRemaining方法时只遍历数组的一部分
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
// 这里将原来的index传入了新的spliterator，保证了顺序递增
new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Node<K,V> p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<K,V>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
Node<K,V> e = current;
current = current.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
}
// 新建普通节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// 将Tree节点转换为普通节点
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
// 新建一个树节点，这个树节点里也保留了链表的特征
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
return new TreeNode<>(hash, key, value, next);
}
// 将普通节点转换为树节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
/**
* 重置状态. Called by clone and readObject.
*/
void reinitialize() {
table = null;
entrySet = null;
keySet = null;
values = null;
modCount = 0;
threshold = 0;
size = 0;
}
// 为LinkedHashMap提供的回调函数
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
// 按照数组和链表结构遍历，将键值对写入流
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
/* ------------------------------------------------------------ */
// Tree bins
/**
树节点
主体是红黑树的结构
红黑树的特点：每个节点到叶子节点路线上的黑色节点数相同。红色节点的子节点都是黑色节点。
LinkedHashMap.Entry继承了HashMap.Node，因此TreeNode也有HashMap.Node的特性。
有个问题，为什么不直接进行继承HashMap.Node呢，TreeNode添加了prev属性，按理说就是双链表了。继承了LinkedHashMap.Entry但也没用里面的before,after。
*/
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; // 删除后需要取消链接
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回包含此节点的树的根节点
直接通过parent向上遍历即可
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* 保证树的根节点是Node数组位置上的第一个节点
这里要清楚，TreeNode保留了链表的结构，这个结构和树结构是独立的
原链表
+-----+ other node +-----+ +-----+ +-----+
array first node |first| ----> ... ---->| rp | ----> | root| ---->| rn |
+-----+ +-----+ +-----+ +-----+
转换后的链表
+-----+ +-----+ other node +-----+ +-----+
array first node |root | ---->|first| ----> ... ----> | rp | ---->| rn |
+-----+ +-----+ +-----+ +-----+
*/
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;
// first是数组位置上的原节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev; // rp为root前驱节点
if ((rn = root.next) != null) // rn为root后继节点
((TreeNode<K,V>)rn).prev = rp; // 将rn的前驱置为rp (将root节点从原来的顺序中取出)
if (rp != null)
rp.next = rn; // 将rp的后继置为rn (保证双链表不断链)
if (first != null)
first.prev = root; // 将first的前驱置为root
// 将原来的节点放在了root后面(维护的是链表的顺序)
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
/**
* 以当前节点为根节点，对给定的hash进行查找
*/
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) // ph是根节点的hash
p = pl; // 如果hash小于根节点hash，从左子树查找
else if (ph < h)
p = pr; // 如果hash大于根节点hash，从右子树查找
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; // 如果key相等，返回当前节点
else if (pl == null)
p = pr; // 当key的hashcode相同但是并不equal时，从左右子树去找。 因为判断key相同是同时判断hashcode和equals，如果重写了equals方法会导致这种情况。
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr; // 如果实现了compareable接口，通过compareable来判断是去左子树还是右子树。但是这里注意，并不会通过compare来判断key相同。
else if ((q = pr.find(h, k, kc)) != null) // 使用右子树作为root查询一次。不明白为什么。
return q;
else
p = pl;
} while (p != null);
return null;
}
/**
* 通过根节点查找节点
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
// System.identifyHashCode(Object) 是在对象重写hashCode方法情况下，仍然返回默认的hashCode。这个hashCode和对象的地址有关系
/**
* 在hashcode相同的情况下使用此方法。
如果两个key的hashCode相同，但是并不equals（重写过了）,使用者方法确定两个key的顺序
这个在添加树节点的时候会用到，在使用此方法前一定判断了equals
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
// 通过比较默认的对象hashcode来判断顺序
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
/**
* 通过该节点构造树，在链表结构基础上添加红黑树结构
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 通过链表结构遍历
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 没有根节点的话先添加根节点
if (root == null) {
// 根节点parent为null
x.parent = null;
// 如果只有一个根节点，那么根节点为黑色节点
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 判断顺序，决定添加到左还是右
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); // 若是没实现compareable接口或者通过compareable接口也不能比较时，将通过object的默认hash决定顺序
// 将xp作为当前节点
TreeNode<K,V> xp = p;
// 先将节点添加到叶子节点，然后由下到上做自平衡处理
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// x是当前节点，xp是x的父节点
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 每添加一个节点后做自平衡处理
root = balanceInsertion(root, x);
break;
}
}
}
}
// 树构造完成后将根节点放到链表头部
moveRootToFront(tab, root);
}
/**
* 树结构转换成链表结构
因为树结构中也保留了链表的结构，直接转换成普通Node节点即可
*/
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);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
// 返回头结点
return hd;
}
/**
* 树结构添加节点
*/
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;;) {
// 通过dir来判断是在左子树还是右子树
// ph为当前节点的hash
// pk为当前节点的key
int dir, ph; K pk;
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;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) { // 若是没实现compareable接口或者通过compareable接口也不能比较时
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; // 先在左右子树查找一次
}
// 根据object默认的hash决定顺序
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 添加到当前节点的左子树或者右子树，若是存在继续向下遍历
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// xp当前节点的后继节点
Node<K,V> xpn = xp.next;
// 这里将xpn作为新节点的后继节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 保证父子关系
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 保证不断链
xp.next = x;
// 保证父子关系
x.parent = x.prev = xp;
// 若后继节点存在，将新节点作为前驱，保证双链表不断链，
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 添加完成后做自平衡处理
// 将新的root节点移动到链表的头部
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
/**
* 删除树节点
分了两部分。第一部分是在链表结构中删除，第二部分是在红黑树结构中删除。
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
// 数组长度
int n;
if (tab == null || (n = tab.length) == 0)
return;
// 查找Node位置
int index = (n - 1) & hash;
// 根节点为链表的头结点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// succ为后继节点，pred为前驱节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
// 前驱为null代表该节点为链表头结点即root节点，将后继节点作为头结点和根节点
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
// 后继为null代表该节点为链表尾节点
if (succ != null)
succ.prev = pred;
// 头结点为空代表是空树
if (first == null)
return;
// 找到根节点
if (root.parent != null)
root = root.root();
// 节点数少时转换为普通链表
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
// 最多通过两次移动可以将删除节点移动到叶子节点，然后删除
// 因为红黑树的特点导致左右子树的高度差最多为2
// p为要删除的节点
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// 第一次移动是将该节点和该节点的右子树的最左侧节点交换
if (pl != null && pr != null) {
// pr为当前节点的右子树
TreeNode<K,V> s = pr, sl;
// s为当前节点的左子树最左边节点，即最小的节点，将使用这个节点来替换删除的节点。替换删除的节点s一定无左子节点
while ((sl = s.left) != null) // find successor
s = sl;
// 交换节点p和节点s的颜色
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
// 因为s无左子节点，因此维护父子关系时只考虑右子节点即可
// sr为s右子节点
TreeNode<K,V> sr = s.right;
// pp为p的父节点
TreeNode<K,V> pp = p.parent;
// 如果p节点的右子节点pr即为替换节点，表示pr无左子树
if (s == pr) { // p was s's direct parent
// 交换节点p和节点s的位置，即直接交换其父子关系
p.parent = s;
s.right = p;
}
// 如果pr存在左子树
else {
// sp为替换节点s的父节点
TreeNode<K,V> sp = s.parent;
// 交换节点p和节点s的位置，修改其各自的父子关系
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
// 因为pr是右子树是确定的
if ((s.right = pr) != null)
pr.parent = s;
}
// 这里p已经和上面找到的右子树的最左侧节点交换了，因为它在最左侧，因此左子树为空
p.left = null;
// 交换p和s后，保证原来各自的父子关系
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
// 如果替换节点s的右子树存在
if (sr != null)
replacement = sr; // 右子树存在说明还没到叶子节点，将会继续替换到叶子节点
else
replacement = p; // 右子树不存在说明已经到了叶子节点，直接进行删除的自平衡处理
}
// 红黑树的特性导致的，如果一个节点只有一侧的子节点，那么另一侧的子节点不会有任何子节点
// 所以这里pl或者pr肯定为叶子节点
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p; // p节点即为叶子节点
// 如果第一次移动没有将要删除的节点移动到叶子节点，开始第二次移动
// 这里p一定是replacement的父节点
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
// 删除的自平衡处理
// 如果在第一次移动已经移动到了叶子节点，那么节点这时候还没删除，但是颜色已经和替换节点交换了，因此若p是红色，不需进行自平衡处理。下面直接移除即可
// 如果在第一次移动还没移动到叶子节点，那么节点这时候在树结构中已经删除了。若是p是红色，不需要进行平衡处理
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 如果经过第一次移动已经到了叶子节点，将该节点进行拆卸，移除其父子关系
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
// 默认moveable为true，会将新的root节点移动到链表头
if (movable)
moveRootToFront(tab, r);
}
/**
在resize方法时，如果是树节点，将会使用该方法
操作分为两部分。一部分是将链表分为两部分，一部分是将树结构分为两部分
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// 链表分为两部分的算法和普通链表相同，仍然是使用hash和oldTabLength进行位运算，本质是hash的某一位是1的概率
// 两个新的链表中Node顺序整体上和原链表中的顺序相同
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;
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) {
// 如果数量过少，转换为普通的单链表
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) {
// 将新的链表放在index+bit位置上，因为扩容是原来的2倍
// 如果节点数量少转换为普通的单链表
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
// 新的链表转换为树结构
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
// 以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.parent = p; // 保证父子关系
if ((pp = r.parent = p.parent) == null) // 因为左旋后r是p的父节点，因此要将p的父节点赋给r的父节点
(root = r).red = false; // 如果r是根节点，保证根节点为黑色
else if (pp.left == p) // 判断p是父节点的左子节点还是右子节点，保证r和pp的父子关系
pp.left = r;
else
pp.right = r;
r.left = p; // 旋转节点变为原右子节点的左子节点
p.parent = r; // 右子节点变为支点的父节点，保证父子关系
}
return 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.parent = p; // 保证父子关系
if ((pp = l.parent = p.parent) == null) // 因为右旋后l是p的父节点，因此要将p的父节点赋给l的父节点
(root = l).red = false; // 如果l是根节点，保证根节点为黑色
else if (pp.right == p) // 判断p是父节点的左子节点还是右子节点，保证l和pp的父子关系
pp.right = l;
else
pp.left = l;
l.right = p; // 支点变为原左子节点的右子节点
p.parent = l; // 左子节点变为支点的父节点，保证父子关系
}
return root;
}
// 插入一个新节点时的自平衡处理，返回平衡后的根节点
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 由于红黑树的特点，新插入的节点为红色节点
x.red = true;
// 插入时做自平衡需要考虑，父节点，祖父节点，叔叔节点
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) {
// 先对父亲节点左旋，左旋之后插入的节点和父节点位置发生了变化，插入的节点成了原父节点的父节点
// 插入节点变成了xp，原父节点变成了x
// 经历过左旋后的状态和插入节点是其父亲节点的左子节点的状态是相同的
root = rotateLeft(root, x = xp);
// 找到原祖父节点。因为经历过左旋，原祖父节点现在是插入节点的父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 这里注意：如果插入的节点是其父亲节点的左子节点，会忽略上面的if，直接操作xp节点
if (xp != null) {
// 如果插入的节点是其父亲节点的右子节点，那么现在的xp即为原来的x，即插入节点，将插入节点置为黑色
// 如果插入的节点是其父亲节点的左子节点，那么直接操作xp即可
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) {
// 和上面相同，先将父亲节点右旋,经过右旋，插入节点和其父亲节点位置发生了变化。插入的节点成了其父亲节点的父节点
// 插入节点成了xp，原父亲节点成了x
// 经历过右旋后的状态和插入节点是其父亲节点的右子节点的状态是相同的
root = rotateRight(root, x = xp);
// 找到原祖父节点。因为经历过右旋，原祖父节点现在是插入节点的父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 这里注意：如果插入的节点是其父亲节点的右子节点，会忽略上面的if，直接操作xp节点
if (xp != null) {
// 如果插入的节点是其父亲节点的左子节点，那么现在的xp即为原来的x，即插入节点，将插入节点置为黑色
// 如果插入的节点是其父亲节点的右子节点，那么直接操作xp即可
xp.red = false;
if (xpp != null) {
// 将祖父节点置为红色，并对祖父节点进行左旋操作
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
// 删除节点时的自平衡处理
// 这里的x为替代节点
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 删除节点时需要考虑父亲节点，叔叔节点，叔叔节点的两个孩子节点
for (TreeNode<K,V> xp, xpl, xpr;;) {
// 只有一个根节点
if (x == null || x == root)
return root;
// 只有一个根节点，根节点为黑色
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 如果替换节点是红色，将节点变为黑色，不需要做去他操作
// 因为进入到自平衡的情况有两种，一种是已经删除了，替换节点代替删除节点的位置做自平衡处理；一种是节点还未删除，但是将来会直接删除掉
// 若是已经删除了，那么替换节点现在的位置一定是原来位置的父节点，若是替换节点是红色，那么父节点一定是黑色，因此将替换节点的颜色变为黑色，维护原来的平衡
// 若是还未删除，将其变黑还是不变黑都无影响，因为一会就将该节点删除了
else if (x.red) {
x.red = false;
return root;
}
// 如果替换节点是父节点的左子节点
else if ((xpl = xp.left) == x) {
// 如果兄弟节点为红色节点。将兄弟节点变为黑色，将父节点变为红色，对父节点进行左旋
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right; // 这里xpr发生了变化，此时的xpr是原xpr的右子节点
}
// 如果原xpr为红色节点，则这里的xpr为原xpr的左子节点
// 如果原xpr不存在或者为黑色节点，会跳过上面的处理
// 如果x的兄弟节点不存在，将父节点作为当前节点处理
// 因为x是叶子节点，而且是黑色节点，兄弟节点不存在肯定是不平衡的，这时候就让父节点帮忙处理
// 这里说的帮忙，意思是需要借个红节点来平衡
if (xpr == null)
x = xp;
else {
// 兄弟节点为黑色节点
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// 如果兄弟节点的右子节点不存在或者为黑色 并且兄弟节点的左子节点不存在或者为黑色
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 将兄弟节点置为红色，让父节点帮忙处理
xpr.red = true;
x = xp;
}
else {
// 如果兄弟节点的右子节点不存在或者为黑色。注意这里的sl一定是红色节点，因为上面的if语句
if (sr == null || !sr.red) {
// 如果兄弟节点的左子节点存在，将其置为黑色，将兄弟节点置为红色，对兄弟节点进行右旋。继续处理x
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr); // 经过右旋，xpr的左子节点变为xpr的父节点
xpr = (xp = x.parent) == null ?
null : xp.right; // 这时候的xpr为原xpr的左子节点
}
// 这时候sr一定为红色，因为上面的if判断
// 如果兄弟节点存在，将兄弟节点的颜色置为父节点的颜色，如果兄弟节点的右子节点存在，将兄弟节点的右子节点的颜色置为黑色
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
// 如果父节点存在，将父节点颜色置为黑色，将父节点左旋
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
// 最多三次旋转即处理完
x = root;
}
}
}
else { // 对称的
// 兄弟节点为红色。将兄弟节点置为黑色，将父节点置为红色，对父节点右旋，继续处理
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left; // 此时的xpl为原xpl的左子节点
}
// 如果兄弟节点不存在，让父节点帮忙处理
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 {
// 兄弟节点的左子节点为黑色节点。注意这时候的sr一定为红色节点，因为上面的if判断
// 将兄弟节点的右子节点设为黑色，将兄弟节点设为红色，对兄弟节点进行左旋
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; // 这里的xpl为原兄弟节点的右子节点
}
// 这时候兄弟节点的左子节点一定为红色，因为上面的if判断
// 如果兄弟节点存在，将兄弟节点的颜色置为父节点的颜色。如果兄弟节点的左子节点存在，将兄弟节点的左子节点置为黑色
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;
}
}
}
}
}
/**
在MoveRootToFront方法里面有用到，是assert使用的
遍历判断链表结构和树结构是否正确
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
// tp父节点，tl左子节点，tr右子节点，tb前驱节点，tn后继节点
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;
// 如果左子节点存在并且父子关系不正确，或者顺序错误，可以看到这里没有用等号，因为hash相等的情况存在
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
// 如果右子节点存在并且父子关系不正确，或者顺序错误
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
// 如果红色节点的子节点为红色节点。
// 这里有个问题，有些情况如红色节点的其中一个节点为红色，另一个节点不存在，这种也是错误的，但是这里会忽略 t.red && tl!=null && tl.red && tr==null
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;
}
}
}
网友评论