按下标快速读取Fast indexed access
优先选择数组或 ArrayList。连续存储通常也有更好的 CPU 缓存局部性。
Prefer an array or ArrayList. Contiguous storage usually provides better cache locality, too.
list.get(i)JAVA COLLECTIONS选择指南 · SELECTION GUIDE
Choose the right
structure.选对数据结构。
数据结构决定程序如何存储、查找、排序和更新数据。这份手册把 Java 集合框架、时间复杂度与常用代码模式放在同一张地图上。
Data structures determine how a program stores, finds, orders, and updates data. This guide puts Java’s collections, time complexity, and practical coding patterns on one map.
开始选择 · Start choosing ↓约 18 分钟
~18 MIN READ
~18 MIN READ
FIG. 01JAVA COLLECTIONS MAP
DATAHow will you use it?
SEQUENCEListArrayList · LinkedList
UNIQUESetHashSet · TreeSet
KEY → VALUEMapHashMap · TreeMap
NEXT ITEMQueueArrayDeque · PriorityQueue
Default rule: choose the simplest structure that makes the dominant operation cheap.
01 — START WITH THE OPERATION
先问：最常做什么？Start with the dominant operation
通过键快速查找Fast lookup by key
默认使用 HashMap；需要排序、范围查询或最近键时选择 TreeMap。
Default to HashMap; choose TreeMap for sorting, ranges, floor, or ceiling queries.
map.get(key)去重或成员判断Uniqueness or membership
HashSet 适合快速 contains；TreeSet 适合有序唯一值。
HashSet is for fast contains; TreeSet keeps unique values sorted.
set.add(value)从两端进出Add and remove at the ends
使用 ArrayDeque 实现队列、双端队列或栈，通常不要使用旧式 Stack。
Use ArrayDeque as a queue, deque, or stack; usually avoid the legacy Stack class.
deque.offerLast(x)反复取最小或最大值Repeated min or max
PriorityQueue 用堆维持队首元素，而不必每次对全部数据排序。
PriorityQueue maintains the head with a heap instead of sorting everything repeatedly.
queue.poll()保留插入顺序Preserve insertion order
选择 LinkedHashMap 或 LinkedHashSet；它们兼顾哈希查找与稳定迭代顺序。
Choose LinkedHashMap or LinkedHashSet for hashing plus predictable iteration order.
new LinkedHashMap<>()02 — TIME COMPLEXITY
复杂度与集合对照表Complexity & comparison
O(1) constant · 常数O(log n) logarithmic · 对数O(n) linear · 线性O(n log n) efficient sort · 高效排序O(n²) quadratic · 平方
| STRUCTURE · 结构 | ACCESS | SEARCH / CONTAINS | INSERT / ADD | REMOVE | BEST FIT · 适用场景 |
|---|---|---|---|---|---|
| Array / 数组 | O(1) | O(n) | O(n) | O(n) | Fixed size · 连续存储 |
| ArrayList | O(1) | O(n) | O(1)* | O(n) | Fast indexed reads · 随机访问 |
| LinkedList | O(n) | O(n) | O(1)** | O(1)** | Frequent end operations · 两端操作 |
| ArrayDeque | — | O(n) | O(1)* | O(1)* | Stack or queue · 栈或队列 |
| HashMap | O(1) avg | O(1) avg | O(1) avg | O(1) avg | Key lookup · 键值查找 |
| LinkedHashMap | O(1) avg | O(1) avg | O(1) avg | O(1) avg | Predictable order / LRU |
| TreeMap | O(log n) | O(log n) | O(log n) | O(log n) | Sorted keys / range queries |
| HashSet | — | O(1) avg | O(1) avg | O(1) avg | Uniqueness · 去重 |
| TreeSet | — | O(log n) | O(log n) | O(log n) | Sorted unique values |
| PriorityQueue | O(1) peek | O(n) | O(log n) | O(log n) poll | Repeated min/max · 优先级 |
* Amortized / 均摊：偶尔扩容会很慢，但把多次操作平均后仍为 O(1)。Occasional resizing is expensive, but the cost averaged across many operations is O(1).
** At a known end/node / 已知端点或节点：找到位置仍可能需要 O(n)；只有链接本身的修改是 O(1)。Finding the position may still cost O(n); only the link update itself is O(1).
Hash caveat / 哈希说明：O(1) 是平均情况。糟糕的哈希分布或冲突会降低性能；Java 的树化桶可限制部分严重冲突。O(1) is average-case. Poor hashing and collisions hurt performance; Java’s tree bins can limit some severe collision cases.
03 — CORE JAVA COLLECTIONS
从接口思考，从实现选择Think in interfaces, choose implementations
ArrayList vs LinkedList
ArrayList 是绝大多数 List 场景的默认选择：随机访问快、内存紧凑、迭代友好。只有当你确实频繁操作两端，且不需要随机访问时才考虑 LinkedList；队列场景通常 ArrayDeque 更合适。
ArrayList is the default for most List workloads: fast indexed access, compact storage, and efficient iteration. Consider LinkedList only for genuine end-heavy workloads without indexed access; ArrayDeque is usually better for queues.
ArrayList.java
List<String> topics = new ArrayList<>();
topics.add("Arrays");
topics.add("Maps");
topics.add(1, "Lists"); // shifts later elements
String first = topics.get(0); // O(1)
topics.remove("Maps"); // search + shift: O(n)
topics.sort(Comparator.naturalOrder());ArrayDeque.java
Deque<String> work = new ArrayDeque<>();
// Queue: FIFO
work.offerLast("parse");
work.offerLast("compile");
String next = work.pollFirst();
// Stack: LIFO
work.push("test");
String top = work.pop();
// Prefer ArrayDeque over legacy Stack.ArrayDeque
同一个 API 可以表达 FIFO 队列、LIFO 栈和双端队列。它不允许 null；这种约束也让 poll 返回 null 时能明确表示“为空”。
One API models FIFO queues, LIFO stacks, and double-ended queues. It rejects null, so a null result from poll can unambiguously mean “empty.”
HashMap vs TreeMap
HashMap 优先优化键查找；TreeMap 根据键的自然顺序或 Comparator 排序，并提供 firstKey、floorEntry、ceilingEntry 与 subMap 等导航操作。
HashMap optimizes key lookup. TreeMap sorts by natural key order or a Comparator and adds navigation operations such as firstKey, floorEntry, ceilingEntry, and subMap.
FrequencyMap.java
Map<String, Integer> frequency = new HashMap<>();
for (String word : words) {
frequency.merge(word, 1, Integer::sum);
}
String mostCommon = frequency.entrySet().stream()
.max(Map.Entry.comparingByValue())
.orElseThrow()
.getKey();OrderedCollections.java
NavigableMap<Integer, String> releases = new TreeMap<>();
releases.put(8, "LTS");
releases.put(17, "LTS");
releases.put(21, "LTS");
Map.Entry<Integer, String> floor = releases.floorEntry(19);
SortedMap<Integer, String> range = releases.subMap(11, 22);
Set<String> stableUnique = new LinkedHashSet<>(names);TreeMap & LinkedHashSet
“有序”要说清楚：TreeMap 是按键排序；LinkedHashSet 是保留插入顺序。两者解决的不是同一个问题。
Be precise about “ordered”: TreeMap sorts by key; LinkedHashSet preserves insertion order. They solve different problems.
PriorityQueue
Java 的 PriorityQueue 默认是最小堆。peek 读取队首为 O(1)，offer 与 poll 为 O(log n)；遍历顺序并不是优先级顺序。
Java’s PriorityQueue is a min-heap by default. peek is O(1), while offer and poll are O(log n). Iteration is not priority order.
PriorityQueue.java
record Job(String name, int priority) {}
Queue<Job> jobs = new PriorityQueue<>(
Comparator.comparingInt(Job::priority)
);
jobs.offer(new Job("backup", 3));
jobs.offer(new Job("incident", 1));
jobs.offer(new Job("report", 2));
Job urgent = jobs.poll(); // incident04 — PRACTICAL PATTERNS
把结构组合成算法Compose structures into algorithms
频率统计Frequency counting
HashMap + merge 是计数、分组与索引构建的基础模式。HashMap + merge is a foundational pattern for counting, grouping, and indexing.
稳定去重Stable deduplication
new LinkedHashSet<>(items) 在去重的同时保留首次出现顺序。new LinkedHashSet<>(items) removes duplicates while retaining first-seen order.
图的广度优先搜索Breadth-first graph search
邻接表使用 Map + List，访问记录使用 Set，待访问节点使用 ArrayDeque。每个组件都只负责一件事。Use Map + List for adjacency, Set for visited nodes, and ArrayDeque for the frontier. Each structure has one job.
BreadthFirstSearch.java
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", List.of("B", "C"));
graph.put("B", List.of("D"));
graph.put("C", List.of("D"));
graph.put("D", List.of());
Set<String> seen = new HashSet<>();
Deque<String> queue = new ArrayDeque<>();
queue.offer("A");
seen.add("A");
while (!queue.isEmpty()) {
String node = queue.poll();
for (String neighbor : graph.getOrDefault(node, List.of())) {
if (seen.add(neighbor)) queue.offer(neighbor);
}
}用大小为 k 的 PriorityQueue，把 O(n log n) 全量排序降为 O(n log k)。Use a size-k PriorityQueue to replace an O(n log n) full sort with O(n log k).
LinkedHashMap 支持访问顺序，可作为简单 LRU 缓存的基础。LinkedHashMap supports access order, making it a foundation for a simple LRU cache.
TreeMap / TreeSet 提供 floor、ceiling 与区间视图。TreeMap and TreeSet provide floor, ceiling, and range views.
DFS 使用栈；BFS 使用队列。两者通常再配合 Set 防止重复访问。DFS uses a stack; BFS uses a queue. Both typically pair with a Set to avoid revisits.
05 — CORRECTNESS & PITFALLS
复杂度之外，还要看正确性Correctness comes before Big O
正确实现 equals 与 hashCodeImplement equals and hashCode together
作为 HashMap 键或 HashSet 元素的对象，必须保持两者契约一致；键放入集合后不应改变参与哈希的字段。Objects used as HashMap keys or HashSet members must honor both contracts. Do not mutate fields involved in hashing after insertion.
Comparator 必须一致且可传递Comparators must be consistent and transitive
错误的比较器会让 TreeMap、TreeSet 与排序产生丢失元素或异常顺序。A broken comparator can make TreeMap, TreeSet, and sorting lose elements or produce invalid order.
集合默认不是线程安全的Collections are not thread-safe by default
并发访问时应根据语义选择 ConcurrentHashMap、BlockingQueue、CopyOnWriteArrayList 或外部同步。For concurrent access, choose ConcurrentHashMap, BlockingQueue, CopyOnWriteArrayList, or external synchronization according to the workload.
不要只看 Big OBig O is not the whole cost
对象开销、缓存局部性、装箱、扩容、GC 压力与实际数据规模，都会让理论相同的结构表现不同。Object overhead, cache locality, boxing, resizing, GC pressure, and real input sizes can separate structures with identical asymptotic cost.
返回接口，隐藏实现Expose interfaces, hide implementations
字段和方法签名优先使用 List、Map、Set、Deque，使实现可以在不影响调用者的情况下替换。Prefer List, Map, Set, and Deque in fields and method signatures so implementations can change without affecting callers.
FINAL CHECK / 最终检查
选择 → 测量 → 验证Choose → measure → verify
先根据语义和主操作选择最简单的结构，再用真实数据测量。只有指标证明它是瓶颈时，才为复杂度或内存布局做进一步优化。
Choose the simplest structure from semantics and dominant operations, then measure with representative data. Optimize complexity or layout further only when evidence identifies a bottleneck.