详解 Java HashMap 实现原理

时间：2023-03-14 14:14:18|栏目：JAVA代码|点击：次

数据结构

HashMap 是基于哈希值的一种映射，所谓映射，即可以根据 key 获取到相应的 value。例如：数组是一种的映射，根据下标能够取到值。不过相对于数组，HashMap 占用的存储空间更小，复杂度却同样为 O(1)。

HashMap 内部定义了一排“桶”，用一个叫 table 的 Node 数组表示；key-value 存放到 HashMap 中时，根据 key 计算的哈希值决定存放的桶。当多个键值对计算出来的哈希值相等时，就产生了哈希碰撞，此时多个元素会放到同一个桶中。

transient Node<K,V>[] table; // 桶数组
transient int size; // 统计 HashMap 实例中有多少个元素，不等于 table.length

桶的实例有两种，一种是 Node 的实例，是链表；另一种是 TreeNode 的实例，是红黑树。Node 是 HashMap 中的一个静态内部类，TreeNode 继承了 Node。当桶中的元素较少时，桶的结构为单链表；当桶中的元素较多时，桶的结构会被转化为红黑树。

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent; // red-black tree links
  TreeNode<K,V> left;
  TreeNode<K,V> right;
  TreeNode<K,V> prev;  // needed to unlink next upon deletion
  boolean red;
}

下图表示的是一个 HashMap 内部存储结构。第 1 行表示的是 table 数组，数组中的元素可能为 Node 实例，TreeNode 实例，或者 null。table 数组的长度至少为 64 才能存放 TreeNode。

需要注意的是，单链表的长度和红黑树元素数量取决于 TREEIFY_THRESHOLD（值为 8）, UNTREEIFY_THRESHOLD（值为 6），MIN_TREEIFY_CAPACITY（值为 64）三者。

下面几个结论不是很准确：

❌ 单链表长度最多为 8，超过了 8 就会被树化。

✅ 单链表树化不仅要满足单链表长度超过 8，而且要满足 table 数组的长度达到 MIN_TREEIFY_CAPACITY，只不过每次尝试树化而实际没有树化的话，都会将 table 的长度增加 1 倍。所以单链表的长度有可能超过 8。

❌ 红黑树中元素的数量总是超过 8

✅ table 在扩容的过程中可能会触发树的拆分，即一个桶中的元素在 table 扩容之后可能分配到两个不同的桶里，一棵红黑树可能被拆分成两棵。若拆分后红黑树元素的数量小于等于 UNTREEIFY_THRESHOLD ，树会被转化为单链表。意味着拆分之后红黑树元素的数量可能为 7 或者 8。

为什么单链表元素较多的时候要转化为红黑树？

单链表桶转化为红黑树桶的过程称为桶的树化，在 HashMap 源码中对应 treeifyBin(table, hash) 函数。如果使用单链表作为桶的数据结构，存在大量哈希碰撞时，链表会变得很长，进行一次操作的时间复杂度将变成 O(K)，其中 K 为所操作的桶中元素的个数。而红黑树能够保证时间复杂度为 O(log(K))，所以桶中元素过多时，使用树效果会更好，也可以在一定程度上防范利用哈希碰撞进行的黑客攻击。是一种时间上的优化。

不过相对于链表节点 Node，红黑树节点 TreeNode 需要多维护 4 个引用和 1 个红黑标志，存储空间相对更大。而 HashMap 中的大部分桶都是存储很少量元素的（如果大多数桶都存储很多，键的哈希函数设计可能不太不合理），所以在一般情况下，也就是桶中元素很少时使用链表进行存储。是一种空间上的优化。

另外，桶的数据结构之所以不使用二叉排序树，是因为二叉排序树在特殊情况下会退化成单链表。例如：不断往同一个桶中从小到大顺序放入元素，会导致所有的节点都只有右孩子。而红黑树能够确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

构造器

HashMap 提供了 4 个构造器，其中带有参数 initialCapacity 和 loadFactor 这两个参数的构造器最为关键。其源码如下。

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

initialCapacity 表示的为期望的 table 的长度，JDK 源码中的大多数 capacity 指的都是底层存储数组的长度；loadFactor （负载因子）是一个在区间 (0,1) 的小数，它决定了何时应该对 table 进行扩容。

table 数组的长度发生改变时，将根据 loadFactor 计算 threshold 的值，公式为 threshold = table.length * loadFactor。当 HashMap 中元素的数量 size 大于阈值 threshod 时，将触发 table 扩容。

构造器将传入的 loadFactor 直接赋值给了成员变量 this.loadFactor，然后调用了 tableSizeFor(capacity) 函数计算了 this.threshold 的初始值。在这里 thershold 的意义是临时存储 table 的初始长度，只有往 HashMap 中放入元素时，才构造 table 数组，这是一种延迟初始化策略。

tableSizeFor(capacity) 函数将计算出一个恰好大于等于 capacity 的2的n次方整数，作为 table 数组的长度，也就是说 table 数组的长度总是 2 的 n 次方。看这个算法时，将关注点放在 cap 的二进制最高位 1 比较容易理解。

  static final int tableSizeFor(int cap) {
    int n = cap - 1; // 处理特殊情况：cap 恰好为 2 的 n 次方，即最高二进制位 1 右边全部为 0 的情况
    n |= n >>> 1; // 最二进制位1右边1位填充 1 个 1
    n |= n >>> 2; // 继续填充2个 1
    n |= n >>> 4; // 填充 4 个 1
    n |= n >>> 8; // 填充 8 个 1
    n |= n >>> 16; //填充 16 个 1。 执行完这句之后，已经确保最高位右边部分全部填充成了 1，例如：cap = 101_0101b 时，n = 111_1111b
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n+1 进位，返回 1000_0000b
  }

剩下的 3 个构造器如下。

  // 传入 initialCapacity，负载因子使用的是默认值 0.75
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  // capacity 和 loadFactor 均使用默认值
  public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }

  // 传入一个 map，传入的元素会逐个放入到新构造的 HashMap 实例中
  public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
  }

put(k, v) 过程

put(key, v) 是先调用了 hash(key) 方法计算了一下键的哈希值，然后调用的是 putVal() 方法将节点放到 HashMap 中。

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

哈希值计算

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

若 key 为 null，则直接返回 0 作为哈希值；
若 key 不为 null，则对 key.hashCode() 的结果的高 16 位和低 16 位进行异或操作再返回

这里对哈希值二进制的高 16 位和低 16 位取余的原因是为了让这两部分的二进制位都对桶的选择结果产生影响，减小哈希碰撞的概率。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
        boolean evict) {
  // tab 代表 table 数组；p 表示节点；n 表示桶的数量；i 指向应该放入的桶的下标
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // table 没有初始化，调用 resize() 构造 table 数组
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 如果桶中没有元素，则 table 数组的元素作为节点
  if ((p = tab[i = (n - 1) & hash]) == null) // 因为 n=2^x，所以 (n-1)&hash 等价于 hash % n
    tab[i] = newNode(hash, key, value, null);
  else { // 桶中有元素
    Node<K,V> e; K k; // e 表示要存放值的 Node ， k 表示对应的键，如果键不存在 e 的值为空，如果键存在，让 e 指向该节点
    if (p.hash == hash && // p 此时指向 table 中的元素，也就是链表或者树的根
      ((k = p.key) == key || (key != null && key.equals(k)))) // 如果 p.key 恰好与 key 相等，存在着一个节点，让 e 指向它
      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);
          // 这一句很魔幻，有人说链表中达到了 7 个元素就会被树化，也有说是 8 个的，
          // 实际上往桶里放入第 9 个元素时才会树化，不信可以看一下这个实验：https://github.com/Robothy/java-experiments/blob/main/HashMap/TreeifyThreshold/TreeifyThresholdTest.java
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k)))) // 在链表中找到了相同的 key
          break;
        p = e;
      }
    }
    // 如果 key 已经存在了，HashMap 不会取构造新的 Node，而是直接修改 Node 中的 value 属性
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e); // 这句在这里什么也没干，留给 LinkedHashMap 的
      return oldValue;
    }
  }
  ++modCount; // 操作数统计，用来检查是否有多个线程同时修改 HashMap，JDK中很多非线程安全的容器中都用了这些操作
  if (++size > threshold) // size 超过了 threshold，进行扩容操作
    resize();
  afterNodeInsertion(evict);
  return null;
}

上面代码中，需要注意以下几点：

根据哈希值选择桶的算法是 (n-1)&hash，由于 n 为 2 的幂次方，所以 (n-1)&hash 等价于 hash%n 。之所以采用位运算而不使用取余运算，是因为对于计算机来说，取余的计算开销远大于位运算。能够这样进行等价的前提是 n 为 2 的幂次方。这是哈希桶的数量总保持为 2 的幂次方的重要原因。可以在这里验证一下这个算法。
桶中如果只有少量元素，桶的结构为单链表，某个桶中的元素超过了 TREEFIED_THRESHOLD，值为 8（必要非充分条件，前面有介绍，还需要满足桶的数量达到 MIN_TREEIFY_CAPACITY，值为 64 ），该桶的结构将会转化为红黑树；
当 HashMap 中元素的数量超过了阈值 threshold 时（threshold = 桶数量 * loadFactor），将触发哈希表的扩容。

整个 put(k, v) 大致流程：

resize() / rehash

上述流程中，还有两个重要的过程。首先是红黑树的操作，它能够在 log(K) 的时间复杂度内完成增删查改，K 为红黑树中元素的数量。

另一个操作时 resize()，它的目的是初始化哈希表 table 或者增加哈希桶的数量，减小哈希碰撞的概率。具体操作是让成员变量 table 指向一个 Node 数组。

上面流程图中可以看到，有两个地方可能会触发 resize()。一是 table 未初始化时，需要初始化 table。此时 table 初始长度可能为：
1）threshold，指定了 initialCapaclity 的情况下，构造器中会根据 initialCapacity 计算出一个 capcacity 并赋值给 threshold；
2）DEFAULT_INITIAL_CAPACITY（值为 16），没有指定 initialCapacity 的情况下。

二是 HashMap 中元素的数量超过了阈值（即：size > threshold），需要对 table 进行扩容。此时 table 的长度为变为原来的 2 倍，HashMap 的内部结构也会发生改变，同一个桶中的元素可能被分配到不同的桶中。这个过程也叫 rehash。

resize() 源代码比较长，这里分为两部分来看，一部分是构造新的 Node 数组，更新 threshold；另一部分是将旧的 table 中的元素放到新 table 中的过程。先看前一部分：

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table; // oldTab 指向旧的 table
  int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧table的长度，如果 table 为空，则长度为 0
  int oldThr = threshold; // 旧的阈值，如果 table 没有初始化，threshold 临时存储的是构造方法中根据 initialCapacity 计算的初始 capacity
  int newCap, newThr = 0;
  if (oldCap > 0) { // 这句的含义是 table 已经初始化了，现在要对它扩容
    if (oldCap >= MAXIMUM_CAPACITY) { // 值已经达到了 2^31，不能再扩容了，因为 int 范围内不能再进行乘以 2 操作了，否则会导致整数溢出
      threshold = Integer.MAX_VALUE; // 直接将 threshold 的值提高到 int 范围内的最大值，让后续的 put 操作不再触发 resize()
      return oldTab; // 直接返回，不扩容了
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // 新的 threshold 变为原来的两倍，因为新的 capacity 也是原来的两倍，而 threshod = capacity * loadFactor 
  }
  else if (oldThr > 0) // 旧的 threshold 大于 0；含义是 table 需要初始化，不过在构造 HashMap 时指定了 initialCapacity，table 的初始长度已经定下来了，临时存放在 this.threshold 中，等于 oldThr
    newCap = oldThr; // 那么新的 table 的长度直接设置为 oldThr 即可
  else { // 含义是 table 需要初始化，但是构造器中没有指定初始化的相关参数，则直接使用默认参数计算即可
    newCap = DEFAULT_INITIAL_CAPACITY; // 值为 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 值为 16 * 0.75 = 12
  }
  if (newThr == 0) { // table 需要初始化，且构造器中指定了初始化参数
    float ft = (float)newCap * loadFactor; // 使用构造器指定的参数计算阈值，临时放在 ft 中。新阈值 = 新数组长度 * 负载因子
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
         (int)ft : Integer.MAX_VALUE); // 检查 ft 有没有超出范围，毕竟是用户输入的参数，需要进行检查
  }
  threshold = newThr; // 将前面步骤中计算得到的 newThr 赋值给 this.threshold
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 实例化新的 Node 数组
  table = newTab; // 让 table 指向新的 Node 数组
  if (oldTab != null) { // 旧的 table 不为空，则需要将旧 table 中的元素放到新的 table 中
    // 省略将旧的 table 中的元素放到新的 table 中的代码
  }
  return newTab;
}

resize() 前半部分代码计算了新的阈值 threshold，创建了空的哈希表。接下来的代码是将旧的哈希表中的元素放到新的哈希表中。

代码算法的大致流程为：遍历每一个桶，若桶为单链表，则拆成两个链表作为2个新的桶；若桶为红黑树，则拆成2棵红黑树作为新的桶，若新的红黑树中元素的数量小于等于 UNTREEIFY_THRESHOLD，值为 6，则将红黑树转化为单链表。

旧的桶之所以能够恰好拆分成两个新的桶，是因为新的桶的总数 newCap 为旧桶总数 oldCap 的 2 倍，即 newCap = 2 * oldCap，若 hash % oldCap == j，则 hash % (2*oldCap) 的值为 j 或 oldCap + j。也就是说下标为 j 的桶会可能被拆分成下标为 j 和 oldCap+j 的两个桶。

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) // 桶中只有1个元素
        newTab[e.hash & (newCap - 1)] = e;
      else if (e instanceof TreeNode) // 桶为红黑树
        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 同样拆分成两个桶
      else { // 桶为单链表
        Node<K,V> loHead = null, loTail = null; // 子链表（新桶），存放哈希值 % newCap == j 的元素
        Node<K,V> hiHead = null, hiTail = null; // 子链表（新桶），存放哈希值 % newCap == j + oldCap 的元素。
        
        Node<K,V> next;
        do { // 遍历链表
          next = e.next;
          if ((e.hash & oldCap) == 0) { // 算法比较巧妙，通过临界的 1 位二进制位即可判断该哈希值余上 newCap 所属桶
            if (loTail == null)
              loHead = e;
            else
              loTail.next = e;
            loTail = e;
          }
          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;
        }
      }
    }
  }
}

get(k) 过程

get(k) 方法显得比较简单，它调用了 getNode() 方法。算法的时间复杂度约等于 O(1)

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) { // hash%table.length 定位到桶
		
    if (first.hash == hash && // always check first node
      ((k = first.key) == key || (key != null && key.equals(k))))
      return first; // 直接取 table 中的元素
    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;
}

remove(k) 与 remove(k, v)

这两个重载方法均调用了 removeNode 方法。remove(k) 只要找到对应的 key 匹配即移除，remove(k, v) 需要 key 和 value 均匹配才移除。

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}

public boolean remove(Object key, Object value) {
  return removeNode(hash(key), key, value, true, true) != null;
}

removeNode() 方法中流程大致为：根据 key 和 hash 找到对应 Node，然后根据各种条件判断是否执行移除。HashMap 的数据结构决定了此操作的时间复杂度仍然大致为 O(1)。

final Node<K,V> removeNode(int hash, Object key, Object value,
              boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
    (p = tab[index = (n - 1) & hash]) != null) {
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k)))) // key 为桶中的第 1 个元素
      node = p; // 直接取 table[(n-1)&hash] 
    else if ((e = p.next) != null) { // 桶中超过 1 个元素
      if (p instanceof TreeNode) // 桶为红黑树
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else { // 桶为单链表
        do { // 单链表搜索
          if (e.hash == hash &&
            ((k = e.key) == key ||
             (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
		
		// 若找到了 key，对应的节点由 node 指向
    if (node != null && (!matchValue || (v = node.value) == value ||
               (value != null && value.equals(v)))) { // 检查 key 和 value 是否均符合要求
      if (node instanceof TreeNode) // node 为红黑树节点
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); // 执行红黑树移除操作
      else if (node == p) // 查找到的 node 为桶中的第 1 个元素
        tab[index] = node.next; 
      else
        p.next = node.next; // 执行单链表移除
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

迭代

HashMap 没有直接或间接实现 Iterable 接口，因此不能直接使用 for-each 语法结构去遍历一个 HashMap。不过可以通过 entrySet() 方法获取一个 EntrySet，然后对 EntrySet 进行遍历来达到访问每一个 key-value 的目的。

方法 entrySet() 采用了延迟加载和缓存的机制，只有调用 entrySet() 方法时才创建 EntrySet 对象，并赋值给成员变量 this.entrySet 缓存起来。重复调用 entrySet() 并不会产生多个 EntrySet 对象。

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

EntrySet 中的 iterator() 返回的是 EntryIterator 对象，迭代相关的部分代码如下。

int index;       // 指向当前的桶，初始值为 0
final Node<K,V> nextNode() {
  Node<K,V>[] t;
  Node<K,V> e = next;
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  if (e == null)
    throw new NoSuchElementException();
  if ((next = (current = e).next) == null && (t = table) != null) {
    do {} while (index < t.length && (next = t[index++]) == null); // 不断地跳过空的桶
  }
  return e;
}

迭代 HashMap 的顺序是逐个遍历哈希桶，桶中有元素，则遍历单链表或红黑树。因此，遍历 HashMap 时的顺序与放入顺序无任何关系。HashMap 内部也没有维护任何与插入顺序有关的信息。