带你读 HashMap 源码

以下内容基于JDK8

HashMap简介

HashMap主要用于存放键值对，它基于Hash表的Map接口实现，是非线程安全的。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
}

HashMap可以存放null的key和value，但是null key只能有一个，null value可以有很多个。

JDK8之前的HashMap由 数组 + 链表组成，其中数组是HashMap的主体，链表主要是为了解决哈希冲突而存在。JDK8之后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认是8）并且当前数组长度大于等于64时，会将链表转化为红黑树，以减少搜索时间。

HashMap默认的初始化大小是16，扩充时新容量为原来的2倍。HashMap总是使用2的幂次方作为哈希表的大小。

底层数据结构

JDK8之前版本

JDK8之前HashMap底层是由数组和链表组成。

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);
  return null;
}
static int indexFor(int h, int length) {
  return h & (length-1);
}
static int hash(int h) {
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

HashMap通过对Key的hashcode经过哈希运算处理之后得到hash值，然后通过h & (length - 1)的方式来判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素要存入的元素的hash值和key值是否相同，如果相同就使用新值覆盖旧值，如果不相同就使用拉链法解决冲突。

h & (length - 1)的解释

首先，我们知道HashMap使用一个数组来存储键值对，这个数组的长度是2的幂次方，比如16、32、64等等。假设数组的长度为16。我们将键值对中的键通过一个哈希函数计算得到一个哈希值，比如42。哈希值是一个整数。

现在，h & (length - 1)的作用是将哈希值映射到数组的索引位置。

【栗子】假设哈希值为42，转换成二进制表示为101010。数组长度为16，转换成二进制表示为10000。

现在让我们进行位运算 h & (length - 1)：

  101010   // 哈希值42的二进制表示
& 011111   // 数组长度16-1的二进制表示
---------
  001010   // 结果，转换为十进制是10

所以，在哈希表的数组中，键值对会被放置在索引位置为10的位置上。

h & (length - 1)和h % length这两个表达式的作用都是将哈希值映射到数组的索引位置。

• h & (length - 1)：这是使用位运算进行映射的方式，要求数组的长度必须是2的幂次方。通过使用位与运算，可以保证结果在范围 [0, length - 1] 内。这种方式在计算机底层的实现上效率更高，因为位运算是比较快速的操作。
• h % length：这是使用取模运算进行映射的方式，可以适用于任意正整数数组长度。通过取模运算，结果也在范围 [0, length - 1] 内。然而，取模运算在某些情况下可能比位运算更耗费计算资源，因为它涉及除法操作，而除法通常比位运算要慢一些。

尽管h & (length - 1)和h % length在某些情况下可以得到相同的结果，但前者在性能上更加高效，特别适用于数组长度是2的幂次方的情况。

使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

对比JDK8的HashMap#hash方法和JDK7的HashMap#hash方法

JDK8的hash方法相较于JDK7的方法更加简化，但是原理不变：

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

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

相较于JDK8的hash方法，JDK7的hash方法性能会稍差一些，毕竟扰动了4次。

拉链法

将链表和数组相结合，即创建一个链表数组，数组中的每一格就是一个链表。如果遇到哈希冲突，则将冲突的值加到链表中即可。

JDK8及之后版本

JDK8之后的HashMap在解决哈希冲突时有了较大的变化。

当链表长度大于等于阈值（默认是8），会首先调用treeifyBin方法，这个方法会根据HashMap的数组存储情况来决定是否将链表转换成红黑树存储。只有当前数组长度大于等于64时，会将链表转化为红黑树，以减少搜索时间；否则只是执行resize方法对数组进行扩容。

HashMap源码分析

类属性

/**
 * 默认的初始容量为 16
 * The default initial capacity - MUST be a power of two.
 */
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.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认的负载因子
 * The load factor used when none specified in constructor.
 */
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.
 */
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.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶中结构转换为红黑树对应的table的最小容量
 * 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.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
  * 存放元素的数组，容量总是2的幂次方
  * 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.)
  */
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.
  */
transient int size;

/**
  * 每次扩容和更改map结构的计数器
  * 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).
  */
int threshold;

/**
  * 负载因子
  * The load factor for the hash table.
  */
final float loadFactor;

loadFactor负载因子

loadFactor负载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，数组中存放的数据（entry）越多，越密集，也就是会让链表的长度增加；loadFactor越小，趋近于0，数组中存放的数据（entry）越少，越稀疏。

loadFactor太大导致查找效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75是官方给出的一个比较好的临界值（符合泊松分布）。

threshold

threshold = capacity * loadFactor，当size > threshold时，就需要考虑对数组进行扩增了 => 衡量数组是否需要扩增的一个标准。

构造方法

/**
 * 指定容量大小和负载因子的构造函数
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 */
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;
  // 初始容量暂时存放到threshold，在resize方法中再赋值给newCap进行table的初始化
  this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 指定容量大小的构造函数
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 */
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 默认构造器
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 包含另一个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>.
 */
public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false);
}

上述四个构造方法中，都初始化了负载因子loadFactor，由于HashMap中没有capacity这样的字段，即使指定了初始化容量initialCapacity，也只是通过tableSizeFor将其扩容到和initialCapacity最接近的2的幂次方大小，然后暂时赋值给threshold，后续通过resize方法赋值给newCap进行table的初始化。

putMapEntries方法：

/**
 * Implements Map.putAll and Map constructor.
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  int s = m.size();
  if (s > 0) {
		// 判断table是否已经初始化
    if (table == null) { // pre-size
      // 未初始化，s为m的实际元素个数，ft = s/loadFactor => s = ft * loadFactor
      // => 阈值 = 容量 * 负载因子 => ft就是要添加s个元素所需的最小的容量
      float ft = ((float)s / loadFactor) + 1.0F;
      int t = ((ft < (float)MAXIMUM_CAPACITY) ?
               (int)ft : MAXIMUM_CAPACITY);
      // 根据构造函数可以知道，table尚未初始化，threshold实际上存放的是初始化容量
      // 如果添加s个元素所需的最小容量大于初始化容量，则将最小容量扩容为最接近的2的幂次方大小作为初始化
      // 此处不是初始化阈值
      if (t > threshold)
        threshold = tableSizeFor(t);
    }
    // table已经初始化，并且m元素个数大于阈值，进行扩容操作
    else if (s > threshold)
      resize();
    // 将m中的所有元素添加至HashMap中，putVal中会调用resize初始化或者扩容
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
      K key = e.getKey();
      V value = e.getValue();
      putVal(hash(key), key, value, false, evict);
    }
  }
}

put方法（核心）

HashMap中只提供了put方法用于添加元素，putVal方法只是给put方法调用的一个方法，并没有提供给用户使用。

/**
 * 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.
 */
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

putVal()方法

先总体把握对putVal()方法添加元素的步骤：

1. 如果定位到的数组位置没有元素，直接插入
2. 如果定位到的数组位置有元素，就将该元素和插入的元素的key比较：
   1. key相同，直接覆盖
   2. key不相同，判断该位置是否是一个树节点，如果是，调用putTreeVal方法插入元素；如果不是，则遍历链表插入元素

/**
 * 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) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
	// table未初始化 或者 长度为0，进行扩容
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // (n - 1) & hash确定元素存放在哪个位置中，如果该位置为空，新生成节点存入数组的该位置
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
 	// 该位置已经存在元素
  else {
    Node<K,V> e; K k;
    // 判断该位置第一个节点的hash值和key值是否和插入元素相同，如果相同就直接覆盖
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 判断插入的位置是否是树节点
    else if (p instanceof TreeNode)
      // 是树节点，插入到树中
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 不是树节点，是链表，使用尾插法将元素插入到链表尾部
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          // 在链表尾部插入新元素
          p.next = newNode(hash, key, value, null);
          // 节点数量达到阈值（默认为8）是，执行treeifyBin方法
          // 该方法会根据HashMap中数组的情况来决定是否转化为红黑树
          // 只有当数组长度 >= 64时，才会执行转化红黑树，以减少搜索时间
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 判断链表中的节点的key值与插入元素的key值是否相等，相等则跳出循环
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 用于遍历该位置的链表，与前面的 e = p.next 结合，可以遍历链表
        p = e;
      }
    }
    // 表示在该位置找到key值、hash值与插入元素相等的节点
    if (e != null) { // existing mapping for key
      // 记录 旧value
      V oldValue = e.value;
      // onlyIfAbsent为false或者旧值为null
      if (!onlyIfAbsent || oldValue == null)
        // 使用新值替换旧值
        e.value = value;
      afterNodeAccess(e);
      // 放回旧值
      return oldValue;
    }
  }
  ++modCount;
  // 实际大小大于阈值，扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

图示：

对比JDK7的 put 方法

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);
  return null;
}

大致步骤：

1. 如果定位到的数组位置没有元素，直接插入
2. 如果定位到的数组位置有元素，遍历以这个元素为头节点的链表，依次和插入的key比较，如果hash值和key值都相同，就直接覆盖旧值；如果不同就采用头插法插入元素

resize方法

扩容方法，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。resize 方法实际上是将 table 初始化和 table 扩容 进行了整合，底层的行为都是给 table 赋值一个新的数组。

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  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;
    }
    // 未超过最大值，扩容为原来的2倍
    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
    // 创建对象时初始化容量大小放在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) {
    // 创建时指定了初始化容量或者负载因子，在这里进行阈值初始化
    // 或者扩容前旧容量小于16，在这里重新计算新的size上限
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
  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) {
        oldTab[j] = null;
        if (e.next == null)
          // 只有一个节点，直接计算元素新的位置即可
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 将红黑树拆分成2棵子树，如果子树节点数小于等于 UNTREEIFY_THRESHOLD（默认为 6），则将子树转换为链表。
          // 如果子树节点数大于 UNTREEIFY_THRESHOLD，则保持子树的树结构。
          ((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;
            // 原索引
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            // 原索引+oldCap
            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;
          }
          // 原索引+oldCap 放到数组里
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

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