java集合Map

一、Map 顶层特性

1. 双列集合：key(键)–value(值) 键值对存储
2. Key 唯一、Value 可重复
3. 无索引，不能通过下标遍历
4. 常用遍历：keySet、entrySet、forEach

---

二、HashMap

1. 底层结构（JDK1.8）

数组 + 单向链表 + 红黑树

• 主干：哈希数组（桶）
• 哈希冲突少时：链表
• 链表长度 ≥ 8 且 数组长度 ≥ 64：转为红黑树
• 红黑树节点数 ≤ 6：退化为链表

2. 哈希冲突

• 产生原因：不同 key 计算出相同哈希值，落到同一个数组下标桶位
• 解决方式：
  1. 链表挂载（JDK1.7 纯链表）
  2. 树化优化（1.8 引入红黑树，提升查询效率）

3. put 核心执行流程

1. 计算 key 的 hash 值，定位数组下标桶位
2. 桶位为空：直接新建节点存入
3. 桶位不为空：
   • 首节点 key 相同：覆盖旧 value
   • 是链表：遍历链表，key 相同则覆盖；不同则尾插
   • 是红黑树：按树规则插入节点
4. 插入完成后，判断元素个数是否达到阈值，达到则触发扩容

4. get 查询流程

1. 计算 key hash，定位桶下标
2. 匹配桶首节点 key，相同直接返回 value
3. 不匹配：判断是链表 / 红黑树，逐个遍历匹配 key
4. 匹配不到返回 null

5. 扩容机制

• 默认初始容量：16
• 负载因子：0.75
• 扩容阈值 = 容量 × 负载因子
• 扩容规则：容量扩容为原来 2 倍
• 扩容动作：重新计算 hash、迁移所有元素到新数组（耗时操作）

---

三、LinkedHashMap

1. 底层：HashMap + 双向链表
2. 核心特点：保留插入顺序
3. 扩展能力：支持访问顺序排序（LRU 缓存淘汰底层实现）
4. 使用场景：需要键值对去重 + 保证存取顺序

---

四、TreeMap

1. 底层：红黑树
2. 核心特点：key 自动排序
3. 排序规则二选一：
   • 自然排序：key 实体类实现 Comparable 接口
   • 定制排序：创建 TreeMap 传入 Comparator 比较器
4. 限制：key 不能为 null，必须具备比较规则

---

五、HashMap / Hashtable / ConcurrentHashMap 对比

集合	线程安全	key/value 允许 null	底层	效率	锁机制
HashMap	不安全	key 最多 1 个 null，value 可 null	数组 + 链表 + 红黑树	高	无锁
Hashtable	安全	都不允许 null	数组 + 链表	极低	全表 synchronized
ConcurrentHashMap	安全	key/value 不建议 null	数组 + 链表 + 红黑树	中高	分段锁 + CAS+synchronized

关键考点

1. Hashtable 老旧、效率极差，项目彻底废弃不用
2. 单线程：优先用 HashMap
3. 多线程并发：优先用 ConcurrentHashMap，不使用 HashMap、Hashtable