浅入浅出 1.7和1.8的 HashMap

前言

HashMap 是我们最最最常用的东西了，它就是我们在大学中学习数据结构的时候，学到的哈希表这种数据结构。面试中，HashMap 的问题也是常客，现在卷到必须答出来了，是必须会的知识。

我在学习 HashMap 的过程中，也遇到了不少问题，从概念到使用，整个过程都大大小小有些疑惑，然而我这些疑惑是因为我在某个知识环节上出了问题，导致不能理解，当我看了网上各种关于 HashMap 的有关博客以及 HashMap 的源码后，大致是理解了，但是我又不确定我是否是真的理解了，决定把 HashMap 的基本必须会的知识全部梳理下来，势必得搞定它！

从最开始只是会使用它的 API 进行数据的存取，到决定要搞定疑惑、搞懂它的底层原理！

本篇文章，将从 0 浅入，从什么是哈希表讲起，然后再说 Java 是怎样实现哈希表的。整个梳理过程，将通过源码这个第一手的资料进行梳理分析，吸收知识、解决疑问，一步一步进行梳理，如果你是对 HashMap 懵懵懂懂的同学，那么欢迎跟着我的节奏一起来梳理！

阅读完本篇文章，你将收获：

总之，我相信屏幕前的你读完肯定是有收获的，当然，最大的收获目前是我自己哈哈哈。

全文1万2000多字，欢迎慢慢食用！由于本人水平有限，文中肯定还有许多不足之处，欢迎大家指出！

学习 HashMap 之前，我们需要知道什么？

我们知道 HashMap 就是 Java 中对哈希表这种数据结构的实现，倘若你不知道什么是哈希表，那么自然学习 HashMap 就会有大大的困难，倘若你知道哈希表，但仅仅是懵懵懂懂，有个简单了解，那自然困难会降低许多。

所以，在学习 HashMap 之前，我们自然需要先知道什么是哈希表，当然还需要知道链表，不过本篇文章仅对哈希表作出说明。下面将开始讲讲哈希表这种抽象的数据结构，之所以说抽象，是因为下面只说哈希表应该具备的功能，但是不会给出具体实现，比如说我们可以简单地使用数组来实现哈希表，是吧，但是 Java 中的哈希表的实现就不是单单一个数组就实现了的。

好了，废话少说，开搞！

浅入浅出 1.7和1.8的 HashMap

什么是哈希表？

哈希表（Hash Table，也有另一个称呼：散列表）。

哈希表是一种可以通过键（Key）直接访问存储在某个位置上的值（Value）的数据结构。

Hash 被翻译成「哈希」、「散列」。Key 被翻译成「键」、「关键字」

哈希表可以用来干嘛？

很简单，和我们以前学习的数据结构一样，可以用来存储数据。

这不是废话嘛？确实是废话。

好吧，那么都可以存储数据，为什么还会出现哈希表？直接用以前的顺序表、链表、栈、队列，这些数据结构来存储不行吗？这个问题问得好，确实，反正都是存储，为什么还要哈希表？

要回答这个问题，就得说说为什么要有数据结构了，之所以需要数据结构，有一个目的就是：更有效地进行数据的存储，不同的数据结构有不同的特性，顺序表可以通过下标快速的查找出数据、链表可以不需要占用一整片连续的存储空间进行存储等等。哈希表也是一样。

哈希表如何存储数据？

哈希表存储数据，给定一个 Key，存储一个 Value。这里就需要用到一个哈希函数（散列函数）。

以数学中的「函数」来理解，就是有一个函数是这样的 $f(x) = y$，一个 $x$ 通过函数 $f$ 映射成值 $y$ 。

那么哈希函数也可以这样理解：$hash(key) = address$

即键通过哈希函数映射成了一个地址，这个地址可以是数组下标、内存地址等。

所以呢，存储就是，通过哈希函数，把 Key 映射到某个地址，然后将 Value 存储到这个地址上。

那么存储后如何获取，如何查找到这个 Value 呢？还是一样，通过哈希函数获得 Key 映射的地址，然后从这个地址取出 Value 。理想的情况下，在哈希表中查找数据，查找的时间复杂度是 $O(1)$ 。

所谓的「哈希」，就是 Key 通过哈希函数得到一个函数值（哈希值、哈希地址）的过程。

什么是哈希冲突？

在数学上，函数的映射可以是一对一，也可以是多对一的，也就是说一个 $x$ 可以映射一个 $y$ ，也可以多个 $x$ 映射到同一个 $y$ 上。

哈希函数也一样，它有可能出现多对一的情况，即多个不同的 Key，通过哈希函数得到同一个地址（哈希值）。

这就出现问题了，这种情况，就称为「哈希冲突」。

哈希冲突完整定义：哈希函数可能把两个或两个以上的不同关键字映射到同一个地址，这种情况称为冲突。发生冲突的不同关键字称为同义词。

你想一下，如果两个不同的 Key，比方说 Key1 和 Key2，通过哈希函数得到同一个地址，那么你不解决这个冲突，直接进行存储，那么就是这样的：

这种情况是我们不想看到的，所以我们必须解决冲突。

如何解决冲突？

在解决冲突之前，我们应该尽量减少冲突的发生，这就需要设计得OK的哈希函数。当然冲突是必然的，是逃不掉的，当数据量够多的时候，必然会发生冲突，所以就需要设计好解决冲突的方法。

哈希函数的设计注意点：

解决冲突的方法：

解决冲突的思想就是为冲突的 Key 找下一个没有被占用的地址。

这里就只说这个拉链法。

拉链法

把所有发生冲突的 Key 存储在一个线性链表中，这个链表由 Key 哈希过后得到的地址（哈希地址）唯一标识，这就是拉链法，适用于经常插入和删除的情况。

哈希表查找效率

平均查找长度（ASL-Average Search Length），可衡量哈希表的查找效率。

ASL依赖于哈希表的「装填因子（负载因子）」
$$
装填因子的定义：α = \frac{哈希表中的元素个数}{哈希表的长度}​
$$
装填因子越大，那么冲突的可能就越大，反之亦然。

1.7 版 HashMap

浅入浅出 1.7和1.8的 HashMap

现在知道什么是哈希表了，那么接下来就看看 Java 中对哈希表的实现——HashMap

再次初识 1.7 的 HashMap

我们先看看文档是怎样说的，同时我进行了大体的翻译。（这些说明可以从源码的开头找到）

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, 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 接口实现的，因为 Map 接口提供了所有的映射操作，并且允许空值和空键（HashMap这个类可以简单的看作是 HashTable 类，与之不同是，HashMap 是非同步且允许存储空数据的）。HashMap 这个类不保证映射的顺序，特别是不保证这个顺序会随着时间的改变而保持不变。

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap 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.

当哈希函数恰当地将元素映射到哈希桶（the buckets）中，那么就具有常量时间里的基本操作（get 和 put）性能。遍历 HashMap 这个集合的时候，遍历的时间与 HashMap 实例的容量（哈希桶的数量）加上它的大小（Key和Value的映射数量，即键值对的数量）成正比，因此，不要设置初始的容量太高，或者负载因子太低，这是非常重要的。

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity 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 load factor 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 rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

HashMap 的实例，有两个参数会影响它的性能：初始容量和负载因子。

初始容量就是哈希表中的哈希桶的数量，所谓哈希桶，就是一个个的数组元素所占的坑位，我们可以称整个数组为 table 数组，然后里面的一个个元素位置（table[i]）就是哈希桶。你给定一个初始容量，那么这个容量就会在 table 数组创建的时候，作为这个 table 数组的容量，即其长度、大小。

负载因子是衡量在当前 HashMap 自动扩容前，有多少个哈希桶是可以被获取到的。当哈希表中的 Entry 对象（键值对）的数量超过了负载因子和当前容量的乘积时（load factor × capacity），那么哈希表就会进行重新哈希（rehashed，重构整个哈希表），table 数组就变为原来的两倍大，即扩容两倍。

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 HashMap class, including get and put). 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 的初始容量时，应该。考虑好预期的 Entry 数量以及负载因子，以此减少 rehash 的次数。如果哈希表的初始容量（table 数组的长度）大于 Entry 数量除以负载因子，则不会发生 rehash 操作。

If many mappings are to be stored in a HashMap 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 hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

如果需要使用 HashMap 实例来存储许多的映射，那么就需要创建一个够大容量的 HashMap 实例，这样效率是最大的，比起你搞一个小容量的 HashMap，然后让它自己 rehash、table 数组翻倍。注意，使用许多有着相同 hashCode() 的 Key 的话，那肯定是会降低哈希表的性能的，因为冲突多了，为了降低这种影响，当这些 Key 是可比较的情况下，那么哈希表旧可以使用比较的方式去解决。

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must 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 Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new HashMap(...));

上面的意思就是说，需要注意 HashMap 是不同步的，也就是非线程安全的，在多线程并发的情况下对 HashMap 进行操作（添加、删除、映射），就会发生线程安全问题，导致数据不一致，如果想在多线程的情况下使用 HashMap，那么可以使用 Collections.synchronizedMap 方法将普通的 HashMap 包装成同步的 HashMap。不过不推荐这样使用，我们推荐使用 ConcurrentHashMap。

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a 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.

迭代器快速失败（fail-fast）：如果 Map 在迭代器进行迭代的时候，Map 中的数据被修改了，那么迭代器就会抛出一个异常：ConcurrentModificationException。因为怕有不确定的行为风险，主要来说就是怕数据不一致，怕线程不安全。

看完了文档的说明，现在可以知道，HashMap 大概有这样的东西

看到这里，可能还是有些抽象，没事，接下来我们看下源码。

HashMap 中的成员变量

首先先看看 HashMap 定义的成员变量：

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.
     * 默认的初始化容量大小为16，这个大小必须为2次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 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.
     * 最大的容量，如果任意带参构造函数传入的值大于这个最大容量，就使用这个最大容量
     * 1 左移 30位，即 2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * The load factor used when none specified in constructor.
     * 默认负载因子 0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     * table 数组，必要时就可以重置大小，长度必须总是2次幂，注意这里的数组类型的 Entry
     * Entry 是一个内部类，下面就可以看到了
     */
    transient Entry[] table;
    ... 
    /**
     * Entry 类，主要作为一个存储 Key 和 Value 的节点，同时保存当前的通过哈希函数计算出来的 hash
     * next 指针，主要用于发生冲突时，使用拉链法解决冲突，指向链表下一个 Entry 节点的
     */
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;	 // 键
        V value;		 // 值
        Entry<K,V> next; // 指向下一个节点 ，从而形成解决冲突的链表
        final int hash;  // 哈希值
        ...
    }
    /**
     * The number of key-value mappings contained in this map.
     * size 代表的就是当前存储在 map 中的 Key-Value 映射的数量，即 Entry 的数量
     */
    transient int size;
    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     * table 重置大小的阈值，这个阈值就是之前说的 load factor * capacity
     */
    int threshold;
    /**
     * The load factor for the hash table.
     *
     * @serial
     * 负载因子
     */
    final float loadFactor;
     /**
     * 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).
     * 这个变量主要与 fail-fast 快速失败 有关，后面再说，先留个印象。
     */
    transient int modCount;
    ...
}

所以说，在 JDK 1.7 及以前，HashMap 的底层数据结构是「数组+链表」，这里的数组指的就是 Entry 类型的 table 数组，同时使用 Entry 作为链表的节点。

上图说话！

浅入浅出 1.7和1.8的 HashMap

4 个构造方法

接下来看看构造方法，HashMap 中有 4 个构造方法，按源码中的出现顺序如下：

第一个构造方法，两个参数，一个初始容量，另一个负载因子，很明显，就是构造一个有着确切初始容量和确切负载因子的 HashMap 实例，源码是这样的。

    /**
     * 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) {
        // 下面3个if，是保证代码的健壮性，不是主要内容
        // 初始容量小于0，那么抛出非法参数异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始容量大于最大容量（2^30），直接将2^30作为初始容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 如果负载因子小于等于0，或者负载因子有问题，抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
		// 主要内容在这里
        // Find a power of 2 >= initialCapacity
        // 找到一个二次幂的数，如果当前输入的初始容量刚好的二次幂，就不用找了
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;				// 初始化，赋值
        threshold = (int)(capacity * loadFactor);	// 自动扩容的阈值
        table = new Entry[capacity];				// 创建大小为capacity的Entry数组
        init();	// 一个空方法，有什么用？这个先不管，之后再说，目前知道上面的就足够了。
    }

实际上，搞定上面第一个构造方法，后面的构造方法就轻而易举了。第二个构造方法，只是输入了一个初始化容量，直接调用第一个构造方法，而负载因子就是默认的 0.75。

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

第三个无参的构造方法，直接使用默认 0.75 的负载因子以及默认的初始化容量为 16 的 Entry 类型的 table 数组。然后默认的阈值就是 0.75 × 16 = 12，即当 Entry 个数超过 12，存储第 13 个 Entry 的时候，就会进行 resize、rehash。

	public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

第四个构造方法，接收一个确切的 Map，用 HashMap 包装这个确切的 Map

    /**
     * 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
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

以上，就是 HashMap 的 4 个构造方法，看来还是可以搞定的嘛！

扰动/哈希函数

接着看源码，发现就是 hash() 了。我们知道，在 Object 中，已经有一个 hashCode() 方法了，这个 hashCode() 可以说是一个哈希函数，那为什么在 HashMap 中，又还需要另一个 hash() 方法呢？

在源码注释里已经说明了，就是抵御低质量的哈希函数，让 hashCode() 计算出来的哈希码再次扰动（再次哈希），这是非常重要的，因为 HashMap 使用二次幂长度的 table 数组，不进行再次哈希的话，就会遇到 hashCode 在较低位没有差异的冲突，所以需要使用这个 hash() 方法。总而言之，就是再次扰动，降低冲突发生的概率。

有小伙伴可能有疑惑，「低质量的哈希函数」？hashCode() 不是 Java 固定实现好的吗？为什么怕有低质量的 hashCode() ?

这个问题问得好，实际上，我们可以发现 hashCode() 是一个本地方法（Native Method）

public native int hashCode();

这就意味着，hashCode() 并不是由 Java 语言实现的，而是由 C 或 C++ 这些非 Java 语言是实现的。同一个 native 方法，如果用不同的 JVM 去调用，那么运行效率可能是不一样的，因为不同的 JVM 对于某个 native 方法都有自己的实现，所以才需要扰动函数进行再次哈希。

hash() 方法（扰动函数）传入的参数是 Key 的 hashCode() 计算出来的哈希码（值），将这个哈希码经过 hash() 方法得到最终的 hash 值。

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

留个印象-indexFor

indexFor() 方法，哈希值和数组长度减一进行与运算。

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

获取哈希表的大小、判断哈希表是否为空

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }
    /**
     * Returns <tt>true</tt> if this map contains no key-value mappings.
     *
     * @return <tt>true</tt> if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

put 的过程

HashMap 的 put() 方法：

这个方法就是将某个确切的 Key 与 某个确切的 Value 联系起来，存储到哈希表中，这样它们之间就建立起映射的关系了。

如果当前哈希表中有了这个 Key，那么就用新的 Value 覆盖掉旧的 Value。

Key 和 Value 可以是 null，只能有一个 Key 为 null，可以有多个 Value 为 null。

    /**
     * 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) {
        if (key == null)
            return putForNullKey(value);
        // 将 Key 的 hashCode 再次哈希得到最终的 hash 值
        int hash = hash(key.hashCode());
        // 将 hash 值与数组长度减一进行与运算，计算最终的哈希地址（即数组下标）
        int i = indexFor(hash, table.length);
        // for 循环是遍历这个哈希桶上的链表，如果有链表的话，即 e.next != null 说明有链表了
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 如果该位置的 hash 值和当前要存储的 Key 的 hash 值一样，说明可能是同一 Key 或不同的 Key
            // 同一 Key 的话就可以覆盖，不同 Key 的话就需要解决这个冲突
            // 先是比较内存地址是否相等，如果内存地址不相等，再去使用 equals 方法判断两个 Key 是不是同一个。
            // 如果内存地址相等，说明是同一个 Key 了，不必使用 equals 了
            // equals 判断是相等的话，那么肯定是同一个 Key 了，因为 hashCode 相等不能说明两个对象相等
            // 但两个对象相等的话，那么 equals 一定相等。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 进入这里，说明是同一个 Key，那么就可以用新 Value 覆盖掉旧 Value 了
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);	// 这个先不管
                return oldValue;
            }
        }
		// 走到这里，说明 Map 中没有这个 Key，那么就可以添加这个 Key-Value 的映射了
        modCount++;	// 说明数据发生了改变，fail-fast 会用到
        addEntry(hash, key, value, i);	// 添加这个Entry
        return null;
    }
    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 判断有没有这个 null Key，有就新的 Value 覆盖旧的 Value
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // 没有，那么就添加上这个 Key 为 null 的映射
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
	static class Entry<K,V> implements Map.Entry<K,V> {
        ...
         /**
         * 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) {
        }       
    }

所以，整个过程是这样的：

将 Key 的 hashCode 再次哈希得到最终的 hash 值，然后通过这个 hash 值与数组长度减一进行与运算，计算最终的哈希地址，接着就遍历这个哈希桶（如果这个桶上有链表的话，如果这个哈希桶没有存储元素，那么直接存储到当前哈希桶），判断该位置的 hash 值和当前要存储的 Key 的 hash 值是否一样：

那么到这里，我相信你已经看懂了 put 的过程了！

get 的过程

HashMap 的 get() 方法：

如果 HashMap 中有这个 Key，那么就返回这个 Key 映射的 Value。

    /**
     * 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)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        // 将 Key 的 hashCode 再次哈希得到最终的 hash 值
        int hash = hash(key.hashCode());
        // indexFor(hash, table.length) 获取 Key 所在 table 数组中的下标
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            // for 循环是遍历这个哈希桶上的链表，如果有链表的话
            Object k;
            // 判断该位置上的 Key 是否为我们需要的 Key
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

相信你搞懂了 put 的过程，那么 get 的过程也不难理解，过程是这样的：

将 Key 的 hashCode 再次哈希得到最终的 hash 值，然后通过这个 hash 值与数组长度减一进行与运算，计算最终的哈希地址（被封装成 indexFor 方法了），接着还是一样，遍历哈希桶，判断该位置上的 Key 是否为我们需要的 Key。

自动扩容-resize+transfer

上面我们也说了，有一个阈值，即 load factor × capacity 这个阈值，如果当前哈希表的大小超过了这个阈值，那么哈希表是需要扩容的，在 HashMap 中，它是不要手动干预，是会自动进行扩容的。那么它是怎样自动扩容的？

回顾：

我们回去看下 put 操作，可以看到倒数第二行代码有个 addEntry() 方法

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);	// 就是这里，添加 Entry 对象
        return null;
    }

看 addEntry() 的源码，是这样的：

所以这个扩容就是通过 addEntry() 方法里的 size++ >= threshold 进行判断是否需要扩容，进而调用扩容方法 resize() 实现所谓的自动扩容。

    /**
     * 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.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

我们可以看到 resize() 的时候，参数是两倍的数组长度，也就是说将哈希表的容量扩大成原来的两倍。

resize(2 * table.length);

那下面我们看看扩容是怎样子的，看看 resize() 源码：

源码注释也说了，将会对 HashMap 实例存储的 Entry 进行 rehash（再次哈希）到一个扩容后的新数组。如果当前容量是最大容量（MAXIMUM_CAPACITY，1 <<< 30，即$2^{30}$）了，那么就不会进行扩容，同时设置阈值为 Integer.MAX_VALUE。

    /**
     * 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.
     *
     * 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.
     *
     * @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;	// 原数组长度 = 原容量
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        // 创建一个比原数组长度大两倍的新数组
        Entry[] newTable = new Entry[newCapacity];
        // 转移原数组中的元素（Entry 对象）到新数组中
        transfer(newTable);
        // 原数组引用指向新数组
        table = newTable;
        // 重新计算阈值
        threshold = (int)(newCapacity * loadFactor);
    }
    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        Entry[] src = table;	// 原数组
        int newCapacity = newTable.length;
        // 遍历原数组
        for (int j = 0; j < src.length; j++) {
            // e 可以看成一个指针，指向第j个哈希桶上的Entry节点
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    // 看当前位置上的 Entry 有没有 next，有则说明是链表
                    // next 是 null，说明没有链表，那么就不会执行下面的 while
                    Entry<K,V> next = e.next;
                    // 计算当前 Entry 在新数组中的位置
                    int i = indexFor(e.hash, newCapacity);
                    // e 的下一个节点指向新的哈希桶，可以把哈希桶当作表头，这样方便头插法插入元素
                    e.next = newTable[i];
                    // 新的哈希桶存储这个节点
                    newTable[i] = e;
                    // 移动指针 e 指向下一节点
                    e = next;
                } while (e != null);
            }
        }
    }

所以，总的来说，扩容的过程是这样的：

我们 put 一个元素到哈希表，这个过程会调用 addEntry() 方法，在实际插入一个元素后，判断当前 size 是否大于阈值，大于的话就会扩容，扩容的话，会传入一个两倍原数组大小的参数，然后创建一个新的数组，这个数组的长度是原数组的两倍，再通过一个 transfer() 方法，将原数组中的 Entry 重新哈希（rehash）到新数组中，最后将原数组引用指向新数组，同时计算下新的阈值。

1.7 总结

1.7 的 HashMap，底层是 Entry 类型的数组 + Entry 类型的链表。

这个数组称为 table 数组（也有的人称为桶数组），数组上的每个位置，可以称为哈希桶，每一个哈希桶都是存储 Entry 类型的元素的，同时可以知道每个哈希桶位置上都可以对应着一个解决冲突的链表的位置。

如果当要存储的 Key-Value 的 Key 与当前位置上的 Key 发生冲突，那么就需要进行头插法，将该 Key 插入当前哈希桶对应的链表。

如果当前存储的元素的个数超过了阈值（threshold = load factor × capacity），那么就会进行扩容，创建一个两倍原数组大小的新数组，然后将原数组中的元素重新哈希到新数组中，最后原数组引用指向新数组，进而完成扩容。

1.8 版 HashMap

浅入浅出 1.7和1.8的 HashMap

在 JDK 1.8 开始，就变成了「数组+链表/红黑树」

看看源码与1.7有什么区别

看看区别

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

Node

接着，我们看到这里定义了一个 Node 节点，通过对比 1.7 版的，可以发现这个把 1.7 中的 Entry 换了个名，定义成 Node 节点。也就是说，在 1.8 中的 table 数组，其类型不再是 Entry 类型，而是 Node 类型，即 Node 类型的 table 数组。

    /**
     * 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> {
        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;
        }
    }

Node 数组

transient Node<K,V>[] table;

扰动函数

hash()，扰动函数发生了变化，1.8 源码是这样的：

让 Key 的 hashCode 与上 hashCode 无符号右移 16 位，最终与运算的结果就是最终的 hash 值。

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

而 1.7 的是这样的：

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

构造方法

构造方法也有变化，但是主要的过程还是一样的，主要的区别就是，此时的 table 数组还没有被创建出来。

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }
	public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

可以说在 1.8 这里，HashMap 属于懒加载的了，那么 table 数组何时加载（创建）呢？没错，就是在 put 的时候才创建的。下面我们来看看。

put 的变化

put 多了一层封装，需要在 putVal() 方法中理解

put 的思路还是一样的：根据 Key 计算出哈希地址，判断这个地址上有没有冲突，没有则直接插入这个 Node，有则需要解决冲突。变化大的就是代码的实现（红黑树、尾插法）。

    public V put(K key, V value) {
        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
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab-> table 数组
        // p-> node 指针，指向哈希桶中第一个节点，可以说是链表表头节点
        // n-> 代表 table 数组的长度
        // i-> 代表 table 数组的下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 第一次 put 就会进入这个判断，进行数组的创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果 put 的这个 Key，找到的位置不会冲突，那么直接创建一个 Node 节点存储这个键值对
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 发生冲突进入这里
            Node<K,V> e; K k;
            // 判断是否是同一个Key，是就把指针 e 指向这个节点 p，然后直接走下面的 e 是否为空的判断了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)	// Key 不同，走这里，如果这个节点 p 是一个树节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {	// Key 不同，没有树化，需要遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // e 指向的 p 的下一个节点，如果为空，说明是链表尾部了
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 走到这里，不是链表尾部，继续判断 Key 相同与否，相同就跳出循环，走下面的判断
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 移动指针
                    p = e;
                }
            }
            // 这里就是，如果是同一个 Key ，就会走这里的覆盖
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)	// 判断是否需要扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get 的变化

get 也是，多了一层封装，思路还是一样，获取哈希地址，判断该位置上的元素是否是我们想要的。

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 判断当前哈希表是否存在、是否有元素、得到的哈希地址上是否有元素（算法的健壮性）
        // 判断为 false 的话，自然说明没有任何元素，还 get 个 p？
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 哈希桶第一个元素是我们想要的？是就直接返回了
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 不是，那么看哈希桶上的链表/红黑树
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

扩容机制

1.8 的扩容机制，变化就大了！在 1.7 的时候，主要是通过 resize() 和 transfer() 相互配合完成扩容及元素转移的，在 1.8 的时候，直接把 transfer() 也搞到 resize() 中了，而且 transfer 的 rehash 的算法很美妙。不过扩容时机还是一样，超过阈值就会扩容。

我们看看源码是这样的：

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;	// 一开始 table 还没创建，所以第一次这里的 oldTab 为空
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold 阈值更新为原来的两倍
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 默认初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 扩容，创建新的 Node 数组（当然，第一次创建数组也是在这里创建）
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 原数组不为空
        if (oldTab != null) {
            // 遍历原数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;	// 可以看成一个指针
                if ((e = oldTab[j]) != null) {	// 判断第j个哈希桶是否为空
                    oldTab[j] = null;
                    if (e.next == null)		// 如果这个哈希桶没有下一个节点，说明没有链表
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)	// 如果这个节点是树节点
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 不是树节点并且有下一个节点，说明有链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 尾插法转移链表数据，直到链表没有元素为止
                        do {
                            next = e.next;
                            // 如果这个与操作结果为0，那么放入新数组的位置和原数组的位置是一样的
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)	// 直接放入
                                    loHead = e;
                                else				// 尾插法
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 与操作结果不为0，需要重新计算存放的位置
                            else {
                                if (hiTail == null)	// 直接放入
                                    hiHead = e;
                                else				// 尾插法
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            // 新位置：所在的原数组位置下标加上原数组容量（长度）
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 第一次不会走上面的 if，直接返回新创建默认容量和阈值的数组
        return newTab;
    }

这里面最难理解的就是 (e.hash & oldCap) == 0

理解 (e.hash & oldCap) == 0

需要知道的是：

何时这个操作等于 0 ？

我们可以从 oldCap 入手，假设 oldCap 是 16，那么其二进制为 10000

如果我们想 e.hash & oldCap 等于 0，那么该 Key 的 hash 值的二进制最高位必须为 0，剩下的二进制位可以不管，这样进行与运算后的结果肯定是等于 0 的。

举个例子，假设此时 hash 值对应的二进制为 01111，那么和 oldCap 进行与运算：

``e.hash & oldCap=10000 & 01111` = 00000 = 0

显而易见，当 hash 值二进制的最高位为 0 的时候，和 oldCap 进行与运算后，结果必定为0

但是这个和扩容后位置有什么关系呢？我们知道，扩容是扩为原来的两倍的，所以我们可以看下，计算扩容后该Node 节点应该在哪个新位置。

计算扩容后的位置，我们知道是这样的，「hash 值 & 数组长度减一」的运算结果，就是我们需要的数组下标。

扩容后的应该在的位置（oldCap 是 16，2 倍就是32，32 对应二进制 100000，减一操作后为 011111）：

hash & 2 × oldCap - 1 = 01111 & 011111 = 01111

那没扩容之前的位置在那里？我们计算下：

hash & oldCap - 1 = 01111 & 01111 = 01111

所以，我们可以发现，此时扩容后和扩容前，该元素的位置没有发生变化。 因此，才有这个结论：运算结果为 0 的话，那么放入新数组的位置和原数组的位置是一样的。

何时这个操作不等于 0 ？

同样，从 oldCap 入手，假设此时 oldCap 是16，对应二进制为 10000

如果我们想 e.hash & oldCap 不等于 0，那么该 Key 的 hash 值的二进制最高位必须为 1，剩下的二进制位可以不管，这样进行与运算后的结果肯定是不等于 0 的。

还是一样，举例子，假设 hash 值对应的二进制为 10001，那么和 oldCap 进行与运算：

e.hash & oldCap = 10001 & 10000 = 10000 = 16 ≠ 0

显而易见，hash 值二进制的最高位为 1，那么该结果必定不为 0

同理，来看下扩容前后的位置关系。

扩容前的位置：

hash & oldCap - 1 = 10001 & 01111 = 00001 = 1

扩容后的位置：

hash & 2 × oldCap - 1 = 10001 & 011111 = 10001 = 17

它们之间有一种巧妙的关系，就是：「扩容后的位置」会等于「扩容前的位置」加上「扩容前的数组容量」，也就是说 10001(扩容后的位置) = 1(扩容前的位置) + 10000(扩容前的数组容量，16)

所以，才有这个结论：运算结果不为 0 的话，那么就需要重新计算位置（新位置：所在的原数组位置下标加上原数组容量（长度））。

关于红黑树

待完善，等着填坑。

1.8 总结

在 1.8 的 HashMap中，底层是 Node 类型的数组 + Node 类型的链表 或者 + Node 类型的红黑树。

比起 1.7 来说，变化还是挺多的，源码的写法也变得更加高级，当然效率也变得更高了，引入了红黑树提高查找效率。因为引入了红黑树，所以解决冲突的时候，就有些区别了。

如果当要存储的 Key-Value 的 Key 与当前位置上的 Key 发生冲突，那么就需要进行尾插法（1.7 就是头插法），将该 Key 插入当前哈希桶对应的链表，当这个链表的长度大于 8 且数组长度大于等于 64 时，当前链表就会树化，转成红黑树，当红黑树中的元素小于 6 时，那么就会退化回来成为链表。如果仅仅链表长度大于 8，但是数组长度小于 64，那么就只会进行扩容，不会把链表树化（这部分的源码在 treeifyBin() 方法中）。

结语

以上，就是浅入浅出 1.7 和 1.8 的 HashMap！

最后的最后

由本人水平所限，难免有错误以及不足之处， 屏幕前的靓仔靓女们 如有发现，恳请指出！

最后，谢谢你看到这里，谢谢你认真对待我的努力，希望这篇博客对你有所帮助！

你轻轻地点了个赞，那将在我的心里世界增添一颗明亮而耀眼的星！

标签 , , , , , , , , , , , , , ,

发表回复