List、Set、Map 集合知识点

List：有序可重复，有索引 ArrayList、LinkedList、Vector

Set：无序不可重复，无索引 HashSet、LinkedHashSet、TreeSet

Map：键值对<K,V>，键唯一，值可重复 HashMap、LinkedHashMap、TreeMap ConcurrentHashMap、Hashtable

一、List 系列（有序、可重复、带下标）

1. ArrayList

1. 底层：Object [] 动态数组，默认容量 10
2. 扩容：原容量 1.5 倍，old + old>>1
3. 特点：
   • 查询快（下标随机访问 O (1)）、增删末尾快、中间插入删除慢（数组移位）
   • 线程不安全，多线程并发添加会数组越界、数据丢失
   • 允许 null 元素
4. 适用：大量查询、少量增删

2. LinkedList

1. 底层双向链表 Node，无扩容，按需创建节点
2. 特点：
   • 随机查询慢 O (n)、首尾增删快 O (1)，中间增删慢
   • 实现 Deque，可做队列、栈
   • 线程不安全
3. 适用：频繁头尾增删

3. Vector（淘汰）

• 底层数组，扩容 2 倍，所有方法加 synchronized，线程安全，效率极低，基本不用。

List 通用考点

1. Arrays.asList()返回固定长度集合，不能 add/remove
2. 遍历：for 下标遍历、增强 for、Iterator；遍历中用集合 add/remove 会并发修改异常ConcurrentModificationException，要用迭代器自身 remove
3. 排序：Collections.sort()，自定义对象重写 Comparable 或传 Comparator

二、Set 系列（不可重复，无索引）

1. HashSet

1. 底层 HashMap，元素作为 key，value 是静态 Object 占位
2. 去重规则：hashCode()→equals()
   • hash 不同：直接存；hash 相同，equals 不同→链表 / 红黑树；equals 相同→重复丢弃
3. 无序、只允许一个 null、线程不安全
4. 自定义实体存入必须重写hashCode+equals，否则无法去重

坑：存入后修改对象属性→hash 变，remove 删不掉，数据遗留

2. LinkedHashSet

• 继承 HashSet，底层 LinkedHashMap
• 插入有序 + 去重，链表维护插入顺序，性能略低于 HashSet

3. TreeSet

• 底层 TreeMap（红黑树），自动排序 + 去重，不能存 null
• 不靠 hashCode/equals，靠比较器：
  1. 自然排序：元素实现Comparable
  2. 构造传入Comparator定制排序（优先级更高）
• compare 返回 0 = 判定元素重复；增删查 O (logn)

Set 选型

• 只去重无序：HashSet
• 去重 + 插入有序：LinkedHashSet
• 去重 + 自动排序：TreeSet

三、Map 系列（键 K 唯一，值 V 可重复，键值对存储）

1. HashMap（重中之重 JDK7 vs JDK8）

JDK1.7：数组 + 单向链表

• 默认容量 16，负载因子 0.75，扩容 2 倍
• 头插法扩容，并发扩容链表死循环，线程不安全

JDK1.8：数组 + 链表 + 红黑树

1. 链表长度＞8 转红黑树；树节点＜6 退回链表
2. 尾插法，解决死链问题
3. hash=(key.hashCode() ^ (hash>>>16)) & (len-1)扰动算法减少哈希碰撞
4. key 可为 null（null 固定存在下标 0），value 任意 null
5. 负载因子 0.75：平衡空间与查询效率

常用方法

put()、get()、remove()、containsKey()、putIfAbsent()遍历三种：keySet、entrySet、values

2. LinkedHashMap

• HashMap + 双向链表，插入有序，可开启 LRU 最近最少淘汰（重写 removeEldestEntry）

3. TreeMap

• 红黑树，key 自动排序，key 必须实现 Comparable 或构造传 Comparator，key 不能 null

4. Hashtable（过时）

• 方法全synchronized，锁整张表，效率差；key、value 都不能 null

5. ConcurrentHashMap（线程安全 Map）

JDK7：Segment 分段锁

• Segment 数组 (默认 16 段)，每段继承 ReentrantLock，分段上锁，并发度 16

JDK8：CAS + synchronized 锁桶头

1. 空桶 CAS 插入；已有数据锁住当前桶首 Node，锁桶不锁整张表
2. get 无锁，依靠 volatile 保证可见性
3. sizeCtl 控制初始化、扩容；多线程协助扩容 transfer
4. putIfAbsent/computeIfAbsent原子方法，替代 if+put 非原子代码

Map 选型

• 单线程无序：HashMap
• 单线程插入有序：LinkedHashMap
• 需要 key 排序：TreeMap
• 多线程安全：ConcurrentHashMap

四、List/Set/Map 对比总结