Java 集合框架一览

JDK 集合框架 一览

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/package-summary.html

两大类(Collection, Map) 四小类

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是 K/V映射集合（Map），存储键/值对映射， Collection 和 Map 是 Java 集合框架的根接口!。Collection 接口可以再细分为 3 种子类型，List、Set 和 Queue

Collection

List: 有序性： List是有序的，即元素按照插入的顺序排列，并且可以通过索引来访问元素。 允许重复元素： List允许存储重复的元素，同一个元素可以出现多次。 常见实现类： 常见的List实现类包括ArrayList、LinkedList、Vector等。

Set: 不允许重复元素： Set不允许存储重复的元素，每个元素在集合中是唯一的。访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）; 无序性： Set不保证元素的顺序，即元素没有特定的排列顺序。 常用于去重： 由于不允许重复元素，Set常常用于去重的场景。 常见实现类： 常见的Set实现类包括HashSet、LinkedHashSet、TreeSet等。

Queue: FIFO（先进先出）： Queue是先进先出的数据结构，即最先进入队列的元素最先被移除。 可用于实现阻塞队列： Queue的子接口BlockingQueue可以用于实现阻塞队列，支持线程安全的生产者-消费者模型。 允许重复元素： 与List一样，Queue也允许存储重复的元素。 常见实现类： 常见的Queue实现类有LinkedList、PriorityQueue等。

Map

Map: 键值对存储： Map是Key-value 对形式的元素，每个元素都包含一个键和对应的值。 键的唯一性： 每个键在Map中是唯一的，但值可以重复。 无序性： Map中的元素没有特定的顺序。 常见实现类： 常见的Map实现类包括HashMap、LinkedHashMap、TreeMap等

Collection 集合实现

List

All Known Implementing Classes: AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

名称	线程安全	有序性	允许 Null 元素	有界性	核心特点与应用场景	底层实现原理
​​ArrayList​​	❌	✅ (插入顺序)	✅	❌ (动态扩容)	​​最常用的List​​。随机访问性能极佳(O(1))。在中间插入/删除元素较慢(O(n))。默认初始容量为10，扩容因子通常为1.5倍。	动态数组
​​LinkedList​​	❌	✅ (插入顺序)	✅	❌	实现了List和Deque接口。在任意位置插入/删除元素快(O(1))，但随机访问慢(O(n))。可被用作栈、队列或双端队列。	双向链表
​​Vector​​	✅ (同步方法)	✅ (插入顺序)	✅	❌ (动态扩容)	​​线程安全的动态数组​​，是Java的早期实现。由于其同步方法导致性能较低，在现代Java开发中已不推荐使用，可由Collections.synchronizedList或CopyOnWriteArrayList替代。	动态数组
​​Stack​​	✅ (继承自Vector)	✅ (插入顺序)	✅	❌	继承自Vector，表示后进先出（LIFO）的堆栈。同样是遗留类，更推荐使用Deque接口的实现（如ArrayDeque）来模拟栈行为。	动态数组
​​CopyOnWriteArrayList​​	✅	✅ (插入顺序)	✅	❌	​​线程安全List​​。所有写操作（增、删、改）都会创建底层数组的新副本。​​读操作无锁且非常快​​，适用于​​读多写少​​的并发场景。 使用CopyOnWriteArrayList 可以线程安全地遍历, 因为如果另外一个线程在遍历的时候修改List的话, 实际上会拷贝出一个新的List上修改, 而不影响当前正在被遍历的List;	动态数组 + 写时复制
​​AbstractList​​	❌	✅ (插入顺序)	(取决于子类)	(取决于子类)	为List接口提供了​​骨架实现​​，是一个​​抽象类​​。用于减少实现自定义List的工作量，不可直接实例化。	(骨架实现)
​​AbstractSequentialList​​	❌	✅ (插入顺序)	(取决于子类)	(取决于子类)	继承自AbstractList，为​​顺序访问​​的数据结构（如链表）提供骨架实现。降低了实现基于迭代器操作的List的难度。	(骨架实现)
​​AttributeList​​ / ​​RoleList​​ / ​​RoleUnresolvedList​​	❌	✅ (插入顺序)	(具体实现决定)	❌	这些是​​JMX（Java管理扩展）​​ 相关的专用List实现，通常用于管理MBean的属性或角色。它们在底层通常基于ArrayList，但包含了特定领域的类型检查和逻辑，一般在通用业务开发中不会使用。	动态数组 (基于ArrayList)

如何安全的遍历?

• 使用迭代器
• forEach List.forEach 方法是 Java 8新增的一个方法, 主要目的还是用于让List来支持Java 8的新特性: Lambda表达式; Vector 的 forEach方法上加了 synchronized 来控制线程安全的遍历, 也就是Vector的forEach方法可以线程安全地遍历;

Set

All Known Implementing Classes: AbstractSet, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

名称	线程安全	有序性	允许 Null	有界性	核心特点与应用场景	底层实现原理
​​HashSet​​	❌	❌ 无序	✅	❌ 无界	​​最常用的Set​​。利用哈希表实现，提供平均O(1)时间复杂度的添加、删除和查询操作。适用于需要快速去重且不关心元素顺序的场景 。	基于 HashMap(哈希表+链表/红黑树)
​​LinkedHashSet​​	❌	✅ (插入顺序)	✅	❌ 无界	在HashSet基础上维护了一个贯穿所有元素的双向链表，从而​​保留了元素的插入顺序​​。迭代性能很好，适用于需要保持插入或访问顺序的去重场景。	继承HashSet，但内部使用LinkedHashMap(哈希表+双向链表)
​​TreeSet​​	❌	✅ (按元素的自然顺序或比较器顺序)	❌	❌ 无界	元素始终处于排序状态。支持一系列范围操作（如subSet, headSet）。添加、删除、查询的时间复杂度为O(log n)。适用于需要元素有序或范围查询的场景 。	基于 TreeMap(红黑树)
​​CopyOnWriteArraySet​​	✅	✅ (插入顺序)	✅	❌ 无界	​​线程安全​​。采用“写时复制”技术，所有写操作（增、删、改）都会创建底层数组的新副本，而读操作直接在原数组上进行。​​读操作非常快且无锁​​，但写操作开销大。适用于​​读多写极少​​的并发场景 。	基于 CopyOnWriteArrayList(写时复制数组)
​​ConcurrentSkipListSet​​	✅	✅ (按元素的自然顺序或比较器顺序)	❌	❌ 无界	​​线程安全的有序Set​​。底层使用跳表实现，平均时间复杂度为O(log n)。支持高并发访问，是TreeSet的并发版本。适用于高并发环境下需要有序集合的场景 。	基于 ConcurrentSkipListMap(跳表)Skip List
​​EnumSet​​	❌	✅ (枚举常量声明顺序)	❌	✅ (受枚举类型常量数量限制)	专为枚举类型设计的Set，性能极高且内存占用小。所有元素必须是同一枚举类型的值。迭代顺序与枚举常量声明顺序一致。是存储枚举值的最佳选择 。	位向量 (Bit Vector)
​​AbstractSet​​	(取决于具体子类)	(取决于具体子类)	(取决于具体子类)	(取决于具体子类)	一个抽象类，为Set接口提供了​​骨架实现​​。它减少了实现自定义Set的工作量，本身不能被实例化，特性由其具体子类决定 。	(骨架实现)
​​ConcurrentHashMap.KeySetView​​	✅	❌ 无序	❌ (与ConcurrentHashMap一致)	❌ 无界	这是ConcurrentHashMap的键集合视图。它本身不是一个独立的实现，而是与底层映射的键集保持实时联动。它是线程安全且无序的 。	基于 ConcurrentHashMap

Queue

All Known Implementing Classes: AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

链表队列的吞吐量通常而言要高于基于数组的队列, 队列通常（不一定）以FIFO（先进先出）的方式对元素进行排序;

名称	线程安全	阻塞	允许 Null	有界性	核心特点与应用场景	底层实现原理
​​ArrayBlockingQueue​​	✅ 是	✅ 是	❌ 否	✅ 有界	​​经典的有界阻塞队列​​。内存连续，缓存友好。生产者和消费者共用一把锁。适用于固定大小的资源池、传统生产者-消费者模型 。	固定大小的数组 + 一把可重入锁 (ReentrantLock) 和两个条件变量 (notEmpty, notFull)
​​LinkedBlockingQueue​​	✅ 是	✅ 是	❌ 否	可选（默认无界）	采用分离锁，生产者（put）和消费者（take）的操作通常不冲突，吞吐量常优于ArrayBlockingQueue。默认构造时容量为Integer.MAX_VALUE，可视为无界，也可指定为有界。是Executors.newFixedThreadPool默认的任务队列 。	链表 + ​​两把可重入锁​​ (putLock和 takeLock)
​​PriorityBlockingQueue​​	✅ 是	✅ 是	❌ 否	❌ 无界	​​支持优先级的无界阻塞队列​​。元素需实现Comparable接口或提供Comparator。出队顺序由优先级决定。适用于定时任务、有优先级的任务处理 。	二叉堆（动态数组）+ 一把公共锁
​​DelayQueue​​	✅ 是	✅ 是	❌ 否	❌ 无界	​​无界阻塞延迟队列​​。只有元素的延迟时间到期后才能被取出。适用于定时任务调度、缓存过期失效、重试机制等场景 。	内部封装一个PriorityQueue，元素必须实现Delayed接口
​​SynchronousQueue​​	✅ 是	✅ 是	❌ 否	✅ 容量为0	​​一种不存储元素的阻塞队列​​。每个插入操作（put）必须等待一个对应的移除操作（take），反之亦然，实现信息的直接传递。是Executors.newCachedThreadPool默认使用的队列，吞吐量很高 。	无内部数据存储结构，支持公平（队列）和非公平（栈）模式
​​LinkedTransferQueue​​	✅ 是	部分方法阻塞	❌ 否	❌ 无界	是ConcurrentLinkedQueue, SynchronousQueue, 和LinkedBlockingQueue功能的超集。特有的transfer()方法允许生产者阻塞直到元素被消费者取走，确保”送达”。适用于需要高并发且偶尔需要阻塞传递的场景 。	链表 + 无锁（CAS）算法
​​LinkedBlockingDeque​​	✅ 是	✅ 是	❌ 否	可选（默认无界）	​​线程安全的双端阻塞队列​​。支持在队列的首尾两端进行插入和移除操作。适用于工作窃取（work-stealing）算法等场景 。	双向链表
​​ConcurrentLinkedQueue​​	✅ 是	❌ 非阻塞	❌ 否	❌ 无界	​​高性能的非阻塞线程安全队列​​。使用CAS（Compare-And-Swap）操作实现并发控制，在高并发环境下提供极佳的吞吐量。但因其无界，需警惕可能的内存溢出（OOM）风险。适用于高并发非阻塞场景，如消息总线、日志缓冲 。	基于节点的无锁（CAS）链表
​​ConcurrentLinkedDeque​​	✅ 是	❌ 非阻塞	❌ 否	❌ 无界	ConcurrentLinkedQueue的双端队列版本，支持从两端进行无锁的并发操作 。	基于节点的无锁（CAS）链表
​​ArrayDeque​​	❌ 否	❌ 非阻塞	❌ 否	❌ 无界（可扩容）	​​单线程环境下高效的双端队列实现​​。作为栈或队列使用时，性能通常优于Stack和LinkedList（因内存连续，缓存友好）。​​非线程安全​​。	动态循环数组
​​LinkedList​​	❌ 否	❌ 非阻塞	✅ 是	❌ 无界	同时实现了List和Deque接口。由于其链式结构，随机访问性能差（O(n)），但元素插入删除灵活。​​非线程安全​​ 。	双向链表
​​PriorityQueue​​	❌ 否	❌ 非阻塞	❌ 否	❌ 无界	​​非线程安全的优先级队列​​。特性同PriorityBlockingQueue，但无线程安全保证。适用于单线程优先级任务处理 。	二叉堆（动态数组）

关键方法说明

1. 获取并移除 poll() 获取并移除此队列的头, 如果此队列为空, 则返回 null remove() 获取并移除此队列的头, 如果此队列为空, 则抛出 NoSuchElementException 异常

2. 获取但不移除 peek() 获取队列的头但不移除此队列的头; 如果此队列为空, 则返回 null element() 获取队列的头但不移除此队列的头; 如果此队列为空, 则将抛出 NoSuchElementException 异常

3. 添加元素 offer() 将指定的元素插入此队列（如果立即可行且不会违反容量限制）, 插入成功返回 true; 否则返回 false; 当使用有容量限制的队列时, offer方法通常要优于 add方法——add方法可能无法插入元素, 而只是抛出一个 IllegalStateException 异常 add() 将指定的元素插入此队列, 无法添加会抛出异常

Map 集合实现

All Known Implementing Classes: AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

名称	线程安全	有序性	允许Null键/值	有界性	核心特点	底层实现原理
​​HashMap​​	❌ 不安全	❌ 无序	✅/✅	❌ 无界	最常用的Map，性能好，允许一个null键 。	数组+链表/红黑树（JDK8+）
​​Hashtable​​	✅ 安全（全表锁）	❌ 无序	❌/❌	❌ 无界	古老实现类，线程安全但效率较低，已不推荐使用 。	数组+链表
​​LinkedHashMap​​	❌ 不安全	✅ 按插入顺序或访问顺序	✅/✅	❌ 无界	在HashMap基础上维护了元素的插入或访问顺序，遍历性能较好 。	继承HashMap，增加双向链表维护顺序
​​TreeMap​​	❌ 不安全	✅ 按Key的自然顺序或比较器顺序	❌/✅（键不能为null，值可以为null）	❌ 无界	元素始终处于排序状态，查询、插入、删除的时间复杂度为O(log n) 。	红黑树
​​ConcurrentHashMap​​	✅ 安全（分段锁/CAS）	❌ 无序	❌/❌	❌ 无界	高并发场景首选，性能远优于Hashtable 。	JDK8+: 数组+链表/红黑树 + CAS/synchronized
​​ConcurrentSkipListMap​​	✅ 安全	✅ 按Key排序	❌/❌	❌ 无界	支持高并发访问的有序Map。	跳表（Skip List）
​​WeakHashMap​​	❌ 不安全	❌ 无序	✅/✅	❌ 无界	当key不再被强引用时，对应的键值对会被自动回收 。	哈希表，对key是弱引用
​​IdentityHashMap​​	❌ 不安全	❌ 无序	✅/✅	❌ 无界	使用==进行键的相等性比较，允许重复键（如果它们是不同的对象） 。	数组，使用==代替equals()比较key
​​EnumMap​​	❌ 不安全	✅ 按枚举常量声明顺序	❌/✅（键不能为null，值可以为null）	✅ Key为枚举类型，受枚举常量数量限制	专为枚举类型作为Key设计，性能极高，内存占用小 。	紧凑的数组，以枚举序数为索引
​​Properties​​	✅ 安全（继承Hashtable）	❌ 无序（但加载/存储时通常按固定顺序）	❌/❌（key和value必须是String）	❌ 无界	专门处理属性文件（.properties），key和value都是String类型 。	继承Hashtable

注意: 作为 key 的对象 equal 和 hashcode 都 必须重写! 必须重写! 必须重写! 重要的事情说三遍

一个 LRU Map的实现

一个指定最大容量, 超出容量后自动丢弃最后元素的 Map容器

val callbacks = KeyedBoundedQueue<String, Promise<Message>>(500);

public class KeyedBoundedQueue<K, V> {
    private final int capacity;
    private final ConcurrentHashMap<K, V> map;
    private final ReentrantLock lock = new ReentrantLock();
 
    public KeyedBoundedQueue(int capacity) {
        this.capacity = capacity;
        this.map = new ConcurrentHashMap<>(capacity);
    }
 
    /**
     * 添加或更新元素
     * @param key 键
     * @param value 值
     */
    public void put(K key, V value) {
        lock.lock();
        try {
            if (map.size() >= capacity) {
                // 找到并移除最早插入的元素
                K eldestKey = map.keySet().iterator().next();
                map.remove(eldestKey);
            }
            map.put(key, value);
        } finally {
            lock.unlock();
        }
    }
    /**
     * 获取元素
     * @param key 键
     * @return 对应的值
     */
    public V get(K key) {
        return map.get(key);
    }
 
    /**
     * 检查是否包含某个键
     * @param key 键
     * @return 是否包含该键
     */
    public boolean containsKey(K key) {
        return map.containsKey(key);
    }
 
    /**
     * 移除元素
     * @param key 键
     * @return 被移除的值
     */
    public V remove(K key) {
        return map.remove(key);
    }
 
    /**
     * 获取当前队列大小
     * @return 队列大小
     */
    public int size() {
        return map.size();
    }
 
    @Override
    public String toString() {
        return map.toString();
    }
}

关于 Collections::synchronizedXXX

java.util.Collections类中的 synchronizedXxx()方法系列。这些方法是 Java 早期（在 java.util.concurrent包出现之前）为​​非线程安全​​的标准集合类（如 ArrayList, HashMap, HashSet等）提供基本线程安全访问的主要方式。

• 将​​非线程安全​​的集合实例包装成一个​​线程安全​​的视图。
• 通过在包装器对象的每个公共方法上添加 synchronized关键字（即使用对象内部锁）来实现同步。
• 使用排斥锁(mutex) , 以实现线程安全 Collections::synchronizedMap

多线程遍历集合问题

fail-safe ( 安全失败 )

fail-safe:这种遍历基于容器的一个克隆。因此，对容器内容的修改不影响遍历。

java.util.concurrent 包下的容器都是安全失败的,可以在多线程下并发使用,并发修改。 常见的使用 fail-safe方式 遍历的容器有ConcerrentHashMap和CopyOnWriteArrayList等。

fail-fast ( 快速失败 )

fail-fast:直接在容器上进行遍历，在遍历过程中，一旦发现容器中的数据被修改了，会立刻抛出ConcurrentModificationException异常导致遍历失败。

java.util包下的集合类几乎都是快速失败机制的, 常见的的使用fail-fast方式遍历的容器有HashMap和ArrayList等。