HashMap

ℹ️定位说明

Map 系列第 1 篇。核心原理速览：put/get 存储流程 + 关键参数 + 与其他 Map 对比。想看源码细节（hash 计算、扩容、树化、线程安全）直接进 02-HashMap源码解析。

核心特性

数据结构
- JDK 1.8 之前：数组 + 链表（拉链法解决哈希冲突）。
- JDK 1.8 及之后：数组 + 链表 + 红黑树（当链表长度 ≥ 8且数组容量 ≥ 64 时，链表转为红黑树；长度 < 6 时退化为链表）。
- 目的：提升哈希冲突时的查询性能（链表平均查询 O (n) → 红黑树 O (log n)）。
存储特点
- 无序性：不保证元素插入顺序（依赖哈希值分布）。
- 键唯一性：键通过 equals() 和 hashCode() 保证唯一性（值可重复），允许一个 null 键和多个 null 值。
- 线程不安全：多线程下可能出现死锁、数据丢失等问题（需用 ConcurrentHashMap 或手动同步）。

关键参数

参数	含义	默认值
capacity	哈希表初始容量（数组长度，必须为 2 的幂，如 16、32）	16
loadFactor	负载因子（控制哈希表扩容时机，值越小，冲突概率越低，空间利用率越低）	0.75
threshold	扩容阈值（= capacity × loadFactor，如默认 16×0.75=12）	无默认值

核心原理

1. 存储流程（put (key, value)）

计算哈希值：
- 对 key 调用 hashCode() 得到哈希值，再通过 扰动函数（hash(key) 方法）优化哈希分布，减少冲突：

     static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高低位异或，降低哈希碰撞
     }

确定数组下标：
- index = hash & (capacity - 1)（等价于取模运算 hash % capacity，但效率更高）。
处理哈希冲突：
- 若该下标处无元素，直接插入。
- 若有元素，比较 key：
  - 若 key 相等（equals 为 true），覆盖 value。
  - 若 key 不等，判断当前节点类型：
    - 链表节点：遍历链表，若找到相等 key 则覆盖；否则新增节点（尾插法，JDK 1.8 后改为尾插）。
    - 红黑树节点：按红黑树规则插入新节点，若插入后树高 < 6，退化为链表。
扩容机制：
- 当元素数量（size）超过 threshold 时，触发扩容（容量翻倍，如 16 → 32）。
- 扩容重哈希：重新计算所有元素的哈希值和下标（性能消耗大，应避免频繁扩容）。

2. 查询流程（get (key)）

计算 key 的哈希值，确定数组下标。
若该下标处无元素，返回 null。
若有元素，比较 key：
- 若 key 相等，直接返回 value。
- 若为链表，遍历链表查找；若为红黑树，按红黑树规则查找。

源码分析

HashMap源码解析

性能分析

操作	平均时间复杂度	最坏时间复杂度	影响因素
插入	O(1)	O (n) 或 O (log n)	哈希冲突次数、链表 / 树长度
查询	O(1)	O (n) 或 O (log n)	同上
删除	O(1)	O (n) 或 O (log n)	同上

优势：平均性能极高，适用于高频的插入、查询操作。
劣势：扩容时性能开销大；多线程下不安全。

与其他 Map 的对比

实现类	数据结构	顺序性	线程安全	适用场景
HashMap	数组 + 链表 + 红黑树	无序	不安全	单线程下的高频增删查（默认选择）
LinkedHashMap	数组 + 链表（维护双向链表）	插入顺序 / 访问顺序	不安全	需要保留插入顺序或实现 LRU 缓存
TreeMap	红黑树	自然顺序 / 定制顺序	不安全	需要排序或范围查询（如按 key 排序）
Hashtable	数组 + 链表	无序	安全（synchronized）	遗留系统的线程安全场景（性能低，不推荐）

常见问题与最佳实践

为什么容量必须是 2 的幂？
- 为了保证 hash & (capacity - 1) 等价于 hash % capacity，且运算更快（位运算）。
- 若用户传入非 2 的幂，HashMap 会自动调整为大于等于该值的最小 2 的幂（如传入 10 → 16）。
如何优化 HashMap 性能？
- 预设置合适的初始容量：避免频繁扩容。例如，若已知存储 1000 个元素，初始容量可设为 (1000 / 0.75) ≈ 1334，取最近的2 的幂（16384）。
- 选择合适的负载因子：若内存充足且需减少冲突，可设为 0.5（空间换时间）；若内存紧张，可设为 1.0（但冲突概率增加）。
多线程下如何使用 HashMap？
- 不推荐直接使用，可改用 ConcurrentHashMap（JDK 1.8 后基于 CAS + synchronized，性能更高）或手动同步（如 Collections.synchronizedMap(new HashMap<>())）。
key 的最佳实践
- 自定义类作为 key 时，必须重写 equals() 和 hashCode()，且保证相同 key的 hashCode() 一致。
- 推荐使用不可变类（如 String、Integer）作为 key，避免因 key 可变导致哈希值变化。

总结

核心优势：高效的平均性能，适用于大多数 “键值对快速存取” 场景。
适用场景：缓存、字典、统计计数等单线程场景。
注意事项：多线程需同步，避免 key 可变，合理设置初始容量以减少扩容开销。

⬅️ 00-Map总览 🏠 00-Java ➡️ HashMap源码解析

01-HashMap

HashMap

核心特性

关键参数

核心原理

1. 存储流程（put (key, value)）

2. 查询流程（get (key)）

源码分析

性能分析

与其他 Map 的对比

常见问题与最佳实践

总结

💬 评论