深入 Java HashMap

HashMap 是 Java 自带的基础类库中使用频率极高的一个类，其内部使用java.util.HashMap.Entry<K, V>对象来保存键值对，并且使用哈希表作为内部的存储数据结构，读写效率极高，但是其本身存储的数据是无序的。HashMap 位于rt.jar的java.util包下，最初于 JDK1.2 中首次发布。

这篇文章所分析的 HashMap 的源码对应 JDK 的版本为 1.7，该版本 HashMap 的代码出自鼎鼎大名的 Doug Lea 之手。在 JDK1.8 中 HashMap 被重写，与 1.7 版本中的源码差异比较大，敬请读者注意。

1. 使用 Entry<K, V>来存储每一组数据

HashMap 的最基本单元是Entry<K,V>，每一个 Entry 对象包含了如下的四个属性：

final K key;      // 保存一组数据的 key
V value;          // 保存一组数据的 value
Entry<K,V> next;  // 保存该对象所指向的下一个 Entry 对象
int hash;         // 保存 key 所对应的 hash 值

Entry 的构造方法如下，构造方法的目的是对上面的四个参数进行初始化：

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

Entry 类还包含了 getKey()、getValue()、setValue等等这样的方法，因为这些方法的实现比较简单，就不一一赘述了。

下面我们来讨论一下 Entry 类所对应的这 4 个全局变量，理解它们的含义：

变量 key 与变量 value
这两个变量对应的是我们要保存的键值对的 key 和 value，也是 HashMap 的核心数据。每一个被 put 到 HashMap 中的键值对都会创建一个对应的 Entry 对象，而该 Entry 对象中的 key 和 value 属性就保存了我们 put 进去的键值对的 key 和 value 的值。
其中类型 K 和 V 是 Java 中的泛型一种写法，泛型保证了 HashMap 中所保存的所有的 key 的类型一致，所保存的所有的 value 的类型也一致。
变量 next
HashMap 中的哈希表使用的是数组+链表的形式，所以 Entry 类需要是设计成一种可以构成链表的结构。Entry 对象中的 next 变量就是一个指向 Entry 链表中的下一个 Entry 对象的指针，通过这个变量，就可以把 Entry 对象通过链表的形式连接起来。关于哈希表数据结构的更多信息，可以参见我之前所写的 HashTable 的 Python 实现。
变量 hash
把当前对象的 key 所对应的 hash 值保存起来，方便之后调用。

以上就是 Entry 类所对应的几个变量和方法，都比较简单。需要知道的是，Entry 类是 HashMap 的一个内部类，并且实现了java.util.Map.Entry<K,V>接口。接下来我们看看 HashMap 是通过何种方式来构建哈希表的。

2. 通过 Entry 数组来构建一个哈希表结构

HashMap 一共有四个构造方法，抛开一个用来从其他 Map 对象构建 HashMap 的构造方法不谈，另外三个构造分别方法是：

public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap();

第 2 和第 3 个构造方法都是在调用第一个构造方法，只是把某些参数设为了默认值而已，所以现在我们重点看看第一个构造方法的两个参数所代表的意义。

initialCapacity 的意思是初始化容量，回想一下 Hash 表的结构，这里所谓的初始化容量其实对应的就是保存哈希值的数组的初始长度（对哈希表结构不清楚的同学还是建议先看看文章 HashTable 的 Python 实现），同时也表示了所有可能产生的哈希值的数量。如果不主动设置，哈希表的初始容量会被设置为 16。
loadFactor 的意思是加载因子，在任一个时刻，如果数组已经使用的容量（即已经保存有值、非空的位置）大于或等于临界值，那么数组就需要把自己的容量扩大到原来的容量的两倍。而在 HashMap 中临界值threshold的计算方式为 [当前数组的容量 * 加载因子]，所以加载因子就是用来控制数组容量的增长速度的。如果不主动设置，那么加载因子默认为 0.75。

讲了哈希表的初始化方法，我们就可以了解 HashMap 中的哈希表的结构了。哈希表其实在本质上就是一个Entry类型的数组，因为Entry本身可以构成一个链表，所以这就和经典的哈希表的结构一致起来了。下面看一下哈希表的初始内容：

/**
 * 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.
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

可以发现，哈希表的初始化只是把变量 table 设置为一个空的Entry数组而已，接下来我们所有的数据都将会保存在这个数组里面。

3. 向 HashMap 中放入数据吧！

好了，既然已经了解了哈希表是怎么构成的了，是时候向 HasMap 中放入数据了，让我们来看一下 HasMap 的public V put(K key, V value)是如何实现的。

下面这个方法主要是对 table 和 key 进行了空判断并进行了相应的操作，之后根据 key 来计算 hash 值和数组的下标。然后在指定的数组下标中，对这个数组项对应的 Entry 链表进行遍历，如果发现之前已经有对应该 key 的值存在了链表里面，则把旧的值替换为新的要保存的值并把旧的值返回，操作完成。

public V put(K key, V value) {
    // 如 table 为空，则需要把 table 扩展到默认容量的大小
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 为空，则会把其保存在数组的第 0 位
    if (key == null)
        return putForNullKey(value);
    // 根据 key 计算对应的 hash 值
    int hash = hash(key);
    // 根据 hash 值和数组的长度计算出这个 hash 值对应的数组的下标
    int i = indexFor(hash, table.length);
    // 因为已经知道数组的下标，所以只对数组中与该 key 的 hash 一致的那个链表进行一次遍历操作就可以了，如果发现连表中的某
    // 个节点的 key 与我们所要 put 的 key 是一样的，那么只需要把旧的值覆盖掉置换为新的值就行了，然后把旧的值返回
    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++; // 可以忽视此操作
    // 如果在链表中没能够找到一致的 key，则需要插入新的 Entry 对象用来保存新值
    addEntry(hash, key, value, i);
    return null;
}

如果没能在链表中找到对应的 key 值，则意味着需要在表中插入新的值了，下面这个方法就表示了这种情况。这里会分成两种情况：

若数组容量达到了扩容的条件，则需要先对哈希表进行扩容，扩容之后对哈希表进行重新排列，然后再把值插入哈希表中；

如果不需要扩容，则直接把对应的值插入到哈希表中即可；

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果当前数组的容量已经大于或等于临界值且这个 hash 值对应的链表不为空，那么就需要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length); // 扩容
        hash = (null != key) ? hash(key) : 0; // 扩容之后重新计算 hash 值
        bucketIndex = indexFor(hash, table.length); // 重新计算对应的下标
    }

    createEntry(hash, key, value, bucketIndex);
}

我们先讨论一下不需要扩容的单纯的插入操作，因为这一步比较简单，扩容操作后面会再说。插入节点对应着两步操作：

把新节点的 next 指针指向当前数组上对应下标位置的头结点；
把当前节点置换为新的头结点。

具体的实现在下面，比较简单，就不多说了。

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

下面我们重点来讲一下扩容的相关操作，我们先看一下 HashMap 中是怎么实现扩容操作的：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) { // 如果容量已达扩展上限，把临界值改为 int 最大值
        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); // 修改临界值
}

首先是判断了一下当前数组的容量，如果容量已达上限，就把临界值改为 int 最大值，意味着不会再进行扩展。

如果没有达到容量上限，那么首先会创建一个新的 Entry 数组，其容量是当前数组的容量的两倍，之后会把当前的哈希表中的值全部转移到新的数组中去（这一步极其耗费时间），之后再根据新容量把临界值修改一下即可。下面我们再讨论一下如何把旧表中的值转移到新建的表中，具体实现如下：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

其实原理也很简单，就是把旧表中的所有的值全部遍历一遍，然后每从旧表中查到一个值，就把它插入到新的表中。

因为这一步的操作非常耗时，所以我们在操作 HashMap 的时候要尽量避免频繁的对表进行扩容操作。如果能够大概的估算出 HashMap 所需要的容量大小，那么在定义 HashMap 的时候最好就指定好其容量，这样就能避免在频繁扩容的时候带来的性能的损失。

最后，放上一张 HashMap 中的插入操作的流程图：

4. 从 HashMap 中查找数据

在从 HashMap 中查找数据的时候，同样需要对 key 进行是否为空的判断。如果 key 为空，因为之前我们把 key 为空的值都保存在table[0]中了，所以这一次在取得时候也只需要从table[0]去取就行了。

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

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

如果 key 不为空，就调用Entry<K,V> getEntry(Object key)方法，getEntry 方法的实现很简单，分为以下这几步：

通过 key 来计算出对应 hash 值；
通过 hash 计算出对应的 table 下标；
通过下标已知了 table 中的槽位，然后对该槽位的链表做个遍历，找到了符合要求的 Entry 就返回，否则返回 null；

实际的实现代码如下：

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

    int hash = (key == null) ? 0 : hash(key);
    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;
}

5. 从 HashMap 中删除数据

删除操作同样也很非常简单，只是对 key 所对应的槽位的链表做一次遍历，之后找出对应的 Entry 就把其删除掉。

不过删除需要注意的一点是删除的节点是否是头结点：

如果是头结点，那么就让头结点的下一个节点成为新的头结点，头结点删除完成；
如果不是头结点，就让对应节点的前一个节点的next指向要删除节点的下一个节点，指定节点删除完成；

具体实现如下：

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

6. 更多

HashMap 是 Java 中最常用的数据结构之一，除此之外还有几个比较常见的类：

HashTable，与 HashMap 相比，HashTable 是线程安全的并且不可插入空值，其余部分基本一样；
TreeMap，这也是一种实现了 Map 接口的实现类，与 HashMap 相比，其内部实现的数据结构为红黑树，操作效率略低于 HashMap，不过其存储的数据是有序的，TreeMap 适用于需要对数据进行有序存储的场合；
ConcurrentHashMap，是 HashMap 的线程安全的实现版本，同样出自于 Doug Lea 之手；

本文所讲解的 HashMap 的内容源于 JDK 版本 1.7，HashMap 的实现在 JDK1.8 中被重写了，如果想了解 JDK1.8 中相关的操作的实现方法，可以参考：Java HashMap 工作原理及实现