HashMap 类属性

HashMap 继承于 AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口，是非常常用的一个集合类，同时在 JDK 1.7 和 JDK 1.8 版本的底层实现上也有很大区别。

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import sun.misc.SharedSecrets;

/**
 * Hash table based implementation of the <tt>Map</tt> interface.  This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 *
 * <p>This implementation provides constant-time performance for the basic
 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
 * disperses the elements properly among the buckets.  Iteration over
 * collection views requires time proportional to the "capacity" of the
 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
 * of key-value mappings).  Thus, it's very important not to set the initial
 * capacity too high (or the load factor too low) if iteration performance is
 * important.
 *
 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
 * performance: <i>initial capacity</i> and <i>load factor</i>.  The
 * <i>capacity</i> is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created.  The
 * <i>load factor</i> is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased.  When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 *
 * <p>As a general rule, the default load factor (.75) offers a good
 * tradeoff between time and space costs.  Higher values decrease the
 * space overhead but increase the lookup cost (reflected in most of
 * the operations of the <tt>HashMap</tt> class, including
 * <tt>get</tt> and <tt>put</tt>).  The expected number of entries in
 * the map and its load factor should be taken into account when
 * setting its initial capacity, so as to minimize the number of
 * rehash operations.  If the initial capacity is greater than the
 * maximum number of entries divided by the load factor, no rehash
 * operations will ever occur.
 *
 * <p>If many mappings are to be stored in a <tt>HashMap</tt>
 * instance, creating it with a sufficiently large capacity will allow
 * the mappings to be stored more efficiently than letting it perform
 * automatic rehashing as needed to grow the table.  Note that using
 * many keys with the same {@code hashCode()} is a sure way to slow
 * down performance of any hash table. To ameliorate impact, when keys
 * are {@link Comparable}, this class may use comparison order among
 * keys to help break ties.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it <i>must</i> be
 * synchronized externally.  (A structural modification is any operation
 * that adds or deletes one or more mappings; merely changing the value
 * associated with a key that an instance already contains is not a
 * structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the map.
 *
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the map:<pre>
 *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 *
 * <p>The iterators returned by all of this class's "collection view methods"
 * are <i>fail-fast</i>: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator's own
 * <tt>remove</tt> method, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the
 * future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */
// 这里继承了 AbstractMap<K,V>，而 AbstractMap<K,V> 也实现了 Map 接口，所以这里每没必要再去实现 Map 接口，会产生什么影响呢？
// 1. 在 java 文件编译成 class 字节码文件时
// 		首先会把 java.util.Map 会被编译到 CONSTANT_UTF8_INFO 中，最终完全字面量的解析
//		如果多实现一个接口的情况下，在接口索引集合中会多出一个接口
// 2. class 文件最终会被加载到运行时数据区的方法区形成一个动态数据结构，每次调用 HashMap 时这个 Map 接口都会加载
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { // 实现了 Map、Cloneable、Serializable

    private static final long serialVersionUID = 362498820763181265L; // 随机序列化编号

    /*
     * Implementation notes.
     *
     * This map usually acts as a binned (bucketed) hash table, but
     * when bins get too large, they are transformed into bins of
     * TreeNodes, each structured similarly to those in
     * java.util.TreeMap. Most methods try to use normal bins, but
     * relay to TreeNode methods when applicable (simply by checking
     * instanceof a node).  Bins of TreeNodes may be traversed and
     * used like any others, but additionally support faster lookup
     * when overpopulated. However, since the vast majority of bins in
     * normal use are not overpopulated, checking for existence of
     * tree bins may be delayed in the course of table methods.
     *
     * Tree bins (i.e., bins whose elements are all TreeNodes) are
     * ordered primarily by hashCode, but in the case of ties, if two
     * elements are of the same "class C implements Comparable<C>",
     * type then their compareTo method is used for ordering. (We
     * conservatively check generic types via reflection to validate
     * this -- see method comparableClassFor).  The added complexity
     * of tree bins is worthwhile in providing worst-case O(log n)
     * operations when keys either have distinct hashes or are
     * orderable, Thus, performance degrades gracefully under
     * accidental or malicious usages in which hashCode() methods
     * return values that are poorly distributed, as well as those in
     * which many keys share a hashCode, so long as they are also
     * Comparable. (If neither of these apply, we may waste about a
     * factor of two in time and space compared to taking no
     * precautions. But the only known cases stem from poor user
     * programming practices that are already so slow that this makes
     * little difference.)
     *
     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
     *
     * The root of a tree bin is normally its first node.  However,
     * sometimes (currently only upon Iterator.remove), the root might
     * be elsewhere, but can be recovered following parent links
     * (method TreeNode.root()).
     *
     * All applicable internal methods accept a hash code as an
     * argument (as normally supplied from a public method), allowing
     * them to call each other without recomputing user hashCodes.
     * Most internal methods also accept a "tab" argument, that is
     * normally the current table, but may be a new or old one when
     * resizing or converting.
     *
     * When bin lists are treeified, split, or untreeified, we keep
     * them in the same relative access/traversal order (i.e., field
     * Node.next) to better preserve locality, and to slightly
     * simplify handling of splits and traversals that invoke
     * iterator.remove. When using comparators on insertion, to keep a
     * total ordering (or as close as is required here) across
     * rebalancings, we compare classes and identityHashCodes as
     * tie-breakers.
     *
     * The use and transitions among plain vs tree modes is
     * complicated by the existence of subclass LinkedHashMap. See
     * below for hook methods defined to be invoked upon insertion,
     * removal and access that allow LinkedHashMap internals to
     * otherwise remain independent of these mechanics. (This also
     * requires that a map instance be passed to some utility methods
     * that may create new nodes.)
     *
     * The concurrent-programming-like SSA-based coding style helps
     * avoid aliasing errors amid all of the twisty pointer operations.
     */

    /**
     * The default initial capacity - MUST be a power of two. 必须是 2 的 n 次幂
     */
    // 默认初始容量是 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    // 数组的最大长度是 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    // 默认装载因子，和默认容量配合 16 * 0.75 = 12，所以真正可以存放元素的大小是 12，当数组中超过这个数之后就要进行一次扩容，精确扩容为 2 倍
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 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.
     */
    // 转树，链表转换红黑树的阈值是 8，同时要求 table 的长度也要大于 64（MIN_TREEIFY_CAPACITY）才会转换红黑树
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 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.
     */
    // 解树，红黑树退化为链表的阈值是 6
    // 这里为什么是 6，不是 7 呢？
    // 两层含义
    // 1. 当链表是 8 的时候刚转成红黑树，由于二叉树是一棵自平衡二叉搜索树，所以节点为 8 个时最后一层有一个元素，7 的时候正好是左右对称的，搜索性能最好，到 6 的时候可以考虑再变链表
    // 2. 懒加载的思想，第一次删除元素后我不变链表，第二次删除元素的时候再变，否则刚变成红黑树就要退化成链表，损耗性能。
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 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.
     */
    // 转变红黑树的最小数组容量是 64
    static final int MIN_TREEIFY_CAPACITY = 64;
 
    // ...
    
    /* ---------------- 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.)
     */
    // table 桶数组，存放 Node 节点
    // 这里用 transient 修饰，不能被序列化，但它还要被序列化，怎么做的呢？和 ArrayList 一样，都是自己实现了序列化方法 writeObject、readObject
    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;

    /**
     * The number of key-value mappings contained in this map.
     */
    // HashMap 的 size，记录有元素的节点
    transient int 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;

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (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;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    // 加载因子
    final float loadFactor;
}

【重点】Node<K, V> 节点

/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> { // 实现了 Map.Entry<K,V>
    // 为什么 hash 和 key 设置成 final
    final int hash; // 1. hash 值在一定程度上代表了对象的地址，内存地址是不能随便改变的 
    				// 2. 同时在 32 位虚拟机的对象头 Mark Word 中有一个 15 位的 hash 值，4 位分代年龄 2 位锁标记位、1 位是否为偏向锁，对象头中的内容是不能改变的
    
    final K key; // 1. 而 key 不能修改，只能通过先删除再添加的方式 曲线救国 2. key 还会用于对比传入的 key 是否已经存在，不能随便修改
    
    V value; // value 可以重新赋值的
    Node<K,V> next; // 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() { // 【重要】当前 node 的 hashCode也做了一次扰动处理，直接调用 Object 的 hashCode() 方法，将 key 的 hashcode 和 value 的 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)  // 如果地址相等说明对象相等，则直接返回 true
            return true;
        if (o instanceof Map.Entry) { // 判断 o 的类型是 Map.Entry
            Map.Entry<?,?> e = (Map.Entry<?,?>)o; // 将 o 强转成 Map.Entry<?,?>，强转之后才能用 HashMap 的方法
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue())) // 然后调用 Objects【不是 Object】 的 equals() 方法判断 key、value 和传入的 key、value 是否相等
                return true;
        }
        return false;
    }
}

// Objects 类
/**
 * Returns {@code true} if the arguments are equal to each other
 * and {@code false} otherwise.
 * Consequently, if both arguments are {@code null}, {@code true}
 * is returned and if exactly one argument is {@code null}, {@code
 * false} is returned.  Otherwise, equality is determined by using
 * the {@link Object#equals equals} method of the first
 * argument.
 *
 * @param a an object
 * @param b an object to be compared with {@code a} for equality
 * @return {@code true} if the arguments are equal to each other
 * and {@code false} otherwise
 * @see Object#equals(Object)
 */
public static boolean equals(Object a, Object b) {
    // 先判断对象地址是否相等，再根据传入的 Object 的具体类型的 equals() 方法进行比较（如果这个类重写了 equals() 那就按重写的逻辑比较
    // 没有重写按 Object 的 equals() 还是比较对象地址）
    return (a == b) || (a != null && a.equals(b)); 
}

【重点】hash(Object key)

注意：==null key 的哈希值是 0，不会调用 hashCode() 方法==

/**
 * 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.
 */
// 求 key 的哈希值，自身和右移 16 位做异或
static final int hash(Object key) {
    int h;
    // null key 的哈希值是 0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

comparableClassFor(Object x)

/**
 * Returns x's Class if it is of the form "class C implements
 * Comparable<C>", else null.
 */
// 判断当前类 x 是否实现了 Comparable<C> 接口（是否进行比较），如果是返回当前类的 Class 对象，否则返回 null
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) { // 类型判断
        // c 是 Class 对象，ts、as 是类型数组 (s) 复数，t 是类型并且是 ts 中的元素，p 是参数化类型（ArrayList<String>）
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        
        // 如果 x 的 Class 对象是 String 类型，直接返回类型 c。因为 String 类实现了 Comparable<C> 接口
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        // 获取实现的接口是否为空，并赋值给 ts【List, RandomAccess、Cloneable、Seriablizable】
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) { // 循环每个接口
                if (((t = ts[i]) instanceof ParameterizedType) && // 判断当前接口是否是参数类类型的，即 List<Object> 形式
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&		// 且 判断这个参数化类型的外层【List】 是否 是 Comparable.class 类型
                    (as = p.getActualTypeArguments()) != null && // 且 判断这个参数化类型的内层 【Object.class[]】是否为空
                    as.length == 1 && as[0] == c) // type arg is c // 且内层数组的大小必须是 1 且第一个元素的类型是 c 
                    return c; // 才返回类型 c
            }
        }
    }
    return null; // 否则返回 null
}

compareComparables(Class<?> kc, Object k, Object x) {

/**
 * Returns k.compareTo(x) if x matches kc (k's screened comparable
 * class), else 0.
 */
// 对于对象 k，k 的类型是 kc，比较 k 和 x
@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));
}

【重点】tableSizeFor(int cap)

/**
 * Returns a power of two size for the given target capacity.
 */
// 取出一个数字的最接近 2^n 次方的数（向上取整）
static final int tableSizeFor(int cap) {
    int n = cap - 1; // 9
    n |= n >>> 1; // 1001 | 0100 = 1101
    n |= n >>> 2; // 1101 | 0011 = 1111
    n |= n >>> 4; // 1111 | 0000 = 1111
    n |= n >>> 8; // 1111
    n |= n >>> 16;// 1111
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n + 1 = 1 0000 = 2^4 = 16
}

HashMap 构造器

/* ---------------- Public operations -------------- */

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
// 带初始容量和负载因子的构造器
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) // 初始容量小于 0 直接抛异常
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) // 初始容量大于 2^30 赋值给 2^30
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 负载因子小于 0 或传入的不是一个数，直接抛异常
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); // 否则将初始容量向上取最近的 2^n 次幂
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
// 只带初始容量的构造器
public HashMap(int initialCapacity) {
    // 调用的还是两个参数的构造器，只不过负载因子指定为默认的 0.75
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
// 空参构造器没有对 table 赋值（即 threshold 变量）
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param   m the map whose mappings are to be placed in this map
 * @throws  NullPointerException if the specified map is null
 */
// 带 Map 参数构造器，用另一个 Map 初始化当前 HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false); // evcit = false 表示第一次构造，否则 true
}

putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

/**
 * Implements Map.putAll and Map constructor
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 如果 table 是 null，则给 threshold 赋值
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F; // 通过 元素个数 / 加载因子 反向得到容量，因为不能整除，所以保险起见向上取整
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY); // float 转 int
            if (t > threshold) // 如果 m 需要的空间大小 t > table 的大小 threshold，容量向上取最近的 2^n
                threshold = tableSizeFor(t);
        }
        else if (s > threshold) // 如果 table 不为空且 m 中的元素个数 s 大于table 的大小 threshold，放不下了就进行扩容
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { // 最后就是初始化，把 m 中的每个 key-value 放到 table 数组中
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict); // 调用私有的 putVal()
        }
    }
}

【重点】get(Object key)

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
// 根据 key 获取值
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value; // 调用内部的 getNode() 方法
}

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
// 根据 hash 值和 key 获取 Node 节点
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; // 定义的一个临时 Node 数组，用于存放 table 数组
    Node<K,V> first, e; // first 表示链表的头节点，e 是一个临时节点
    int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && // table 不为空
        (first = tab[(n - 1) & hash]) != null) { // 且 取出当前的节点 Node 不为空； tab[(n - 1) & hash]，(n - 1) & hash 定位底层数组的索引下标
        // hash 值相等且 key 相等 且 equals() 相等, 直接返回 first，
        // 为什么要三个判断呢？因为根据 hash 值相等不能判断两个对象相等
        if (first.hash == hash && // always check first node 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 否则比较头节点的下一个节点（可能是 Node、也可能是 TreeNode）
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) // 如果是 TreeNode，则从红黑树中查询 getTreeNode
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 否则遍历链表，从链表里找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 找不到就返回 null
    return null;
}

containsKey(Object key)

/**
 * Returns <tt>true</tt> if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key.
 */
// getNode() 返回值是 null 表示不存在，否则存在
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

【重点】put(K key, V value) 添加和修改方法

通过看源码我们发现，如果 put 是修改的情况则会返回旧值，如果 put 是添加的话，最后添加成功返回 null

根据这个特性，我们在需要确保唯一的 key 的业务场景下，就可以使用这个返回值来判断在业务执行的过程中 key 到底是不是唯一的，如果出现了不唯一的情况抛出异常，排查问题。

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    // 调用 putVal
    return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
// 真正的 put
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    
    Node<K,V>[] tab; // table 数组的副本
    Node<K,V> p; // p 是桶下标的头节点
    int n, i; // n 是 table 数组的大小
    
    // 如果 table 是 null 或者 table 没有元素
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length; // 进行一次扩容，第一次就是 16 赋值给 n
    
    // 此时 table 不为 null，定位桶下标
    // 如果当前槽位上没有数据，直接放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 否则说明当前槽位上有数据
    else {
        Node<K,V> e; K k;
        // 如果头节点的 key 就是就是传入的 key，则直接将头节点 p 赋值给 e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果头节点 p 是红黑树节点，则需要进行 TreeNode 的添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 否则那就是链表形式，而且头节点的 key 不是传入的 key
        else {
            // 遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { // 如果当前节点的 next 是空，则尾插法插入传入的节点，结束 put
                    p.next = newNode(hash, key, value, null);
                    // 当链表长度达到 8，执行 treeifyBin() 链表转红黑树，至于最终转不转还要 table 的长度是否大于 64，大于才转，否则执行扩容
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 
                        treeifyBin(tab, hash);
                    break;
                }
                // 否则如果找到了 key 相同的节点，也要结束 put
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e; // 否则 p = (e = p.next) 其实就是 p = p.next
            }
        }
        // 如果 e 不为 null 说明从 HashMap 中找到了这个 key 对应的节点，那么执行修改逻辑，修改 key 对应的值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent 如果是 true 则不能修改
                e.value = value;
            afterNodeAccess(e);
            return oldValue; // 修改完返回旧值
        }
    }
    ++modCount; // 修改数 + 1
    
   	// 注意：HashMap 是先添加再扩容
    if (++size > threshold) // 如果元素个数超过扩容阈值，进行扩容
        resize();
    afterNodeInsertion(evict);
    return null; // 如果添加成功则返回 null
}

// 如果 put 的 key 存在且 value 不是 null 就不覆盖这个 value
// 如果 key 存在且 value 是 null，则覆盖这个 value
// 如果 key 不存在就直接添加
@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

resize() 扩容方法

思考题：HashMap 最多能放多少个元素呢？

和底层数组 table 的大小有关，与 threshold 没有关系，threshold 只有扩容有关，它的大小不会限制其他的操作。

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // oldTable 表示原来的 table，做一个副本
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 如果 oldTable 的长度是空容量为 0，否则容量为 length
    int oldThr = threshold; // oldThr 表示原 table 的 threshold (= length * load_factor)
    int newCap, newThr = 0; //定义 新 table 的容量和阈值
    if (oldCap > 0)  // 如果 oldTable 容量 oldCap 大于 0
        if (oldCap >= MAXIMUM_CAPACITY) { // 如果旧容量大于 2^30，放弃扩容，直接修改 threshold
            threshold = Integer.MAX_VALUE; // threshold 直接赋值为 INT_MAX
            return oldTab; // 返回了旧 table
        }
    	// 继续扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 首先就是扩容为两倍 且 小于 2^30 次方
                 oldCap >= DEFAULT_INITIAL_CAPACITY) // 且 旧容量 大于等于 初始容量
            newThr = oldThr << 1; // double threshold // newThr (新的 threshold) 变成原来 oldThr 的两倍
    }
	// 否则 oldTable 容量 oldCap 小于等于 0
    else if (oldThr > 0) // initial capacity was placed in threshold // oldThr 大于 0
        newCap = oldThr; // 新容量 newCap 赋值为 oldThr
	// 否则 oldTable 容量 oldCap 小于等于 0 且阈值 oldThr 也是小于等于 0，那么就用默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; // 新容量 newCap 为默认初始容量 64
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新阈值 newThr 为默认加载因子 * 默认初始容量
    }

    if (newThr == 0) {	// 如果信阈值为 0
        float ft = (float)newCap * loadFactor; // 得到 HashMap 实际可以使用的大小，即阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
                  (int)ft : Integer.MAX_VALUE); // 新容量小于最大容量 2^30 且 ft 也要小于 2^30，此时新的阈值 newThr 等于 ft，否则就取 int 最大值
    }
	
	// -------------------

    threshold = newThr; // 真正的给 threshold 进行 newThr 的赋值
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建扩容两倍后的 table
    table = newTab; // 真正的给 table 进行 newTab 的赋值

	// -----节点的迁移（原位置和新位置）----
	// 如果 oldTable 不为空，则进行节点迁移，否则直接返回扩容后的 newTable
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) { // for 循环取每个节点
            Node<K,V> e;  // e 用于存放 oldTable 的每个节点
            if ((e = oldTab[j]) != null) { // 如果 e 不是空
                oldTab[j] = null; // 则将 oldTable[j] 的内容置空，方便 gc，真正的值已经存到 e 中了
                if (e.next == null) // 如果 e.next 为空，说明 e 是槽位上的头节点
                    newTab[e.hash & (newCap - 1)] = e; // 则直接插入到 newTabale 对应的槽位上
                else if (e instanceof TreeNode) // 否则如果 e 是树节点，则进行【拆分树】
                    // 如果进行 HashMap 扩容，我们的树肯定会被拆掉，会产生一定性能消耗
                    // 实际情况下，我们的 HashMap 很难达到红黑树。1. hash 十分散列 2. 业务中 不可能、不能够、不允许 在一个 map 中放这么多元素
                    // 如果我需要从 db 中取出 2^30 个数据，需要用 HashMap 进行处理，怎么办？
                    // 想到 ArrayList 的 clear() 方法，能够复用，不需要再次扩容
                    // 【重要】HashMap 也是如此，利用 clear() 方法进行分批处理，再 clear() 再放数据，只需要扩容一次
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order // 否则链表上不止一个节点就需要遍历链表
                    Node<K,V> loHead = null, loTail = null; // loHead 是 old 链表的头节点，loTail 是 old 链表的尾节点
                    Node<K,V> hiHead = null, hiTail = null; // hiHead 是 new 链表的头节点，hiTail 是 new 链表的尾节点
                    Node<K,V> next; // 记录 next 节点
                    
                    // 【创建链表】
                    // do while 循环遍历链表，分别建立了两个链表，一个 old 链表，一个 new 链表
                    // old 链表存的是位置不变的节点，new 链表是需要变化位置的节点
                    do { 
                        next = e.next; // 记录 next 节点
                        if ((e.hash & oldCap) == 0) { // 如果当前节点的 hash 值 & 旧容量 等于 0，则位置不变
                            if (loTail == null) // 如果尾节点是空，说明链表为空，那么 e 就是 old 链表的头节点
                                loHead = e;
                            else
                                loTail.next = e; // 【尾插法】否则将 e 插入尾节点后面
                            loTail = e; // 最后更新尾节点为 e
                        }
                        else { // 否则，变化位置，将该元素放在新链表中
                            if (hiTail == null) // 如果尾节点是空，说明链表为空，那么 e 就是 new 链表的头节点
                                hiHead = e;
                            else
                                hiTail.next = e; // 【尾插法】否则将 e 插入尾节点后面
                            hiTail = e; // 最后更新尾节点为 e
                        }
                    } while ((e = next) != null);
                    
                    // 【真正添加到 newTable 中】
                    // old 链表尾部最终判断
                    if (loTail != null) { // 如果 old 链表的尾节点 loTail 不为空，说明旧链表有元素（里面就是那些位置不变的节点），则将其置为空，并且将旧链表放到 newTable 的对应对应槽位上
                        loTail.next = null;
                        newTab[j] = loHead; // 按照 oldTable 的位置不变，将旧链表的头节点 loHead 挂到 newTable 的槽位 j 上
                    }
                    // new 链表尾部最终判断
                    if (hiTail != null) { // 如果 new 链表的尾节点 loTail 不为空，说明新链表有元素（里面就是位置需要变化的节点），则将其置为空，并且将旧链表放到 newTable 的对应对应槽位上
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead; // 将新链表的头节点 hiHead 挂到 newTable 的 j + oldCap 槽位上，所以位置由原来的 j 变到了 j + oldCap
                    }
                }
            }
        }
    }
	// 最后返回 newTable
    return newTab;
}

clear() 清空元素，但容量不变，可以复用

/**
 * Removes all of the mappings from this map.
 * The map will be empty after this call returns.
 */
public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0; // 元素个数置为 0，但是容量没变
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null; // 清空每个槽位
    }
}

getOrDefault(key, defaultValue)

Map 接口的 getOrDefault(key, defaultValue) 实现

/**
 * Returns the value to which the specified key is mapped, or
 * {@code defaultValue} if this map contains no mapping for the key.
 *
 * @implSpec
 * The default implementation makes no guarantees about synchronization
 * or atomicity properties of this method. Any implementation providing
 * atomicity guarantees must override this method and document its
 * concurrency properties.
 *
 * @param key the key whose associated value is to be returned
 * @param defaultValue the default mapping of the key
 * @return the value to which the specified key is mapped, or
 * {@code defaultValue} if this map contains no mapping for the key
 * @throws ClassCastException if the key is of an inappropriate type for
 * this map
 * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if the specified key is null and this map
 * does not permit null keys
 * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
 * @since 1.8
 */
default V getOrDefault(Object key, V defaultValue) {
    V v;
    // 两个判断：1. 先判断值是否为 null  2. 再判断是否包含 key
    // 这里的 get(key) 调用的是子类的实现
    return (((v = get(key)) != null) || containsKey(key))
        ? v
        : defaultValue;
}

HashMap 接口的 getOrDefault(key, defaultValue) 实现

和 Map 接口的实现不一样，HashMap 直接通过 getNode() 判断节点是否为 null

同时我们的 HashMap 是允许 null key 和 null value 的，但只允许一个 null key，而且 ==null key 的散列位置在 0 号位置==

// Overrides of JDK8 Map extension methods

@Override
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    // 只有一个判断：判断通过 key 获取到的 Node 是否为空，如果是空返回默认值，否则返回 value
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

treeifyBin(Node<K,V>[] tab, int hash) 链表树化

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
// 树化方法：链表转红黑树，tab 就是底层数组，hash 是当前槽位上的链表 hash 值，它们的哈希值都是相等的
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 如果 table 为空 或者 table 的容量小于 64
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) { // 判断链表头节点是否为空，并把头节点赋值给 e，此时 e 的类型还是链表节点 Node
        TreeNode<K,V> hd = null, tl = null; // 定义红黑树节点变量 hd：可以理解为树的根节点（双向链表的尾节点），tl：树的尾节点（双向链表的尾节点）
        
        // do while 循环把单链表 Node 替换成 TreeNode，同时把单链表变成了双链表
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null); // 每次把链表节点 e 转换成 TreeNode
            if (tl == null) // 第一次 do while，tl = null，只会执行一次
                hd = p; // 将链表头节点对应的 TreeNode 赋值给 hd（可以理解为根节点）
            else { // 除了第一次之外，都需要建立前后两个节点之间的关系
                // ------- 卧槽，这是干啥呢？将单链表形式的 TreeNode 转换成双链表形式的 TreeNode
                p.prev = tl; // 当前节点 p 的前一个节点 指向 尾节点 tl
                tl.next = p; // 尾节点 tl 的下一个节点 指向 当前节点 p
            }
            tl = p; // 树的尾节点赋值为当前节点 p
        } while ((e = e.next) != null); // e = e.next 遍历单链表
        
        // 将树根节点 hd 替换到要树化的槽位上
        if ((tab[index] = hd) != null)
            // 传入 table，调用 TreeNode 内部的 treeify 执行真正的树化逻辑
            hd.treeify(tab);
    }
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    // 通过 hash、key、value、next 创建一个 TreeNode
    // 通过查看源码发现 TreeNode 是 Node 的子类，TreeNode 中没有 next 指针，但是 Node 中有
    // 我们知道二叉树节点只需要一个 left 和 right 就够了，为什么还需要一个 next 指针呢？这样设计的好处是什么？
    // 【重点】这个 next 指针是用来【快速解树】的，从红黑树快速变成链表，通过遍历每个节点的 next 指针马上就可以恢复成一个链表，太妙了！！！！
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
// TreeNode 的结构，继承 LinkedHashMap.Entry<K,V>，最终继承了 Node
// 为什么不直接继承 Node？
// 因为 TreeNode 还需要继承 LinkedHashMap.Entry<K,V> 中的属性方便对 LinkedHashMap 操作。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    
    // 没有 next 指针
    
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    
    // ...
    
}

// LinkedHashMap.Entry<K,V>
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 记录了前驱节点和后继节点
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

/**
 * Forms tree of the nodes linked from this node.
 * @return root of tree
 */
// TODO
// 将双向链表树化为红黑树 - 简化版：双向链表转换二叉树，LeetCode 类似题目：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
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 {
            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);
}

putAll(Map<? extends K, ? extends V> m)

/**
 * Copies all of the mappings from the specified map to this map.
 * These mappings will replace any mappings that this map had for
 * any of the keys currently in the specified map.
 *
 * @param m mappings to be stored in this map
 * @throws NullPointerException if the specified map is null
 */
// put 一个 map 到 map 中
public void putAll(Map<? extends K, ? extends V> m) {
    // 调用的就是 putMapEntries，上面已经分析过了
    putMapEntries(m, true);
}

remove(Object key)

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
// 根据 key 删除一个节点
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
// 删除一个节点
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 && // (tab = table) != null && (n = tab.length) > 0 表示 HashMap 不为空，且有元素
        (p = tab[index = (n - 1) & hash]) != null) { // 获取当前槽位上的头节点 p 且 p 不为 null
        Node<K,V> node = null, e; K k; V v; // node 就是最后要删除的节点
        // 说明头节点 p 就是要删除的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 如果不是头节点，继续判断，这里 p.next 既可以得到链表的下一个节点也可以得到红黑树的下一个节点，原因就是 TreeNode 是 Node 子类，同时我们也给 next 赋值了
        else if ((e = p.next) != null) {
            // 如果是树节点，则获取 TreeNode
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 否则就是链表
            else { 
                // do while 遍历链表，如果 e 是待删除节点则赋值给 node，直接 break
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e; // p 最终指向待删除的节点 e 的上一个节点
                } while ((e = e.next) != null);
            }
        }
        
        // ----- 真正的删除 node 节点
        // node 不为空，说明找到了 node，上面 remove() 方法传入的 matchValue = false
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果 node 是树节点，则调用 removeTreeNode 删除树节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 否则如果 node 是槽位上的链表的头节点 p，则头节点替换为下一个节点
            else if (node == p)
                tab[index] = node.next;
            // 否则如果 node 不是链表头节点，则一步操作单链表删除 node
            else
                p.next = node.next;
            ++modCount; // 修改次数 + 
            --size; // 元素个数 - 1
            afterNodeRemoval(node); // LinkedHashMap 的模板方法，对 HashMap 不起作用
            return node; // 返回删除的值
        }
    }
    return null; // 不存在返回 null
}

containsValue(Object value)

/**
 * Returns <tt>true</tt> if this map maps one or more keys to the
 * specified value.
 *
 * @param value value whose presence in this map is to be tested
 * @return <tt>true</tt> if this map maps one or more keys to the
 *         specified value
 */
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) { // 保证 table 不为空，有元素
        for (int i = 0; i < tab.length; ++i) { // 遍历数组
            for (Node<K,V> e = tab[i]; e != null; e = e.next) { // 遍历每个槽位上的节点（可能是链表、可能是树）都可以通过 next 指针遍历
                if ((v = e.value) == value ||
                    (value != null && value.equals(v))) // 如果值相等返回 true
                    return true;
            }
        }
    }
    return false;
}

keySet() 和 values()

/**
 * 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
 */
// 获取 HashMap 的所有 key，是通过继承类 AbstractMap 的属性赋值的
// 这里的 key 都是指向 HashMap 的一个引用，而不存储真正的值，所以当 HashMap 中删除了某个键值对，keySet() 也就没有了这个 key
// 根据注释可以看到不支持 add() 和 addAll()，因为 KeySet 没有实现 add() 和 addAll() 调用父类的实现就是抛出异常
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet(); // KeySet 是内部类，有 remove() 方法
        keySet = ks;
    }
    return ks;
}

/**
 * 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 是内部类，没有 remove() 方法，所以不能删除值，只能删除 key
        values = vs;
    }
    return vs;
}

// AbstractMap<K,V>
transient Set<K>        keySet;
transient Collection<V> values;

entrySet()

/**
 * 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
 */
// 获取 HashMap 的键值对
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

// HashMap
/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

// EntrySet 是内部类

remove(Object key, Object value)

// 只有 key 和 value 都匹配才去删除节点 
@Override
public boolean remove(Object key, Object value) {
    // 第一个 true 表示 matchValue = true，调用 removeNode() 的时候会判断
    return removeNode(hash(key), key, value, true, true) != null; 
}

replace()

@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)))) { // getNode 获取匹配的节点，匹配就修改返回 true，否则返回 false
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

@Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) { // getNode 获取匹配的节点，匹配就修改返回 true，否则返回 false
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

clone() 浅克隆

/**
 * 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() { // 调用方式 B = A.clone() 克隆 A 赋值给 B
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone(); // 调用的就是 Object 的 clone()
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    result.reinitialize(); // result 重新初始化
    result.putMapEntries(this, false); // 将 A 的键值对 put 到 result 里
    return result;
}

loadFactor() 和 capacity() 获取两个属性值

// These methods are also used when serializing HashSets
final float loadFactor() { return loadFactor; }
final int capacity() {
    return (table != null) ? table.length : // table 不为空容量就是 length
        (threshold > 0) ? threshold :
        DEFAULT_INITIAL_CAPACITY;
}

writeObject() 序列化和 readOject() 反序列化

/**
 * 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); // 再遍历 HashMap 一个一个的序列化键值对，空位置不处理
}

// 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) { // table 不为空
        for (int i = 0; i < tab.length; ++i) { // 遍历每个槽位
            for (Node<K,V> e = tab[i]; e != null; e =  e.next) { // 遍历每个槽位上的键值对
                s.writeObject(e.key); // 写 key
                s.writeObject(e.value); // 写 value
            }
        }
    }
}

/**
 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
 * deserialize it).
 */
// 反序列化
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
        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
        // 遍历 size 次，每次读取一个 key 和 value，put 到 table 中
        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);
        }
    }
}