HashMap

1. Hash 冲突后的数据结构变化（jdk8 之后的优化）

在 jdk8 之前，HashMap 发生冲突后使用的是链表结构，导致在极端情况下时间复杂度退化为 O(n)。

jdk8 开始引入红黑树结构优化：

• 当某个桶（链表）中的元素个数超过 TREEIFY_THRESHOLD = 8 且容量超过 MIN_TREEIFY_CAPACITY = 64 时，该桶的链表会被转化为红黑树；
• 当元素个数减少至 UNTREEIFY_THRESHOLD = 6 以下时会退回链表结构。

这种优化在提升查找效率的同时避免了 O(n) 的性能陷阱。

✅ 补充说明：红黑树的引入，除了提升查询性能外，还与负载因子的设定策略密切相关。负载因子本质上控制了哈希桶的平均元素个数，而红黑树则保证了极端情况下查询不会退化为链表，两者共同构成了 HashMap 查找性能的保障机制。因此在介绍负载因子与扩容逻辑时，也可以顺带说明红黑树优化是对冲突处理的“兜底”方案。

2. Hash 函数实现与扰动函数（Hash扰动）

在 HashMap 中，计算 key 的哈希值时，不仅仅是 key.hashCode()，还做了一步扰动：

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

这个扰动函数的作用是：

• 将高位信息混合进低位，避免低位哈希分布不均；
• 配合数组长度是 2 的幂，使用 (n - 1) & hash 做快速取模。

✅ 补充说明：扰动函数的目的是让 key 的分布更加均匀，从而减少哈希冲突的发生，这与负载因子（决定何时扩容）共同起到控制哈希桶中元素密度的作用。因此，扰动函数间接影响了负载因子的实际表现，这部分可以单独作为“HashMap 的哈希计算机制”来展开，放在负载因子前后位置都合适。

3. resize（扩容）机制的成本与时间复杂度

HashMap 的扩容操作成本较高：

• 需要重新申请更大的数组；
• 对原有元素重新计算桶位置（Rehash）；
• 在 jdk8 中还涉及链表与红黑树之间的结构转化。

因此，频繁扩容会极大影响系统性能，尤其在高并发场景下会造成短暂“卡顿”或“抖动”。

✅ 补充说明：扩容并不是轻量操作，它会触发大量数据迁移（尤其是树结构重建），这也解释了为什么我们强调在创建 HashMap 时应预估好初始容量，合理设置 loadFactor 和初始容量是控制扩容代价的关键手段。

4. 初始容量为什么不是无限增长？

你可能会想，能不能一开始就分配一个很大的数组避免扩容？

事实上，HashMap 的容量被限定为 2 的幂次方，而且在 tableSizeFor(cap) 中做了计算：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这段代码可以快速计算出大于等于 cap 的最小 2 的幂，主要为了：

• 优化哈希桶定位（使用位运算代替模运算）；
• 保证扩容后的散列效果均匀。

✅ 补充说明：你可以在“容量为什么是 2 的幂”之后加上一段说明 tableSizeFor() 的意义：这是一个典型的位运算优化技巧，通过将 cap 向上取整为最近的 2 的幂，有效简化了取模运算，并提升了 hash 映射效率。它的存在也确保了容量和负载因子乘积后的 threshold 始终是整数，避免边界错误。

5. 并发场景下的线程安全问题（为什么不能直接用 HashMap）

在多线程环境下，直接使用 HashMap 可能导致：

• 数据丢失（覆盖）；
• 死循环（jdk7 下 resize 的链表重排）。

解决方案：

• 使用 Collections.synchronizedMap() 包装；
• 使用 ConcurrentHashMap 替代，分段锁 + CAS 机制 + Node 桶数组。

✅ 补充说明：尤其在 jdk7 中由于链表插入顺序不一致，扩容时容易形成环状链表，造成 get() 方法死循环。这是 HashMap 在多线程环境下最危险的陷阱之一。因此，如果你要使用 HashMap 在并发场景中缓存数据，一定要采用 ConcurrentHashMap 或加锁包装形式。

6. 什么是 loadFactor

首先我们来介绍下什么是负载因子（loadFactor），如果读者对这部分已经有了解，那么可以直接跨过这一段。

我们知道，第一次创建 HashMap 的时候，就会指定其容量（如果未明确指定，默认是 16），那随着我们不断的向 HashMap 中 put 元素的时候，就有可能会超过其容量，那么就需要有一个扩容机制。

所谓扩容，就是扩大 HashMap 的容量：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

从代码中我们可以看到，在向 HashMap 中添加元素过程中，如果 元素个数（size）超过临界值（threshold） 的时候，就会进行自动扩容（resize），并且，在扩容之后，还需要对 HashMap 中原有元素进行 rehash，即将原来桶中的元素重新分配到新的桶中。

在 HashMap 中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。

loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，也就是说默认情况下，当 HashMap 中元素个数达到了容量的 3/4 的时候就会进行自动扩容。

7. 为什么默认 loadFactor 是 0.75

解释了这么多，我们终于回归到了标题上的问题。

至此，我们知道了 loadFactor 是 HashMap 中的一个重要概念，他表示这个 HashMap 最大的满的程度。

为了避免哈希碰撞，HashMap 需要在合适的时候进行扩容。那就是当其中的元素个数达到临界值的时候，而这个临界值前面说过和 loadFactor 有关，换句话说，设置一个合理的 loadFactor，可以有效的避免哈希冲突。

那么，到底 loadFactor 设置成多少算合适呢？

这个值现在在 jdk 的源码中是 0.75：

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

那么，为什么选择 0.75 呢？背后有什么考虑？为什么不是 1，不是 0.8？不是 0.5，而是 0.75 呢？

在 jdk 的官方文档中，有这样一段描述描述：

As a general rule, the default load factor (.75) offers a good tradeoff 
between time and space costs. Higher values decrease the space overhead 
but increase the lookup cost (reflected in most of the operations of the 
HashMap class, including get and put).

大概意思是：一般来说，默认的负载因子 (0.75) 在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在 HashMap 类的大多数操作中，包括 get 和 put)。

试想一下，如果我们把负载因子设置成 1，容量使用默认初始值 16，那么表示一个 HashMap 需要在 "满了" 之后才会进行扩容。

那么在 HashMap 中，最好的情况是这 16 个元素通过 hash 算法之后分别落到了 16 个不同的桶中，否则就必然发生哈希碰撞。而且随着元素越多，哈希碰撞的概率越大，查找速度也会越低。

8. 0.75 的数学依据和必然性

理论上我们认为负载因子不能太大，不然会导致大量的哈希冲突，也不能太小，那样会浪费空间。

通过一个数学推理 log(2)/log(s/(s - 1)) ，当 s 趋于无穷大时，如果增加的键的数量使 P(0) = 0.5，那么 n/s 很快趋近于 log(2)，测算出这个数值在 log(2)（即：0.7 左右）时是比较合理的。

当然，这个数学计算方法，并不是在 java 的官方文档中体现的，而是查询了一些资料习得，所以也无从考证，只做参考了。

那么，为什么最终选定了 0.75 呢？

还记得前面我们提到过一个公式吗，就是：临界值（threshold） = 负载因子（loadFactor） \* 容量（capacity）。

根据 HashMap 的扩容机制，它会保证 capacity 的值永远都是 2 的幂；

那么，为了保证负载因子（loadFactor） * 容量（capacity）的结果是一个整数，这个值是 0.75(3/4) 比较合理，因为这个数和任何 2 的幂乘积结果都是整数。

9. 总结

HashMap 是一种 K-V 结构，为了提升其查询及插入的速度，底层采用了链表的数组这种数据结构实现的。

但是因为在计算元素所在的位置的时候，需要使用 hash 算法，而 HashMap 采用的 hash 算法就是链地址法。这种方法有两个极端。

如果 HashMap 中哈希冲突概率高，那么 HashMap 就会退化成链表（不是真的退化，而是操作上像是直接操作链表），而我们知道，链表最大的缺点就是查询速度比较慢，他需要从表头开始逐一遍历。

所以，为了避免 HashMap 发生大量的哈希冲突，所以需要在适当的时候对其进行扩容。

而扩容的条件是元素个数达到临界值时。

HashMap 中临界值的计算方法：

临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）

其中负载因子表示一个数组可以达到的最大的满的程度。这个值不宜太大，也不宜太小。

loadFactor 太大，比如等于 1，那么就会有很高的哈希冲突的概率，会大大降低查询速度。

loadFactor 太小，比如等于 0.5，那么频繁扩容没，就会大大浪费空间。

所以，这个值需要介于 0.5 和 1 之间。根据数学公式推算。这个值在 log(2) 的时候比较合理。

另外，为了提升扩容效率，HashMap 的容量（capacity）有一个固定的要求，那就是一定是 2 的幂。

所以，如果 loadFactor 是 3/4 的话，那么和 capacity 的乘积结果就可以是一个整数。

最后，一般情况下，我们不建议修改 loadFactor 的值，除非特殊原因。