掌握 List、Set、Map 的核心原理和使用场景
集合框架是 Java 开发的基础，也是面试的高频考点。本篇系统梳理集合的底层实现和常见陷阱。
本篇重点围绕集合框架的核心知识，帮助你系统掌握：
// ArrayList：基于数组
List arrayList = new ArrayList<>();
arrayList.get(0); // O(1) 快速访问
arrayList.add(0, "item"); // O(n) 需要移动元素
// LinkedList：基于链表
List linkedList = new LinkedList<>();
linkedList.get(0); // O(n) 需要遍历
linkedList.addFirst("item"); // O(1) 快速插入 使用场景：
底层结构：数组 + 链表 + 红黑树（JDK 1.8+）
JDK 1.8 优化：
// put 流程
public V put(K key, V value) {
// 1. 计算 hash 值
int hash = hash(key);
// 2. 定位桶位置
int index = (n - 1) & hash;
// 3. 如果桶为空，直接插入
if (table[index] == null) {
table[index] = new Node(key, value);
}
// 4. 如果桶不为空，处理冲突
else {
// 链表或红黑树插入
}
// 5. 检查是否需要扩容
if (++size > threshold) {
resize();
}
}扩容时机：当元素数量超过 容量 × 负载因子 时触发扩容。
// 扩容示例
HashMap map = new HashMap<>();
// 初始容量 16，阈值 16 * 0.75 = 12
// 当添加第 13 个元素时，触发扩容到 32
// 指定初始容量（推荐）
HashMap map = new HashMap<>(100);
// 实际容量会是大于等于 100 的最小 2 的幂次，即 128 扩容过程：
JDK 1.7：分段锁（Segment）
JDK 1.8：CAS + synchronized
// JDK 1.8 put 流程
public V put(K key, V value) {
for (Node[] tab = table;;) {
// 1. 如果桶为空，CAS 插入
if (tabAt(tab, i) == null) {
if (casTabAt(tab, i, null, new Node(key, value)))
break;
}
// 2. 如果桶不为空，synchronized 锁住桶头
else {
synchronized (f) {
// 链表或红黑树插入
}
}
}
} 优势：
底层实现：HashSet 内部使用 HashMap 实现。
public class HashSet {
private transient HashMap map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
} // HashMap：允许 null
Map hashMap = new HashMap<>();
hashMap.put(null, "value"); // OK
hashMap.put("key", null); // OK
// Hashtable：不允许 null
Map hashtable = new Hashtable<>();
hashtable.put(null, "value"); // NullPointerException
hashtable.put("key", null); // NullPointerException 三种方案：
// 方案1：使用 ConcurrentHashMap（推荐）
Map map = new ConcurrentHashMap<>();
// 方案2：使用 Collections.synchronizedMap
Map map = Collections.synchronizedMap(new HashMap<>());
// 方案3：使用 Hashtable（不推荐，已过时）
Map map = new Hashtable<>(); 性能对比：
扩容规则：每次扩容为原容量的 1.5 倍。
// ArrayList 扩容源码
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 使用示例
List list = new ArrayList<>(); // 初始容量 0
list.add("a"); // 扩容到 10
// 添加到第 11 个元素时，扩容到 15
// 添加到第 16 个元素时，扩容到 22 new ArrayList<>(100)四种方案：
// 方案1：Vector（不推荐，已过时）
List list = new Vector<>();
// 方案2：Collections.synchronizedList
List list = Collections.synchronizedList(new ArrayList<>());
// 方案3：CopyOnWriteArrayList（推荐，读多写少）
List list = new CopyOnWriteArrayList<>();
// 方案4：手动加锁
List list = new ArrayList<>();
synchronized (list) {
list.add("item");
} CopyOnWriteArrayList 原理：
红黑树 vs AVL 树：
选择红黑树的原因：
Map map = new HashMap<>();
// 方式1：entrySet（推荐，性能最好）
for (Map.Entry entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
}
// 方式2：keySet（需要 key 和 value 时不推荐）
for (String key : map.keySet()) {
Integer value = map.get(key); // 额外的查询开销
}
// 方式3：values（只需要 value 时使用）
for (Integer value : map.values()) {
// 只能获取 value
}
// 方式4：forEach（JDK 8+，简洁）
map.forEach((key, value) -> {
System.out.println(key + ": " + value);
});
// 方式5：Stream API（JDK 8+，功能强大）
map.entrySet().stream()
.filter(e -> e.getValue() > 10)
.forEach(e -> System.out.println(e.getKey())); 性能对比：
fail-fast（快速失败）：遍历时检测到修改，立即抛出 ConcurrentModificationException。
// fail-fast 示例
List list = new ArrayList<>(Arrays.asList("a", "b", "c"));
for (String item : list) {
list.remove(item); // ConcurrentModificationException
} fail-safe（安全失败）：遍历时操作副本，不会抛异常，但可能看不到最新数据。
// fail-safe 示例
List list = new CopyOnWriteArrayList<>(Arrays.asList("a", "b", "c"));
for (String item : list) {
list.remove(item); // 不会抛异常
} List list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
// 错误方式1：for-each 中删除
for (String item : list) {
if (item.equals("b")) {
list.remove(item); // ConcurrentModificationException
}
}
// 错误方式2：普通 for 循环删除（会漏删）
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("b")) {
list.remove(i); // 删除后，后面的元素前移，导致漏删
}
}
// 正确方式1：Iterator.remove()
Iterator it = list.iterator();
while (it.hasNext()) {
String item = it.next();
if (item.equals("b")) {
it.remove(); // 使用迭代器的 remove
}
}
// 正确方式2：倒序遍历
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i).equals("b")) {
list.remove(i);
}
}
// 正确方式3：removeIf（JDK 8+，推荐）
list.removeIf(item -> item.equals("b"));
// 正确方式4：Stream filter（JDK 8+）
list = list.stream()
.filter(item -> !item.equals("b"))
.collect(Collectors.toList()); // Queue 基本操作（FIFO）
Queue queue = new LinkedList<>();
queue.offer("A"); // 入队，返回 boolean
queue.offer("B");
String first = queue.peek(); // 查看队首，不删除
String polled = queue.poll(); // 出队，删除并返回
// Deque 双端操作
Deque deque = new ArrayDeque<>();
deque.offerFirst("First"); // 头部插入
deque.offerLast("Last"); // 尾部插入
String first = deque.peekFirst(); // 查看头部
String last = deque.peekLast(); // 查看尾部
deque.pollFirst(); // 头部删除
deque.pollLast(); // 尾部删除
// Deque 可以当栈使用（LIFO）
Deque stack = new ArrayDeque<>();
stack.push("A"); // 等价于 addFirst
stack.push("B");
String top = stack.pop(); // 等价于 removeFirst 核心原理：PriorityQueue 基于优先堆（默认小顶堆）实现，保证队首元素始终是最小（或最大）的。
// 默认小顶堆
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
System.out.println(minHeap.poll()); // 2（最小值）
// 大顶堆：自定义比较器
PriorityQueue maxHeap =
new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
System.out.println(maxHeap.poll()); // 8（最大值）
// 对象自定义排序
PriorityQueue taskQueue =
new PriorityQueue<>(Comparator.comparing(Task::getPriority));
class Task {
private String name;
private int priority; // 数字越小优先级越高
public int getPriority() { return priority; }
// getter/setter...
} // Properties 基本用法
Properties props = new Properties();
props.setProperty("db.url", "jdbc:mysql://localhost:3306/test");
props.setProperty("db.username", "root");
props.setProperty("db.password", "123456");
// 从配置文件加载
try (InputStream input = new FileInputStream("config.properties")) {
props.load(input);
}
// 保存到配置文件
try (OutputStream output = new FileOutputStream("config.properties")) {
props.store(output, "Database Configuration");
}
// 获取配置（有默认值）
String url = props.getProperty("db.url", "default_url");
String timeout = props.getProperty("connection.timeout", "5000");
// 遍历所有配置
props.forEach((key, value) ->
System.out.println(key + " = " + value));// 1. 排序操作
List list = Arrays.asList(3, 1, 4, 1, 5);
Collections.sort(list); // 升序排序
Collections.reverse(list); // 反转
Collections.shuffle(list); // 随机打乱
Collections.swap(list, 0, 4); // 交换位置
// 2. 查找操作（需要先排序）
Collections.sort(list);
int index = Collections.binarySearch(list, 4); // 二分查找
Integer max = Collections.max(list); // 最大值
Integer min = Collections.min(list); // 最小值
// 3. 创建特殊集合
List emptyList = Collections.emptyList(); // 不可变空列表
List singletonList = Collections.singletonList("only"); // 单元素列表
List unmodifiableList = Collections.unmodifiableList(new ArrayList<>()); // 不可变列表
// 4. 同步集合（线程安全）
List syncList = Collections.synchronizedList(new ArrayList<>());
Map syncMap = Collections.synchronizedMap(new HashMap<>());
// 5. 频率统计
List words = Arrays.asList("a", "b", "a", "c", "b", "a");
int count = Collections.frequency(words, "a"); // 3
boolean disjoint = Collections.disjoint(list1, list2); // 是否无交集
// 6. 填充和替换
List numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
Collections.fill(numbers, 0); // 全部填充为0
Collections.replaceAll(numbers, 0, 1); // 替换所有0为1
Collections.rotate(numbers, 2); // 向右旋转2位 核心考察点：线程安全集合设计、CopyOnWrite 机制、读写分离思想、并发编程实践。
从设计思想到具体实现的完整分析：
// CopyOnWriteArrayList 核心原理
public class CopyOnWriteArrayList {
private volatile Object[] array;
public E get(int index) {
return (E) array[index]; // 无锁读取
}
public boolean add(E e) {
lock.lock();
try {
Object[] newArr = Arrays.copyOf(array, array.length + 1);
newArr[array.length] = e;
array = newArr; // 原子替换
return true;
} finally { lock.unlock(); }
}
} CopyOnWriteArrayList 特性分析：
// 适用场景：事件监听器管理（读多写少）
List listeners = new CopyOnWriteArrayList<>();
listeners.add(listener); // 偶尔写
for (EventListener l : listeners) l.onEvent(event); // 频繁读 适用场景：
不适用场景：
核心考察点：LRU 算法、LinkedHashMap 原理、数据结构设计、缓存实现思路。
从算法原理到源码分析的完整实现：
// 方式1：基于 LinkedHashMap 实现 LRU 缓存
public class LRUCache extends LinkedHashMap {
private final int maxCapacity;
public LRUCache(int initialCapacity, int maxCapacity) {
super(initialCapacity, 0.75f, true); // accessOrder=true
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > maxCapacity; // 超过容量时删除最老元素
}
// 使用示例
public static void main(String[] args) {
LRUCache cache = new LRUCache<>(16, 3);
cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
System.out.println(cache); // {A=1, B=2, C=3}
cache.get("A"); // 访问 A，A 变为最新
cache.put("D", 4); // 添加 D，最老的 B 被淘汰
System.out.println(cache); // {C=3, A=1, D=4}
}
} // 方式2：手写LRU（HashMap + 双向链表）
class LRUCache {
private Map cache = new HashMap<>();
private Node head, tail;
private int capacity;
public V get(K key) {
Node n = cache.get(key);
if (n == null) return null;
moveToHead(n);
return n.value;
}
public void put(K key, V value) {
Node n = cache.get(key);
if (n != null) { n.value = value; moveToHead(n); }
else {
n = new Node(key, value);
cache.put(key, n);
addToHead(n);
if (cache.size() > capacity) {
cache.remove(tail.prev.key);
removeNode(tail.prev);
}
}
}
} 核心考察点：哈希表实现、线程安全设计、冲突解决、扩容机制、并发优化。
从基础实现到并发优化的完整方案：
// 线程安全HashMap核心实现
class ThreadSafeHashMap {
private Node[] table;
private int size;
public synchronized V put(K key, V value) {
if (size >= table.length * 0.75) resize();
int i = hash(key) % table.length;
for (Node n = table[i]; n != null; n = n.next) {
if (n.key.equals(key)) { n.value = value; return n.value; }
}
table[i] = new Node<>(key, value, table[i]);
size++;
return null;
}
public synchronized V get(K key) {
int i = hash(key) % table.length;
for (Node n = table[i]; n != null; n = n.next) {
if (n.key.equals(key)) return n.value;
}
return null;
}
}
// 分段锁优化（类似JDK7 ConcurrentHashMap）
class SegmentedHashMap {
private Segment[] segments = new Segment[16];
public V put(K key, V value) {
return segments[hash(key) % 16].put(key, value);
}
} 关键技术要点：
核心考察点：限流算法设计、时间窗口控制、高并发处理、精确度优化。
从基础限流到高精度时间窗口的完整实现：
// 滑动窗口限流器
class SlidingWindowRateLimiter {
private Queue requests = new LinkedList<>();
private int maxRequests;
private long windowMillis;
public synchronized boolean allow() {
long now = System.currentTimeMillis();
while (!requests.isEmpty() && now - requests.peek() > windowMillis) {
requests.poll();
}
if (requests.size() < maxRequests) {
requests.offer(now);
return true;
}
return false;
}
}
// 分布式限流（Redis + Lua）
String lua = "redis.call('zremrangebyscore', KEYS[1], '-inf', ARGV[1]) " +
"if redis.call('zcard', KEYS[1]) < tonumber(ARGV[2]) then " +
" redis.call('zadd', KEYS[1], ARGV[3], ARGV[4]); return 1 " +
"else return 0 end";
jedis.eval(lua, 1, key, windowStart, maxReq, now, clientId); 高精度限流关键技术：
核心考察点：缓存设计、LRU 算法、过期机制、并发安全、性能优化。
从基础缓存到功能完善的内存缓存系统：
// 内存缓存：LRU + 过期时间
class MemoryCache {
class Node { K key; V value; long expireTime; Node prev, next; }
private Map cache = new HashMap<>();
private Node head, tail;
private int maxSize;
public synchronized void put(K key, V value, long ttlMs) {
Node n = cache.get(key);
if (n != null) {
n.value = value;
n.expireTime = System.currentTimeMillis() + ttlMs;
moveToHead(n);
} else {
n = new Node(key, value, System.currentTimeMillis() + ttlMs);
if (cache.size() >= maxSize) removeTail();
cache.put(key, n);
addToHead(n);
}
}
public synchronized V get(K key) {
Node n = cache.get(key);
if (n == null) return null;
if (System.currentTimeMillis() > n.expireTime) {
removeNode(n); cache.remove(key); return null;
}
moveToHead(n);
return n.value;
}
} 内存缓存设计要点：