2022 最新 JDK 17 HashMap 源码解读 (一)

HashMap简介

Map 接口的基于哈希表的实现。此实现提供所有可选的映射操作，并允许空值和空键。 （HashMap 类大致相当于 Hashtable，除了它是不同步的并且允许空值。）这个类不保证映射的顺序；特别是，它不保证订单会随着时间的推移保持不变。

此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。对集合视图的迭代需要的时间与 HashMap 实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低），这一点非常重要。

HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表的桶数大约增加一倍。

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

如果要在一个 HashMap 实例中存储许多映射，则创建具有足够大容量的映射将比让它根据需要执行自动重新散列以增加表来更有效地存储映射。请注意，使用具有相同 hashCode() 的多个键是降低任何哈希表性能的可靠方法。为了改善影响，当键是 Comparable 时，此类可以使用键之间的比较顺序来帮助打破平局。

请注意，此实现不同步。如果多个线程同时访问一个哈希映射，并且至少有一个线程在结构上修改了映射，则必须在外部进行同步。 （结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常通过在自然封装映射的某个对象上同步来完成.如果不存在这样的对象，则应使用 Collections.synchronizedMap 方法“包装”Map。

这最好在创建时完成，以防止对Map的意外不同步访问： Map m = Collections.synchronizedMap(new HashMap(…));所有此类的“集合视图方法”返回的迭代器都是快速失败的：如果在创建迭代器后的任何时间对映射进行结构修改，除了通过迭代器自己的 remove 方法之外，迭代器将抛出 ConcurrentModificationException .因此，面对并发修改，迭代器快速而干净地失败，而不是在未来不确定的时间冒任意的、非确定性的行为。

请注意，不能保证迭代器的快速失败行为，因为一般来说，在存在不同步的并发修改的情况下，不可能做出任何硬保证。快速失败的迭代器会尽最大努力抛出 ConcurrentModificationException。因此，编写一个依赖于这个异常的正确性的程序是错误的：迭代器的快速失败行为应该只用于检测错误。

此类是 Java 集合框架的成员。从以下版本开始：1.2 另请参见：Object.hashCode()、Collection、Map、TreeMap、Hashtable 作者：Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 类型参数： – 此映射维护的键的类型 – 映射值的类型

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

    @java.io.Serial
    private static final long serialVersionUID = 362498820763181265L;

实施说明。此映射通常充当分箱（分桶）哈希表，但当箱变得太大时，它们将转换为 TreeNode 的箱，每个结构类似于 java.util.TreeMap 中的结构。大多数方法尝试使用正常的 bin，但在适用时中继到 TreeNode 方法（只需检查节点的实例）。 TreeNode 的 bin 可以像任何其他 bin 一样被遍历和使用，但在填充过多时还支持更快的查找。然而，由于绝大多数正常使用的 bin 并没有被过度填充，因此在 table 方法的过程中检查树 bin 的存在可能会被延迟。

树箱（即元素都是 TreeNodes 的箱）主要按 hashCode 排序，但在 ties 的情况下，如果两个元素属于相同的“C 类实现 Comparable”，则 type 然后它们的 compareTo 方法用于订购。 （我们保守地通过反射检查泛型类型来验证这一点——参见方法 compatibleClassFor）。当键具有不同的哈希值或可排序时，树箱增加的复杂性在提供最坏情况 O(log n) 操作时是值得的，因此，在 hashCode() 方法返回的值很差的意外或恶意使用下，性能会优雅地下降分布式的，以及许多键共享一个 hashCode 的，只要它们也是 Comparable 的。 （如果这些都不适用，与不采取预防措施相比，我们可能会浪费大约两倍的时间和空间。但唯一已知的案例源于糟糕的用户编程实践，这些实践已经很慢，以至于这没什么区别。）

因为 TreeNode 的大小大约是常规节点的两倍，所以我们仅在 bin 包含足够的节点以保证使用时才使用它们（请参阅 TREEIFY_THRESHOLD）。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通垃圾箱。在具有良好分布的用户哈希码的使用中，很少使用树箱。理想情况下，在随机 hashCodes 下，bin 中节点的频率遵循泊松分布 (http:en.wikipedia.orgwikiPoisson_distribution)，默认调整大小阈值为 0.75，平均参数约为 0.5，尽管由于调整大小粒度而存在很大差异.忽略方差，列表大小 k 的预期出现是 (exp(-0.5) pow(0.5, k) factorial(k))。第一个值是：

0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 更多：小于千万分之一 树箱的根通常是它的第一个节点。然而，有时（目前仅在 Iterator.remove 上），根可能在其他地方，但可以在父链接之后恢复（方法 TreeNode.root()）。

所有适用的内部方法都接受哈希码作为参数（通常由公共方法提供），允许它们相互调用而无需重新计算用户哈希码。大多数内部方法还接受“tab”参数，通常是当前表，但在调整大小或转换时可能是新表或旧表。

当 bin 列表被树化、拆分或未树化时，我们将它们保持在相同的相对访问遍历顺序（即字段 Node.next）中，以更好地保留局部性，并稍微简化调用 iterator.remove 的拆分和遍历的处理。在插入时使用比较器时，为了在重新平衡之间保持总排序（或此处要求的接近），我们将类和 identityHashCodes 比较为决胜局。

由于子类 LinkedHashMap 的存在，普通模式与树模式之间的使用和转换变得复杂。请参阅下面定义为在插入、删除和访问时调用的钩子方法，这些方法允许 LinkedHashMap 内部保持独立于这些机制。 （这还需要将映射实例传递给可能创建新节点的某些实用程序方法。）类似并发编程的基于 SSA 的编码风格有助于避免在所有曲折的指针操作中出现别名错误。

默认初始容量 - 必须是 2 的幂。 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量，如果一个更高的值由任何一个带参数的构造函数隐式指定时使用。必须是 2 <= 1<<30 的幂 static final int MAXIMUM_CAPACITY = 1 << 30;

构造函数中未指定时使用的负载因子。 static final float DEFAULT_LOAD_FACTOR = 0.75f;

使用树而不是列表的 bin 计数阈值。将元素添加到至少具有这么多节点的 bin 时，bin 将转换为树。该值必须大于 2 并且应至少为 8 以与树木移除中关于在收缩时转换回普通 bin 的假设相吻合

static final int TREEIFY_THRESHOLD = 8;

在调整大小操作期间 untreeifying（拆分）bin 的 bin 计数阈值。应小于 TREEIFY_THRESHOLD，并且最多 6 以在移除时进行收缩检测。

static final int UNTREEIFY_THRESHOLD = 6;

可对其进行树化的 bin 的最小表容量。 （否则，如果 bin 中有太多节点，则调整表的大小。）应至少为 4 TREEIFY_THRESHOLD 以避免调整大小和树化阈值之间的冲突。

static final int MIN_TREEIFY_CAPACITY = 64;

基本哈希 bin 节点，用于大多数条目。 （参见下面的 TreeNode 子类，以及 LinkedHashMap 中的 Entry 子类。）

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;

            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }

计算 key.hashCode() 并将哈希的较高位传播（XOR）到较低位。由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。 （已知的例子是在小表中保存连续整数的 Float 键集。）因此，我们应用了一种变换，将高位的影响向下传播。在位扩展的速度、实用性和质量之间存在折衷。因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最便宜的方式对一些移位的位进行异或，以减少系统损失，以及合并最高位的影响，否则由于表边界，这些最高位将永远不会用于索引计算。

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

如果 x 的 Class 是“class C implements Comparable”的形式，则返回 x 的 Class，否则返回 null。

 static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (Type t : ts) {
                    if ((t instanceof ParameterizedType) &&
                        ((p = (ParameterizedType) t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

如果 x 匹配 kc（k 的筛选可比类），则返回 k.compareTo(x)，否则返回 0。

 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

/**
 * 返回给定目标容量的 2 次方。
 */

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

该表在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。 （我们还在某些操作中允许长度为零，以允许当前不需要的引导机制。 transient Node<K,V>[] table;

保存缓存的 entrySet()。请注意，AbstractMap 字段用于 keySet() 和 values()。 transient Set<Map.Entry<K,V>> entrySet;

此映射中包含的键值映射的数量 transient int size;

此 HashMap 已在结构上修改的次数 结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构（例如，重新散列）的那些。该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。 （请参阅 ConcurrentModificationException）

transient int modCount;

要调整大小的下一个大小值（容量负载因子）。 （javadoc 描述在序列化时为真。此外，如果尚未分配表数组，则此字段保存初始数组容量，或零表示 DEFAULT_INITIAL_CAPACITY。） int threshold;

/**
 * 哈希表的负载因子
 *
 * @serial
 */
final float loadFactor;

构造一个具有指定初始容量和负载因子的空HashMap 。 参数： initialCapacity - 初始容量 loadFactor – 负载因子 抛出： IllegalArgumentException – 如果初始容量为负或负载因子为非正

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

构造一个具有指定初始容量和默认加载因子 (0.75) 的空 HashMap。参数： initialCapacity - 初始容量。抛出： IllegalArgumentException – 如果初始容量为负数。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap 。

  public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

构造一个与指定Map具有相同映射的新HashMap 。 HashMap是使用默认加载因子 (0.75) 和足以容纳指定Map中的映射的初始容量创建的。 参数： m - 其映射将放置在此Map中的Map 抛出： NullPointerException – 如果指定的Map为空

   public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

实现 Map.putAll 和 Map 构造函数。 参数： m – Map evict – 最初构造此映射时为 false，否则为 true（中继到方法 afterNodeInsertion）

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            } else {
                // Because of linked-list bucket constraints, we cannot
                // expand all at once, but can reduce total resize
                // effort by repeated doubling now vs later
                while (s > threshold && table.length < MAXIMUM_CAPACITY)
                    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);
            }
        }
    }

返回此映射中键值映射的数量。 返回： 此映射中的键值映射的数量

 public int size() {
        return size;
    }

备注: 0—520行

如果大家觉得还不错，点赞，收藏，分享，一键三连支持我一下~