Java常用集合框架类库与List、Map

选择关键看操作模式：随机访问多用ArrayList（O(1)），中间增删多用LinkedList（O(1)插入删除）；误用是用for循环遍历LinkedList导致O(n²)。

ArrayList 和 LinkedList 的选择关键看操作模式

不是“ArrayList 更快所以默认用它”，而是得看你的主要操作是随机访问多，还是频繁在中间增删多。ArrayList 底层是数组，get(i) 是 O(1)，但 add(index, e) 或 remove(index) 在中间位置会触发数组拷贝，平均 O(n)；LinkedList 是双向链表，按索引查元素要从头或尾遍历，get(i) 是 O(n)，但 addFirst、addLast、以及已有 ListIterator 时的插入/删除都是 O(1)。

常见误用：for (int i = 0; i 配合 LinkedList —— 这会变成 O(n²)。改用增强 for 循环或迭代器即可避免。

• 读多写少、需要下标快速访问 → 选 ArrayList
• 高频头/尾插入、已有迭代器且需边遍历边删 → LinkedList 仍有价值（但注意 JDK 21+ 中 SequencedCollection 接口让 ArrayList 也支持高效头插语义）
• 别为了“看起来更通用”而声明为 LinkedList 却只用 add(e) 和 get(i)

HashMap 的线程不安全体现在哪？ConcurrentHashMap 怎么规避

HashMap 在多线程 put 时可能触发扩容重哈希，若两个线程同时判断需扩容、又同时执行 transfer()（JDK 7）或 split()（JDK 8），会导致链表成环（JDK 7）或数据丢失（JDK 8+）。这不是“偶尔错”，而是明确未定义行为，get() 可能死循环或返回 null。

ConcurrentHashMap 不是简单加锁整张表：JDK 7 用分段锁（Segment 数组），JDK 8 改为 CAS + synchronized 控制单个桶

（Node 链表头或红黑树根），写操作只锁必要范围，读操作完全无锁。

• 只要没显式要求强一致性（如“所有线程立刻看到最新值”），ConcurrentHashMap 比 Collections.synchronizedMap(new HashMap()) 并发吞吐高得多
• computeIfAbsent() 是原子的，适合缓存场景；但 map.get(key) == null ? map.put(key, compute()) : map.get(key) 是经典竞态，必须换用原子方法
• size() 在并发下是弱一致的（可能滞后），如需精确计数，考虑 mappingCount()（返回 long，更准确）

ArrayList.subList() 返回的是视图，不是新集合

subList(fromIndex, toIndex) 返回的是原 ArrayList 的一个动态视图，底层共享同一份 elementData 数组。对子列表的结构性修改（如 add()、clear()）会直接影响原列表，反之亦然。

ArrayList list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
List sub = list.subList(1, 3); // ["b", "c"]
sub.add("x"); // list 变成 ["a", "b", "c", "x", "d"]
list.remove(0); // sub 变成 ["c", "x", "d"] —— 注意 sub.size() 现在是 3！

• 需要独立副本？显式构造：new ArrayList(list.subList(from, to))
• 传给不可信 API 时尤其危险：对方调 clear() 会清空你原列表的一部分
• 子列表的 indexOf()、contains() 正常工作，但 retainAll() 这类结构性操作要格外小心

Map 接口里 keySet()、values()、entrySet() 的性能与用途差异

三者都返回视图，不复制数据，但迭代成本不同：entrySet() 是最高效的遍历方式，一次拿到 key 和 value；keySet() 迭代后若还需取 value，每次 map.get(key) 是额外哈希查找；values() 无法反查 key，且某些 Map 实现（如 IdentityHashMap）的 values 视图甚至不保证顺序或唯一性。

典型低效写法：for (String key : map.keySet()) { String value = map.get(key); ... } —— 多了一倍哈希计算。

• 只关心 key？用 keySet()
• 只关心 value？用 values()，但注意它不支持 remove()（除非是 LinkedHashMap 的 values 视图）
• 要同时用 key 和 value？必须用 entrySet()，且优先用 Map.Entry::getKey 和 Map.Entry::getValue
• HashMap 的 values() 视图在并发修改时可能抛 ConcurrentModificationException，和 keySet/entrySet 一样

实际项目里最容易被忽略的，是 subList() 的视图语义和 entrySet() 的遍历必要性——它们不报错，但会在数据规模上去后突然暴露性能或逻辑问题。