HashMap 的效率主要体现在 增、删、改、查 这四个基本操作上，其时间复杂度的表现，主要取决于两个核心概念：哈希冲突 和 扩容机制。
核心结论先行
在理想情况下,HashMap 的增、删、改、查操作的时间复杂度是 O(1)，即常数时间。
在最坏的情况下（所有键都发生哈希冲突），时间复杂度会退化到 O(n)，即线性时间。
但请记住： 在 Java 的实现中，通过精心设计的哈希函数和冲突解决策略（链表法 -> 红黑树），HashMap 在绝大多数实际应用场景下，都能非常接近 O(1) 的性能。
时间复杂度详解
HashMap 的性能瓶颈在于 哈希冲突，当两个不同的 key 通过哈希函数计算出相同的 index（桶的位置）时，就发生了冲突。HashMap 使用两种主要策略来解决冲突：
- 链表法
- 红黑树法
1. 理想情况：无冲突
如果哈希函数完美,且容量足够大，使得每个 key 都能被哈希到不同的桶中，
- 增/删/改/查：只需通过
key的哈希值直接计算出桶的位置，然后进行操作，无需遍历，这就是 O(1) 时间复杂度的来源。
2. 实际情况：存在冲突
哈希函数无法做到绝对完美,且 HashMap 的容量是有限的，冲突在所难免。HashMap 的性能好坏，就体现在处理冲突的效率上。
使用链表法
当发生冲突时,HashMap 会在同一个桶的头部（JDK 1.7及之前是尾部，JDK 1.8是头部）插入一个新节点，形成一个链表。
- 查询：要查找一个
key，需要先定位到对应的桶，然后遍历该桶上的整个链表，逐个比较key是否相等。 - 删除：同理，需要先找到节点，然后从链表中移除。
如果某个桶上的链表很长,比如有 n 个节点，那么最坏情况下，遍历这个链表就需要 n 次比较，该桶上的操作时间复杂度就是 O(n)。
性能瓶颈：当 HashMap 中的元素数量 n 远大于桶的数量 capacity 时，平均每个桶上的链表长度就会变长，导致操作效率急剧下降。
引入红黑树（JDK 1.8的重大优化）
为了解决链表过长导致性能下降的问题,JDK 1.8 引入了红黑树作为优化。
-
触发条件：当某个桶的链表长度超过
TREEIFY_THRESHOLD（默认为 8），并且HashMap的总容量capacity大于MIN_TREEIFY_CAPACITY（默认为 64）时，这个链表就会被转换成一颗红黑树。 -
红黑树的优势：红黑树是一种自平衡的二叉搜索树，其增、删、改、查的时间复杂度为 O(log n)。
n是树中节点的数量。 -
退链表条件：当红黑树的节点数在删除操作后减少到
UNTREEIFY_THRESHOLD（默认为 6）时，红黑树会退化回链表。
综合时间复杂度
| 操作 | 理想情况 (无冲突) | 一般情况 (有冲突，链表) | 一般情况 (有冲突，红黑树) | 最坏情况 (所有key冲突) |
|---|---|---|---|---|
put(key, value) |
O(1) | O(1) (平均) | O(log n) | O(n) |
get(key) |
O(1) | O(1) (平均) | O(log n) | O(n) |
remove(key) |
O(1) | O(1) (平均) | O(log n) | O(n) |
“平均”的含义：HashMap 的平均时间复杂度是 O(1)，这是基于“哈希值均匀分布”这一统计学假设，在实际应用中，只要你的 key 的哈希函数设计得不错，这个假设基本成立。
空间复杂度
HashMap 的空间复杂度主要取决于其容量和负载因子。
- 容量：
HashMap底层数组的长度，它总是 2 的幂次方（如 16, 32, 64...）。 - 负载因子：一个介于 0.0 和 1.0 之间的浮点数，默认值为 75，它代表了
HashMap的“满”的程度。
空间占用公式：
总空间 ≈ capacity * (Node 对象大小 + 数组引用开销)
负载因子的作用：
它决定了 HashMap 在何时进行扩容。
- 扩容阈值：
threshold = capacity * loadFactor - 当
HashMap中的元素数量size超过threshold时，HashMap会进行扩容。
扩容机制：
- 创建一个新的、容量是原来两倍的底层数组。
- 重新计算所有
key的哈希值，并将它们重新散列到新的数组中（这个过程也叫rehash）。
空间与时间的权衡：
- 高负载因子（如 0.9）：
HashMap会更“满”才扩容，节省了内存空间，但增加了哈希冲突的概率，导致链表/树变长，查询效率降低。 - 低负载因子（如 0.5）：
HashMap扩容更频繁，占用了更多内存，但哈希冲突减少，查询效率更高。
默认值 0.75 是在时间和空间之间取得的一个很好的平衡点。
影响效率的关键因素
1. 哈希函数的质量
这是影响 HashMap 性能的最根本因素，一个好的哈希函数应该能让不同的 key 尽可能地均匀分布到不同的桶中。
String类：String类的hashCode()方法经过精心设计，能很好地分散哈希值。- 自定义
key类：必须重写hashCode()和equals()方法。hashCode()：返回值要尽可能分散，且对于相等的对象，必须返回相同的哈希值。equals()：对于相等的对象，必须返回true。- 契约：
a.equals(b)为true，则a.hashCode()必须等于b.hashCode()，反之不成立（哈希冲突是允许的）。
2. 容量与负载因子
如上所述,它们直接决定了 HashMap 的扩容时机和空间占用，从而影响性能，在创建 HashMap 时，如果能预估出元素的大致数量，可以预先设置一个合适的初始容量，以减少扩容带来的性能损耗。
计算初始容量：
初始容量 = 预期元素数量 / 负载因子
预期存储 1000 个元素，使用默认负载因子 0.75：
初始容量 = 1000 / 0.75 ≈ 1333
由于容量必须是 2 的幂次方，所以选择离 1333 最近的 2 的幂，即 2048。
// 创建一个初始容量为 2048 的 HashMap Map<String, String> map = new HashMap<>(2048);
3. 键的类型
String：作为键是很好的选择，因为它的哈希分布均匀，且不可变，保证了hashCode()在其生命周期内不变。- 基本类型包装类：如
Integer,Long等，它们的哈希值就是它们本身的值，分布也相对均匀。 - 自定义对象：如果自定义对象的哈希函数设计不当，会导致严重的哈希冲突，性能急剧下降。
与其他 Map 的效率对比
| Map | 实现原理 | 时间复杂度 (增删改查) | 有序性 | 线程安全 | 备注 |
|---|---|---|---|---|---|
HashMap |
哈希表 | 平均 O(1)，最坏 O(n) | 无序 | 否 | 高性能的通用选择 |
LinkedHashMap |
哈希表 + 链表 | 平均 O(1)，最坏 O(n) | 插入/访问有序 | 否 | 继承自 HashMap，额外维护了双向链表来记录顺序 |
TreeMap |
红黑树 | O(log n) | 键排序 | 否 | 基于键的自然排序或自定义比较器排序，性能稳定但略低于 HashMap |
Hashtable |
哈希表 | 平均 O(1)，最坏 O(n) | 无序 | 是 (方法级锁) | 线程安全但性能差，已不推荐使用，被 ConcurrentHashMap 替代 |
ConcurrentHashMap |
CAS + synchronized | O(1) | 无序 | 是 (分段锁/CAS) | 高性能的线程安全 Map，是并发场景下的首选 |
总结与最佳实践
- 默认选择：在单线程环境下，需要
Map时，HashMap应该是你的首选，它在绝大多数情况下都能提供卓越的性能。 - 预估容量：如果你能预估出
Map的大致大小，在初始化时设置一个合适的初始容量，可以显著减少因扩容带来的性能开销。 - 实现好
hashCode()和equals()：如果你使用自定义对象作为key，务必正确地重写这两个方法，这是保证HashMap高效运行的前提。 - 避免可变
key：不要使用可变对象作为key，如果在key存入HashMap后修改了它的状态（比如修改了String的内容，虽然String不可变，但其他自定义对象可能），会导致key的hashCode()改变，从而再也找不到这个key了。 - 有序需求：如果需要
Map按插入顺序或访问顺序排列，使用LinkedHashMap，如果需要按键的自然顺序或自定义顺序排列，使用TreeMap。 - 并发环境：在多线程环境下，使用
ConcurrentHashMap来保证线程安全，而不是使用过时的Hashtable或对HashMap进行外部同步包装。
通过理解 HashMap 的工作原理，你可以在实际开发中更好地利用它，避免常见的性能陷阱。
