关于 HashMap

Context

关于 HashMap, 有一件事儿一直很困惑，，在『Redis 核心历险』中是这样被提到的:

Redis 的字典相当于 Java 语言中的 HashMap，它是无序字典，内部存储了很多键值对。实现结构上与 Java 的 HashMap 也是一样的，都是”数组 + 链表”二维结构。第一维的 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

嗯，第一句没啥问题，，然而”数组 + 链表”什么鬼？还有 hash 碰撞。。作者并没有详细解释这儿，应该默认是每个 Java 开发者都知道的知识点了。然而我却在这儿卡壳了，心慌慌。。趁着周末赶紧补补课。事实证明，这波补课是很有效果的，在这本书后边的内容中，hash 还将会一直出现。

Hash

在 Wiki 中的定义为:

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

用我自己的话来说就是，，为数据创建指纹摘要，通过该摘要就可以找到原始数据。我觉得更多的场景是为相对大的数据创建摘要。假如有个 hash()，可以为任意数据生成一个32位的摘要。那么我们在互联网下载文件的时候，有的网站会在下来链接处给出该文件的 hash 值，等用户下载完成之后，通过 hash() 对该文件提取摘要，将两个 hash 值，进行对比。如果结果一样，说明文件在下载过程中没有被篡改。

那倘若我们对数字 1 进行 hash()，那应该也会得到一个长度为 32 位的摘要，但这时候还能叫『摘要』么？我感觉是不太合适的。

HashMap

-Basic JDK7

OK，back to the point..关于 Hash 我们需要知道👇

所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。但另一方面，散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。

按我之前不成熟的想法，，HashMap 中为什么要放链表？直接放数据对象不就够了么。。原因就是当我们通过 get(key) 方法从 HashMap 中获取对象的时候，理论上这个 key 对应的 hash 值和某个 whateverKey 对应的 hash 值是一样的(即，散列碰撞)，，因为『如果两个散列值相同，两个输入值很可能是相同的，但也可能不同(即，key 和 whateverKey)』。此时我们可以通过 key 和 whateverKey 都可以获取到对应的数据对象。如此，为了解决散列碰撞带来的问题，我们需要在 HashMap 中将两个‘key’都指向同一个数据对象，而在 HashMap 中的链表就是用来维护这些‘key’的。下面，我们试着读读 HashMap 源码。

HashMap 的 DOC 注释

/**
 * 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.
 * 👆散列表也基于对 Map 接口的实现。HashMap 也是对是 Map 接口的实现，提供了所有对 Map 的可选操作(的方法)，并且允许 null 值和 null 键。HashMap 大致相当与 HashTable 相同，除了 HashMap 是非同步的，且接受 null。该类不保证数据对象在内部的顺序，同时也不保证内部的顺序是一成不变的。
 * 
 * <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.
 * 👆HashMap 中 get 和 put 这两项基本操作提供复杂度为常数级别的性能表现，假定 hash 方法把元素均匀的分配到桶中。对整个集合视图进行迭代所需的时间与 HashMap 实例(桶的数量)乘以它的容量(键值对的数量)之积。所以，如果迭代性能很重要的话，不要在初始化 HashMap 的时候设置过高的容量，及太小的负载系数(负载因子)
 * * <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.
 * 👆一般，默认的负载系数（0.75）在时间和空间成本之间提供了很好的平衡。更高的值会减少了空间开销，但同时会增加查找成本（反映在 Hashmap 的大多数操作中，包括 get 和 put）。在设置初始容量时，应考虑到 Map 中预期的条目数量及其负载系数，以尽量减少 rehash 的次数。如果初始容量大于最大条目数除以负载系数的值，则不会发生 rehash 操作。
 * <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.
 * 👆如果要在一个 HashMap 实例中存储多个键值对，那么创建实例时指定足够大的容量将比让它根据需要 rehash 以扩充容量的效率更高。
 * <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.
 * 👆需要注意的是，HashMap 是非线程安全的。如果多线程同时请求访问 HashMap，并且有至少一条线程改变了 HashMap 实例的结构，那么必须在 HashMap 外层对它添加 synchronized 修饰。（结构修改是指任何添加或删除一个或多个键值对的操作；仅更改实例已包含的键关联的值不是结构修改。）（这一句不太懂诶。。。）
 * 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>
 * 👆如果这样的对象不存在，则该 HashMap 应该被Collections.synchronizedMap()方法包裹起来。最好在对象初创建的时候就这样做，以免发生不可预知的对 HashMap 的访问。
 * <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.
 * 👆HashMap 的迭代器返回的这个类的所有集合视图方法都是‘快速失效’的: 所有在迭代器创建之后对 HashMap 进行结构性修改，除了迭代器自己的 remove()方法外，会抛出 ConcurrentModificationException。在面对并发对 HashMap 的修改时，迭代器会快速彻底的失效，而不会选择在之后冒不确定的、未知的风险。
 * <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>
 * 👆需要注意的是，迭代器的快速失效并不能被保证(一定发生)，，通常来讲，在非同步并发修改 HashMap 的情况下，无法(对快速失效)做出硬性保证。迭代器快速失效后会尽最大努力抛出 ConcurrentModificationException 异常。因此，不能依靠是否抛出该异常来确定写的程序是否是正确的：迭代器的快速失效行为只能被用来查明bug。
 */
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

/**
 * The default initial capacity - MUST be a power of two.
 * HashMap 的默认初始容量--必须是 2 的 N 次方
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 (Also Known As, 即初始值为 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 的 N 次方，且不大于 2^30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 构造器未指定负载系数时，使用该默认值
 * (当 HashMap 的 size 大于 HashMap 的 capacity * loadFactor 时，HashMap 扩容，即 capacity *= 2，并 rehash())
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
/**
 * An empty table instance to share when the table is not inflated.
 * 在表还没有扩容之前，共享该空数组实例
 */
static final Entry<?,?>[] EMPTY_TABLE = {};

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 * 整个表的容量，如果有必要的话(键值对条数/负载系数 >= table.length)会进行扩容。容量大小必须是 2 的幂次方
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
 * The number of key-value mappings contained in this map.
 * map 中键值对的条数
 */
transient int size;

/**
 * The next size value at which to resize (capacity * load factor).
 * @serial
 * 下一次扩容后的大小(容量*负载系数)
 */
int threshold;

/**
 * The load factor for the hash table.
 * table 的负载系数
 * @serial
 */
final float loadFactor;

/**
 * 无参构造方法，使用默认初始容量(16)，默认负载系数(.75)
 */
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
 * 带参构造方法，指定初始容量为initialCapacity
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
 * 带参构造方法，指定初始容量和负载系数
 * 最终所有构造函数都指向该构造函数
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 如果指定的初始容量 <0，则抛出不合法参数异常
    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;
    threshold = initialCapacity;
    init();
}

/**
 * 组建一个与指定 map 相同的 HashMap，使用默认负载系数，初始容量足以盛下该 Map。
 */
public HashMap(Map<? extends K, ? extends V> m) {
    // 如果初始容量大于允许的最大容量，则使用最大容量；否则初始容量为指定 Map 的大小除以负载系数后加一
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    // HashMap扩容到指定容量
    inflateTable(threshold);

    putAllForCreate(m);
}

/**
 * Inflates the table.
 * 表扩容
 */
 private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    // 找到大于 toSize 的最小的2的幂次方的值(因为容量只能为2的幂次方)
    int capacity = roundUpToPowerOf2(toSize);
    // 下次扩容时创建表的初始大小
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
// 寻找大于某个非负数的的最小的2的幂次方的值(eg. roundUpToPowerOf2(5)=8)
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    // 断言 number 为非负数
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    // 当 number 不小于允许的最大容量时，直接返回最大值；
    // 当 number = 1 时，直接返回 1。
    // 否则返回 Integer.highestOneBit((number - 1) << 1)：
    // (number - 1) << 1) = (number - 1)*2
    // Integer.highestOneBit(i): 取 i 这个数的二进制形式最左边的最高一位且高位后面全部补零，最后返回int型的结果。

    // 假设 number 值为 5；那么十进制 5 减去 1 之后得 4，4 的二进制带符号左移一位，得十进制 8；8 的二进制为：1000；经过 Integer.highestOneBit 处理后值还是 8。
    // 假设 number 值为 6，那么十进制 6 减去 1 之后得 5，5 的二进制带符号左移一位，得十进制 10；10 的二进制为 1010；取最高位 1，其余 3 位补零，得 1000，即十进制 8。
}

// 再看看 HashMap 的静态内部类 Entry<K,V>
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    // 只有 next，没有 prev，即单向链
    Entry<K,V> next;
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

    // key 的 getter 方法..略
    // value 的 getter 方法..略
    // value 的 setter 方法
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    // Entry 的 key 和 value 与 o 的 key 和 value 都相等，则return true，否则return false
    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }

    /**
     * This method is invoked whenever the value in an entry is
     * overwritten by an invocation of put(k,v) for a key k that's already
     * in the HashMap.
     */
    void recordAccess(HashMap<K,V> m) {
    }

    /**
     * This method is invoked whenever the entry is
     * removed from the table.
     */
    void recordRemoval(HashMap<K,V> m) {
    }
}

put() 方法

public V put(K key, V value) {
    // 如果这是空表，则首先为表进行扩容，threshold 初始值为 DEFAULT_INITIAL_CAPACITY，即 16
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 为 null
    if (key == null)
        // 该方法进行的操作与下面对非 null key值的操作逻辑基本一致，只不过是在 for 循环中的 判断条件改为了 e.key == null
        return putForNullKey(value);
    int hash = hash(key);
    // 通过 Hash 值找到在数组中的索引值
    int i = indexFor(hash, table.length);
    // 遍历索引指向的单向链表，查看 key 在当前 Map 中是否存在
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果 当前 Entry 对象 e 的 hash 值与 key 的 hash 值相等，且 e.key 与 key 相等，则覆盖原有 e.value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果要插入的 key 在 map 中不存在，，
    // 结构修改次数 ++
    modCount++;
    // 在 HashMap 的 Entry 数组中添加新的 Entry 对象
    addEntry(hash, key, value, i);
    return null;
}

/**
 * Returns index for hash code h.
 * 找到 hash 值在 table 中的索引值
 */
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    //Integer.bitCount(length) 用于计算十进制 length 值的二进制值中 '1' 的个数；Integer.bitCount(length) == 1，即断言 length 值(HashMap 中Entry<?,?>[]的length，即 HashMap capacity)为 2 的幂次方。
    
    // 刚开始是没有看明白这行代码的，求助搜索引擎之后，才有些眉目。
    // 首先，这是按位与操作，，因为 length 值为 2 的幂次方，所以 length - 1后，其二进制的值除高位外全为1(eg. 假设length 值为 8(二进制表现为 1000)， 减 1 得 7；7 的二进制为 0111)
    return h & (length-1);
}

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 * 通过指定的 key、value、hash code 向指定的 bucket 添加一个新的 entry 对象。在适当的时候扩容 table 也是该方法的主要责任。
 * Subclass overrides this to alter the behavior of put method.
 * 子类重写该方法可以修改 put() 方法的行为。
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果当前 HashMap 的 size 大于等于扩容临界值，且当前 Entry 不为 null 的时候
    // 当 table 的 capacity 等于 Integer.MAX_VALUE时，int 类型的 size 最多与 threshold(此时 threshold = Integer.MAX_VALUE)相等，而且 null != table[bucketIndex] 肯定为 true。所以，当 table 达到最大容量后，再调用 put() 会一直覆盖原有的值。
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 2 倍扩容
        resize(2 * table.length);
        // key 为 null，则 hash 值为 0；否则 通过 hash() 方法计算 hash 值
        hash = (null != key) ? hash(key) : 0;
        // 计算扩容之后 entry 将要被放在的 bucket 索引
        bucketIndex = indexFor(hash, table.length);
    }
    // 实际添加 entry 对象的方法
    createEntry(hash, key, value, bucketIndex);
}

/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 * Rehash 当前 map 对象到一个新的更大的数组中去；该方法在 map.size() 达到临界值时自动调用
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 * 如果当前容量达到允许的最大容量时，该方法不会再进行扩容操作，而是直接将临界值设置为 Integer.MAX_VALUE。
 * @param newCapacity the new capacity, MUST be a power of two;
 *        must be greater than current capacity unless current
 *        capacity is MAXIMUM_CAPACITY (in which case value
 *        is irrelevant).
 */
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY = 2^30，即 oldCapacity 最大值为 2^30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // Integer.MAX_VALUE = 2^31 - 1，之后不可能再进行扩容操作了
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization).  This version needn't worry about resizing the table.
 * 本方法与 addEntry() 类似，只不过是用于'伪构造方法时'(克隆、反序列化)，而且该方法不用担心扩容的问题~
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 在未发生散列碰撞时，e 为 null；否则 e 为 entry 实例
    Entry<K,V> e = table[bucketIndex];
    // 构建新的Entry对象，并其属性 next 指向 e，，即在发生散列碰撞的情况下，每次添加 entry 实例时，都是 insert(添加到单向链开始位置)，而非 append。
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
/**
 * Transfers all entries from current table to newTable.
 * 将现在的 table 转移到新的 table中
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 遍历原 Entry 数组中所有对象
    for (Entry<K,V> e : table) {
        // 遍历每个槽位的 entry 单向链
        while(null != e) {
            // ① 👉 记录下 e.next 先
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 计算 e.hash 在新 entry 数组中 bucket 索引
            int i = indexFor(e.hash, newCapacity);
            // ② 👉 将原槽位的 entry 单向链添加到当前 e 的 next 属性中。
            e.next = newTable[i];
            // ③ 👉 将 新数组的指定索引的值 指向 拼接过的新的 entry 单向链。
            newTable[i] = e;
            // ④ 👉 将之前记录下来的 e.next 值重新赋给 e，开始下一轮循环(类似 for 循环中的 i++)。
            e = next;
        }
    }
}
// 👆 transfer() 方法中 将while 循环转成 for 循环，①、④ 处可能会更好理解一点； ②、③ 位置不太好理解，我也是反复咀嚼了好多遍才大概明白一点。
// eg. 我们假设在索引为 i 的槽位处有个 entry 对象 e0，它链接的 entry 对象结构大概为：e0 -> e1 -> e2 -> e3；现在有个 entry 对象 e，e 的 hash 值在新数组中计算得到的索引值同样为 i(即，散列碰撞)；此时需将 e 添加到 e0 的单向链中，③、④ 操作执行过后，该槽位的单向链结构变为：e -> e0 -> e1 -> e2 -> e3。

get() 方法👇

public V get(Object key) {
 if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

/**
 * Offloaded version of get() to look up null keys.  Null keys map
 * to index 0.  This null case is split out into separate methods
 * for the sake of performance in the two most commonly used
 * operations (get and put), but incorporated with conditionals in
 * others.
 * key 值为 null 的指向 map 中 Entry 数组 index 为 0 的 entry 对象。为了更高的性能表现，在 get 和 put 请求中，key 为 null 的情况被分支出单独的方法来处理，但在其他方法中并没有这样去做。
 */
 private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    // 遍历指定 index 位置的的单项链
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

remove() 方法

public V remove(Object key) {
    // 直接看关键方法
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    // ①看到这儿时候我是有些懵哔的..
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        // ③ 关键在这儿
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            // ②直到看到了这儿，我意识到我刚才懵逼早了...
            // 由 ① 很容易得出结论啊，妥妥相等
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        ④
        prev = e;
        e = next;
    }
    return e;
}
// 👆在上面的代码中，如果只看①②，会蒙圈的，，关键在③的分支判断。
// 在发生散列碰撞(由不同的 key，生成了相同的 hash 值)情况下，e.hash == hash 是成立的，但 (k = e.key) == key 或 key.equals(k)就不成立了。
// eg. 如果要删除的单向链节点在链的开头，则直接走 (prev == e) 分支，将 table[i] 指向 其 next 属性的节点；如果要删除的单向链节点位于第二，则在直接将第一个节点的 next 属性指向第 3 个节点即可。

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.
 * 返回当前 map 键值对映射的 set 快照(??)。该集合由 map 支持，所以对 map 的修改会反映到 set中，反之亦然。
 * 如果 map 在 set 迭代的过程中被修改(除了迭代器本身的remove()和迭代器返回的 map entry的 setValue()操作)话，其结果是未知(??)的。
 * set 支持移除元素， Set.remove(),removeAll(), retainAll() 和 clear() 会直接影响到相关的 map。set 不知道 add()和 addAll() 操作。
 * @return a set view of the mappings contained in this map
 */
public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}
(实测，在 for(Map.Entry<String,String> m:map.entrySet()) 循环中，通过 map.put() 方法放入新的值，会抛出 ConcurrentModificationException：👇
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextEntry(HashMap.java:922)
    at java.util.HashMap$EntryIterator.next(HashMap.java:962)
    at java.util.HashMap$EntryIterator.next(HashMap.java:960)
    at Test.main(Test.java:12)
如果放入 map 中已存在的 key，不会抛出 ConcurrentModificationException。)

 private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

到这里之后是有点儿懵的，，因为 entrySet0() 方法中第一行代码，entrySet在 HashMap 中是这样声明的：👇

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

之后在其他地方没有明确对其进行赋值的代码，然鹅我们在 Test 类进行 for(Map.Entry<String,String> m: map.entrySet()) 循环时，entrySet明明是有值的。那么 map.entrySet() 到底是在什么时候进行赋值的呢？！这个问题困扰了我很久，在 HashMap 显式继承的 AbstractMap 类和实现的 Map<K,V> 接口中，也没有找到答案。出门遛了一圈，突然想到了 Test 类被编译之后的 class 文件！！然后用 JD-JUI 反编译之后，终于有些发现了：👇

// class 文件反编译之后的 forEach 循环
for (Iterator i$ = map.entrySet().iterator(); i$.hasNext(); localEntry = (Map.Entry)i$.next())

👆我们可以看到，虽说用的是 forEach 循环，但在编译之后还是通过 Iterator 迭代器进行遍历的。首先初始条件 Iterator i$ = map.entrySet().iterator()，我们可以看到 map.entrySet() 返回的是一个 Set<Map.Entry<K,V>>，所以其 iterator() 是 Set 接口实现类的 iterator() 方法。我们继续看 entrySet0() 方法的第二行代码，在 entrySet 为空的情况下，会初始化一个新的 Set<Map.Entry<K,V>> 对象，即 new EntrySet()，我们看看 EntrySet 类：👇

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}
// EntrySet 类集成了 AbstractSet 类，而 AbstractSet 类又实现了 Set<E> 接口，那么 EntrySet 类中的 iterator() 方法就是我们要找的。我们继续顺着往下看 newEntryIterator ：👇
Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}
// 形式渐渐明朗，，再看 nextEntry()
private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;        // next entry to return
    int expectedModCount;   // For fast-fail
    int index;              // current slot
    Entry<K,V> current;     // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }

    public void remove() {
        if (current == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }
}
// 至此，所有问题解决~ 在 Iterator i$ = map.entrySet().iterator() 中，i$ 为 HashIterator，i$.hasNext() 调用的是 HashIterator.hasNext()，(Map.Entry)i$.next() 调用的是 EntryIterator.next()，而 EntryIterator.next() 最终还是调用了 HashIterator.nextEntry()。

<<<<<<<<<<<< 2019-04-02.update

上个月末的时候，花了一个晚上更新了下简历，但并没有到处去投，只是对外可见。陆陆续续开始有公司接触，其中还接到一个电话面试，，是某外包公司的。突如其来的电话面试，有点仓促，但好在前端时间也一直在看书恶补。其中有个很基础的问题，，『简单说下 Java 集合框架各容器类之间的关系』。多亏了学习 『Redis 核心历险』时，对 LinkedList 多看了一眼，也经受住了超越妹妹的考验。当中面试官特地提到 Map 和 Collection 有没有关系? 可以确定是肯定有关系，但有什么关系呢？没有答上来。。那时还没有整理 HashMap 这篇文章，只有 LinkedList。其实在整理这篇文章时也没找到两者之间的关系，因为 interface Map<K,V> 与 interface Collection<E>并没有直接的继承关系。。这时候需要感谢的是『码出高效 Java 开发手册』了，平时把这本书放在了床头，睡前会翻一翻从此再无失眠，并没有从第一张开始读，而是直接挑了最薄弱的数据结构与集合这一章。

OK，下面来说说 Map 和 Collection 的关系！在书中是这样描述的: 👇

在数据元素的存储、查找、修改和遍历中，Java 中的 Map 类集合都与 Collection 类集合存在很大的不同。它是与 Collection 类平级的一个接口，在集合框架图上，它有一条微弱的依赖线月 Collection 类产生联系，那是因为部分方法返回 Collection 视图，比如 values() 方法返回的所有 values 的列表

我们先看 Map 接口的 values() 方法：👇

// Map 接口类
Collection<V> values();

非常明显，，说到values()方法，肯定会想到 keySet() 和 entrySet() ，毕竟这三个方法在 HashMap 迭代的时候可是肩并肩的~👇

// Map 接口类
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();

我们再看看，这三个方法在 HashMap 中的实现~ 👇

// values 方法
public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
}
// Values 类，AbstractCollection 类实现类了 Collection 接口
private final class Values extends AbstractCollection<V> {
    public Iterator<V> iterator() {
        return newValueIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsValue(o);
    }
    public void clear() {
        HashMap.this.clear();
    }
}
// keySet 方法
public Set<K> keySet() {
    Set<K> ks = keySet;
    return (ks != null ? ks : (keySet = new KeySet()));
}
// KeySet 类，abstract class AbstractSet<E> 继承了 AbstractCollection<E> 实现了 Set<E>，而抽象类 AbstractCollection 和 Set 接口 都继承了 Collection 接口。
private final class KeySet extends AbstractSet<K> {
    public Iterator<K> iterator() {
        return newKeyIterator();
    }
    public int size() {
        return size;
    }
    public boolean contains(Object o) {
        return containsKey(o);
    }
    public boolean remove(Object o) {
        return HashMap.this.removeEntryForKey(o) != null;
    }
    public void clear() {
        HashMap.this.clear();
    }
}
// 至于 entrySet() 方法，我们在分析 HashMap 的 forEach 循环时已经挖过源码了。EntrySet 类与 KeySet 类一样，都继承了 AbstractSet 抽象类。

1. 米一–Hash表的前世今生
2. 追逐盛夏流年–HashMap中的indexFor方法分析
3. March@dhyin.top--hashmap的实现原理 数组 entry
4. 哈希拉链法
5. 贝壳风铃–Java遍历HashMap并修改(remove)