• List 特点：元素有放入顺序，元素可重复;
  • Map 特点：元素按键值对存储，无放入顺序 ;
  • List 接口有三个实现类：LinkedList，ArrayList，Vector;
  • LinkedList：底层基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢;
  • Map 接口有三个实现类：HashMap，HashTable，LinkedHashMap
  • Map 相当于和 Collection 一个级别的；Map 集合存储键值对，且要求保持键的唯一性；

特征清单之上，这个题目真正想考察的是集合体系的结构位置与两种数据组织的访问模型差异。本文补全体系图、复杂度对比、以及”什么时候该把 List 换成 Map”的重构信号。

体系位置：Map 不在 Collection 里

Java 集合体系是两棵独立的树：

  • Collection（单值容器）→ List / Set / Queue
  • Map（键值容器）→ HashMap / TreeMap / LinkedHashMap / ConcurrentHashMap

Map 不继承 Collection，因为它存储的是**entry（键值对）**而非单一元素；它的 values()、keySet()、entrySet() 三个视图才返回 Collection。理解这一点能解释很多 API 形态：遍历 Map 必须选一个视图，增强 for 不能直接遍历 Map 本身。

访问模型：位置 vs 键

  • List 按位置访问：get(i) 是”第 i 个”，语义依赖顺序；ArrayList O(1)、LinkedList O(n)
  • Map 按键访问：get(k) 是”键为 k 的那条”，语义依赖键的唯一性；HashMap O(1)、TreeMap O(logN)

这决定了二者的适用问题域：List 回答”序列里有什么、第几个是什么”，Map 回答”某个标识对应的值是什么”。用 List 存”按 ID 查”的数据、然后线性扫描，是最典型的结构误用。

实现类速览与选型

List 侧：

  • ArrayList：动态数组，默认选择；扩容 1.5 倍，尾部摊销 O(1)
  • LinkedList：双向链表，头尾操作与迭代器删除友好；随机访问差、节点内存开销大
  • Vector：全方法同步的遗留类，新代码不用

Map 侧：

  • HashMap：无序、O(1)，键需正确实现 equals/hashCode；非线程安全
  • LinkedHashMap：插入序（accessOrder=true 时可做 LRU），比 HashMap 多一条链表
  • TreeMap：红黑树，键排序、范围查询（subMap/headMap），O(logN)
  • Hashtable：遗留同步类；并发用 ConcurrentHashMap
  • ConcurrentHashMap：桶级锁+CAS，并发唯一推荐

重构信号：List 该换 Map 的时刻

  • 循环中 list.stream().filter(x -> x.getId().equals(id)) 反复出现 → 建 Map<Id, X> 索引，O(n) 查询变 O(1)
  • 两个 List 按某字段关联（join）→ 先把一侧转 Map，避免 O(n×m)
  • 计数/分组统计 → Map<Key, Integer> 或 groupingBy，而非 List 手动累加
  • 去重 → Set/Map.keySet，而非 List.contains

反过来，Map 不能替代 List 的场景：需要顺序遍历输出、需要重复元素、需要位置语义（分页切片 subList）。

复杂度对照

操作 ArrayList LinkedList HashMap TreeMap
按位置/键取 O(1) O(n) O(1) O(logN)
尾部/任意增 摊销 O(1)/O(n) O(1)(持迭代器) O(1) O(logN)
判含/按键查 O(n) O(n) O(1) O(logN)
有序遍历 插入序 插入序 无（LinkedHashMap 插入序） 键排序

List 与 Map 的区别，结构上是 Collection 与独立体系的分野，语义上是位置索引与键索引两种访问模型的分野。选型时先问”我按什么找数据”：按顺序位置找选 List，按唯一标识找选 Map——答案通常在这一问里就确定了。