JDK8 HashMap源码行级解析史上最全最详细解析

怼烎@ 2023-06-20 03:56 11阅读 0赞

**HashMap源码解析系列文章**  
[JDK8 HashMap源码行级解析 史上最全最详细解析][JDK8 HashMap_]  
[JDK8 HashMap源码行级解析 红黑树操作 史上最全最详细图解][JDK8 HashMap_ _]  
[JDK8 HashMap源码 putMapEntries解析][JDK8 HashMap_ putMapEntries]  
[JDK8 HashMap源码 clone解析][JDK8 HashMap_ clone]  
[深入理解HashMap：那些巧妙的位操作][HashMap]  
[听说你看过HashMap源码，来面试下这几个问题][HashMap 1]

### 文章目录 ###

*  前言
 *  静态变量
 *  Static utilities
 *  Fields
 *  Public operations
 *   *  构造器
     *  常用操作
 *  Overrides of JDK8 Map extension methods
 *  Cloning and serialization
 *  迭代器
 *   *  iterators
     *  spliterators
 *  LinkedHashMap support
 *  其他

# 前言 #

**源码面前,了无秘密。**

除了红黑树部分，本文对HashMap的1789行源码进行了详细解析。

虽然我觉得前来阅读HashMap源码的同学肯定已经了解了HashMap的常用方法和基本性质，不用我再重复介绍了，但这里我还是简单说一下吧：

*  HashMap的内部实现为哈希桶的数组（即为散列表），哈希桶里面的数据结构可能是单链表结构，也可能是红黑树结构，对数组取下标会指向该哈希桶的头节点；
 *  使用装载因子和阈值两个概念来保证散列表的装填程度不会超过设置的装载因子；
 *  用红黑树结构来保证一个哈希桶内元素过多时的查找效率。

本文将会在代码里把注释写得尽可能地全，以理解源码的各个细节，而在源码片段后则将进行提纲挈领的总结性讲解。本文既适合已经阅读过部分源码的同学，可以来这里查漏补缺，或解决疑惑；也适合从头开始阅读HashMap源码的同学。由于HashMap源码里已经将各个部分进行了分类，所以本文为了方便读者进行查阅，也完全按照源码的分类顺序进行编排。

当然，您在阅读时，可能会以会某种函数执行顺序来进行跳转返回式的阅读（比如，刚用无参构造器构造出来的HashMap，在第一次put元素时，会先执行到resize，多次put后可能会执行到treeifyBin），这种阅读方式可以帮助你很好地理解HashMap的处理过程。

另外，本文不会介绍红黑树相关的操作，我会在另外一篇文章专门介绍。建议读者在遇到红黑树相关函数时，先停止“深度遍历”，等本文内容阅读完毕后再去看，效果更佳，但建议通过当前函数实现来猜测该红黑树操作的大概实现，并找个地方记录下来，为以后研究红黑树操作做个铺垫（其实只要你把当前函数实现看懂了，那个另外的红黑树操作你也能猜个八九不离十）。

# 静态变量 #

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

默认的初始容量，但必须为2的次方。

static final int MAXIMUM_CAPACITY = 1 << 30;

允许的最大容量，这是int值（4字节，32个bit）的正数范围内最大的2的次方。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的装载因子。

static final int TREEIFY_THRESHOLD = 8;

The bin count threshold for using a tree rather than list for a bin. Bins are converted to trees when adding an element to a bin with at least this many nodes. The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree removal about conversion back to plain bins upon shrinkage.   
每一个哈希桶里，刚开始用的数据结构是链表，当超过一个阈值后，需要转换为红黑树。如果当前是链表，需要转为红黑树的阈值就是这个TREEIFY\_THRESHOLD。

static final int UNTREEIFY_THRESHOLD = 6;

The bin count threshold for untreeifying a (split) bin during a resize operation. Should be less than TREEIFY\_THRESHOLD, and at most 6 to mesh with shrinkage detection under removal.   
如果当前哈希桶里的数据结构是红黑树，那么数量少于这个阈值UNTREEIFY\_THRESHOLD时，就会转换为链表。

static final int MIN_TREEIFY_CAPACITY = 64;

The smallest table capacity for which bins may be treeified. (Otherwise the table is resized if too many nodes in a bin.) Should be at least 4 \* TREEIFY\_THRESHOLD to avoid conflicts between resizing and treeification thresholds.   
这是treeification树化的第一个条件，必须满足table的容量大于等于MIN\_TREEIFY\_CAPACITY。

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;
            }
    
            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;
            }
        }

Basic hash bin node, used for most entries. (See below for TreeNode subclass, and in LinkedHashMap for its Entry subclass.) 作为链表数据结构的节点，这个类已经够用了，但要是用作红黑树的节点，还需要继承它并加一些新功能。LinkedHashMap的节点也是一样，需要继承。

*  Node有4个成员变量。key和hash都是final的，因为每个映射的key在创建以后都不应该被改变，这个hash存的也是key的hash。value却不是final的，因为可以改变一个映射对应的value。next即节点后继，这个也不是final的，因为随时都可能增加或删除节点。
 *  `hashCode()`。为一个映射找到它的哈希桶位置肯定是只依靠它的key的hash的，但这个Node类有一个hashCode方法会把key和value的hash值异或起来，再返回。
 *  `setValue()`。为一个映射设置新value时，会返回旧value。
 *  `equals()`。判断两个映射相同，必须两个key和两个value的equals比较都返回true。

# Static utilities #

HashMap提供了一些静态方法方便大家使用。

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

*  这里把key的hashCode与它本身无符号右移16位的异或结果作为返回值。
 *  之所以要这么做，要从HashMap怎么根据hashcode获得table下标讲起：table下标可以通过`hashcode % table大小`算出来，但取余操作的效率还是比较低的，所以jdk里永远把2的n次方作为table的大小，这样就**不必真的去做取余操作，取而代之的用一些位操作就可以代替取余操作了**。比如table大小为 2 5 2^5 25，那么将`hashcode & 0001 1111`同样能够得到hashcode取余 2 5 2^5 25的值（从位操作上来讲，舍弃掉了权值>= 2 5 2^5 25的bit，只保留了权值< 2 5 2^5 25的bit）。用专业一点的话，这里**使用了掩码来得到table下标**。
 *  但是这样有个弊端，就是永远只有低位bit能够影响到计算出来的table下标，而这可能会造成更多的哈希冲突。所以源码里使用了`(h = key.hashCode()) ^ (h >>> 16)`，这样哈希值的高16位还是保持不变（因为无符号右移填充0，0异或任何数是它本身），哈希值的低16位受到高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) {  // 首先检查x是否可以转型为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) &&
                            (as = p.getActualTypeArguments()) != null &&
                            as.length == 1 && as[0] == c) // type arg is c
                            return c;
                    }
                }
            }
            return null;
        }

*  如果参数x的类定义是Comparable接口的**泛型自限定**，则返回其Class对象。这个函数重点就在于泛型自限定了，因为String的类定义是`public final class String implements java.io.Serializable, Comparable<String>, CharSequence`，抽取关键部分信息则是`class String implements Comparable<String>`，所以说String已经是泛型自限定了，所以`if ((c = x.getClass()) == String.class)`可以直接返回。
 *  而其他情况则要复杂一点了，首先需要通过`c.getGenericInterfaces()`获得**接口信息的Type数组**，包含泛型信息（你可以简单把Type理解为更高端的Class，因为它还能包含泛型的类型参数信息，即能包含尖括号里面的信息）。因为参数x可能实现了多个接口，所以需要去遍历`c.getGenericInterfaces()`的返回值，而像Comparable这样的泛型接口，其Type对象肯定是`ParameterizedType`的实例，所以需要先通过`instanceof ParameterizedType`的判断。
 *  `(p = (ParameterizedType)t).getRawType() == Comparable.class`这里，虽然一个接口已经能确定是一个泛型接口了，但它也不一定是Comparable啊，所以需要通过`getRawType()`的返回值和`Comparable.class`进行比较。这里使用`==`操作符是肯定可以的，因为`getRawType()`的返回值类型为`Type`，而`Type`是Java中所有类型的父接口，两边操作数能够**赋值相容**就肯定可以`==`比较。
 *  `as = p.getActualTypeArguments()`这里，虽然能够肯定参数x实现了Comparable接口，但是这里还不能确定其类定义符合泛型自限定啊，所以需要通过`getActualTypeArguments()`获得尖括号里面的类型参数，其返回值是一个Type数组。然后再通过`as.length == 1 && as[0] == c`，如果`as[0] == c`了，那么就说明Comparable尖括号里的类型就是参数x的类型本身了。
 *  有个判断`as.length == 1`，这里加判断是因为如果参数x实现的是Comparable接口的原生类型的话（即类定义里Comparable后面没有尖括号），那么这个length为0。

--------------------

Returns k.compareTo(x) if x matches kc (k’s screened comparable class), else 0.

static int compareComparables(Class<?> kc, Object k, Object x) { 
            return (x == null || x.getClass() != kc ? 0 :
                    ((Comparable)k).compareTo(x));
        }

*  执行这个函数前，已经执行过了前面讲解的`comparableClassFor`的了。即参数`k`执行`comparableClassFor`后返回了非null值`kc`。
 *  有了前提条件，不确定的就只有参数`x`了。这里需要`x.getClass() == kc`，即必须x的实际类型和k的实际类型一样，就算`x的实际类型`是`k的实际类型`的子类也不可以（如果父类是Comparable的自限定，那么子类也是可以和父类的实例进行compareTo比较的，看来这个函数的要求比较严格）。

--------------------

Returns a power of two size for the given target capacity. 根据目标容量返回一个2的次方再作为容量。如果cap刚好是2的次方，那么此函数返回其本身；如果不刚好是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;
        }

*  先不要管最前面减一和最后面加一的操作，先理解这五步 位或 的操作。看下图，先假设n的bit为`000000...01XXXXXXXXXX...XXXXX`，这里的1代表的是左起的第一个1，后面的X代表不确定（0或1）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]

*  可见刚开始的时候，只知道n的bit位最前面有一个1。但执行了`n |= n >>> 1`后，就能确定前面有`1*2`个1了；执行了`n |= n >>> 2`后，就能确定前面有`2*2`个1了。按照这个过程，执行了`n |= n >>> 16`，就能确定前面有`16*2`个1了。但是**int总共才4个字节，32个bit，也就是说，执行完这5次位或后，左起第一个1后面的所有bit都将变成1**，只不过如果n比较小的话，就只需要少于5次的位或就可以了。
 *  之所以有最后的`n+1`操作，是因为前面的位或操作已经让左起第一个1直到最后的bit都变成了1，形如`000111...11111`，此时再加1，就可以使得n变成2的次方。此函数的目的就是返回2的次方作为容量。
 *  之所以有前面的`int n = cap - 1`操作，是因为如果参数cap刚好是2的次方时，此函数希望返回这个数本身。比如cap是`1000`：如果没有减一操作，那么执行完位或操作后，变成了`1111`，再加个1，就变成了`10000`；但现在有了减一操作，减一后为`0111`，再执行位或操作后，还是`0111`，再加个1，就变回它本身`1000`了。
 *  最后的`(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1`，就是最大容量的判断，最终确定的容量不能比`MAXIMUM_CAPACITY`还大了。MAXIMUM\_CAPACITY的定义是`1 << 30`即`01000...000`，因为有符号数的最高位bit是符号位，所以它已经是正数范围内最大的2的次方了。如果五次位或算出来的n比`1 << 30`还大（那么肯定是`01111...111`），再加个1就得溢出了。

# Fields #

The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two. (We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.) 构造时会初始化为null，必要时会再分配大小。table的大小肯定是2的次方。

transient Node<K,V>[] table;

HashMap内部实现的真面目，其实就是Node泛型类的数组。这个Node是之前讲解的那个静态内部类，这个table就是我们平常说的哈希桶，table下标就是哈希桶的位置，table的大小就是HashMap的capacity容量。

--------------------

Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and values().

transient Set<Map.Entry<K,V>> entrySet;

调用`entrySet()`后，会把返回结果保存在这个成员变量上。

--------------------

The number of key-value mappings contained in this map.

transient int size;

map里映射的数量。我们常说的map的大小就是指size，换个说法，那就是迭代器可以移动的次数。

--------------------

The number of times this HashMap has been structurally modified Structural modifications are those that change the number of mappings in the HashMap or otherwise modify its internal structure (e.g., rehash). This field is used to make iterators on Collection-views of the HashMap fail-fast. (See ConcurrentModificationException).

transient int modCount;

用来统计结构化修改的次数。增加映射、删除映射都属于结构化修改；再哈希会重新生成table，所以也是结构化修改。这个成员被用来检测快速失败。

--------------------

The next size value at which to resize (capacity \* load factor).(The javadoc description is true upon serialization. Additionally, if the table array has not been allocated, this field holds the initial array capacity, or zero signifying DEFAULT\_INITIAL\_CAPACITY.)

int threshold;

这个指的是映射的数量，当映射数量超过了这个阈值，就需要再哈希。注意它不再是transient的了。

--------------------

final float loadFactor;

装载因子。注意它是final的，却不再是transient的了。装载因子的计算公式就是`映射数量 / 容量`即`size / capacity`。

--------------------

注意到，**HashMap的成员变量居然没有一个叫capacity的，看来是作为table成员变量的大小而隐式存在的了**。

# 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;
            this.threshold = tableSizeFor(initialCapacity);
        }

我们知道，tableSizeFor函数算出来的是capacity，和这个threshold明显是两个概念（难不成我发现了jdk源码的错误吗，当然不是）。但capacity是作为table的大小而隐式存在的，而这个构造器里很明显还没有去初始化这个table引用，看来只是把容量暂时放到threshold成员变量里，在之后初始化table时肯定会进行修正的。

public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

如果没有给初始装载因子，会使用静态变量的装载因子。

public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

如果装载因子和容量都没有给，会使用静态变量的装载因子，但threshold会被初始化为0。

public HashMap(Map<? extends K, ? extends V> m) { 
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

HashMap的拷贝构造函数。会调用到putMapEntries。

## 常用操作 ##

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //m的类型参数是? extends，所以只能使用泛型代码的出口，比如get函数
            int s = m.size();
            if (s > 0) { //前提是传入map的大小不为0
                if (table == null) {  // 说明是拷贝构造函数来调用的putMapEntries，或者构造后还没放过任何元素
                    //先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。
                    //但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1
                    float ft = ((float)s / loadFactor) + 1.0F;
                    //如果小于最大容量，就进行截断；否则就赋值为最大容量
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    //虽然上面一顿操作猛如虎，但只有在算出来的容量t > 当前暂存的容量(容量可能会暂放到阈值上的)时，才会用t计算出新容量，再暂时放到阈值上
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                //说明table已经初始化过了；判断传入map的size是否大于当前map的threshold，如果是，必须要resize
                //这种情况属于预先扩大容量，再put元素
                else if (s > threshold)
                    resize();
                //循环里的putVal可能也会触发resize
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { //下面的Entry泛型类对象，只能使用get类型的函数
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }

*  putMapEntries可能由拷贝构造函数调用，也可能被putAll或者clone调用到。
 *  `float ft = ((float)s / loadFactor) + 1.0F`这里最后的加1，是因为不考虑容量必须为2的幂的情况下，`(float)s / loadFactor`能算出来一个刚好够大的capacity，使得size刚好不会大于threshold，但由于这个除法式子一般都会算出来小数，所以**算出来的小数容量必须向上取整**，所以这里最后要加1。
 *  `if (t > threshold)`这里的threshold：如果是刚用无参构造器构造出来的HashMap，由于没有初始化，所以threshold是int的默认值0；如果是那两个有参构造器，那么threshold的值就是暂存下来的capacity。
 *  `else if (s > threshold)`这里之所以不写成`else if (s + size> threshold)`，是因为HashMap的“懒汉模式”机制（类似于HashMap的构造器，等构造完了table还是没有初始化的）。而且这样写可以避免过大地分配空间，如果已经`s > threshold`了，那么两个map取并集，就算当前map是传入map的真子集，当前map的容量也最终肯定是不够装的，所以当`s > threshold`时这里必须得resize。而其他情况都不一定了，所以可能再次resize的任务就留给了循环里的putVal，size超过threshold时putVal也会resize的，但这样就是需要的时候才resize。

public int size() { 
            return size;
        }
        public boolean isEmpty() { 
            return size == 0;
        }

size就是我们常说的map的大小，即map中映射的数量。

Returns the value to which the specified key is mapped, or `null` if this map contains no mapping for the key.   
More formally, if this map contains a mapping from a key `k` to a value `v` such that `(key==null ? k==null : key.equals(k))`, then this method returns `v`; otherwise it returns `null`. (There can be at most one such mapping.)   
A return value of `null` does not *necessarily* indicate that the map contains no mapping for the key; it’s also possible that the map explicitly maps the key to `null`. The `containsKey` operation may be used to distinguish these two cases.

public V get(Object key) { 
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

此函数会根据key获得该映射对应的value，如果该映射存在的话。但从函数实现来看，此函数返回null有两种可能：

1.  不存在以形参作为key的mapping
2.  存在以形参作为key的mapping，但对应的value为null

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) { //first会指向该哈希桶的首节点
                if (first.hash == hash && // 首先检查首节点的key是否与形参相同。虽然hash值相同，但不一定是相同的
                    ((k = first.key) == key || (key != null && key.equals(k))))//如果地址相同，或者equals判定成功
                    return first;
                if ((e = first.next) != null) { //如果首元素还有后继
                    if (first instanceof TreeNode)//如果是红黑树
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do { //如果是链表，遍历所有元素，如果找到相同的key，返回该mapping
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;//如果哈希桶所有key都不与形参相同，那么返回null
        }

*  getNode通过形参hash找到table下标，通过形参key找到含有相同key的mapping。如果找不到这样的映射返回null。
 *  如果该哈希桶的数据结构为红黑树（通过判断首节点是否为TreeNode的实例），那么调用TreeNode类的`getTreeNode`方法。`getNode`做了基本的判断和链表的处理，而剩下红黑树的处理则交给了`getTreeNode`。

public boolean containsKey(Object key) { 
            return getNode(hash(key), key) != null;
        }

containsKey操作。如果含有该key的映射都存在的话，那么该key自然也肯定存在了。上面的`get`如果返回了null，可以通过`containsKey`来确认到底是哪种情况。

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

put操作。将key和value作为一个映射放入map中，如果该映射已经存在，那么旧的value会被替换掉。

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;
            if ((p = tab[i = (n - 1) & hash]) == null) // 如果该table下标所在哈希桶没有元素
                tab[i] = newNode(hash, key, value, null);
            else {  // 如果该table下标所在哈希桶有元素，此时p为这个哈希桶的首节点（p = tab[i = (n - 1) & hash]）
                Node<K,V> e; K k;
                if (p.hash == hash && //如果hash值相同，但也不一定是相同元素(是equal的)，所以需要下面的判断
                    ((k = p.key) == key || (key != null && key.equals(k))))//能通过==判断说明是同一个对象了；如果不是，那么调用equals来判断
                    e = p;//p是哈希桶里与形参相同的那个既存元素（与形参重复了），这里让e也指向既存元素
                else if (p instanceof TreeNode)//与首节点不equal，且该哈希桶为红黑树
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { //与首节点不equal，且该哈希桶为链表，需要与首节点后面的所有元素都进行比较
                    for (int binCount = 0; ; ++binCount) { //由于p已经是该哈希桶的首节点了，所以binCount计数是从第二个节点开始算的
                        if ((e = p.next) == null) { //e指向p的后继
                        //说明已经遍历过链表里所有元素，且所有元素都和形参不相同，这里遍历到最后元素，所以后继为null才进入这个if
                        //如果在这个if里break了，那么e肯定为null
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1是因为从第二个节点开始循环的
                                treeifyBin(tab, hash); //树化这个哈希桶，hash形参能计算出table下标
                            break;
                        }
                        if (e.hash == hash && //现在e是p的后继，这里和上面一样判断相等的操作
                        //如果在这个if里break了，那么e肯定不为null
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;  //往后移动
                    }
                }
                if (e != null) {  // 从上面可以看出，如果e不为null，那么说明e指向的就是哈希桶里与形参相同的那个既存元素
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null) // 如果onlyIfAbsent为false，那么旧value被替换为新value
                    // 如果onlyIfAbsent为true，且旧value为null，那么旧value被替换为新value
                    // 如果onlyIfAbsent为true，且旧value不为null，那么旧value不会被替换
                    // onlyIfAbsent顾名思义，当它为true时，只有当value缺席（旧value为null）时，才会替换
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;//不管替没替换，都会把旧value返回
                }
            }
            ++modCount;//上面如果执行了return oldValue，也就不会到这里，因为替换value不属于结构性修改；其他情况则肯定是添加了新节点
            if (++size > threshold)//如果超过了阈值，则再哈希
                resize();
            afterNodeInsertion(evict);
            return null;
        }

*  如果是刚构造出来的HashMap，table还没有初始化过（table是个null），那么会执行到`n = (tab = resize()).length`的resize方法。
 *  函数逻辑主要从`if ((p = tab[i = (n - 1) & hash]) == null)`这里开始，此时`p`指向了该哈希桶的第一个元素，这样，将分为这几种情况：
    
     *  如果`p`为null，那么好办，直接创建个新节点放在该下标位置就行。
     *  如果`p`不为null，那么首先和这第一个元素进行比较。如果与第一个元素相等，那么进入`if (e != null)`分支。
     *  如果`p`不为null，且传入元素与`p`不相等，且`p`为TreeNode实例，那么说明该哈希桶为红黑树结构，则把任务交给putTreeVal函数。
     *  如果`p`不为null，且传入元素与`p`不相等，且`p`为Node实例，那么说明该哈希桶为单链表结构。那么需要遍历该哈希桶内所有节点，并判断各节点是否传入节点相同，如果有既存的相同节点，则进入`if (e != null)`分支，然后根据onlyIfAbsent参数执行相应的替换策略，如果没有，则该哈希桶新增一个映射。主要逻辑都在`for (int binCount = 0; ; ++binCount)`循环里。
 *  分析`for (int binCount = 0; ; ++binCount)`循环的处理过程：
    
     *  循环的主要结构为`先e = p.next 再p = e`，因为在此之前p是该哈希桶的首元素，所以这会使得e不断指向下一个节点。循环中，`e`为当前要比较的那个元素，而`p`则保持了`e`的前驱。
     *  在某次循环中，如果当前元素`e`与传入元素判定相等，说明找到了相同元素，那么break出循环，进入`if (e != null)`分支。
     *  如果当哈希桶里所有元素都与传入元素不相同，那么会进入`if ((e = p.next) == null)`分支，进入后p指向哈希桶链表的尾元素（此时`e`已经为null，幸好`p`保存了引用）。然后创建新元素，并让尾元素的后继指向新元素。但添加新元素后，需要检测当前哈希桶元素个数是否有超过TREEIFY\_THRESHOLD，如果超过，则需要调用`treeifyBin`函数（给`treeifyBin`函数以hash值，以便通过hash值找到table下标进而得到该下标哈希桶的首元素，毕竟此时`p`已经指向尾元素了）。
 *  进入`if (e != null)`分支说明找到了相同元素，根据onlyIfAbsent执行不同的替换策略，不论有没有用新value来替换旧value，都不算是“结构化修改”，所以会提前return，modCount不会增加。

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

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) {  
                 //table已经被初始化过了，如果容量已经是MAXIMUM_CAPACITY，那么也不可能再resize了，所以设为int最大值
                 //所以这里直接return
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // 装载因子不变，所以容量翻倍，阈值也翻倍
            }
            // 说明旧容量为0即oldTab为null即table成员变量还没初始化。用的是有参构造器的initialCapacity形参，
            // 因为这个形参会通过tableSizeFor算出一个新容量暂时放到threshold成员变量上去，所以进入这个else if
            // 代表这个map刚用有参构造器构造了，但还没往里面放过东西呢
            else if (oldThr > 0)
                newCap = oldThr;//oldThr此时只是暂时放容量的，所以赋值给newCap
            // table成员没初始化，且threshold成员被给了默认值0。代表这个map使用无参构造器构造后，还没放过东西呢
            else {                
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            // 经过上面的if else后，newCap肯定有值了，但newThr却可能还没赋值，
            // 可能是因为else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)，
            // 或者是上面的else if (oldThr > 0)分支
            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) { //否则table还没初始化
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {  //遍历每一个哈希桶，e可能是链表，可能是红黑树
                        oldTab[j] = null; //将旧table的某个哈希桶置为空引用
                        if (e.next == null) //如果哈希桶只有一个元素
                            newTab[e.hash & (newCap - 1)] = e; //这里找到table下标的操作相当于 % newCap
                        //否则都是桶里有多个元素的情况，即e.next不为null
                        else if (e instanceof TreeNode) //如果该哈希桶是红黑树
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {  // //如果该哈希桶是链表，且会保存顺序
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do { 
                                // 在do的逻辑里，是为了把e存到low或者high链表里
                                // 在do的逻辑里，next只是存一下e的下一个元素
                                next = e.next;
                                // 现在多了一个bit能到影响元素的新table下标，所以看这个bit是否等于0
                                // 如果这个bit等于0，说明新table下标和旧table下标是一样的
                                if ((e.hash & oldCap) == 0) {  
                                     // 如果low链表的head和tail还没初始化，这里只要执行过一次，head和tail都不会是null的
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;// 把e赋值给tail的后继
                                    loTail = e;//更新tail
                                }
                                // 如果这个bit等于1，说明新table下标和旧table下标不一样的
                                else { 
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);//将do逻辑里存的next赋值给e，把e这个指针往后移动，因为do逻辑已经处理了e
                            // 如果哈希桶里，所有元素的那个bit都为1，那么它们都会存到high链表里去。自然low链表为null
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            // 如果哈希桶里，所有元素的那个bit都为0，那么它们都会存到low链表里去。自然high链表为null
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

*  解释下英文注释：当table是null时，threshold成员变量是用来暂存size的。如果table已经初始化，那么哈希桶里面的元素要么处于该table下标，要么处于该table下标再加某个2的幂。
 *  整个函数的过程分为两部分，前半部分是根据各种情况，计算出newCap新容量和newThr新阈值：
    
     *  进入`if (oldCap > 0)`分支说明table已经初始化过了，不再为null了。如果发现旧容量是最大容量，那么就把阈值设为`Integer.MAX_VALUE`即int的最大值，因为到达最大容量后也就不可能再次resize了。最大容量是 2 30 2^\{30\} 230，如果当前容量是 2 29 2^\{29\} 229，那么resize会进入到`else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)`，这里会把新容量赋值为 2 30 2^\{30\} 230，但这个if判断通不过。然后在之后的`if (newThr == 0)`里，会把新阈值设为`Integer.MAX_VALUE`。
     *  进入`else if (oldThr > 0)`分支说明table还没初始化过（从oldCap大于0推断出），会把暂存了容量的threshold成员取出来，赋值给新容量。
     *  进入最后的`else`分支，说明使用的构造器是无参构造器，所以才会table没初始化，threshold被给默认值0。
     *  而`if (newThr == 0)`分支则最终都会进入，并给newThr赋值。
 *  `Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]`之前会把newCap和newThr都算出来，并用newCap作为新table的大小来进行初始化。
 *  整个函数的过程的后半部分才是真正的resize操作，如果oldTab不为null，那么需要将原table里的所有元素进行再哈希。过程是一个双层循环，外层的for循环，和里面的do while循环。首先分析外层的for循环：
    
     *  for循环是为了依次遍历各个哈希桶，所以循环变量`j`从`0`变化到`capacity-1`。
     *  `e`开始时会指向该哈希桶的首元素，并判断`e`是否为null。如果`e`为null，说明该哈希桶没有元素，则不需要处理；如果`e`不为null，说明该哈希桶有元素，则需要处理：
        
         *  如果该哈希桶里只有一个元素，那么好办，直接把该元素放在新table的新下标`e.hash & (newCap - 1)`；
         *  如果该哈希桶里有多个元素，且`e`为TreeNode实例（红黑树结构），那么把任务交给split函数；
         *  如果该哈希桶里有多个元素，且`e`为Node实例（单链表结构），那么把任务交给内层do while循环。
 *  而内层的do while循环做的事情其实就是将单链表分离为low链表和high链表（因为现在hash值又多了一个bit能影响到最终得到的table下标，如果该bit为0，那么元素还在原地，即在low链表里；如果该bit为1，那么元素所在table下标 = 原下标 + oldCap，即在high链表里）
 *  举例说明链表分离的过程，假设现在的容量是`0b10000`即`16`，那么可能的table下标范围为`0b0000 - 0b1111`，即**能影响到元素所在table下标的bit只有后4位bit`0b????`**。假设有四个元素，它们的hash值的最后4位bit都是`XYZQ`，由于当前容量`16`的限制，它们会被放置到同一个哈希桶（table下标为`0bXYZQ`）里，如下图所示；现在resize后，容量升为`0b100000`即`32`，所以现在**能影响到元素所在table下标的bit只有后5位bit`0b?????`，但相比之前，只有右起第5位bit可能发生变化。所以，如果这个关键bit为0，那么元素还是处于原table下标，如果这个关键bit为1，那么元素处于 原table下标+旧容量 的新下标。**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]
 *  上图通过颜色来表示不同的元素，注意链表分离后，它们也能保持之前的相对位置（具体看源码，因为按原顺序处理链表的元素，所以有这个的保证）。

final void treeifyBin(Node<K,V>[] tab, int hash) { 
            int n, index; Node<K,V> e;
            //如果size是小于MIN_TREEIFY_CAPACITY，那么不会进行树化，只是resize
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            else if ((e = tab[index = (n - 1) & hash]) != null) { //e指向首元素
                TreeNode<K,V> hd = null, tl = null;
                do { 
                    TreeNode<K,V> p = replacementTreeNode(e, null);//用e来new一个TreeNode实例
                    if (tl == null)//如果head和tail都还没有赋值过
                        hd = p;
                    else { //如果head和tail已经赋值过，那么把p和tail相互连起来（p作为新tail放在后面）
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;//更新tail
                } while ((e = e.next) != null); //如果e的后继不为空，让e往后移动
                //现在执行完，只是让原链表元素保持原来顺序全部替换为TreeNode实例，然后将它们之间的前驱后继连起来，成为双向链表
                if ((tab[index] = hd) != null)
                    hd.treeify(tab); //调用首元素的treeify方法
            }
        }

*  此函数用来树化参数`hash`代表的那个哈希桶，把其结构变成哈希桶。但如果size小于MIN\_TREEIFY\_CAPACITY，则不能树化，只能再次resize。因为这种情况被认为是容量太小才导致哈希桶太挤（哈希桶节点超过8个）的。
 *  树化过程是用Node实例的信息来new出新的TreeNode实例，利用循环将各个TreeNode的双链表结构连接起来。循环完毕后，执行`tab[index] = hd`，将数组下标指向双向链表头节点，这样，以前的Node实例的单链表就丢掉了。
 *  TreeNode实例的双链表结构有了，就可以遍历它们了。有了这个前提，最后再调用TreeNode的treeify方法，将红黑树结构建立起来。

public void putAll(Map<? extends K, ? extends V> m) { 
            putMapEntries(m, true);
        }

HashMap的拷贝构造函数。

public V remove(Object key) { 
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

*  删除特定的key对应的mapping。返回null代表两种情况：1.map中没有这个key 2.map中有这个key，也确实删除掉了这个mapping，但mapping的旧value是null。
 *  如果matchValue参数（removeNode的第四个参数）为true，还会多一种情况：虽然map中有这个key，但由于参数value与mapping的value不相同，所以返回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;
            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;
                //p是哈希桶的第一个节点，判断参数key是否与p.key相同
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;//node存找到的那个相同的Node
                //如果不和第一个相同，那就和剩下的比较
                else if ((e = p.next) != null) { 
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //交给红黑树操作
                    else { 
                        do { //e为当前循环处理的节点
                            if (e.hash == hash && //前提是hash值相同，key才可能相同
                                ((k = e.key) == key || //如果是同一个引用
                                 (key != null && key.equals(k)))) {  //如果不是同一个引用，则避免null引用
                                node = e; //找到了相同节点
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                //如果找到了相同节点(node != null)，并且
                //如果matchValue为false，或者
                //如果matchValue为true（需判定成功两个value相等），且传入value与node.value是同一个引用
                //如果matchValue为true（需判定成功两个value相等），且不是同一个引用，那么需要equals判定成功
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) { 
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //交给红黑树操作
                    else if (node == p) //如果哈希桶是链表结构，且相同节点是链表头节点，则头节点的后继作为新头节点
                        tab[index] = node.next;
                    else  //如果哈希桶是链表结构，且相同节点不是链表头节点，则此时p为相同节点(node)的父节点
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

*  要删除节点，必须先找到这个Node。此函数先与哈希桶里第一个节点进行比较，如果不相同，再与剩余节点比较。
 *  与剩余节点比较时，如果该哈希桶是红黑树结构（`if (p instanceof TreeNode)`），那么把任务交给getTreeNode函数；如果该哈希桶是链表结构，那么把任务交给do while循环。
 *  找到相同节点后（`node != null`），如果该哈希桶是红黑树结构，那么把任务交给removeTreeNode函数；如果哈希桶是链表结构，就改变引用的指向来做到删除节点。
 *  改变引用时，如果相同节点是第一个节点（`else if (node == p)`），那么好办，直接让数组下标指向头节点的后继；如果相同节点不是第一个节点，那么最后break之前，do while循环做过的动作是`p = e; e = e.next;`，所以`p`会是相同节点`node/e`的父节点。所以删除操作是`p.next = node.next`。

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;//将每个数组下标的引用置为null
            }
        }

clear函数将清空所有mapping。

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是否当前value相等
                            (value != null && value.equals(v)))
                            return true;//一旦找到一个，就返回
                    }
                }
            }
            return false;
        }

containsValue返回true代表至少有一个相同的value在map里。

--------------------

这里我先提及一下HashMap从AbstractMap那里继承而来的两个成员：

transient Set<K>        keySet;
        transient Collection<V> values;

Returns a `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 `remove` operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the `Iterator.remove`, `Set.remove`, `removeAll`, `retainAll`, and `clear` operations. It does not support the `add` or `addAll` operations.

public Set<K> keySet() { 
            Set<K> ks = keySet;
            if (ks == null) { 
                ks = new KeySet();
                keySet = ks;
            }
            return ks;
        }

keySet函数直接使用了从AbstractMap继承而来的成员keySet，该函数会使得keySet成员一种单例模式。

final class KeySet extends AbstractSet<K> { 
            public final int size()                 {  return size; }
            public final void clear()               {  HashMap.this.clear(); }//调用外部类的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) { //该迭代过程中，也是不允许有别的线程来做结构化修改，所以检查modCount
                    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();
                }
            }
        }

*  该KeySet内部类是成员内部类，所以持有外部类HashMap的引用，自然也可以获得外部类的成员和调用外部类的方法。
 *  这个set是该HashMap作为key的视图，这点很重要。**就是说，根本没有把HashMap里各个映射里的key单独复制出来，再做成一个集合，而是间接地对外部类HashMap的table成员进行读或者写。**
 *  如果KeySet正在迭代过程中，HashMap被修改了，那么将会发生未定义的行为。
 *  KeySet支持删除操作。支持`Iterator.remove`，等讲到了迭代器再说这个（可以猜想，这个迭代器肯定也是一种视图的作用）。
 *  支持`Set`接口的`remove`和`clear`函数，因为它已经重写实现了。它还支持`Set`接口的`removeAll`和`retainAll`函数，但它却没有重写：因为AbstractSet里面已经实现好了`removeAll`函数，并且内部会调用到重写后的`remove`，或者调用到重写后的`iterator`方法返回的迭代器的`remove`（前者是自己这个集合的大小 > 传入的集合，后者是自己这个集合的大小 <= 传入的集合）；同样的，AbstractCollection里面已经实现好了`retainAll`函数，并且内部会调用到重写后的`iterator`方法返回的迭代器的`remove`；

Returns a `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 `remove` operation), the results of the iteration are undefined. The collection supports element removal, which removes the corresponding mapping from the map, via the `Iterator.remove`, `Collection.remove`, `removeAll`, `retainAll` and `clear` operations. It does not support the `add` or `addAll` operations.

public Collection<V> values() { //同样是单例模式
            Collection<V> vs = values;
            if (vs == null) { 
                vs = new Values();
                values = vs;
            }
            return vs;
        }
    
        final class Values extends AbstractCollection<V> { //注意继承的是AbstractCollection
            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();
                }
            }
        }

分析完全类似。但注意这个成员内部类继承的是AbstractCollection：

*  首先肯定不能继承AbstractSet了，因为value是可能重复的。
 *  但为什么不继承AbstractList呢，我觉得是List这个概念太具体了，而这个`values`不需要这么具体的东西（假如要是继承的AbstractList，那么要必须要实现的方法就是`get() & size()`方法，瞬间变成了一个可以随机存取的列表了，但我这可是HashMap，怎么可能按索引来取值呢）。
 *  综上所述，所以继承的是AbstractCollection。

另外，你会注意到继承AbstractSet和继承AbstractCollection时，需要实现的东西都是一样的。这一点看完源码你会发现：

*  AbstractSet虽然继承了AbstractCollection，但AbstractSet自身并没有添加任何抽象方法。
 *  AbstractCollection这个抽象类，里面的抽象方法也只有`iterator() & size()`方法而已。所以上面两个成员内部类KeySet和Values在类定义时，只是实现了两个抽象方法，且重写了几个方法（虽然这几个方法已经有实现，但重写后让方法直接去调用外部类对象的方法，这样让逻辑更加清晰，也更加符合“视图”这个概念）。

Returns a `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 `remove` operation, or through the `setValue` 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 `Iterator.remove`, `Set.remove`, `removeAll`, `retainAll` and `clear` operations. It does not support the `add` or `addAll` operations.

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))//首先检查是否为Entry实例
                    return false;
                //转成Entry接口，这样可以接受任何Entry的实现类，而不是只能接受HashMap的Node内部类
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Node<K,V> candidate = getNode(hash(key), key);//通过key找到映射
                return candidate != null && candidate.equals(e);//equals会判断key相等和value相等
            }
            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();
                }
            }
        }

*  分析类似。但`contains`和`remove`方法需要写逻辑，其实就是加些必要的判定（这都是因为这两个方法的形参类型是Object导致的，要是形参类型是`Map.Entry<K,V>`就不用了）。

# Overrides of JDK8 Map extension methods #

接下来介绍一些JDK8里Map接口新增的一些方法。

@Override
        public V getOrDefault(Object key, V defaultValue) { 
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
        }

如果存在含有key的映射，那么返回该映射的value；否则，返回defaultValue。注意，`key`的类型是Object，因为`getNode`的第二个参数也只是需要为Object而已。

@Override
        public V putIfAbsent(K key, V value) { 
            return putVal(hash(key), key, value, true, true);
        }

此函数终于把putVal的`onlyIfAbsent`形参派上了用场，让`onlyIfAbsent`为True。这样，只有当映射对应的旧value为null时，才能把旧value替换为新value，并返回旧value。但如果新value是null，且该函数返回了null，那么就有几种可能：

*  map没有含有入参`key`的映射，所以putVal会新增一个映射，新增映射后，putVal返回值必为null。
 *  map有含有入参`key`的映射，但该映射的旧value不为null，那么不能替换，所以还是返回null。
 *  map有含有入参`key`的映射，且该映射的value也为null，那么发生替换，返回了旧value——null。

@Override
        public boolean remove(Object key, Object value) { 
            return removeNode(hash(key), key, value, true, true) != null;
        }

此函数终于把removeNode的`matchValue`形参派上了用场，让`matchValue`为True。removeNode是否返回null分为几种情况：

*  map没有含有入参`key`的映射，所以没法删除节点，返回值必为null。
 *  map有含有入参`key`的映射，但传入value和旧value不相等，所以也返回null。

上面这两种情况则会导致此函数返回false。

@Override
        public boolean replace(K key, V oldValue, V newValue) { 
            Node<K,V> e; V v;
            if ((e = getNode(hash(key), key)) != null &&//首先必须，有含有key的映射
                ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { //然后入参oldValue和映射的旧value是相等的
                //然后才能，newValue替换映射的旧value
                e.value = newValue;
                afterNodeAccess(e);//通看用到afterNodeAccess，发现全在映射替换value后调用，但LinkedHashMap里才会实现afterNodeAccess
                return true;
            }
            return false;
        }
    
        @Override
        public V replace(K key, V value) { 
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) != null) { //必须，有含有key的映射
                V oldValue = e.value;
                e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
            return null;
        }

*  第一个重载版本的replace，由于入参已经有了旧value和新value了，所以返回值是布尔型的。返回true则代表肯定替换成功了。
 *  第二个重载版本的replace，入参`value`的含义就是新value。由于返回值类型为`V`，所以返回null时有歧义（到底是`return null`，还是`return oldValue`）。

If the specified key is not already associated with a value (or is mapped to `null`), attempts to compute its value using the given mapping function and enters it into this map unless `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;//必要时进行resize
            if ((first = tab[i = (n - 1) & hash]) != null) { //如果哈希桶里第一个节点不为null
                if (first instanceof TreeNode)//如果第一个节点为红黑树节点，那么交给getTreeNode
                    old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);//同时赋值给old和t，不能浪费TreeNode类型，免得之后又得强转
                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);
                    //如果能找到相同节点，那么old和e都不为null
                    //如果不能找到相同节点，那么old和e都为null
                }
                V oldValue;
                if (old != null && (oldValue = old.value) != null) { //如果有相同节点，且映射的旧value不为null
                    afterNodeAccess(old);
                    return oldValue;//那么直接返回旧value，因为是if absent缺席的时候
                }
            }
            //执行到这里说明，要么没有相同节点，要么相同节点的value为null
            V v = mappingFunction.apply(key);//通过入参计算出新value
            if (v == null) { //如果新value为null，那么毫无意义，直接返回
                return null;
            } else if (old != null) { //如果新value不为null，且存在相同节点（且该节点的value为null，前面解释了）
                old.value = v;//所以用新value替换旧value
                afterNodeAccess(old);//替换value后执行
                return v;//注意，此函数一反常态，返回的是新value
            }
            //执行到这里，说明old为null。不存在相同节点
            else if (t != null)//如果t不为null，说明该哈希桶是红黑树结构
                t.putTreeVal(this, tab, hash, key, v);//通过putTreeVal增加新节点
            else { //说明该哈希桶是单链表结构
                tab[i] = newNode(hash, key, v, first);//把新节点作为新的头节点，后继指向旧的头节点
                if (binCount >= TREEIFY_THRESHOLD - 1)//上面那个循环又是从第二个节点开始计数的
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
            return v;//注意，此函数一反常态，返回的是新value
        }

该函数会在absent缺席时发挥作用。

1.  map里根本没有含有key的映射，那么认为缺席，新增一个节点。
2.  map有含有key的映射，但映射的value却是null，那么也认为缺席，此时替换节点的旧value为新value。
3.  新value通过入参的函数式接口计算得出，且上述两种情况，会返回新value。其余情况返回null。

注意，如果新value算出来是null，那么既不会新增节点（无相同节点），也不会替换节点（有相同节点），然后返回null。

computeIfAbsent的逻辑（absent缺席时，才计算），整理一下就是：

*  如果有相同映射：
    
     *  如果旧value不为null（出席），那么直接返回旧value。
     *  如果旧value为null（缺席），新value不为null（有意义），那么执行**替换操作**，返回新value。
     *  如果旧value为null（缺席），如果新value为null（无意义）， 那么直接返回null。
 *  如果没有找到相同映射（缺席）：
    
     *  如果新value不为null（有意义），那么执行**新增操作**，返回新value。
     *  如果新value为null（无意义），那么直接返回null。

If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value.   
If the function returns `null`, the mapping is removed. If the function itself throws an (unchecked) exception, the exception is rethrown, and the current mapping is left unchanged.

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) { //新value不为null
                    e.value = v;
                    afterNodeAccess(e);
                    return v;
                }
                else//新value为null
                    removeNode(hash, key, null, false, true);
            }
            return null;
        }

该函数会在present出席时发挥作用。当map里有含有key的映射且该映射的value不为null时，认为出席；反之认为缺席。

1.  确认present后，如果计算出来的新value不为null，那么执行替换操作。返回新value。
2.  确认present后，如果计算出来的新value为null，那么执行删除操作（删除这个映射）。返回null。
3.  当确认不是present后，直接返回null。

computeIfPresent的逻辑（present出席时，才计算），整理一下就是：

*  如果有相同映射：
    
     *  如果旧value为null（缺席），直接返回null。
     *  如果旧value不为null（出席），新value不为null（有意义），那么执行**替换操作**。
     *  如果旧value不为null（出席），新value为null（无意义），那么执行**删除操作**。
 *  如果没有找到相同映射（缺席）：
    
     *  不管新value为不为null，直接返回null。

Attempts to compute a mapping for the specified key and its current mapped value (or `null` if there is no current mapping).

@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);
                }
            }
            //old为null代表没有相同节点。如果没有相同映射，那么认为旧value为null；如果有相同映射，那么使用映射的旧value
            //简单的说，oldValue为null则代表缺席；反之，代表出席
            V oldValue = (old == null) ? null : old.value;
            V v = remappingFunction.apply(key, oldValue);//计算出新value
            if (old != null) { //如果有相同映射
                if (v != null) { 
                    old.value = v;
                    afterNodeAccess(old);
                }
                else
                    removeNode(hash, key, null, false, true);
            }
            else if (v != null) { //如果没有相同映射，且新value不为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;
        }

此函数前半段和computeIfAbsent差不多，但此函数不管这个映射是否缺席。

compute的逻辑（不管出没出席了），整理一下就是：

*  如果有相同映射：
    
     *  如果新value不为null，那么执行**替换操作**。
     *  如果新value为null， 那么执行**删除操作**。
 *  如果没有找到相同映射：
    
     *  如果新value不为null，那么执行**新增操作**。
     *  如果新value为null，那么直接返回null。

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is `null`. This method may be of use when combining multiple mapped values for a key.

@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;//新value
                if (old.value != null)//如果旧value不为null
                    v = remappingFunction.apply(old.value, value);//通过旧value和传入value，计算出新value
                else//如果旧value为null
                    v = value;//那么将传入value，作为新value
                //以上计算出了新value
                if (v != null) { //如果新value不为null
                    old.value = v;//执行替换操作
                    afterNodeAccess(old);
                }
                else//如果新value为null
                    removeNode(hash, key, null, false, true);//执行删除操作
                return v;
            }
            //上面有return，所以如果执行到这里，说明没有相同映射
            if (value != null) { //如果传入value不为null（传入value作为新value）
                //接下来执行新增操作
                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;
        }

相比之前三个方法，此方法有三个参数，出了一个传入value。而新value的计算有几种情况：

*  如果属于出席（有相同映射且旧value不为null），那么新value则由旧value和传入value通过BiFunction计算出来。
 *  如果属于缺席，那么新value直接取传入value。

merge的逻辑，整理一下就是：

该函数肯定会返回新value（不管它为不为null），且除了新value的得到方式有所不同外，其余地方都和compute函数一样。

@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();
            }
        }

此函数已经帮我们把遍历代码写好了，我们只需要用Lambda表达式来实现BiConsumer函数式接口就好了。别看BiConsumer的accept只是个void返回类型的函数，因为Lambda表达式实际就是匿名内部类，所以你在Lambda表达式内部可以访问外部类的。

@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();
            }
        }

此函数通过BiFunction函数式接口，使得每个映射的旧value会被替换为新value，而新value是通过key和旧value计算出来的。

# Cloning and serialization #

public Object clone() { 
            HashMap<K,V> result;
            try { 
                result = (HashMap<K,V>)super.clone();//.的优先级高，之后再强转。这个result确实是新创建的
            } catch (CloneNotSupportedException e) { 
                // this shouldn't happen, since we are Cloneable
                throw new InternalError(e);
            }
            result.reinitialize();
            result.putMapEntries(this, false);
            return result;
        }

注释已经说了这是一个浅拷贝操作，具体讲解可见本人这篇博客——[HashMap源码 clone解析][JDK8 HashMap_ clone]。如下图所示，`this`就是oldMap，而`result`就是newMap，到达虚线以后，你就发现这是一个浅拷贝了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 2]

final float loadFactor() {  return loadFactor; }
        final int capacity() { 
            return (table != null) ? table.length ://如果table已经初始化了，那么table的大小就是容量
                (threshold > 0) ? threshold ://如果table还没初始化，那么capacity暂存在threshold里
                DEFAULT_INITIAL_CAPACITY;//如果table还没初始化，且threshold还没有暂存capacity
        }

序列化时会用到以上函数。

private void writeObject(java.io.ObjectOutputStream s)
            throws IOException { 
            int buckets = capacity();
            // Write out the threshold, loadfactor, and any hidden stuff
            // this对象的所有non-static和non-transient的field，会写入到s中
            // 但HashMap也只有threshold和loadfactor这两个field符合条件
            s.defaultWriteObject();
            s.writeInt(buckets);
            s.writeInt(size);
            internalWriteEntries(s);
        }

序列化时会调用到此函数。

*  defaultWriteObject会把non-static和non-transient的field写入到流中。
 *  接下来的两个writeInt操作，会把两个int值写入到流中，感觉这个和`android.os.Parcel`的用法很像。

private void readObject(java.io.ObjectInputStream s)
            throws IOException, ClassNotFoundException { 
            // Read in the threshold (ignored), loadfactor, and any hidden stuff
            s.defaultReadObject();
            reinitialize();//将threshold和loadfactor读取到自己的field后，马上就忽略掉了threshold
            //但不会忽略掉loadFactor，因为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));//其余情况，利用tableSizeFor算出一个2的幂来
                float ft = (float)cap * lf;
                threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                             (int)ft : Integer.MAX_VALUE);
                @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);
                }
            }
        }

反序列化时会调用到此函数。

*  defaultReadObject操作与之前讲解的defaultWriteObject操作相对，会读出流中non-static和non-transient的field到`this`对象中。
 *  两个readInt与之前讲解的两个writeInt操作相对，会读出两个int值来。
 *  之后就是根据size，算出capacity和threshold。然后取出key和value，通过putVal来放置元素。

# 迭代器 #

## iterators ##

abstract class HashIterator { 
            Node<K,V> next;        // 调用next时，将会返回的那个entry
            Node<K,V> current;     // 上次调用next时，返回的那个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
                    //遍历各个哈希桶的第一个元素，所以第一个元素为null则继续循环
                    //所以当遇到第一个有元素的哈希桶时，循环停止，next指向此哈希桶第一个元素
                    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();
                //让next的下一个节点成为next，但如果它为null（当它是哈希桶内最后一个节点时）
                //则用相同的do while循环来找到下一个不为null的节点
                if ((next = (current = e).next) == null && (t = table) != null) { 
                    do { } while (index < t.length && (next = t[index++]) == null);
                }
                return e;//返回那个没有更新过的next
            }
            //综上，index = next节点所在哈希桶的下标 + 1
            
            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);//调用外部类的removeNode
                expectedModCount = modCount;//更新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(); }
        }

*  `HashIterator`是一个成员内部类，这意味它持有外部类map的引用，可以调用外部类的方法。毕竟迭代器自己没有保存数据，数据都来自于外部类的map的table成员。`HashIterator`的访问权限是default的，这意味着同一个包内，和HashMap的子类都可以使用到它。
 *  `next`成员代表调用next方法后，将会返回的那个节点。`current`成员代表上一次调用next时，已经返回过的那个节点。`expectedModCount`用来实现“快速失败”的机制，并且它会在必要时和外部类的modCount再保持一致（比如remove后）。因为有这句`next = t[index++]`的存在，所以`index`总是等于，next节点所在哈希桶的下标+1。
 *  迭代器使用构造器构造以后，`current`成员为null，`next`成员指向散列表里第一个节点（即table里第一个有节点的哈希桶的第一个节点）。
 *  每次调用`next`方法后，会返回一个节点。此时，`current`成员指向已经返回过的这个节点，`next`成员指向下一次调用`next`将会返回的那个节点（即为了下一次调用`next`方法作好了准备）。
 *  注意下图的继承关系，`Iterator`接口需要实现hasNext和next方法，虽然KeyIterator只实现了next方法，但是从HashIterator那里也继承了一个hasNext方法，所以KeyIterator也算是实现了`Iterator`接口。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 3]

## spliterators ##

static class HashMapSpliterator<K,V> { 
            final HashMap<K,V> map;
            Node<K,V> current;          // 其实是下一次将要被处理的节点
            int index;                  // index初始为范围左端，它永远是current所在哈希桶的下标加1.
            int fence;                  // 范围的右端，但不包括它
            int est;                    // 估计的size
            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) { //当fence为0时，if分支会进入一次；执行一次后，以后再执行也不会进入if分支
                    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;
            }
        }

*  这是三个分割迭代器的父类，它的getFence方法里的实际逻辑只会执行一次（就算你执行多次getFence，里面的if分支只会进入一次），在子类的方法其实都有调用到它，`trySplit`和`tryAdvance`直接调用了，而`forEachRemaining`虽然没有直接调用它，但却有一段类似的逻辑（`if ((hi = fence) < 0)`分支）。

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;//除以2，并向下取整
                return (lo >= mid || current != null) ? null ://如果low不小于middle，或者虽然low小于middle但current不为null，则返回null
                    //如果low小于middle，且current为null，则执行下面
                    new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
                                            expectedModCount);
                    //自己的index提高到了mid，返回的那个迭代器的fence下降到了mid
                    //且，自己迭代器和返回的迭代器的est成员都>>>= 1
            }
    
            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;//更新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;
                        }
                        //上面两个分支，p都会更新到下一个可访问的节点（不为null）
                        //但if分支只有在，开始p为null(说明p之前为null)，然后更新p为下一个哈希桶的第一个节点，i也会加加
                    } while (p != null || i < hi);
                    //循环继续条件：1.p不为null 2.p虽为null，但i < high
                    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) { 
                    //如果current不为null，
                    //或者current虽然为null，但index < high(说明还没有超过fence)
                    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() { 
                //如果est=map.size，那说明当前分割迭代器的范围和map的范围一样大
                return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                    Spliterator.DISTINCT;
            }
        }
        //剩下两个分割迭代器类似，就不贴了

*  其实这个分割迭代器，和**归并排序**的思想很像，都是将table数组一分为二，二分为四。然后分割出来的迭代器又可以各自处理自己范围的数据。
 *  这几个分割迭代器都是静态内部类，这导致他们的构造器必须传入一个HashMap来持有引用。
 *  成员里，最有助于我们理解的两个成员是`index`和`fence`。首先，Spliterator是按照HashMap的table成员来分割，而`index`和`fence`指的是table的下标，它俩代表着当前分割迭代器的遍历范围是`[index, fence)`，即左闭右开的，因为`fence`一般为`table.length`即是一个不可能的索引。
 *  所以一般情况下，初始化时，给构造器传值时，要让`index = 0`，且`fence = table.length`。而且这种左闭右开的遍历范围，还使得可以迭代器方便分割。  
    ![在这里插入图片描述][20200104163604660.jpg]
 *  上图展示了`trySplit`方法的作用（注意，两个蓝色说明分割后，this对象的范围变成`[low, mid)`，而返回对象的范围则是`[mid, high)`）。注意，当`(lo >= mid || current != null)`时该方法会返回null，由于一般情况下，`lo >= mid`都不会成立（这都会成立那说明当前迭代器已经无法分割了），则`current`不为null时，该方法会返回null。这说明，正常情况下，一个可split的分割迭代器的`current`成员是为null的。
 *  `est`成员的意思是估计的大小，且`trySplit`方法会给两个分割后的迭代器以`est >>>= 1`的估计大小。它确实只能算是估计大小：
    
     *  首先，将table的范围一分为二后，由于各个哈希桶的节点数量不尽相等，所以除以2后，是不准的。比如下面这张情况：  
        ![在这里插入图片描述][20200104165516523.jpg]
     *  而且，`est >>>= 1`这种除以2，是向下取整的。比如7/2 = 3，两个3加起来还少1呢。

接下来讲解forEachRemaining方法：

*  首先`fence <= table.length`和`index >= 0`这两个边界的条件得成立（对应源码的`tab.length >= hi && (i = index) >= 0`），然后`index < fence`或者`current != null`至少有一个成立（对应源码的`i < (index = hi) || current != null`）（要么`index < fence`成立，不用管后面这个条件；要么虽然`index >= fence`了，但current却不为null），接着再执行主要的逻辑。
 *  再看do while循环的处理逻辑，其实就是遍历`[index, fence)`范围内的所有节点。下图的“超过边界后”的状态，再去判断`p != null || i < hi`则通不过了，因为虽然p为null，但`i`已经等于`hi`即`fence`了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 4]
 *  forEachRemaining执行完毕后，`index`成员将会和`fence`一样大（因为`index = hi`），且会使得current为null（因为`current = null`）。

接下来讲解tryAdvance方法：

*  主要逻辑在while循环里，注意循环的成立条件有两种：1.current不为null 2.虽current为null，但index还是小于hi的。初始时，肯定是进入第二种情况。
 *  但是该方法是，只有找到一个范围内的节点就处理它，然后就返回true，所以该方法每次只处理一个节点。所以，该函数返回false的情况是，current是null且index已经提升到fence了，这意味着之前可能已经经历了若干次tryAdvance了。
 *  所以通过`current`和`index`的组合，可以判断当前分割迭代器的状态。初始的分割迭代器执行若干次tryAdvance后，但还没有超过边界的话，那么它就处于一种“中间状态”。那么可能此时，`current`不为null，且`index`是小于`fence`的。

解释一下，为什么forEachRemaining里的判断有一句`i < (index = hi) || current != null`，要想通过这个判断，有两种情况：

1.  `i < fence`成立，不管后面的条件。既然`i < fence`了，那么说明当前分割迭代器处于中间状态，肯定还有哈希桶没有被遍历过（`i`还没到达边界）。
2.  此时`i = fence`了，但current不为null。这个已经遍历到范围内最后一个哈希桶的中间状态，要想到达这种状态，是通过执行数次tryAdvance来做到的。如下图所示，当前还有两个节点可以遍历，current和current和后继。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 5]

总结一下就是，forEachRemaining会使得current成员为null，而tryAdvance则都有可能。这里我们再回过头看一下trySplit里的这个`lo >= mid || current != null`这个判断，如果通不过判断则返回null，说明这个迭代器当前不可以split，通不过有两种情况：

1.  `index >= fence`，这种情况说明当前这个分割迭代器已经超过了边界了，所以不能split。
2.  虽然`index < fence`即还没有超过边界，但current却不为null，这说明至少执行了一次tryAdvance，而且这将会导致当前这个哈希桶里的元素还有元素没有遍历呢，所以不能split（PS：桶里的节点还没遍历完，你就想split，那些哈希桶里还没遍历的节点们上哪说理去）。如下图，第二种状态下，当前的哈希桶里已经遍历完了，所以可以split。顺便说一句，只有当tryAdvance返回false时，你才有可能可以split，当然如果tryAdvance返回false是因为分割迭代器已经超过边界，那么此时也不可以split了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 6]

# LinkedHashMap support #

// 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() { //重置所有field为默认值
            table = null;
            entrySet = null;
            keySet = null;
            values = null;
            modCount = 0;
            threshold = 0;
            size = 0;
        }
    
        // Callbacks to allow LinkedHashMap post-actions
        // 这些都是LinkedHashMap的后续操作，所以现在是空实现
        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**的内容我将在另外一篇博客专门进行讲解，毕竟这些都是关于红黑树的操作。

[JDK8 HashMap_]: https://blog.csdn.net/anlian523/article/details/103435732
[JDK8 HashMap_ _]: https://blog.csdn.net/anlian523/article/details/103649200
[JDK8 HashMap_ putMapEntries]: https://blog.csdn.net/anlian523/article/details/103639094
[JDK8 HashMap_ clone]: https://blog.csdn.net/anlian523/article/details/103797056
[HashMap]: https://blog.csdn.net/anlian523/article/details/103812105
[HashMap 1]: https://blog.csdn.net/anlian523/article/details/103745773
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191208122244127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019122811252467.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200102214842163.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020010414332551.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[20200104163604660.jpg]: https://img-blog.csdnimg.cn/20200104163604660.jpg
[20200104165516523.jpg]: https://img-blog.csdnimg.cn/20200104165516523.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200104175353224.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200104182849699.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200104184549281.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70