『源码』HashMap源码注释详解

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; /** * 默认的初始容量，必须是2的幂 */ 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; /** * 树退化阈值：红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算）， * 在重新计算存储位置后，当原有的红黑树内节点数量<该值时，则将红黑树转换成链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 最小树形化阈值：当桶数组的容量>该值时，才允许树形化链表（即将链表转换成红黑树） * 否则，若桶内元素超过阈值时，则直接扩容（拆分链表），而不是树形化 * 为了避免进行扩容、树形化选择的冲突，这个值不能小于4 * TREEIFY_THRESHOLD */ static final int MIN_TREEIFY_CAPACITY = 64; /** * 链表基本对象，实现了Map.Entry接口 */ static class Node<K,V> implements Map.Entry<K,V> { final int hash; //用来定位数组索引位置 final K key; V value; Node<K,V> next; //链表的下一个node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } /* ---------------- Static utilities -------------- */ /** * 计算hash * 后面计算下标(n - 1) & hash，体现了桶数组容量为2的幂的优点（(n - 1)低位全为1） */ static final int hash(Object key) { int h; // 低16位与高16位异或，让高16位参与 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * Returns x's Class if it is of the form "class C implements * Comparable<C>", else null. */ static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks 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) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * Returns k.compareTo(x) if x matches kc (k's screened comparable * class), else 0. */ @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如果就是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; } /* ---------------- Fields -------------- */ /** * 桶数组 */ transient Node<K,V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set<Map.Entry<K,V>> entrySet; /** * HashMap中实际存在的键值对数量 */ transient int size; /** * HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时， * 如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作）， * 需要抛出异常ConcurrentModificationException */ transient int modCount; /** * 阈值，当table还未初始化时，该值为初始容量（初始容量默认为16） * 当table被初始化后，也就是为table分配内存空间后，threshold一般等于capacity*loadFactory * HashMap在进行扩容时需要参考threshold */ int threshold; /** * 加载因子（减缓哈希冲突） */ final float loadFactor; /* ---------------- Public operations -------------- */ /** * 构造器 * 提供初始容量，提供加载因子 */ 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; // 数组还未被初始化，该值等于初始容量 // 等到数组初始化后，该值等于capacity*loadFactory this.threshold = tableSizeFor(initialCapacity); } /** * 构造器 * 提供初始容量，使用默认加载因子0.75 */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 默认构造器（默认初始容量16，默认加载因子0.75） * * 只有该构造器使用默认初始容量16，且threshold没有赋值 */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } /** * 构造器 * 使用足够的初始容量装载m中键值对，使用默认加载因子0.75 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } /** * 将参数m中的键值对复制到本HashMap桶数组中，方法为final，不可被覆写 */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // 桶数组还未被初始化 // 根据参数m的键值对数量和本HashMap的加载因子计算出合适的数组容量 // 公式((float)s / loadFactor) + 1.0F中的size是使用float计算的 // +1.0F是因为((float)s / loadFactor)使用float计算，在转换成整数的时候会进行舍入 // 为了保证最终计算出来的size足够大不至于触发扩容，所以进行了+1.0F操作 float ft = ((float)s / loadFactor) + 1.0F; // 确保不会超过最大容量 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) // 桶数组还未被初始化 threshold = tableSizeFor(t); } else if (s > threshold) // 桶数组已经被初始化，并且m的键值对数量超过桶数组阈值，扩容 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; } /** * 获取key对应的value */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 获取key对应的Node，方法为final，不可被覆写 */ final Node<K,V> getNode(int hash, Object key) { 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（链表的首结点） if (first.hash == hash && ((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 { // 从首节点的下一个结点开始，往后检验每一个Node结点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 搜索失败，返回null return null; } /** * 判断HashMap中是否存在该key（true 存在） */ public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } /** * 往HashMap中加入键值对key-value */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * 方法为final，不可被覆写 * 子类可以通过实现afterNodeAccess，afterNodeInsertion方法来增加自己的处理逻辑 * * @param hash 由key计算出来的 hash值 * @param onlyIfAbsent 如果当前位置已存在一个值，是否替换，false是替换，true是不替换 * @param evict 表是否在创建模式，如果为false，则表是在创建模式。 * * @return 如果有相等的key，则返回原有的value，否则返回null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果桶数组还未初始化，则进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 检查桶数组中位置为(n -1) & hash是否为空，如果为空，直接放入（这是放在数组里） if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { // 该位置已有Node，也就是说发生了碰撞 Node<K,V> e; K k; // 该Node中的key正好与要插入的key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果该Node属于红黑树，则进行红黑树插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 遍历链表，找到链表末尾插入键值对（Node） for (int binCount = 0; ; ++binCount) { // 到达链表末尾（e == null） if ((e = p.next) == null) { // 插入键值对（Node） p.next = newNode(hash, key, value, null); // 如果该链表超过化树阈值，则将链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 在链表中找到一个Node中的key正好与要插入的key相等，退出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 等同于p = p.next } } // 对key相等的情况进行处理（覆盖旧value） if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 访问后调用 afterNodeAccess(e); return oldValue; } } // 将记录修改次数加一 ++modCount; // 如果桶数组需要扩容，则进行扩容 if (++size > threshold) resize(); // 插入后调用 afterNodeInsertion(evict); return null; } /** * 初始化桶数组或者将桶数组扩容为原来的两倍，方法为final，不可被覆写 */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 桶数组的原长度（未初始化为0） int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原扩容阈值（未初始化为初始容量，使用默认构造器该值为0） int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 桶数组已初始化 // 如果原容量大于等于最大容量，则将阈值设置为最大（之后再也不进行扩容） if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 桶数组扩容位置！！！ // 如果原容量扩容后（*2）小于最大容量，且原容量大于等于默认初始容量16， // 则更新扩容阈值为原来的两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } else if (oldThr > 0) // 桶数组未初始化，且原扩容阈值大于零（使用含参构造器） // 使用阈值中的值作为桶数组的初始容量 newCap = oldThr; else { // 桶数组未初始化，且原扩容阈值等于零（使用默认构造器） // 使用默认初始容量16 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) { // 该位置上有Node元素 oldTab[j] = null; // 方便垃圾回收 if (e.next == null) // 该Node没有链接其他元素 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 该Node为红黑树节点 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 该Node为链表节点 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 数组长度为2的幂的优势！！！ // hash **** 0 1011 // oldCap 1 0000 // newCap-1 1 1111 // 如果该位为0，则说明散列值hash计算出来的位置与原位置相同 // 如果该位为1，则说明新位置比原位置多oldCap // 则lo链表（低位链表）用尾插法将该位为0的Node链接起来 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // hi链表（高位链表）将该位为1的Node链接起来 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 将链表复制到正确的位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } /** * 将单向链表转换为红黑树（中间借助双向链表），方法为final，不可被覆写 */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 当桶数组还未初始化，或者桶数组的长度小于最小树形化阈值64，则进行扩容操作 // 一般扩容后，过长的链表会拆分到两个不同位置上 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; // hd首节点，tl尾节点 do { // 将链表节点Node转换为红黑树节点TreeNode TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; // 将TreeNode用尾插法链接为双向链表 } while ((e = e.next) != null); // 用双向链表替代原来的单向链表，并转换为红黑树 if ((tab[index] = hd) != null) hd.treeify(tab); } } /** * 将某个Map中的键值对加入到本HashMap中 */ public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } /** * 从HashMap中移除键为key的节点Node（存在返回该节点的值，否则返回空） */ public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * 方法为final，不可被覆写，子类可以通过实现afterNodeRemoval方法来增加自己的处理逻辑 * * @param hash 由key计算出来的 hash值 * @param key 要移除的键值对中的key * @param value 只有当matchValue为true时才有作用 * @param matchValue 如果为true，则移除key和value都匹配的Node * @param movable 如果为false，则在移除节点的时候，不移动其他节点 * @return 返回移除的节点Node（没有该节点则返回null） */ 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; // 数组不为空且数组长度大于零（已初始化），且hash值对应的位置不为空 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; // 首节点的键key与要删除的key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; 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，即让p存储的永远是下一次循环里e的父节点 } while ((e = e.next) != null); } } // node不为空（已经找到目标节点）， // 且不需要对比value值 或者 需要对比value值但是value值也相等（这里用到了短路特性）， // 则进行节点node的移除 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) // node为红黑树节点 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) // node为链表的首节点 tab[index] = node.next; else // 将父节点p的下一个节点指向node的下一个节点（常用的节点删除） p.next = node.next; // 将记录修改次数减一 ++modCount; // HashMap的元素个数减一 --size; // 删除后调用 afterNodeRemoval(node); return node; // 返回被移除的节点 } } return null; } /** * 清除该HashMap中的所有键值对 */ 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; } } /** * 判断HashMap中是否存在该value（true 存在） * 红黑树也是一个双向链表，因此可以和单向链表统一 */ 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; } /** * Returns a {@link Set} view of the keys contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation), the results of * the iteration are undefined. The set supports element removal, * which removes the corresponding mapping from the map, via the * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> * operations. * * @return a set view of the keys contained in this map */ public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } final class KeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<K> iterator() { return new KeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { 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(); } } } /** * Returns a {@link Collection} view of the values contained in this map. * The collection is backed by the map, so changes to the map are * reflected in the collection, and vice-versa. If the map is * modified while an iteration over the collection is in progress * (except through the iterator's own <tt>remove</tt> operation), * the results of the iteration are undefined. The collection * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Collection.remove</tt>, <tt>removeAll</tt>, * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not * support the <tt>add</tt> or <tt>addAll</tt> operations. * * @return a view of the values contained in this map */ public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } 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); } 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(); } } } /** * Returns a {@link Set} view of the mappings contained in this map. * The set is backed by the map, so changes to the map are * reflected in the set, and vice-versa. If the map is modified * while an iteration over the set is in progress (except through * the iterator's own <tt>remove</tt> operation, or through the * <tt>setValue</tt> operation on a map entry returned by the * iterator) the results of the iteration are undefined. The set * supports element removal, which removes the corresponding * mapping from the map, via the <tt>Iterator.remove</tt>, * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and * <tt>clear</tt> operations. It does not support the * <tt>add</tt> or <tt>addAll</tt> operations. * * @return a set view of the mappings contained in this map */ 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(); return removeNode(hash(key), key, value, true, true) != null; } 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(); } } } // Overrides of JDK8 Map extension methods /** * 获取key对应Node的value，如果不存在该Node，则返回默认值defaultValue */ @Override public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; } /** * 如果不存在key，则添加到HashMap中（跟put方法相同） * 如果存在key，且value不为null，则不会覆盖value，否则覆盖value（与put方法相同） * 返回值必然为null */ @Override public V putIfAbsent(K key, V value) { 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-oldValue相匹配的节点中的value替代为newValue */ @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的节点中的value替代为新的value，并返回原value（没有该节点则返回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; } /** * */ @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; 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 { tab[i] = newNode(hash, key, v, first); if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); } ++modCount; ++size; afterNodeInsertion(true); return v; } /** * */ 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 removeNode(hash, key, null, false, true); } return null; } /** * */ @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; 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 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; afterNodeInsertion(true); } return v; } /** * */ @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); } } 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 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; 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(); } } @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(); } } /* ------------------------------------------------------------ */ // Cloning and serialization /** * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and * values themselves are not cloned. * * @return a shallow copy of this map */ @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; } final int capacity() { return (table != null) ? table.length : (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY; } /** * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., * serialize it). * * @serialData The <i>capacity</i> of the HashMap (the length of the * bucket array) is emitted (int), followed by the * <i>size</i> (an int, the number of key-value * mappings), followed by the key (Object) and value (Object) * for each key-value mapping. The key-value mappings are * emitted in no particular order. */ 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); internalWriteEntries(s); } /** * Reconstitutes this map from a stream (that is, deserializes it). * @param s the stream * @throws ClassNotFoundException if the class of a serialized object * could not be found * @throws IOException if an I/O error occurs */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); reinitialize(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new InvalidObjectException("Illegal load factor: " + loadFactor); s.readInt(); // Read and ignore number of buckets int mappings = s.readInt(); // Read number of mappings (size) 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; 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; // Read the keys and values, and put the mappings in the 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); } } } /* ------------------------------------------------------------ */ // iterators abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != 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; } 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); 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 static class HashMapSpliterator<K,V> { final HashMap<K,V> map; Node<K,V> current; // current node int index; // current index, modified on advance/split int fence; // one past last index int est; // size estimate 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; if ((hi = fence) < 0) { HashMap<K,V> m = map; est = m.size; expectedModCount = m.modCount; Node<K,V>[] tab = m.table; hi = fence = (tab == null) ? 0 : tab.length; } return hi; } public final long estimateSize() { getFence(); // force init 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; return (lo >= mid || current != null) ? null : new KeySpliterator<>(map, lo, index = mid, est >>>= 1, 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; 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.key); p = p.next; } } while (p != null || i < hi); if (m.modCount != mc) throw new ConcurrentModificationException(); } } public boolean tryAdvance(Consumer<? super K> 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 { K k = current.key; current = current.next; action.accept(k); 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; } } 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); } } 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() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid || current != null) ? null : 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; } } /* ------------------------------------------------------------ */ // LinkedHashMap support /* * The following package-protected methods are designed to be * overridden by LinkedHashMap, but not by any other subclass. * Nearly all other internal methods are also package-protected * but are declared final, so can be used by LinkedHashMap, view * classes, and HashSet. */ // Create a regular (non-tree) node Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } // For conversion from TreeNodes to plain nodes Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { return new Node<>(p.hash, p.key, p.value, next); } // Create a tree bin node TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { return new TreeNode<>(hash, key, value, next); } // For treeifyBin TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); } /** * Reset to initial default state. Called by clone and readObject. */ void reinitialize() { table = null; entrySet = null; keySet = null; values = null; modCount = 0; threshold = 0; size = 0; } // Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { } // Called only from writeObject, to ensure compatible ordering. 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） * 所以Node可以强转为TreeNode */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 指向父节点 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); } /** * 返回该TreeNode所在红黑树的根节点 */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } /** * 就是保证树的根节点一定要成为双向链表的首节点（没有破坏红黑树结构） */ static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; // 根节点root不为空，且桶数组已初始化 if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; // 根节点root对应的位置 TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 该位置上的第一个节点 if (root != first) { Node<K,V> rn; // root的后一个节点 tab[index] = root; // 将该位置的第一个节点设置为root TreeNode<K,V> rp = root.prev; // root的前一个节点 // 如果root的后节点不为空，则将后节点的前一个结点指向到root的前节点 if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; // 如果root的前节点不为空，则将前节点的后一个结点指向到root的后节点 if (rp != null) rp.next = rn; // 该数组位置上存在Node节点，则将该节点的前一个结点指向到root if (first != null) first.prev = root; root.next = first; // root的后一个结点指向Node（可以为null） root.prev = null; // root的前一个结点置为null（首节点） } assert checkInvariants(root); } } /** * Finds the node starting at root p with the given hash and key. * The kc argument caches comparableClassFor(key) upon first use * comparing keys. */ 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; else if (pl == null) p = pr; 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; else if ((q = pr.find(h, k, kc)) != null) return q; else p = pl; } while (p != null); return null; } /** * Calls find for root node. */ final TreeNode<K,V> getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } /** * Tie-breaking utility for ordering insertions when equal * hashCodes and non-comparable. We don't require a total * order, just a consistent insertion rule to maintain * equivalence across rebalancings. Tie-breaking further than * necessary simplifies testing a bit. */ static int tieBreakOrder(Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; } /** * 将该结点链接的链表（双向链表）转换为红黑树 */ 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) { x.parent = null; x.red = false; // 根节点为黑色 root = x; } else { // 获取当前节点的key和hash 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); TreeNode<K,V> xp = p; // 循环结束条件（插入到叶子节点的孩子） if ((p = (dir <= 0) ? p.left : p.right) == null) { x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x; root = balanceInsertion(root, x); //插入后调整红黑树 break; } } } } moveRootToFront(tab, root); // 确保根节点是双向链表的首节点 } /** * 将红黑树转换成单向链表 */ 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) { // 将TreeNode替换为Node Node<K,V> p = map.replacementNode(q, null); // 尾插法 if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } /** * Tree version of putVal. */ 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, 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) { 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; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { 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.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; 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; int index = (n - 1) & hash; // 计算要删除节点所在的数组位置 // first双向链表头节点、root红黑树根节点、rl根节点的左孩子 TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // succ要删除节点的后节点、pred要删除节点的前节点 TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; // 对双向链表的删除维护！！！ // 要删除节点的前节点为空（要删除节点为头节点） if (pred == null) tab[index] = first = succ; // 头节点指向后节点 else pred.next = succ; if (succ != null) succ.prev = pred; // 头节点为空（双向链表删除节点后，使红黑树为空） if (first == null) return; // 根节点的父节点不为空，获取新的根节点 if (root.parent != null) root = root.root(); /** * 当以下三个条件任一满足时，且满足红黑树条件时， * 说明该位置元素的长度少于6（UNTREEIFY_THRESHOLD），需要对该位置元素链表化 * 1、root == null：根节点为空，树节点数量为0 * 2、root.right == null：右孩子为空，树节点数量最多为2 * 3、(rl = root.left) == null || rl.left == null)： * (rl = root.left) == null：左孩子为空，树节点数最多为2 * rl.left == null：左孩子的左孩子为NULL，树节点数最多为6 */ if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) { tab[index] = first.untreeify(map); // 将红黑树转换为单向链表 return; } // 对红黑树的删除维护！！！ // p调用此方法的节点（要删除节点）、pl要删除节点的左孩子、pr要删除节点的右孩子 // replacement替换节点 TreeNode<K,V> p = this, pl = left, pr = right, replacement; // 1、要删除节点有两个子节点 if (pl != null && pr != null) { // 第一步：找到当前节点的后继节点 // （值大于当前节点值的最小节点，以右子树为根节点，查找它的最左节点） TreeNode<K,V> s = pr, sl; // s要删除节点的右孩子 while ((sl = s.left) != null) // 找到右子树的最左节点（后继节点） s = sl; // 第二步：交换后继节点和删除节点的颜色，最终删除的是后继节点 // 故红黑树是否平衡是以后继节点的颜色来判断的 boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode<K,V> sr = s.right; // sr后继节点的右孩子 TreeNode<K,V> pp = p.parent; // pp要删除节点的父节点 // 第三步：修改当前节点和后继节点的父节点 if (s == pr) { // 如果后继节点与要删除节点的右孩子相等,即要删除节点是后继节点的父节点 // 交换两个节点的位置 p.parent = s; s.right = p; } else { // 如果要删除节点的右子树不止一个节点 TreeNode<K,V> sp = s.parent; // sp后继节点的父节点 // 交换待删除节点和后继节点的的父节点 // 如果后继节点父节点不为null，指定后继节点父节点的孩子节点 if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } // 修改后继节点的右孩子值，如果不为null，同时指定其父节点的值 if ((s.right = pr) != null) pr.parent = s; } // 第四步：修改要删除节点和后继节点的孩子节点 p.left = null; // 要删除节点现在变成后继节点了，故其左孩子为null // 修改删除节点的右孩子指向后继节点的右孩子 if ((p.right = sr) != null) sr.parent = p; // 修改后继节点的左孩子指向删除节点的左孩子 if ((s.left = pl) != null) pl.parent = s; // 修改后继节点的父节点指向删除节点的父节点（为null说明后继节点变为root） if ((s.parent = pp) == null) root = s; else if (p == pp.left) // 要删除节点为父节点的左孩子 pp.left = s; else // 要删除节点为父节点的右孩子 pp.right = s; // 后继节点的右孩子不为空，则替代节点为右孩子 if (sr != null) replacement = sr; else // 否则替代节点为要删除节点 replacement = p; } // 2、删除节点有一个左子节点，左子节点作为替代节点 else if (pl != null) replacement = pl; // 3、删除节点有一个右子节点，右子节点作为替代节点 else if (pr != null) replacement = pr; // 4、删除节点没有子节点，直接删除当前节点 else replacement = p; 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; } 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; } } if (movable) moveRootToFront(tab, r); } /** * 只在HashMap扩容时（resize()）进行调用 * 将一颗红黑树拆分为两颗（小于等于树化阈值，则红黑树转换为单向链表） * * @param map 代表要扩容的HashMap * @param tab 代表新创建的数组，用来存放旧数组迁移的数据 * @param index 代表旧数组的索引 * @param bit 代表旧数组的长度，需要配合使用来做按位与运算 */ 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; 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) 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); } } } /* ------------------------------------------------------------ */ // Red-black tree methods, all adapted from CLR /** * 左旋 */ 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) (root = r).red = false; else if (pp.left == p) pp.left = r; else pp.right = r; r.left = p; p.parent = r; } return root; } /** * 右旋 */ 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) (root = l).red = false; else if (pp.right == p) pp.right = l; else pp.left = l; l.right = p; p.parent = l; } return root; } /** * 插入元素后进行平衡调整（x为插入节点） */ 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; } // 父节点为黑色，或者 父节点为红色且祖父节点为空（不会有这种情况，只是为了赋值xpp） // 则返回根节点 else if (!xp.red || (xpp = xp.parent) == null) return root; // --------------------------------- // 父节点为祖父节点的左孩子 if (xp == (xppl = xpp.left)) { // 祖父节点的右孩子（叔叔节点）不为空且为红色 if ((xppr = xpp.right) != null && xppr.red) { xppr.red = false; // 祖父节点的右孩子（叔叔节点）变为黑色 xp.red = false; // 父节点变为黑色 xpp.red = true; // 祖父节点变为红色 x = xpp; // 将祖父节点作为下一轮循环的当前节点 } // 叔叔节点为黑色（空节点本身也是黑色） else { if (x == xp.right) { // 当前节点为父节点的右孩子 // 将父节点设为新的当前节点，并以其为支点进行左旋 root = rotateLeft(root, x = xp); // 更新新的当前节点的父节点和祖父节点 xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { // 父节点不为空 xp.red = false; // 父节点变为黑色 if (xpp != null) { xpp.red = true; // 祖父节点变为红色 // 以祖父节点为支点进行右旋 root = rotateRight(root, xpp); } } } } // 父节点为祖父节点的右孩子（与上面对称） else { if (xppl != null && xppl.red) { xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } // 叔叔节点为黑色（空节点本身也是黑色） else { if (x == xp.left) { root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } } } /** * 删除元素后进行平衡调整（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; } 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 { // 兄弟节点的右孩子为黑色 if (sr == null || !sr.red) { if (sl != null) // 兄弟节点的左孩子不为空 sl.red = false; xpr.red = true; root = rotateRight(root, xpr); xpr = (xp = x.parent) == null ? null : xp.right; } 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; } 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; } } } } } /** * Recursive invariant check */ 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; } } }