深入 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个全局变量，理解它们的含义：

1. 变量key与变量value

   这两个变量对应的是我们要保存的键值对的key和value，也是HashMap的核心数据。每一个被put到HashMap中的键值对都会创建一个对应的Entry对象，而该Entry对象中的key和value属性就保存了我们put进去的键值对的key和value的值。

   其中类型 K 和 V 是Java中的泛型一种写法，泛型保证了HashMap中所保存的所有的key的类型一致，所保存的所有的value的类型也一致。

2. 变量next

   HashMap中的哈希表使用的是数组+链表的形式，所以Entry类需要是设计成一种可以构成链表的结构。Entry对象中的next变量就是一个指向Entry链表中的下一个Entry对象的指针，通过这个变量，就可以把Entry对象通过链表的形式连接起来。关于哈希表数据结构的更多信息，可以参见我之前所写的HashTable 的 Python 实现。

3. 变量hash

   把当前对象的key所对应的hash值保存起来，方便之后调用。

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

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

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

1. public HashMap(int initialCapacity, float loadFactor);
2. public HashMap(int initialCapacity);
3. 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);
  }

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

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

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

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方法的实现很简单，分为以下这几步：

1. 通过key来计算出对应hash值；
2. 通过hash计算出对应的table下标；
3. 通过下标已知了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工作原理及实现