集合框架总览

Java集合主要分为两大体系：

• Collection（单列集合，存单个对象）
  • List（有序、可重复）
  • Set（无序、不可重复）
  • Queue / Deque（队列、双端队列）
• Map（双列集合，存键值对）

List接口

• ArrayList
  • 底层结构：动态数组
  • 特点：查询快、增删慢（中间位置）、线程不安全
  • 适用场景：频繁随机访问，末尾增删
• LinkedList
  • 底层结构：双向链表
  • 特点：增删快（两端/中间）、查询慢、线程不安全
  • 适用场景：频繁插入删除，做队列/栈
• Vector
  • 底层结构：动态数组
  • 特点：方法同步（线程安全），性能差
  • 适用场景：几乎不用，替代为 CopyOnWriteArrayList 或手动同步

关键点：ArrayList 默认容量 10，扩容为 1.5 倍

Set接口

• HashSet
  • 底层结构：哈希表（HashMap）
  • 特点：O(1) 增删改查，无序
  • 注意：依赖 hashCode() + equals()
• LinkedHashSet
  • 底层结构：哈希表 + 链表
  • 特点：插入顺序遍历
  • 注意： 比 HashSet 略慢
• TreeSet
  • 底层结构：红黑树（NavigableMap）
  • 特点：有序（自然/定制排序），O(log n)
  • 注意：元素必须可比

Queue/Deque接口

• PriorityQueue
  • 底层结构：优先堆（数组）
  • 特点：按优先级出队，非 FIFO
  • 场景：任务调度、TopK
• ArrayDeque
  • 底层结构：循环数组
  • 特点：双端队列，比 LinkedList 做栈/队列更快
  • 场景：栈、队列、双端操作
• LinkedList
  • 底层结构：链表
  • 特点：也实现 Deque
  • 场景：任务调度、栈、队列、双端操作

Map接口

• HashMap
  • 底层结构：哈希表（数组+链表/红黑树）
  • 特点：O(1)，无序，允许 null key/value
  • 注意：最常用，非线程安全
• LinkedHashMap
  • 底层结构：哈希表 + 双向链表
  • 特点：插入顺序或访问顺序遍历
  • 注意：可做 LRU 缓存
• TreeMap
  • 底层结构：红黑树
  • 特点：有序（按 key），O(log n)
  • 注意：key 必须可比
• Hashtable
  • 底层结构：哈希表
  • 特点：线程安全，不允许 null
  • 注意：不推荐，用 ConcurrentHashMap
• ConcurrentHashMap（JUC）
  • 底层结构：分段锁/CAS
  • 特点：高并发安全，性能好
  • 注意：并发必选

关键点：HashMap 扩容因子 0.75，链表长度 ≥8 且数组 ≥64 转红黑树

并发集合（java.util.concurrent）

• ConcurrentHashMap
• CopyOnWriteArrayList：读多写少，写时复制
• CopyOnWriteArraySet
• ConcurrentLinkedQueue：无界非阻塞队列
• BlockingQueue 系列（ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue）