集合体系结构

Iterable // 可迭代接口，表示可以使用迭代器或增强 for 遍历
└── Collection // 单列集合的根接口，存一个一个的元素
├── List // 有序、可重复、有索引
│ ├── ArrayList // 底层是动态数组，查询快，增删慢
│ ├── LinkedList // 底层是双向链表，增删快，查询慢
│ └── Vector // 老版本动态数组，线程安全，较少使用
├── Set // 无索引、元素不可重复
│ ├── HashSet // 基于哈希表，无序，去重常用
│ │ └── LinkedHashSet// 在 HashSet 基础上维护插入顺序
│ └── TreeSet // 可排序，不可重复，底层是红黑树
└── Queue // 队列，一般用于先进先出
├── LinkedList // 也可作为队列或双端队列使用
├── ArrayDeque // 基于数组的双端队列，效率较高
└── PriorityQueue // 优先队列，按优先级出队，不一定先进先出

Map // 双列集合根接口，存储键值对 key-value
├── HashMap // 基于哈希表，key 无序、不可重复，最常用
│ └── LinkedHashMap // 在 HashMap 基础上维护插入顺序
├── Hashtable // 老版本哈希表，线程安全，不常用了
│ └── Properties // 属性集合，常用于配置文件，key/value 多为字符串
└── TreeMap // 可按 key 排序，底层是红黑树

辨析：Collections和Collection的区别

Collection是Java集合框架中的一个接口，它是所有集合类的基础接口。Collection接口有许多实现类，如List、Set和Queue等。

Collections（注意有一个s）是Java提供的一个工具类，位于java.util包中。它提供了一系列静态方法，用于对集合进行操作和算法。Collections类中的方法包括排序、查找、替换、反转、随机化等等。这些方法可以对实现了Collection接口的集合进行操作，如List和Set。

常见方法：

Collections.sort(list);        // 排序
Collections.reverse(list);     // 反转
Collections.shuffle(list);     // 打乱
Collections.max(list);         // 最大值
Collections.min(list);         // 最小值

1
2
3

Collections.synchronizedList(new ArrayList<>());
Collections.synchronizedSet(new HashSet<>());
Collections.synchronizedMap(new HashMap<>());

作用是给普通集合包装成同步集合。

1
2
3

Collections.unmodifiableList(list);
Collections.unmodifiableSet(set);
Collections.unmodifiableMap(map);

表示返回一个只读视图，不能再直接增删改。

线程安全的集合

在 java.util 包中的线程安全的类主要 2 个，其他都是非线程安全的。

Vector：线程安全的动态数组，其内部方法基本都经过synchronized修饰，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。

Hashtable：线程安全的哈希表，HashTable 的加锁方法是给每个方法加上 synchronized 关键字，这样锁住的是整个 Table 对象，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用，如果要保证线程安全的哈希表，可以用ConcurrentHashMap。

在多线程的情况下，会使用JUC下的并发集合包

List

ArrayList

底层数据结构

ArrayList 底层是 动态数组。

本质是数组
但它能自动扩容
所以看起来比普通数组更灵活

扩容机制

ArrayList 底层数组容量不够时会扩容
一般扩容为 原来的 1.5 倍
扩容会涉及 新建数组 + 拷贝数据
所以如果频繁扩容，会影响性能

面试回答可以这么说：

ArrayList 底层是动态数组，新增元素时如果容量不足，会触发扩容。扩容通常是原容量的 1.5 倍，并把原数组元素复制到新数组中，所以大量插入时最好提前指定初始容量。

查询和增删性能

查询：

按索引查询快
因为数组支持随机访问

增删：

尾部添加通常较快
中间或头部插入、删除较慢
因为会涉及元素移动

结论：

查快，增删中间慢

初始容量

new ArrayList<>() 刚执行时，底层并不会立刻创建一个长度为 10 的数组。

而是先给你一个空数组。

等你第一次 add() 元素时，才真正去创建底层数组，并且这时容量变成 10。

为什么ArrayList是线程不安全的？

ArrayList 线程不安全，因为它的方法没有加锁。

比如 add() 底层大致会做两件事：

1 2	elementData[size] = e; size++;

这两步不是原子操作。
如果多个线程同时执行，可能会：

写到同一个位置，导致数据覆盖
size 计算错误
扩容时数据异常

LinkedList

底层数据结构

LinkedList 底层是 双向链表。

特点：

每个节点保存数据
还保存前驱、后继引用

查询和增删性能

查询

按索引查询慢
因为链表不能像数组那样直接定位
需要从前或后逐个找

增删

在已知位置的情况下，插入删除效率高
不需要大量移动元素

结论：

增删快，查询慢

LinkedList 虽然理论上增删快，但如果先要按索引找到位置，查找过程本身也有成本，所以实际使用中未必总比 ArrayList 更快。

LinkedList 还能当什么用

LinkedList 不仅实现了 List，还实现了 Deque，所以还能当：

队列
双端队列
栈

常见方法：

addFirst()
addLast()
removeFirst()
removeLast()

ArrayList 和 LinkedList 的对比

对比项	ArrayList	LinkedList
底层结构	动态数组	双向链表
查询	快	慢
头部/中间插入删除	慢	较快
尾部添加	较快	较快
内存占用	相对少	相对多
适用场景	查询多	增删多

Vector

底层也是数组
线程安全
很多方法带 synchronized
性能一般比 ArrayList 低
现在用得少

`ArrayList` 和 `Vector` 区别

ArrayList 线程不安全，效率高
Vector 线程安全，效率相对低

List常用方法

add(E e)                  // 在集合末尾添加一个元素，添加成功返回 true

add(int index, E element) // 在指定索引位置插入元素，原位置及后面的元素依次后移

get(int index)            // 获取指定索引位置上的元素

set(int index, E element) // 修改指定索引位置上的元素，并返回被替换掉的旧元素

remove(int index)         // 删除指定索引位置上的元素，并返回被删除的元素

remove(Object o)          // 删除集合中第一次出现的指定元素，删除成功返回 true，失败返回 false

size()                    // 返回集合中元素的个数

isEmpty()                 // 判断集合是否为空，为空返回 true，否则返回 false

contains(Object o)        // 判断集合中是否包含指定元素，包含返回 true，否则返回 false

List遍历

普通 for

1
2
3

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

增强 for

1
2
3

for (String s : list) {
    System.out.println(s);
}

注意：

一般不建议在foreach循环中直接修改正在遍历的List元素，因为这可能会导致意外的结果或ConcurrentModificationException异常。在foreach循环中修改元素可能会破坏迭代器的内部状态，因为foreach循环底层是基于迭代器实现的，在遍历过程中修改集合结构，会导致迭代器的预期结构和实际结构不一致。

Iterator

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

ListIterator

这是 List 特有的，面试可能会问。

特点：

可以双向遍历
可以在遍历中修改元素

List排序

1	Collections.sort(list);

或者：

1	list.sort(Comparator.naturalOrder());

常见问题

List 可以重复吗？

可以。

List 有顺序吗？

有，按插入顺序保存。

List 可以通过索引取值吗？

可以。

linkedlist通过get(index) 需要顺着节点找，速度比较慢

List 可以存 null 吗？

通常可以，像 ArrayList 和 LinkedList 都可以。

List和数组的相互转换

数组转 List

用 `Arrays.asList()`

1 2	String[] arr = {"A", "B", "C"}; List<String> list = Arrays.asList(arr);

这是最常见写法
转完后得到的是一个 固定大小的 List
可以改元素，但不能增删

例如：

1
2
3

list.set(0, "X");   // 可以
list.add("D");      // 报异常
list.remove("A");   // 报异常

报的是：

1	UnsupportedOperationException

想要可增删的 List

如果你想转成真正常用的 ArrayList，要再包一层：

1 2	String[] arr = {"A", "B", "C"}; List<String> list = new ArrayList<>(Arrays.asList(arr));

这样就可以正常增删了。

List 转数组

转成 `Object[]`

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

Object[] arr = list.toArray();

返回的是 Object[]
不够精确，实际开发里用得不如下面这种多

转成指定类型数组

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

String[] arr = list.toArray(new String[0]);

得到的就是 String[]。

这是最常见、最标准的写法。

总结

转换方向	写法	特点
数组转 List	`Arrays.asList(arr)`	固定大小，不能增删
数组转可变 List	`new ArrayList<>(Arrays.asList(arr))`	可增删
List 转 Object 数组	`list.toArray()`	返回 `Object[]`
List 转指定类型数组	`list.toArray(new String[0])`	返回指定类型数组

List<>里面填基本数据类型为什么会报错？

List<> 等泛型集合类要求填充的必须是引用类型（对象类型），而不能直接使用基本数据类型（如 int、char、double 等），否则会编译报错。

这么设计的原因是：

泛型的类型擦除机制：Java 泛型在编译后会被擦除为 Object 类型，而 Object 只能接收引用类型，不能接收基本数据类型。

Set

`Set` 的核心特点

元素不可重复
通常没有索引
不能通过下标取值

set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复。当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断是否已经存在相同的元素，如果存在则不会再次插入，保证了元素的唯一性。

Set 常见实现类

HashSet：无序，不重复
LinkedHashSet：有插入顺序，不重复
TreeSet：可排序，不重复

HashSet

特点：

元素不重复
不保证顺序
允许一个 null

底层结构

HashSet 底层其实是基于 HashMap 实现的。

面试里可以说：

HashSet 底层本质上是一个 HashMap，只不过它只用到了 Map 的 key 来存元素，value 是一个固定的占位对象。

HashSet的去重

HashSet 去重依赖两个方法：

hashCode()
equals()

判断流程大致是：

先算对象的 hashCode
根据 hashCode 找存储位置
如果该位置没有元素，直接存
如果该位置有元素，再用 equals() 比较
equals() 为 true，说明重复，不存
equals() 为 false，说明不重复，可以共存

（String/基本类型包装类：已经写好了，直接用。

自定义实体类：同时重写 hashCode 和 equals，否则 HashSet 的去重会失效。）

LinkedHashSet

LinkedHashSet 可以理解成：

HashSet + 链表维护顺序

特点：

元素不可重复
能保持插入顺序
遍历顺序比较稳定

面试里一句话答：

LinkedHashSet 在 HashSet 的基础上增加了链表来维护元素插入顺序，所以既能去重，又能保证遍历顺序和插入顺序一致。

TreeSet

特点

元素不可重复
元素可以排序
默认自然排序，也可以自定义比较器排序

底层结构

底层是 红黑树

去重规则

TreeSet 的去重和 HashSet 不一样。

它主要依赖：

compareTo()或
Comparator.compare()

如果比较结果为：

就认为是重复元素，不会存进去。

所以：

HashSet 去重靠 hashCode + equals
TreeSet 去重靠 比较结果是否为 0

Set 遍历方式

因为 Set 没有索引，所以一般不用普通 for。

常见遍历方式：

增强 for

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");

for (String s : set) {
    System.out.println(s);
}

Iterator

Iterator<String> it = set.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Map

特点

存的是 键值对：key-value
key 不能重复
value 可以重复
一个 key 对应一个 value

Map常用方法

put(K key, V value)      // 添加键值对
get(Object key)          // 根据 key 获取 value
remove(Object key)       // 根据 key 删除
containsKey(Object key)  // 判断是否包含某个 key
containsValue(Object v)  // 判断是否包含某个 value
size()                   // 键值对个数
isEmpty()                // 是否为空
clear()                  // 清空

Map遍历

遍历 key，再取 value

Map<String, Integer> map = new HashMap<>();
for (String key : map.keySet()) {
    System.out.println(key + "=" + map.get(key));
}

遍历 entrySet

这个更推荐。

1
2
3

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

遍历 values

1
2
3

for (Integer value : map.values()) {
    System.out.println(value);
}

面试里最好补一句：

一般遍历 Map 更推荐 entrySet()，因为同时拿 key 和 value 更高效。

方式	遍历内容	能否拿到 key	能否拿到 value
`keySet()`	key 集合	能	能，通过 `get()`
`entrySet()`	键值对	能	能
`values()`	value 集合	不能	能

HashMap

特点

存储 key-value 键值对

key 不能重复

value 可以重复

无序

线程不安全

允许：

一个 null key
多个 null value、

底层数据结构

JDK 7：数组 + 链表

JDK 8 中，HashMap 底层是：

数组 + 链表 + 红黑树

HashMap
└── 数组
├── 桶0 -> 单个节点
├── 桶1 -> 链表
├── 桶2 -> 空
├── 桶3 -> 红黑树
└── …

可以这样理解：

先有一个数组
数组的每个位置叫一个“桶”
不同的 key 经过计算后，会落到数组的某个下标
如果多个元素落到同一个位置，就会形成链表
当链表过长时，为了提高查询效率，链表会转成红黑树

为什么要有红黑树

如果某个桶里的链表太长，查询效率会越来越低。

因为链表查找要一个个比，效率接近：

O(n)

所以在 JDK 8 中，如果链表长度达到一定条件，就会把链表转换成 红黑树（维护成本更高）。

红黑树查找效率更高，大致是：

O(log n)

这样在高冲突情况下，性能会更好。

HashMap 的 put 过程

1	map.put(key, value);

先算 key 的哈希值

HashMap 会先根据 key 算一个哈希值。

你可以先简单理解成：

先把 key 转成一个“更适合定位位置”的数字。

再算数组下标

有了哈希值之后，再结合数组长度，算出这个元素该放到哪个桶。

1	index = (数组长度 - 1) & hash

也就是确定：

放到数组的几号位置

判断这个位置有没有元素

情况一：没有元素

那最简单，直接放进去。

情况二：有元素

说明发生了哈希冲突，不能直接放，要继续判断。

如果有冲突，就比较 key

这时会看：

新 key 和旧 key 是不是同一个 key

判断时主要看：

hash 是否相同
equals() 是否为 true

如果相同

说明是重复 key。

这时不会新增，而是：

用新的 value 覆盖旧的 value

如果不同

说明不是重复 key，只是碰巧落到了同一个位置。

这时就会把新节点挂到链表后面，或者放进树里。

判断是否需要扩容

插入完成后，会检查当前元素个数有没有超过阈值。

如果超过了，就扩容。

比如默认情况下：

初始容量：16
加载因子：0.75
阈值：12

超过 12 之后，可能触发扩容。

为什么 HashMap 的数组长度最好是 2 的幂

HashMap 的数组长度通常设计成 2 的幂，让哈希值更均匀地映射到各个桶中，减少哈希冲突。

HashMap如何判断key相同

和hashset一样，但一个是覆盖一个是不添加

对比项	HashMap	HashSet
判断对象	key	元素本身
判断依据	`hashCode + equals`	`hashCode + equals`
发现重复后	覆盖旧 value	拒绝新增
是否保留旧内容	key 保留，value 更新	原元素保留

HashMap 的扩容机制

默认初始容量：16（底层数组的长度）

默认加载因子：0.75

扩容阈值：容量 × 加载因子

默认阈值：16 × 0.75 = 12（元素个数达到多少时，HashMap 需要考虑扩容）

扩容后容量：通常变成原来的 2 倍

为什么要扩容

让更多元素分散到更多桶里，减少冲突。

扩容时会发生什么

创建一个更大的新数组

比如从 16 创建成 32。

把旧数组中的元素重新放到新数组里

注意这里不是简单复制下标，而是要重新计算位置。

因为数组长度变了，原来的元素在新数组中的桶位置可能也会变。

用新数组替换旧数组

扩容完成后，HashMap 就用新的更大数组来存数据。

扩容和性能的关系

不扩容会怎样

桶太少
冲突变多
链表 / 树更容易变长
查询效率下降

扩容太频繁会怎样

不断新建数组
不断搬迁元素
插入性能受影响

所以 HashMap 的扩容机制，本质上是在做一个平衡：

空间和时间的平衡。

查询时怎么找

假设你要查一个 key：

1	map.get(key);

先算这个 key 的 hash

确定它应该去哪个桶找。

到对应桶里找

如果这个桶里只有一个节点，直接比
如果是链表，就沿链表一个个比
如果是红黑树，就按树的方式查找

找到相同 key

返回它对应的 value。

所以你可以看出：

冲突越严重，桶内结构越复杂，查找成本越高。

红黑树

红黑树 = 一种特殊的二叉搜索树 + 自平衡

二叉搜索树

特点是：

左子树的值比当前节点小
右子树的值比当前节点大

自平衡

如果插入的数据是有序的，树会退化成一个“链表”，导致查询效率从 $O(\log n)$ 崩塌到 $O(n)$。红黑树通过一套复杂的“着色”和“旋转”规则，确保树的高度始终维持在 $O(\log n)$，从而保证了极高的查找、插入和删除效率。

红黑树通过“红黑规则 + 旋转 + 变色”来维持平衡。通过颜色规则，来约束整棵树不要长得太歪。

为什么 HashMap 无序

HashMap 无序，是因为它根据 key 的哈希值计算元素存储位置，底层按桶来组织数据，而不是按插入顺序保存。因此遍历顺序通常不等于插入顺序，扩容后顺序还可能发生变化。如果需要保持插入顺序，可以使用 LinkedHashMap。

为什么 HashMap 线程不安全

HashMap 线程不安全，因为它的 put、remove、resize 等操作都没有加锁，这些操作又不是原子性的。多个线程并发修改同一个 HashMap 时，可能导致数据覆盖、丢失、扩容异常，或者在遍历时触发 ConcurrentModificationException。并发场景下一般使用 ConcurrentHashMap。

HashMap 和 Hashtable 的区别

对比项	HashMap	Hashtable
线程安全	否	是
性能	较高	较低
null key	允许一个	不允许
null value	允许多个	不允许
是否常用	很常用	较少用
并发替代方案	ConcurrentHashMap	一般不优先用

HashMap 和 LinkedHashMap 的区别

对比项	HashMap	LinkedHashMap
顺序	无序	有序
是否保持插入顺序	否	是
底层结构	哈希表	哈希表 + 链表
性能	略高	略低
使用场景	只关心查找	既关心查找又关心顺序

TreeMap

TreeMap 是 Map 的一个实现类，底层基于红黑树，所以它可以按照 key 自动排序。默认情况下使用 key 的自然排序，也可以通过 Comparator 自定义排序规则。TreeMap 判断 key 是否重复不是依赖 hashCode 和 equals，而是依赖比较结果：如果 compareTo 或 compare 返回 0，就认为是同一个 key，并覆盖旧 value。

自定义对象作为 TreeMap 的 key，必须实现 Comparable 或传入 Comparator。

TreeMap 和 HashMap 的区别

对比项	HashMap	TreeMap
底层结构	哈希表	红黑树
顺序	无序	按 key 排序
判断 key 重复	`hashCode + equals`	`compareTo / Comparator`
查询效率	通常快	稳定有序
适用场景	只关心查找	既关心查找又关心排序

自然排序和比较器排序

自然排序：对象自己定义比较规则

比较器排序：外部单独指定比较规则

自然排序是什么

自然排序指的是：

类本身实现 Comparable 接口，并重写 compareTo() 方法。

也就是说，这个类自己就规定好了“比较大小的规则”。

例子

class Student implements Comparable<Student> {
    String name;
    int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Student other) {
        return this.age - other.age;
    }
}

这里表示：

Student 默认按年龄排序

放进 TreeMap 或 TreeSet 时，如果你没有额外传比较器，就会用这个规则。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

这里 Integer 本身就实现了 Comparable，所以会自动按从小到大排。

结果：

1	{1=A, 2=B, 3=C}

比较器排序是什么

比较器排序指的是：

在创建 TreeMap 或 TreeSet 时，传入一个 Comparator 对象，由外部指定比较规则。

也就是说：

类自己不一定要会比
你可以临时告诉它“这次按什么规则排”

例子

TreeMap<Student, String> map = new TreeMap<>(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.age - s2.age;
    }
});

等价于：

1
2
3

TreeMap<Student, String> map = new TreeMap<>(
    (s1, s2) -> s1.age - s2.age
);

这里表示：

这次 TreeMap 按 Student 的年龄排序

如果你想按名字排，也可以改：

1
2
3

TreeMap<Student, String> map = new TreeMap<>(
    (s1, s2) -> s1.name.compareTo(s2.name)
);

对比

对比项	自然排序	比较器排序
接口	`Comparable`	`Comparator`
方法	`compareTo()`	`compare()`
规则位置	类内部	类外部
灵活性	较低	更高
适合场景	默认规则明确	需要多种规则

集合体系结构

线程安全的集合

List

ArrayList

底层数据结构

扩容机制

查询和增删性能

初始容量

为什么ArrayList是线程不安全的？

LinkedList

底层数据结构

查询和增删性能

LinkedList 还能当什么用

ArrayList 和 LinkedList 的对比

Vector

ArrayList 和 Vector 区别

List常用方法

List遍历

普通 for

增强 for

Iterator

ListIterator

List排序

常见问题

List 可以重复吗？

List 有顺序吗？

List 可以通过索引取值吗？

List 可以存 null 吗？

List和数组的相互转换

数组转 List

用 Arrays.asList()

想要可增删的 List

List 转数组

转成 Object[]

转成指定类型数组

总结

List<>里面填基本数据类型为什么会报错？

Set

Set 的核心特点

Set 常见实现类

HashSet

HashSet的去重

LinkedHashSet

TreeSet

Set 遍历方式

Map

特点

Map常用方法

Map遍历

遍历 key，再取 value

遍历 entrySet

遍历 values

HashMap

特点

底层数据结构

为什么要有红黑树

HashMap 的 put 过程

先算 key 的哈希值

再算数组下标

判断这个位置有没有元素

如果有冲突，就比较 key

判断是否需要扩容

为什么 HashMap 的数组长度最好是 2 的幂

HashMap如何判断key相同

HashMap 的扩容机制

为什么要扩容

扩容时会发生什么

扩容和性能的关系

查询时怎么找

红黑树

二叉搜索树

自平衡

为什么 HashMap 无序

为什么 HashMap 线程不安全

HashMap 和 Hashtable 的区别

HashMap 和 LinkedHashMap 的区别

TreeMap

TreeMap 和 HashMap 的区别

自然排序和比较器排序

自然排序是什么

`ArrayList` 和 `Vector` 区别

用 `Arrays.asList()`

转成 `Object[]`

`Set` 的核心特点