【面经总结】Java集合 - Map
Map 概述
Map 架构
HashMap
要点
- 以 散列(哈希表) 方式存储键值对，访问速度快
- 没有顺序性
- 允许使用空值和空键
- 有两个影响其性能的参数：初始容量和负载因子。
- 初始容量：哈希表创建时的容量
- 负载因子：其容量自动扩容之前被允许的最大饱和量
- 不是线程安全的
Java7
数据结构
实现机制：**数组 + 链表，**通过链表解决哈希冲突。
- table：存储 K-V 的数组
- size：容量，初始为 16
- loadFactor：负载因子，默认为 0.75（元素个数超过容量的 75％ 会触发自动扩容，扩容为原始的 2 倍）
获取元素 get
- 通过 key 的哈希计算存储位置
- 遍历链表
计算 hash 方式：高16位不变，低16位和高16位做异或
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算下标的时候，是使用 & 位操作，而非求余
(n - 1) & hash
优点：能使用32位计算哈希，避免因为高位没有参与下标的计算而碰撞
添加元素 put
- 通过 key 的哈希计算存储位置
- 查找 key 是否存在
- 存在：覆盖 Value
- 不存在：放到桶里 or 插入链表（头插法）
删除元素 remove
找到指定数据并修改链表引用
Java8
- 实现机制：数组 + 链表 + 红黑树
- 当容量达到 64，且元素达到 8 个时会将链表转为红黑树
- 将链表插入方式改为尾插法（解决循环链表）
链表查询复杂度取决于链表长度，为 O(n)。为了降低开销，Java8 中当容量达到 64，且元素达到 8 个时会转为红黑树，降低复杂度为 O(logN)
Java7 使用 Entry 表示数据节点，Java8 使用 Node 和 TreeNode。
LinkedHashMap
在 HashMap 的基础上，维护一个双向链表，实现插入顺序
TreeMap
- 实现机制：红黑树
- 有序（默认为升序）
- Key 需要定义比较逻辑
- 实现 Comparable 接口
- 重写 compareTo() 方法