List、Set 和 Map 的区别
| 特性 | List | Set | Map |
|---|---|---|---|
| 元素顺序 | 有序 | 无序（部分实现有序） | 无序（部分实现有序） |
| 元素唯一性 | 允许重复 | 不允许重复 | 键唯一，值可重复 |
| 访问方式 | 通过索引 | 通过元素本身 | 通过键 |
| 常见实现 | ArrayList, LinkedList | HashSet, TreeSet | HashMap, TreeMap |
| 底层数据结构 | 动态数组、双向链表 | 哈希表、红黑树 | 哈希表、红黑树 |
| 适用场景 | 需要顺序或索引访问 | 需要去重或快速查找 | 需要键值对映射 |
List、Set 和 Map 的常见实现类及其底层数据结构
1. List（列表）
| 实现类 | 底层数据结构 | 特点 |
|---|---|---|
| ArrayList | 动态数组 | - 基于数组实现，支持随机访问。 - 插入和删除效率较低（需要移动元素）。 |
| LinkedList | 双向链表 | - 基于链表实现，插入和删除效率高。 - 随机访问效率低（需要遍历链表）。 |
| Vector | 动态数组（线程安全） | - 类似 ArrayList，但线程安全。- 性能较低，通常不推荐使用。 |
2. Set（集合）
| 实现类 | 底层数据结构 | 特点 |
|---|---|---|
| HashSet | 哈希表（基于 HashMap） | - 基于哈希表实现，插入、删除和查找效率高（平均 O(1)）。 - 无序。 |
| LinkedHashSet | 哈希表 + 双向链表 | - 在 HashSet 基础上维护插入顺序。- 插入和查找效率接近 HashSet。 |
| TreeSet | 红黑树 | - 基于红黑树实现，元素按自然顺序或自定义顺序排序。 - 插入、删除和查找效率为 O(log n)。 |
3. Map（映射）
| 实现类 | 底层数据结构 | 特点 |
|---|---|---|
| HashMap | 哈希表 | - 基于哈希表实现，插入、删除和查找效率高（平均 O(1)）。 - 无序。 |
| LinkedHashMap | 哈希表 + 双向链表 | - 在 HashMap 基础上维护插入顺序或访问顺序。- 插入和查找效率接近 HashMap。 |
| TreeMap | 红黑树 | - 基于红黑树实现，键按自然顺序或自定义顺序排序。 - 插入、删除和查找效率为 O(log n)。 |
| Hashtable | 哈希表（线程安全） | - 类似 HashMap，但线程安全。- 性能较低，通常不推荐使用。 |
常见的线程安全集合类及其底层数据结构和线程安全实现方式
1. List（列表）
| 实现类 | 底层数据结构 | 线程安全实现方式 |
|---|---|---|
| Vector | 动态数组 | 使用 synchronized 关键字修饰方法，保证线程安全。 |
| Collections.synchronizedList | 基于传入的 List | 使用同步包装器，对所有方法加 synchronized 锁。 |
| CopyOnWriteArrayList | 动态数组 | 使用写时复制（Copy-On-Write）技术，读操作无锁，写操作复制新数组。 |
2. Set（集合）
| 实现类 | 底层数据结构 | 线程安全实现方式 |
|---|---|---|
| Collections.synchronizedSet | 基于传入的 Set | 使用同步包装器，对所有方法加 synchronized 锁。 |
| CopyOnWriteArraySet | 动态数组 | 基于 CopyOnWriteArrayList，使用写时复制技术。 |
3. Map（映射）
| 实现类 | 底层数据结构 | 线程安全实现方式 |
|---|---|---|
| Hashtable | 哈希表 | 使用 synchronized 关键字修饰方法，保证线程安全。 |
| Collections.synchronizedMap | 基于传入的 Map | 使用同步包装器，对所有方法加 synchronized 锁。 |
| ConcurrentHashMap | 哈希表（分段锁） | 使用分段锁（JDK 7）或 CAS + synchronized（JDK 8+）。 |
4. Queue（队列）
| 实现类 | 底层数据结构 | 线程安全实现方式 |
|---|---|---|
| BlockingQueue（接口） | 数组或链表 | 使用锁和条件变量实现线程安全。 |
| ArrayBlockingQueue | 数组 | 使用 ReentrantLock 和 Condition 实现线程安全。 |
| LinkedBlockingQueue | 链表 | 使用两把锁（putLock 和 takeLock）提高并发性能。 |
| ConcurrentLinkedQueue | 链表 | 使用 CAS（Compare-And-Swap）实现无锁线程安全。 |
5. 总结对比
| 实现类 | 底层数据结构 | 线程安全实现方式 | 适用场景 |
|---|---|---|---|
| Vector | 动态数组 | synchronized 方法锁 | 已过时，不推荐使用 |
| Hashtable | 哈希表 | synchronized 方法锁 | 已过时，不推荐使用 |
| Collections.synchronizedXxx | 基于传入的集合 | synchronized 方法锁 | 简单场景，性能要求不高 |
| CopyOnWriteArrayList | 动态数组 | 写时复制（Copy-On-Write） | 读多写少的场景 |
| CopyOnWriteArraySet | 动态数组 | 写时复制（Copy-On-Write） | 读多写少的场景 |
| ConcurrentHashMap | 哈希表 | 分段锁（JDK 7）或 CAS（JDK 8+） | 高并发场景 |
| ConcurrentLinkedQueue | 链表 | CAS | 高并发队列场景 |
| ArrayBlockingQueue | 数组 | ReentrantLock + Condition | 有界阻塞队列 |
| LinkedBlockingQueue | 链表 | 两把锁（putLock 和 takeLock） | 无界或有界阻塞队列 |
