《Java 集合框架详解》

一、HashMap

HashMap 是 Java 中最常用的集合之一，理解其底层实现原理对于编写高效代码至关重要。

---

1. JDK 1.7 版本

（1）组成结构

数组 + 链表 的形式（链表主要为了解决哈希冲突而存在）

工作原理：

• HashMap 通过 key 的 hashCode 经过 hash 方法处理得到 hash 值
• 通过 (n - 1) & hash 判断当前元素存放的位置（n 指数组的长度）
• 如果当前位置存在元素，就判断该元素与要存入元素的 hash 值以及 key 是否相同
• 如果相同直接覆盖，不相同就通过拉链法解决冲突

---

（2）源码分析

Entry 数组：HashMap 的主干是一个 Entry 数组，Entry 实现了 Map.Entry 接口，包含：

• key-value 键值对
• next 指向下一个节点的引用
• 通过 key 计算出来的 hashcode

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

初始化参数：

// 初始化桶大小，默认是 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 桶最大值
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载因子（0.75）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// table 真正存放数据的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

// Map 存放数量的大小
transient int size;

// 桶大小，可在初始化时显式指定
int threshold;

// 负载因子，可在初始化时显式指定
final float loadFactor;

---

（3）注意点

① 扩容机制

• 给定的初始容量为 16（数组长度），负载因子为 0.75
• Map 在使用过程中不断存放数据，当数量达到 16 * 0.75 = 12 就需要扩容
• 扩容过程涉及到 rehash、复制数据等操作，非常消耗性能

② 负载因子

定义：负载因子控制数组存放数据的疏密程度

• 越趋近于 1：数组中存放的数据越多，链表的长度增加，查找效率降低
• 越趋近于 0：数组中存放的数据越少，数组利用率低，存放的数据会很分散

💡 为什么默认是 0.75？

0.75f 是官方给出的一个比较好的临界值，在时间和空间成本之间取得了平衡。

③ 为什么扩容是 2 的倍数？

原因 1：计算效率

• HashMap 通过 (n-1) & hash 来确定索引位置，实际上相当于 hash % n 取余数
• 当容量为 2 的 n 次幂时，n-1 的二进制表示都是 ...1111 的形式
• 例如：15 的二进制是 1111，31 的二进制是 11111
• 与运算比取余运算速度更快

原因 2：扩容优化

• 扩容时只移动大约一半的数据
• 不会造成扩容之后碰撞更加严重的情况

原因 3：均匀分散

• 在 JDK 1.8 中，resize 过程因为容量翻倍，只会在 n-1 的二进制高位新增一个 bit 位
• 这个 bit 位与 hash 值对应位置与操作是 0 的话索引没变，是 1 的话索引变成”原索引 + oldCap”
• 均匀地把之前冲突的节点分散到新的数组里

---

2. JDK 1.8 版本

（1）可以优化的地方

JDK 1.7 的问题：

• 当 Hash 冲突严重时，桶上形成的链表会变得越来越长
• 查询效率越来越低，时间复杂度为 O(N)

（2）组成结构

数组 + （链表/红黑树）

（3）主要区别

特性	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表/红黑树
插入方式	头插法	尾插法
链表转红黑树	不支持	链表长度 > 8 且数组长度 ≥ 64 时转换
扩容问题	可能导致链表成环	尾插法解决了链表成环问题

⚠️ 注意：JDK 1.8 虽然解决了链表成环问题，但仍然存在多线程下数据丢失的问题。

转换规则：

• 当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin() 方法
• 这个方法会根据 HashMap 数组来决定是否转换为红黑树
• 只有当数组长度大于或等于 64 的情况下，才会执行转换红黑树操作
• 否则，只是执行 resize() 方法对数组扩容

---

3. put 方法流程

// put 方法的核心流程

1. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空
   • 为空表明没有 Hash 冲突，直接在当前位置创建一个新桶即可
2. 如果当前桶有值（Hash 冲突），那么就要比较当前桶中的 key
   • key 相等则覆盖
   • 不等则通过步骤 3、4 解决
3. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据
4. 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）
5. 接着判断当前链表的大小是否大于预设的阈值
   • 大于时就要转换为红黑树（前提是数组长度 ≥ 64，否则 resize() 扩容）
6. 最后判断是否整个 map 的 size 是否大于预设 threshold，需要进行扩容

---

4. get 方法流程

1. 首先将 key 的 hashcode hash 之后取得所定位的桶
2. 判断桶的第一个位置（有可能是链表、红黑树）的 key 是否为查询的 key
   • 是就直接返回 value
3. 如果第一个不匹配，则判断它的下一个是红黑树还是链表
   • 红黑树就按照树的查找方式返回值
   • 不然就按照链表的方式遍历匹配返回值

---

5. resize 扩容方法

进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，非常耗时。

💡 最佳实践：在编写程序时，要尽量避免 resize，可以在初始化时指定合适的容量。

---

6. HashMap 安全问题

（1）HashMap 是线程不安全的

（2）可能出现的问题

• JDK 1.7：并发场景下使用时容易出现死循环
  • 在 HashMap 扩容时会调用 resize() 方法
  • 并发操作容易在一个桶上形成环形链表
  • 当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环
• JDK 1.8：通过尾插法解决了链表成环问题，但仍然可能出现数据丢失等问题

⚠️ 建议：多线程下不建议使用 HashMap，应该使用 ConcurrentHashMap。

---

7. 使用细节

// 创建 HashMap
Map<Integer, Integer> maps = new HashMap<Integer, Integer>();

// 写入
maps.put(222, 333);

// 读取
maps.get(222);

// 迭代方式
Iterator<Map.Entry<Integer, Integer>> iterator = maps.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, Integer> next = iterator.next();
    System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}

注意事项：

• HashMap 使用泛型，且泛型只能是引用数据类型
• put 写入 int 型的数据会自动转化为 Integer（自动装箱）
• get 读取数据会把 Integer 自动转化为 int（自动拆箱）

---

8. 使用场景

• ✅ 做数据匹配
• ✅ 适合一次写入，多次读取的场景

💡 扩展知识：Redis 数据库底层的整体结构就是一个 HashMap，适合 token 等一次写入、多次读取的场景。

---

9. 时间复杂度

操作	时间复杂度	说明
单查	O(1)	直接定位到桶
整体数据匹配	O(n)	遍历所有元素
单次删改	O(1)	直接定位
单次插入（无冲突）	O(1)	链表未达到阈值
单次插入（扩容）	O(n)	数组扩容，需要 rehash，重新散列

---

二、ConcurrentHashMap

ConcurrentHashMap 是线程安全的 HashMap，在并发编程中被广泛使用。

---

1. JDK 1.7 版本

（1）组成结构

Segment 数组 + HashEntry 数组 = 数组 + 链表的形式

（2）实现原理

分段锁技术：

• ConcurrentHashMap 采用了分段锁技术
• Segment 继承于 ReentrantLock
• 不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理
• 理论上 ConcurrentHashMap 支持 CurrencyLevel（Segment 数组数量）的线程并发
• 每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment
• 每一个 Segment 存储的都是一个 HashMap 结构
• Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16

---

（3）源码分析

HashEntry 组成：

• 和 HashMap 非常类似
• 唯一的区别就是其中的核心数据如 value，以及链表都是 volatile 修饰的
• 保证了获取时的可见性

put 操作：

1. 首先通过 key 定位到 Segment
   • 如果指定位置的 Segment 为空，则初始化这个 Segment
2. 之后在对应的 Segment 中进行具体的 put
3. 虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但不能保证并发的原子性
   • 所以 put 操作时仍然需要加锁处理
4. 第一步时会尝试获取锁
   • 如果获取失败肯定就有其他线程存在竞争
   • 则利用 scanAndLockForPut() 自旋获取锁
5. 如果重试的次数达到了 MAX_SCAN_RETRIES
   • 则改为 lock() 阻塞获取锁，保证能获取成功

get 操作：

1. 只需要将 Key 通过 Hash 之后定位到具体的 Segment
2. 再通过一次 Hash 定位到具体的元素上
3. 由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的
   • 保证了内存可见性，所以每次获取时都是最新值

✅ 高效：ConcurrentHashMap 的 get 方法非常高效，因为整个过程都不需要加锁。

---

2. JDK 1.8 版本

（1）主要改进

解决链表查询低效的问题：

• 抛弃了原有的 Segment 分段锁
• 采用了 CAS + synchronized 来保证并发安全性
• Node 数组 + 链表/红黑树
• 当冲突链表达到一定长度时，链表会转换成红黑树

Node 节点：

• 将 1.7 中存放数据的 HashEntry 改为 Node，作用相同
• 其中的 val、next 都用了 volatile 修饰，保证了可见性

---

（2）put 操作

1. 根据 key 计算出 hashcode，计算出桶的位置
2. 当前 key 定位出的 Node，如果为空表示当前位置可以写入数据
   • 利用 CAS 尝试写入，失败则自旋保证成功
3. 如果当前位置的 hashcode == MOVED == -1，则需要进行扩容
4. 如果都不满足，则利用 synchronized 锁写入数据
5. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树

---

（3）get 操作

1. 根据计算出来的 hashcode 寻址
   • 如果就在桶上那么直接返回值
2. 如果是红黑树那就按照树的方式获取值
3. 如果不满足那就按照链表的方式遍历获取值

---

三、HashTable

1. 时间复杂度

HashTable 哈希表：理论上增删改查 O(1) 级别（暂时不考虑哈希冲突）

为什么是 O(1) 级别？

• HashTable 本质上是一个数组，根据索引”删查改”，是 O(1) 级别

📝 举例：maps.get("name") 工作原理

根据 name 的 hashcode 通过哈希函数计算出索引地址，就能找到数组中对应的存储位置

公式：索引地址 = f(hashcode)

---

2. HashMap 和 HashTable 的区别

相同点

• 都是存储 key-value 键值对的

不同点

特性	HashMap	HashTable
null 值	可以存储 null 的 key 和 value null 作为键只能有一个 null 作为值可以有多个	不允许有 null 键和 null 值
线程安全	没有考虑同步，线程不安全	线程安全，大多数方法用 synchronized 修饰
初始容量	默认 16	默认 11
容量增长	每次变为”原始容量 × 2”	每次变为”原始容量 × 2 + 1”
继承	继承于 AbstractMap 类	继承于 Dictionary 类
迭代器	Iterator 是 fail-fast 迭代器	enumerator 迭代器不是 fail-fast 的
hash 算法	使用自定义的哈希算法	直接采用 key 的 hashCode()

💡 fail-fast 机制：当有其它线程改变了 HashMap 的结构（增加或移除元素），将会抛出 ConcurrentModificationException。

---

四、Set

Set 集合的特点是不允许重复元素。

---

1. HashSet（无序，唯一）

底层实现：通过 HashMap 结构，继承 Set 父类

Set<Integer> sets = new HashSet<Integer>();

结构：数组 + 链表，数据是无序的

适用场景：

• ✅ 把一堆数据存到 HashSet 里面，然后查找某个数据存不存在
• ✅ 去除一堆数据中的重复项

主要作用：去重

---

2. TreeSet（有序，唯一）

底层实现：通过红黑树，继承 Set 父类

Set<Integer> sets = new TreeSet<Integer>();

结构：红黑树，key 值不允许为空，数据是有序的

主要作用：去重 + 排序

---

3. comparable 和 Comparator 的区别

接口	包	方法	说明
Comparable	java.lang	compareTo(Object obj)	用于对象自然排序
Comparator	java.util	compare(Object obj1, Object obj2)	用于自定义排序

使用场景：

• 当需要对一个集合使用自定义排序时，重写 compareTo() 或 compare() 方法
• 如果需要对某一个集合实现两种排序方式（如 song 对象按歌名和歌手名分别排序）
  • 可以重写 compareTo() 方法 + 使用自制的 Comparator 方法
  • 或者用两个 Comparator 实现，使用两个参数版的 Collections.sort()

---

4. 比较 HashSet、LinkedHashSet 和 TreeSet

特性	HashSet	LinkedHashSet	TreeSet
底层实现	HashMap	HashSet 的子类	红黑树
线程安全	不安全	不安全	不安全
null 值	可以存储	可以存储	不可以存储
有序性	无序	按照添加顺序	自然排序或定制排序
特点	Set 的主要实现类	能够按照添加顺序遍历	可以按照添加元素的顺序遍历

---

五、List

List 集合的特点是有序、可重复。

---

1. ArrayList（线程不安全）

底层实现：数组队列，相当于动态数组

与 Java 中的数组相比，它的容量能动态增长。

扩容原理（JDK 1.8）

1. 添加元素时，首先判断是否大于默认容量 10
2. 如果小于默认容量，直接在原来基础上 +1，元素添加完毕
3. 如果大于默认容量，则需要进行扩容，扩容核心是 grow() 方法
   • 3.1 扩容之前，首先创建一个新的数组，且旧数组被复制到新数组中
   • 3.2 然后通过位运算符将新的容量更新为旧容量的 1.5 倍
     • int newCapacity = oldCapacity + (oldCapacity >> 1)
     • 原来长度的一半再加上原长度
   • 3.3 如果新的容量 - 旧的容量 <= 0，就拿新的容量 - 最大容量长度
     • 如果 <= 0，那么最终容量就是扩容后的容量

为什么是 1.5 倍？

int newCapacity = oldCapacity + (oldCapacity >> 1)

• >> 1 相当于除以 2
• 所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右
  • oldCapacity 为偶数就是 1.5 倍
  • 否则是 1.5 倍左右

---

2. LinkedList（线程不安全）

底层数据结构：双向链表

📌 历史变化：JDK 1.6 之前为循环链表，JDK 1.7 取消了循环

为什么取消循环？

1. 代码更清晰：first/last 有更清晰的链头、链尾概念，代码看起来更容易明白
2. 节省内存：first/last 方式能节省 new 一个 headerEntry
   • 实例化 headerEntry 是为了让后面的方法更加统一
   • 否则会多很多 header 的空校验
3. 操作更高效：在链头/尾进行插入/删除操作，first/last 方式更加快捷

插入/删除操作分析：

按照位置分为两种情况：中间 和 两头

• 在中间插入/删除：两者都一样
  • 先遍历找到 index
  • 然后修改链表 index 处两头的指针
• 在两头：
  • 循环链表：由于首尾相连，还是需要处理两头的指针
  • 非循环链表：只需要处理一边 first.previous / last.next
  • 理论上非循环链表更高效

💡 恰恰在两头（链头/链尾）操作是最普遍的，所以取消循环更合理。

---

3. ArrayList 与 LinkedList 区别

特性	ArrayList	LinkedList
线程安全	不保证线程安全	不保证线程安全
底层数据结构	Object 数组	双向链表
插入/删除受位置影响	是 末尾添加：O(1) 指定位置：O(n-i)	否 末尾添加：O(1) 指定位置：O(n) 需要先移动到指定位置
快速随机访问	支持，通过序号快速获取元素	不支持
内存空间占用	list 结尾会预留一定的容量空间	每个元素需要存放直接后继、直接前驱以及数据

插入和删除时间复杂度详解：

ArrayList：

• add(E e)：默认在列表末尾追加元素，时间复杂度 O(1)
• add(int index, E element)：在指定位置 i 插入，时间复杂度 O(n-i)
  • 因为第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位/向前移一位的操作

LinkedList：

• add(E e)：在链表末尾添加，时间复杂度 O(1)
• add(int index, E element)：在指定位置 i 插入，时间复杂度近似 O(n)
  • 因为需要先移动到指定位置再插入

---

4. ArrayList 和 Vector 的区别

特性	ArrayList	Vector
实现类型	List 的主要实现类	List 的古老实现类
底层实现	Object[] 存储	Object[] 存储
线程安全	不安全	安全
适用场景	适用于频繁的查找工作	需要线程安全的场景

---

📚 参考资料：本文内容基于个人学习笔记整理