集合 | veyliss

Java 集合底层：List、Set、HashMap 与红黑树

2024年6月11日 · 约 12 分钟阅读

Java 集合面试题经常会从一个很小的问题开始：

List 和 Set 有什么区别？

如果继续追问，很快就会进入 HashMap、HashSet、TreeSet、红黑树、哈希冲突、扩容、equals() 和 hashCode() 这些内容。

这篇文章把几份旧笔记整理成一条完整的复习线：先看集合接口，再看哈希表，最后看树结构。

一、List 和 Set 的区别

List 和 Set 都继承自 Collection 接口，都属于 Java 集合体系中存放单个元素的容器。

它们的核心区别可以从三个角度理解。

是否允许重复

List 允许重复元素：

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

System.out.println(list.size()); // 2

Set 不允许重复元素：

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

System.out.println(set.size()); // 1

需要注意的是，Set 判断重复通常依赖 equals() 和 hashCode()。如果自定义对象放入 HashSet，却没有正确重写这两个方法，就可能出现“看起来相同的对象却没有去重”的问题。

是否保持插入顺序

List 按插入顺序保存元素，可以通过下标访问：

list.get(0);

Set 不一定保持插入顺序，也不能通过下标访问元素。

不同 Set 实现的顺序语义也不同：

HashSet：不保证插入顺序，也不保证排序。
LinkedHashSet：按插入顺序迭代。
TreeSet：按自然顺序或比较器规则排序。

所以不能简单说“Set 会升序排序”。准确说法是：TreeSet 会排序，HashSet 不保证顺序。

查询、插入和删除特点

List 更像动态数组或链表，具体性能取决于实现类。

ArrayList 的特点：

按下标访问快，时间复杂度通常是 O(1)。
中间插入和删除可能需要移动元素，时间复杂度通常是 O(n)。

LinkedList 的特点：

插入和删除节点时，只需要调整节点引用。
但查找指定位置的元素需要遍历链表。

Set 更强调“唯一性”。例如 HashSet 底层依赖哈希表，添加、删除、查找在理想情况下可以接近 O(1)。

二、Collection 常见方法

Collection 是 List、Set 等集合接口的上层接口，常见方法包括：

boolean add(E e);
boolean remove(Object o);
boolean contains(Object o);
boolean isEmpty();
int size();
void clear();
Iterator<E> iterator();
Object[] toArray();

有一个细节很容易忽略：Collection 本身没有 get(index) 方法。

因为不是所有集合都有下标语义。例如 List 可以按下标取值，但 Set 没有稳定的下标概念，只能通过迭代器遍历：

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

三、哈希表是什么

哈希表也叫散列表，是一种非常重要的数据结构。很多缓存、字典、索引、去重结构的核心思想，都是在内存中维护一张哈希表。

哈希表的核心公式可以理解为：

存储位置 = f(关键字)

这里的 f 就是哈希函数。它会根据 key 计算出一个哈希值，再根据数组长度换算成数组下标。

理想情况下，哈希表的查询过程是：

key -> hash -> 数组下标 -> 找到元素

如果没有哈希冲突，查找、插入、删除都可以接近 O(1)。

和其他结构对比：

数组：按下标访问快，按值查找通常需要遍历。
链表：插入删除节点方便，但查找需要遍历。
平衡二叉搜索树：查找、插入、删除通常是 O(log n)。
哈希表：理想情况下查找、插入、删除接近 O(1)。

不过哈希表的性能高度依赖哈希函数、数组容量、负载因子和冲突处理方式。

四、哈希冲突怎么解决

哈希冲突指的是：不同 key 经过哈希计算后，落到了同一个数组位置。

例如：

keyA -> index 3
keyB -> index 3

这时就需要处理冲突。

常见方式有三类：

开放地址法：当前位置冲突后，继续寻找下一个可用位置。
再哈希法：使用另一个哈希函数重新计算位置。
链地址法：数组每个位置挂一个链表或树，把冲突元素放到同一个桶里。

Java HashMap 使用的就是链地址法的思路。更准确地说，在 Java 8 之后，HashMap 的桶结构可能是：

数组 + 链表
数组 + 红黑树

当同一个桶里的元素过多时，链表会在满足条件后树化，变成红黑树，以降低极端冲突下的查询成本。

五、HashMap 的底层结构

HashMap 存储的是 key-value 键值对。

可以把它简化理解成：

HashMap
  table 数组
    bucket 0 -> null
    bucket 1 -> Node -> Node
    bucket 2 -> Node
    bucket 3 -> TreeNode 红黑树

每个节点大致保存：

hash
key
value
next

put 一个元素时，大致过程是：

计算 key 的 hash。
根据 hash 和数组长度计算桶下标。
如果桶为空，直接放入。
如果桶不为空，判断 key 是否已经存在。
如果 key 已存在，更新 value。
如果 key 不存在，挂到链表或红黑树中。
如果元素数量超过阈值，触发扩容。

六、HashMap 的初始容量和负载因子

HashMap 有两个重要参数：

initialCapacity 初始容量
loadFactor 负载因子

常见默认值是：

initialCapacity = 16
loadFactor = 0.75

阈值计算方式可以理解为：

threshold = capacity * loadFactor

默认情况下：

16 * 0.75 = 12

当元素数量超过阈值后，HashMap 会扩容。扩容通常会带来重新分布元素的成本，所以如果能预估数据量，创建 HashMap 时可以指定合适的初始容量。

七、HashMap 的扩容机制

HashMap 的扩容通常发生在元素数量超过阈值之后：

size > threshold

而阈值由容量和负载因子决定：

threshold = capacity * loadFactor

默认情况下：

capacity = 16
loadFactor = 0.75
threshold = 12

也就是说，当第 13 个元素放入时，HashMap 就可能触发扩容。

扩容的核心动作可以概括成三步：

创建一个更大的新数组。
把旧数组中的节点迁移到新数组。
重新计算扩容后的阈值。

通常情况下，新容量会变成旧容量的 2 倍：

oldCapacity = 16
newCapacity = 32

新阈值也会随之变化：

oldThreshold = 16 * 0.75 = 12
newThreshold = 32 * 0.75 = 24

扩容时元素怎么迁移

在 Java 8 之后，HashMap 扩容迁移时有一个很重要的规律：

元素的新位置要么是原位置，要么是原位置 + oldCapacity

例如旧数组长度是 16，某个元素原来在下标 5：

旧位置：5
新位置：5 或 5 + 16 = 21

为什么会这样？因为数组长度翻倍后，参与下标计算的二进制位多了一位。只需要看 hash 在这一位上是 0 还是 1：

hash & oldCapacity == 0  -> 留在原位置
hash & oldCapacity != 0  -> 移到原位置 + oldCapacity

可以用一个简化例子理解：

旧容量 16：下标范围 0 ~ 15
新容量 32：下标范围 0 ~ 31

原 bucket 5 拆成：
  bucket 5
  bucket 21

这也是 HashMap 容量使用 2 的次幂的一个好处：扩容后不需要完全重新计算每个元素的位置，可以通过位运算快速拆分旧桶。

扩容和链表树化的关系

Java 8 之后，HashMap 桶内链表过长时可能会树化为红黑树，但并不是链表一长就立刻树化。

常见条件可以记成：

桶内链表长度 >= 8
数组容量 >= 64

如果桶内链表已经很长，但数组容量还比较小，HashMap 通常会优先扩容，而不是马上树化。

原因也很直观：容量太小时，冲突可能只是数组太小导致的。先扩容可以让元素重新分布，很多冲突自然会减少。

面试里可以这样总结：

HashMap 默认容量是 16，负载因子是 0.75，超过阈值后通常扩容为原来的 2 倍。Java 8 扩容迁移时，元素的新位置要么保持原下标，要么移动到原下标加旧容量。桶内链表过长时可能树化，但容量较小时会优先扩容。

八、为什么 HashMap 容量常用 2 的次幂

HashMap 的数组长度通常会调整为 2 的次幂。

这样做的一个重要原因是可以用位运算快速计算下标：

index = (n - 1) & hash;

当 n 是 2 的次幂时，n - 1 的二进制低位全是 1，可以更好地利用 hash 的低位信息。

扩容时也有一个好处：元素的新位置通常只有两种可能：

原位置
原位置 + oldCapacity

这可以减少扩容后重新计算和移动元素的成本。

九、equals 和 hashCode 为什么要一起重写

在 HashMap、HashSet 这类哈希结构里，hashCode() 决定元素大致落在哪个桶，equals() 决定桶内元素是否真的相等。

如果两个对象通过 equals() 判断相等，它们的 hashCode() 必须相等。

错误示例：

class User {
    private Long id;

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof User other)) return false;
        return Objects.equals(this.id, other.id);
    }
}

这个类只重写了 equals()，没有重写 hashCode()。放进 HashSet 时，相同 id 的对象可能因为 hash 不同，被放到不同桶里，导致去重失败。

正确做法：

class User {
    private Long id;

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof User other)) return false;
        return Objects.equals(this.id, other.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

面试里可以总结成一句话：

只要重写 equals()，通常就必须重写 hashCode()，否则哈希集合和哈希映射可能出现行为异常。

十、HashSet 的底层原理

HashSet 的底层主要依赖 HashMap。

可以粗略理解成：

HashSet<E>
  内部维护 HashMap<E, Object>

HashSet 添加元素时，本质上是把元素作为 HashMap 的 key 存进去：

map.put(element, PRESENT);

因为 HashMap 的 key 不能重复，所以 HashSet 就天然具备了去重能力。

因此，HashSet 的几个特点可以这样理解：

不允许重复元素。
不保证插入顺序。
底层依赖 hashCode() 和 equals() 判断重复。
查询、插入、删除在理想情况下接近 O(1)。

如果需要保持插入顺序，可以使用 LinkedHashSet。如果需要排序，可以使用 TreeSet。

十一、二叉树、二叉搜索树和平衡二叉树

普通二叉树只限制每个节点最多有两个子节点，本身不要求元素大小关系。

二叉搜索树、退化树和四种平衡旋转示意图

二叉搜索树则有明确规则：

左子树节点 < 当前节点 < 右子树节点

例如下面这棵树就是一棵二叉搜索树：

          8
        /   \
       4     12
      / \    / \
     2   6  10  14

每个节点都满足：

左边比自己小，右边比自己大

插入时：

比当前节点小，放左边。
比当前节点大，放右边。
如果不允许重复，相等元素不再插入。

二叉搜索树的中序遍历可以得到升序结果：

左 -> 根 -> 右

以上面这棵树为例，中序遍历结果是：

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14

但普通二叉搜索树有一个问题：如果插入数据本身接近有序，就可能退化成链表。

例如连续插入：

1, 2, 3, 4, 5

树可能长成这样：

这时查找复杂度会从 O(log n) 退化到 O(n)。

平衡二叉树就是为了解决这个问题。它要求任意节点左右子树高度差不能过大，常见规则是高度差不超过 1。插入或删除节点后，如果树失衡，就通过旋转恢复平衡。

常见失衡情况可以先记四种：

左左：一次右旋。
左右：先局部左旋，再整体右旋。
右右：一次左旋。
右左：先局部右旋，再整体左旋。

左左失衡，做一次右旋：

右右失衡，做一次左旋：

左右失衡，先对左子树左旋，再对整体右旋：

右左失衡，先对右子树右旋，再对整体左旋：

这几张图可以帮助记忆：哪边重，就先看它是不是同方向；同方向一次旋转，折线方向两次旋转。

十二、红黑树和 TreeSet

红黑树是一种自平衡二叉搜索树。

它不像严格平衡二叉树那样要求左右高度差非常精确，而是通过节点颜色和一组规则，让树保持“大致平衡”。

可以简单理解为：

红黑树 = 带颜色规则的二叉搜索树

它的目标是避免树退化成链表，使查找、插入、删除都能保持在 O(log n) 级别。

Java 中：

TreeMap 底层是红黑树。
TreeSet 底层通常基于 TreeMap。
HashMap 在桶内链表过长时，也可能把链表树化成红黑树。

TreeSet 的特点：

元素不能重复。
不保留插入顺序。
会按照自然顺序或自定义比较器排序。
线程不安全。

示例：

Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);

System.out.println(set); // [1, 2, 3]

如果放入自定义对象，需要让对象实现 Comparable，或者创建 TreeSet 时传入 Comparator。

十三、面试回答思路

如果面试官问 HashMap 原理，可以这样答：

HashMap 底层是数组加链表或红黑树。put 时先计算 key 的 hash，再通过数组长度计算桶下标。如果没有冲突直接放入；如果有冲突，就在桶内链表或红黑树中比较 key。默认初始容量是 16，负载因子是 0.75，超过阈值会扩容。Java 8 之后，当桶内链表过长并且数组容量满足条件时，链表会树化成红黑树，以优化极端冲突下的查询性能。

如果问 HashSet 原理，可以这样答：

HashSet 底层依赖 HashMap，元素作为 HashMap 的 key 保存，value 使用一个固定占位对象。因此 HashSet 不允许重复元素，去重依赖 hashCode() 和 equals()。

如果问 List 和 Set 区别，可以这样答：

List 有序、可重复、可按下标访问；Set 不允许重复，通常不能按下标访问。HashSet 不保证顺序，LinkedHashSet 保持插入顺序，TreeSet 按比较规则排序。

如果问 TreeSet 原理，可以这样答：

TreeSet 底层基于红黑树，元素不能重复，并按自然顺序或比较器排序。它不保留插入顺序，查找、插入、删除通常是 O(log n)。

十四、小结

这几个知识点可以串成一张图：

Collection
  ├── List
  │   ├── ArrayList
  │   └── LinkedList
  │
  └── Set
      ├── HashSet       -> HashMap -> 哈希表
      ├── LinkedHashSet -> HashMap + 链表顺序
      └── TreeSet       -> TreeMap -> 红黑树

Map
  ├── HashMap -> 数组 + 链表 + 红黑树
  └── TreeMap -> 红黑树

复习时不要只背结论，而要抓住底层结构：

List 关注顺序和下标。
Set 关注唯一性。
HashMap 关注哈希、冲突、扩容和树化。
HashSet 关注 HashMap 的 key 去重。
TreeSet 和 TreeMap 关注红黑树排序。

这样从使用层一路讲到底层结构，面试回答会更完整。