MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java HashMap 扩容机制深度分析

2021-10-047.8k 阅读

Java HashMap 概述

在深入分析 Java HashMap 的扩容机制之前，我们先来简单回顾一下 HashMap 本身。HashMap 是 Java 集合框架中常用的一个类，它基于哈希表实现，用于存储键值对（key - value pairs）。HashMap 允许 null 键和 null 值，并且不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap 的实现依赖于数组和链表（在 JDK 1.8 及之后，当链表长度达到一定阈值时会转化为红黑树）。数组的每个元素称为一个桶（bucket），通过对键的哈希值进行计算，确定键值对应该存储在哪个桶中。如果不同的键计算出了相同的桶位置，就会发生哈希冲突，此时这些键值对会以链表（或红黑树）的形式存储在该桶中。

核心属性

  1. capacity：哈希表的容量，也就是数组的大小。初始容量通常为 16，且必须是 2 的幂次方。这是因为在计算元素存放位置时，采用位运算(n - 1) & hash（n 为容量），只有容量是 2 的幂次方，这种运算才能均匀地分布元素，减少哈希冲突。
  2. loadFactor：负载因子，默认值为 0.75。它表示哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的键值对数量超过capacity * loadFactor时，就会触发扩容。
  3. threshold：阈值，等于capacity * loadFactor。它是判断是否需要进行扩容的一个临界值。

扩容机制简介

当 HashMap 中的元素数量（size）超过阈值（threshold）时，就会触发扩容操作。扩容的本质是创建一个新的更大的数组，并将原数组中的所有键值对重新计算哈希值并放入新数组中。这个过程比较消耗性能，因为需要重新计算哈希值和移动元素。

扩容机制详细分析

  1. 何时扩容
    • 如前文所述，当size > threshold时，就会触发扩容。在put方法中，每次成功插入一个新的键值对后，都会调用afterNodeInsertion方法，该方法会检查是否需要扩容。
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 处理哈希冲突
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
  2. 如何扩容
    • 创建新数组：扩容时会创建一个新的数组，新数组的大小是原数组大小的 2 倍。例如，如果原数组大小为 16，扩容后新数组大小为 32。
    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;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 其他情况处理
    //...
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 迁移元素
    }
    return newTab;
}
    • 重新计算哈希值并迁移元素：原数组中的每个元素都需要重新计算在新数组中的位置，并移动到新数组中。在 JDK 1.8 中，为了优化这个过程，采用了一种巧妙的方法。对于链表节点，不需要重新计算哈希值，而是根据原数组的容量和节点的哈希值判断是否需要移动到新数组的其他位置。如果节点的哈希值与原数组容量进行按位与运算的结果为 0，则节点在新数组中的位置与原数组相同；否则，位置为原位置加上原数组容量。
    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)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            else { // 链表优化重定位
                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;
                    }
                    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;
                }
            }
        }
    }
}

扩容对性能的影响

扩容是一个相对昂贵的操作，因为它涉及到创建新数组、重新计算哈希值和迁移元素。如果在程序中频繁地触发扩容，会导致性能下降。为了避免这种情况，可以在创建 HashMap 时预先估计需要存储的元素数量，并设置合适的初始容量。例如，如果预计要存储 100 个元素，由于负载因子默认是 0.75，那么初始容量至少应该设置为100 / 0.75 = 134，但由于容量必须是 2 的幂次方，所以可以设置为 128（下一个大于 134 的 2 的幂次方是 256，这样设置可以减少扩容次数）。

示例代码演示扩容过程

import java.util.HashMap;
import java.util.Map;

public class HashMapResizeExample {
    public static void main(String[] args) {
        // 创建一个初始容量为 4 的 HashMap
        Map<String, Integer> hashMap = new HashMap<>(4);

        // 插入元素
        hashMap.put("a", 1);
        hashMap.put("b", 2);
        hashMap.put("c", 3);
        hashMap.put("d", 4);
        hashMap.put("e", 5);

        // 输出 HashMap 的大小和容量
        System.out.println("Size: " + hashMap.size());
        System.out.println("Capacity: " + getCapacity(hashMap));
    }

    // 反射获取 HashMap 的容量
    private static int getCapacity(Map<?,?> map) {
        try {
            java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            return (table == null)? 0 : table.length;
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }
}

在上述代码中，我们创建了一个初始容量为 4 的 HashMap，并向其中插入 5 个元素。由于插入元素数量超过了阈值（4 * 0.75 = 3），HashMap 会触发扩容。通过反射获取 HashMap 的容量并输出，可以看到扩容后的容量变为 8。

总结扩容机制要点

  1. 触发条件：当size > threshold时触发扩容，threshold = capacity * loadFactor。
  2. 扩容方式：创建一个新的容量为原容量 2 倍的数组，并重新计算哈希值和迁移元素。
  3. 性能优化：在 JDK 1.8 中，链表节点的迁移采用了优化方式，减少了重新计算哈希值的开销。同时，合理设置初始容量可以减少扩容次数，提高性能。

了解 HashMap 的扩容机制对于编写高效的 Java 代码非常重要，特别是在处理大量数据时，可以通过优化初始容量和负载因子等参数，避免频繁扩容带来的性能损耗。在实际应用中，需要根据具体的业务场景和数据规模，合理选择和配置 HashMap，以达到最佳的性能表现。

深入理解扩容中的哈希冲突处理

在扩容过程中，哈希冲突的处理至关重要。因为扩容后数组大小发生了变化，原本在同一桶中的元素，在新数组中可能会分布到不同的桶中。

  1. 链表形式的哈希冲突处理
    • 在 JDK 1.8 之前，HashMap 对于哈希冲突的处理主要是通过链表。当发生哈希冲突时，新的元素会被添加到链表的头部。在扩容时，需要将链表中的所有元素重新计算哈希值并插入到新数组的相应位置。这意味着每个元素都需要重新哈希，性能开销较大。
    • 从 JDK 1.8 开始，链表的处理方式有所优化。在扩容时，对于链表中的元素，会根据元素哈希值与原数组容量按位与的结果，将链表拆分成两个子链表。一个子链表中的元素在新数组中的位置与原数组相同，另一个子链表中的元素在新数组中的位置为原位置加上原数组容量。这样避免了每个元素都重新计算哈希值，提高了扩容效率。
  2. 红黑树形式的哈希冲突处理
    • 当链表长度达到一定阈值（默认 8）且数组容量达到一定大小（默认 64）时，链表会转化为红黑树，以提高查找效率。在扩容时，红黑树会调用split方法，将红黑树中的节点重新分布到新数组的相应位置。这个过程相对复杂，需要维护红黑树的特性（如节点颜色、父子关系等）。
    • 在split方法中，会遍历红黑树的节点，根据节点哈希值与原数组容量按位与的结果，将节点分为两组，分别插入到新数组的不同位置。如果分组后的子树节点数量小于一定阈值（默认 6），红黑树会退化为链表。

负载因子对扩容的影响

  1. 负载因子的作用
    • 负载因子是一个权衡空间和时间效率的参数。较小的负载因子意味着在哈希表中元素较少时就会触发扩容，这样可以减少哈希冲突，提高查找效率，但会占用更多的空间。较大的负载因子则允许哈希表在容量较大时才触发扩容，节省了空间，但哈希冲突的可能性增加，查找效率可能会降低。
  2. 选择合适的负载因子
    • 在大多数情况下，默认的负载因子 0.75 是一个比较好的选择，它在空间和时间效率之间取得了较好的平衡。但在某些特定场景下，可能需要调整负载因子。例如，如果应用程序对空间比较敏感，且对查找效率要求不是特别高，可以适当增大负载因子；如果对查找效率非常看重，且空间不是问题，可以适当减小负载因子。

初始容量设置的注意事项

  1. 初始容量的重要性
    • 正确设置初始容量可以避免频繁的扩容操作，从而提高程序的性能。如果初始容量设置过小，可能会导致在添加少量元素后就触发扩容，增加了扩容的开销。如果初始容量设置过大，虽然减少了扩容次数，但会浪费大量的空间。
  2. 如何计算合适的初始容量
    • 假设我们预计要存储n个元素，负载因子为loadFactor，那么合适的初始容量initialCapacity应该满足initialCapacity >= n / loadFactor。并且，由于 HashMap 的容量必须是 2 的幂次方，所以需要找到大于或等于n / loadFactor的最小的 2 的幂次方。例如，如果预计存储 1000 个元素，负载因子为 0.75，则n / loadFactor = 1000 / 0.75 ≈ 1333，大于 1333 的最小的 2 的幂次方是 2048，所以初始容量可以设置为 2048。

并发环境下的扩容问题

  1. 非线程安全的扩容
    • HashMap 本身是非线程安全的，在多线程环境下进行扩容操作可能会导致数据丢失、无限循环等问题。例如，当多个线程同时对 HashMap 进行扩容时，可能会出现链表成环的情况，导致在遍历链表时进入无限循环。
  2. 解决方案
    • 如果需要在多线程环境下使用哈希表，可以使用ConcurrentHashMap。ConcurrentHashMap采用了分段锁的机制，允许多个线程同时对不同的段进行操作，提高了并发性能。并且，ConcurrentHashMap的扩容操作是线程安全的，不会出现上述问题。

与其他集合类扩容机制的对比

  1. 与 ArrayList 扩容机制的对比
    • ArrayList 是基于数组实现的动态数组，其扩容机制与 HashMap 有所不同。ArrayList 在添加元素时，如果当前容量不足，会进行扩容。扩容时，新容量通常是原容量的 1.5 倍（如果原容量的 1.5 倍仍小于所需容量，则直接设置为所需容量）。而 HashMap 的扩容是将容量翻倍。
    • ArrayList 的扩容主要是为了满足元素数量的增加，而 HashMap 的扩容不仅要满足元素数量的增加，还要考虑哈希冲突的影响，以保证哈希表的性能。
  2. 与 HashSet 扩容机制的对比
    • HashSet 底层是基于 HashMap 实现的，其扩容机制与 HashMap 基本相同。HashSet 的容量、负载因子等概念与 HashMap 中的对应概念是一致的，因为 HashSet 实际上是通过调用 HashMap 的方法来实现元素的存储和操作。

实践中的优化建议

  1. 预估计数据规模
    • 在使用 HashMap 之前，尽量准确地估计需要存储的数据规模，以便设置合适的初始容量。如果无法准确估计，可以根据经验值适当设置一个较大的初始容量，以减少扩容次数。
  2. 监控扩容情况
    • 在程序运行过程中，可以通过一些监控工具（如 Java 自带的 JMX 等）监控 HashMap 的扩容次数和容量变化情况。如果发现扩容过于频繁，可以进一步调整初始容量或负载因子。
  3. 选择合适的负载因子
    • 根据应用程序的特点，选择合适的负载因子。如果应用程序对空间敏感，可以适当增大负载因子；如果对查找效率要求极高，可以适当减小负载因子。

总结扩容相关的关键要点

  1. 扩容触发条件：元素数量超过阈值（capacity * loadFactor）时触发扩容。
  2. 扩容方式：创建新的 2 倍容量数组，重新计算哈希值并迁移元素，JDK 1.8 对链表迁移有优化。
  3. 负载因子：权衡空间和时间效率，默认 0.75，可根据场景调整。
  4. 初始容量：合理设置可避免频繁扩容，根据预计数据量和负载因子计算。
  5. 并发问题：HashMap 非线程安全，多线程环境用ConcurrentHashMap。
  6. 与其他集合对比：与 ArrayList、HashSet 等扩容机制有差异。
  7. 优化建议：预估计数据规模、监控扩容、选择合适负载因子。

深入理解 HashMap 的扩容机制，能够帮助我们在编写 Java 程序时，更加合理地使用 HashMap，提高程序的性能和稳定性。无论是在小型应用还是大型项目中，对这些细节的把握都至关重要。通过合理设置初始容量、选择合适的负载因子以及注意并发环境下的使用，我们可以充分发挥 HashMap 的优势，避免潜在的性能问题。在实际开发中，还需要结合具体的业务需求和数据特点，灵活运用这些知识，以达到最佳的开发效果。同时，随着 JDK 的不断更新，HashMap 的实现可能会有所优化和改进，我们也需要持续关注和学习新的特性和变化。