集合框架

Java 集合框架(Collections Framework)提供了一套统一的数据结构接口与实现,核心是 Collection 和 Map 两大体系。

接口层次

Collection 分为 List(有序可重复)与 Set(无序不重复)。List 常用 ArrayList、LinkedList;Set 常用 HashSet、TreeSet。Map 是键值对集合,常用 HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。

ArrayList 与 LinkedList

ArrayList 底层为动态数组,随机访问 O(1),尾部插入均摊 O(1),中间插入需要搬移元素。LinkedList 底层为双向链表,插入删除 O(1),但随机访问需要遍历。多数场景下 ArrayList 因 CPU 缓存友好而更快。

HashMap 内部结构

JDK 8 起 HashMap 采用数组 + 链表 + 红黑树。键的 hashCode() 经扰动后与数组长度取模定位桶(bucket);若桶中链表长度超过 8 且数组长度 ≥ 64,链表转为红黑树,使最坏查找由 O(n) 降为 O(log n)。扩容时容量翻倍,所有元素需要重新散列。

迭代器与 fail-fast

Iterator 提供统一遍历方式。ArrayList、HashMap 等非线程安全集合的迭代器是 fail-fast 的:遍历过程中若检测到结构性修改(modCount 变化),立刻抛出 ConcurrentModificationException。多线程并发修改应使用 ConcurrentHashMap 或在遍历时加锁。