集合框架

体系结构

Iterable
└── Collection
    ├── List
    │   ├── ArrayList
    │   ├── LinkedList
    │   ├── Vector（线程安全，已过时）
    │   └── CopyOnWriteArrayList（并发）
    ├── Set
    │   ├── HashSet
    │   ├── LinkedHashSet（有序）
    │   ├── TreeSet（排序）
    │   └── CopyOnWriteArraySet（并发）
    └── Queue
        ├── LinkedList
        ├── ArrayDeque
        ├── PriorityQueue
        └── BlockingQueue（接口，并发）
            ├── ArrayBlockingQueue
            ├── LinkedBlockingQueue
            └── PriorityBlockingQueue

Map（独立体系）
├── HashMap
├── LinkedHashMap（有序）
├── TreeMap（排序）
├── Hashtable（线程安全，已过时）
├── ConcurrentHashMap（并发）
└── WeakHashMap

List

ArrayList

底层：动态数组，默认容量 10，扩容因子 1.5（新容量 = 旧容量 × 1.5）。

List<String> list = new ArrayList<>();
list.add("a");
list.add(0, "b");          // 指定位置插入，O(n)
list.get(0);               // 随机访问 O(1)
list.remove(0);            // 按下标删除 O(n)
list.remove("a");          // 按元素删除 O(n)
list.subList(1, 3);        // 返回视图，非副本
Collections.sort(list);

操作	时间复杂度
get(i)	O(1)
add(末尾)	O(1) 均摊
add(中间)	O(n)
remove(中间)	O(n)
contains	O(n)

LinkedList

底层：双向链表，同时实现 List 和 Deque。

LinkedList<String> list = new LinkedList<>();
list.addFirst("a");
list.addLast("b");
list.peekFirst();   // 查看不移除
list.pollFirst();   // 查看并移除

选择：频繁随机访问用 ArrayList；频繁头部插入删除用 LinkedList（但实际场景中 ArrayList 通常更快，因 CPU 缓存友好）。

Set

HashSet

底层：HashMap（值存 PRESENT 占位），无序，允许 null，不重复。

Set<String> set = new HashSet<>();
set.add("a");
set.contains("a"); // O(1) 均摊
set.remove("a");   // O(1) 均摊

LinkedHashSet

继承 HashSet，底层用 LinkedHashMap，维护插入顺序。

TreeSet

底层：红黑树，元素自然排序或自定义 Comparator 排序，不允许 null。

TreeSet<Integer> ts = new TreeSet<>();
ts.add(3); ts.add(1); ts.add(2);
ts.first();          // 1
ts.last();           // 3
ts.headSet(2);       // [1]
ts.tailSet(2);       // [2, 3]
ts.floor(2);         // 2（≤2 的最大值）
ts.ceiling(2);       // 2（≥2 的最小值）

Map

HashMap

底层：数组 + 链表/红黑树（Java 8+，链表长度 ≥ 8 且桶数 ≥ 64 时转红黑树）。

默认初始容量 16，负载因子 0.75，扩容时容量翻倍并 rehash。

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.getOrDefault("b", 0);               // 不存在返回默认值
map.putIfAbsent("a", 2);                // 存在则不覆盖
map.computeIfAbsent("c", k -> k.length()); // 不存在时计算并放入
map.merge("a", 1, Integer::sum);        // 存在则合并
map.forEach((k, v) -> System.out.println(k + "=" + v));
 
// 遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

HashMap 线程不安全：并发场景用 ConcurrentHashMap。

LinkedHashMap

维护插入顺序（或访问顺序），可用于实现 LRU 缓存：

// accessOrder=true：按访问顺序排序（LRU）
Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 100; // 超过 100 个自动移除最旧的
    }
};

TreeMap

底层：红黑树，按键排序，时间复杂度 O(log n)。

TreeMap<String, Integer> tm = new TreeMap<>();
tm.firstKey();          // 最小键
tm.lastKey();           // 最大键
tm.headMap("c");        // key < "c" 的视图
tm.floorKey("c");       // ≤ "c" 的最大键

ConcurrentHashMap

线程安全，Java 8 底层用 CAS + synchronized 锁单个桶，比 Hashtable 全表锁粒度细。

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("a", 1);
// 原子操作
map.compute("a", (k, v) -> v == null ? 1 : v + 1);

Queue / Deque

// Queue 操作（两套 API 区别：异常 vs 返回值）
Queue<Integer> q = new LinkedList<>();
q.offer(1);    // 入队，满时返回 false（add 抛异常）
q.poll();      // 出队，空时返回 null（remove 抛异常）
q.peek();      // 查看队头，空时返回 null（element 抛异常）
 
// Deque（双端队列，也可作栈）
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);
deque.offerLast(2);
deque.pollFirst();
deque.pollLast();
 
// PriorityQueue（堆，默认最小堆）
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());

Collections 工具类

Collections.sort(list);
Collections.sort(list, Comparator.reverseOrder());
Collections.binarySearch(sortedList, key);  // 二分查找
Collections.reverse(list);
Collections.shuffle(list);
Collections.min(list);
Collections.max(list);
Collections.frequency(list, elem);          // 出现次数
Collections.disjoint(list1, list2);         // 是否无交集
 
// 不可变包装
List<String> unmodifiable = Collections.unmodifiableList(list);
 
// 线程安全包装（性能差，推荐 ConcurrentHashMap 等）
List<String> synced = Collections.synchronizedList(list);

不可变集合（Java 9+）

List<String> list = List.of("a", "b", "c");
Set<Integer> set = Set.of(1, 2, 3);
Map<String, Integer> map = Map.of("a", 1, "b", 2);
Map<String, Integer> map2 = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2)
);
// 以上都不允许 null，不允许修改

选型参考

需求	推荐
随机访问列表	ArrayList
频繁头插/尾插	ArrayDeque（非 LinkedList）
唯一元素，无序	HashSet
唯一元素，保持插入顺序	LinkedHashSet
唯一元素，排序	TreeSet
键值对，无序	HashMap
键值对，保持插入顺序	LinkedHashMap
键值对，按键排序	TreeMap
并发键值对	ConcurrentHashMap
优先级队列	PriorityQueue

---

相关链接

• 数据类型