3 Java集合框架（List、Set、Map）

问题背景

Java集合框架是面试中最基础、最高频的知识块之一。面试官通常从“ArrayList与LinkedList区别”切入，考察对数据结构、线程安全、扩容机制的理解，并延伸到HashMap原理、红黑树转换、ConcurrentHashMap分段锁等。本章梳理核心接口与实现类的选型对比、底层原理、实战陷阱，帮助你在面试中建立体系化认知。

核心概念

  • Collection：集合根接口，提供add()、remove()、iterator()等通用方法。
  • List：有序可重复，支持索引访问。典型实现：ArrayList（数组）、LinkedList（双向链表）、Vector（线程安全，已很少用）。
  • Set：无序不可重复，基于equals()和hashCode()去重。典型实现：HashSet（哈希表）、TreeSet（红黑树）、LinkedHashSet（哈希表+链表保序）。
  • Map：键值对，键唯一，值可重复。典型实现：HashMap（数组+链表/红黑树）、TreeMap（红黑树）、ConcurrentHashMap（分段锁/CAS）。
Collection 根接口 List 有序可重复 Set 无序不可重复 Map 键值对 常用实现类 ArrayList / HashSet / HashMap

原理机制

3.1 ArrayList 扩容机制

  • 底层 Object[] elementData，默认初始容量 10（懒加载，第一次 add 时创建）。
  • 扩容因子 1.5 倍（oldCapacity + (oldCapacity >> 1)），使用 Arrays.copyOf() 拷贝数组。
  • 如果一次性 addAll 大量元素，会直接扩容至所需最小容量。
面试必问： ArrayList 的 ensureCapacity() 可提前触发扩容，减少后续 add 时的复制开销。

3.2 HashMap 数据结构与哈希冲突

  • JDK 8 中：数组 + 链表 + 红黑树。默认初始容量 16，负载因子 0.75。
  • 链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转红黑树；树节点数 < 6 时退化为链表。
  • 哈希冲突解决：先用 key.hashCode() 扰动（高16位异或），再取模（(n-1) & hash）。
// 扰动函数 (JDK 8)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3.3 线程安全方案对比

方案原理适用场景
Hashtable全表 synchronized遗留系统，不推荐
Collections.synchronizedMap()对象锁包装低并发，简单封装
ConcurrentHashMap (JDK 8)CAS + synchronized + 红黑树高并发首选

流程步骤：集合遍历最佳实践

  1. List 遍历：普通 for 循环（随机访问快）或 Iterator（删除安全）。
  2. Set 遍历：只能用 forEach 或 Iterator，不能按索引。
  3. Map 遍历：用 entrySet() 同时获取 key 和 value，避免重复查 get(key)。
技巧： 使用 Iterator.remove() 删除元素，不要用 list.remove() 在 for-each 中操作，会引发 ConcurrentModificationException。

案例说明

案例1： 使用 HashMap 缓存用户信息，key= userId，value=User对象。注意重写 equals() 和 hashCode()，否则重复 key 无法正常覆盖。

public class User {
    private Long id;
    private String name;
    // 必须重写 equals 和 hashCode（使用 id 字段）
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

案例2： 需要保持插入顺序的 Set → 使用 LinkedHashSet（维护双向链表）；需要按自然排序的 Set → 使用 TreeSet。

表格总结：List、Set、Map 核心实现对比

接口实现类底层结构有序性线程安全适用场景
ListArrayListObject[]是否随机访问、尾部频繁插入
ListLinkedList双向链表是否头部/中间频繁增删
SetHashSetHashMap（key）否否快速去重，无顺序要求
SetTreeSet红黑树按比较器排序否需要自动排序
MapHashMap数组+链表/红黑树否否通用键值存储
MapConcurrentHashMap分段数组+CAS否是高并发无锁读
MapTreeMap红黑树按键排序否需要有序遍历

误区提醒

常见错误：
  • 误以为 Set 就是无序——LinkedHashSet 维护插入顺序，TreeSet 按排序规则有序。
  • 在 HashMap 中修改 key 对象（可变字段）导致哈希值改变，造成无法通过原 key 找到 entry。
  • 混淆 Vector 和 ArrayList —— Vector 的同步方法有性能开销，现在已基本被 CopyOnWriteArrayList 替代。
  • iterator() 遍历时删除元素必须使用 iterator.remove()，否则触发快速失败机制。

实践清单

  • ☐ 能用 ArrayList 时不用 LinkedList（尤其随机访问场景）。
  • ☐ 自定义对象放入 HashSet/HashMap 前，重写 equals() 和 hashCode()。
  • ☐ 多线程环境使用 ConcurrentHashMap 而不是 Hashtable 或 synchronizedMap。
  • ☐ 初始化时预估集合大小，调用 new ArrayList<>(expectedSize) 或 new HashMap<>(expectedSize/0.75f+1) 避免频繁扩容。
  • ☐ 使用 Collections.unmodifiableList() 等返回只读视图，防止集合被意外修改。
← 上一章 📖 返回目录 下一章 →