Java集合进阶——TreeSet、HashMap与工具类

作者：没有四次元口袋的蓝胖
日期：2026-06-15
标签：Java, 集合框架, TreeSet, HashMap, Collections, Arrays

一、TreeSet

1.1 是什么

TreeSet 是 排序的 Set，元素自动按规则排序，且不可重复。

// 默认自然排序（升序）
TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);
set.add(2);
set.add(1);  // 重复，不加
System.out.println(set);  // [1, 2, 3, 5]  自动排序

三大特点：有序（排序）、不可重复、无索引。

1.2 底层结构

TreeSet 底层是 TreeMap，元素存在 key 中，value 统一是一个固定 Object。

// JDK源码（简化）
public class TreeSet<E> implements NavigableSet<E> {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
    
    public TreeSet() {
        m = new TreeMap<>();  // 底层就是TreeMap
    }
    
    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
}

TreeMap 底层是红黑树（自平衡二叉搜索树），所以插入、删除、查找都是 O(log n)。

红黑树示意：

         3(黑)
        /     \
     1(红)    5(红)
       \       /
      2(黑)  4(黑)

中序遍历：1 → 2 → 3 → 4 → 5（升序）

1.3 两种排序方式

方式一：自然排序（Comparable）

元素自身实现 Comparable 接口，定义默认排序规则。

// Integer、String 等内置类已实现 Comparable
// Integer：按数值升序
// String：按字典序升序

// 自定义类实现 Comparable
public class Student implements Comparable<Student> {
    private String name;
    private int age;
    
    @Override
    public int compareTo(Student o) {
        // 先按年龄排，年龄相同按姓名排
        int result = this.age - o.age;
        return result != 0 ? result : this.name.compareTo(o.name);
    }
}

compareTo 返回值规则：

• 返回负数：this 排在 o 前面
• 返回 0：相等（TreeSet 认为是重复元素，不添加）
• 返回正数：this 排在 o 后面

方式二：比较器排序（Comparator）

外部定义排序规则，更灵活，不需要改类本身。

// 构造时传入 Comparator
TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getAge() - s2.getAge();  // 按年龄升序
    }
});

// Lambda 简写
TreeSet<Student> set = new TreeSet<>((s1, s2) -> s1.getAge() - s2.getAge());

两种方式的优先级： Comparator > Comparable。同时存在时用 Comparator。

1.4 自然排序 vs 比较器排序

对比	Comparable	Comparator
定义位置	类内部（implements Comparable）	类外部（new Comparator）
方法	compareTo(T o)	compare(T o1, T o2)
排序规则	只有一种（默认）	可以定义多种
侵入性	需要改类	不需要改类
优先级	低	高

1.5 TreeSet 的特有方法

// 导航方法（利用有序性）
E first()                    // 最小元素
E last()                     // 最大元素
E floor(E e)                 // ≤ e 的最大元素
E ceiling(E e)               // ≥ e 的最小元素
E lower(E e)                 // < e 的最大元素
E higher(E e)                // > e 的最小元素

// 子集
NavigableSet<E> subSet(E from, E to)      // [from, to)
NavigableSet<E> headSet(E to)             // < to
NavigableSet<E> tailSet(E from)           // ≥ from

// 删除
E pollFirst()                 // 删除并返回最小元素
E pollLast()                  // 删除并返回最大元素

TreeSet<Integer> set = new TreeSet<>();
set.add(1); set.add(3); set.add(5); set.add(7); set.add(9);

set.floor(4);    // 3（≤4的最大值）
set.ceiling(4);  // 5（≥4的最小值）
set.lower(5);    // 3（<5的最大值）
set.higher(5);   // 7（>5的最小值）
set.headSet(5);  // [1, 3]（<5的子集）
set.tailSet(5);  // [5, 7, 9]（≥5的子集）

1.6 TreeSet 的坑

坑1：自定义类不实现 Comparable 直接加入 TreeSet → ClassCastException

TreeSet<Student> set = new TreeSet<>();
set.add(new Student("张三", 20));  // 运行时报错！
// Student 没实现 Comparable，TreeSet 不知道怎么排序

解决： 实现 Comparable 或构造时传 Comparator，二选一。

坑2：compareTo 返回 0 的元素被认为是重复的

// 只按年龄排序
public int compareTo(Student o) {
    return this.age - o.age;
}
// 两个年龄相同的 Student 会被认为重复，第二个加不进去！
// 解决：加上第二排序条件（如姓名）

坑3：TreeSet 不允许 null（自然排序时）

TreeSet<String> set = new TreeSet<>();
set.add(null);  // NullPointerException！
// 因为 null 无法调用 compareTo

// HashSet 可以存 null（最多一个）

---

二、HashMap

2.1 是什么

HashMap 是 键值对存储结构，key 不可重复，value 可以重复，根据 key 的 hashCode 快速定位。

HashMap<String, Integer> map = new HashMap<>();
map.put("张三", 90);
map.put("李四", 85);
map.put("张三", 95);  // key重复，覆盖旧值
System.out.println(map);  // {张三=95, 李四=85}
System.out.println(map.get("张三"));  // 95

2.2 底层结构（JDK 8）

数组 + 链表 + 红黑树

HashMap 内部结构：

  数组（默认容量16）
  ┌─────┐
0 │ null│
  ├─────┤
1 │  →  │ → Node("李四",85) → Node("王五",70)   ← 链表
  ├─────┤
2 │ null│
  ├─────┤
3 │  →  │ → TreeNode("张三",95)                  ← 红黑树
  ├─────┤
4 │ null│
  └─────┘

JDK 7 vs JDK 8 的区别：

特性	JDK 7	JDK 8
结构	数组 + 链表	数组 + 链表 + 红黑树
插入方式	头插法	尾插法
链表转树	无	链表长度 ≥ 8 且数组长度 ≥ 64 → 红黑树
树转链表	无	红黑树节点 ≤ 6 → 链表

为什么 JDK 8 改尾插法？ 头插法在多线程扩容时可能导致链表成环（死循环），尾插法避免了这个问题。但 HashMap 依然不是线程安全的！

2.3 put 流程（核心！面试必问）

put("张三", 95) 的完整流程：

1. 计算 key 的哈希值
   hash = "张三".hashCode()
   hash = hash ^ (hash >>> 16)  // 扰动函数，减少碰撞

2. 计算数组下标
   index = (n - 1) & hash  // n是数组长度，等价于 hash % n（但更快）

3. 该位置是否为空？
   ├── 为空 → 直接放入新 Node ✅
   └── 不为空（哈希冲突）→ 判断 key 是否相等
       ├── hash 相同 且 equals 返回 true → 覆盖旧 value ✅
       └── 不相等 → 判断是链表还是红黑树
           ├── 链表 → 尾插法加入，检查长度是否 ≥ 8
           │         长度 ≥ 8 且数组长度 ≥ 64 → 转红黑树
           └── 红黑树 → 按红黑树规则插入

4. 检查是否需要扩容
   size > capacity * loadFactor（默认 16 * 0.75 = 12）
   → 扩容为原来的 2 倍，重新计算所有元素位置

2.4 扩容机制

// JDK 源码关键参数
static final int DEFAULT_INITIAL_CAPACITY = 16;    // 默认容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;    // 负载因子
static final int TREEIFY_THRESHOLD = 8;             // 链表转树阈值
static final int UNTREEIFY_THRESHOLD = 6;           // 树转链表阈值
static final int MIN_TREEIFY_CAPACITY = 64;         // 转树的最小数组长度

扩容触发条件： size > capacity * loadFactor

容量变化：16 → 32 → 64 → 128 → ...
每次翻倍，保证容量始终是 2 的幂次（为了位运算优化）

为什么容量是2的幂次？
→ 计算 index 用 (n-1) & hash，等价于 hash % n
→ 但 & 运算比 % 快得多
→ n 是 2 的幂次时，n-1 的二进制全是1，& 运算等价于取模

2.5 HashMap 的核心操作

// 增
V put(K key, V value)              // 存入键值对，返回被覆盖的旧值（无则null）
void putAll(Map<? extends K, ? extends V> m)

// 删
V remove(Object key)               // 删除，返回被删的value
boolean remove(Object key, Object value)  // JDK 8+

// 改
V replace(K key, V value)          // 替换value
boolean replace(K key, V oldValue, V newValue)  // CAS式替换

// 查
V get(Object key)                  // 取值，不存在返回null
boolean containsKey(Object key)    // 是否包含key
boolean containsValue(Object value)// 是否包含value
int size()                         // 键值对数量
boolean isEmpty()

// 遍历
Set<K> keySet()                    // 所有key的Set
Collection<V> values()             // 所有value的Collection
Set<Map.Entry<K, V>> entrySet()   // 所有键值对的Set

2.6 遍历方式

Map<String, Integer> map = new HashMap<>();
map.put("张三", 90);
map.put("李四", 85);

// 方式1：entrySet（推荐，一次拿到key和value）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

// 方式2：keySet + get（简单但要两次查找，性能略差）
for (String key : map.keySet()) {
    System.out.println(key + "=" + map.get(key));
}

// 方式3：forEach + lambda（Java 8+）
map.forEach((key, value) -> System.out.println(key + "=" + value));

// 方式4：单独遍历value（不需要key时）
for (Integer value : map.values()) {
    System.out.println(value);
}

面试题：“entrySet 和 keySet 遍历哪个好？”
→ entrySet。keySet 遍历时每次 get(key) 都要重新算 hash 找位置，而 entrySet 一次遍历直接拿到 key 和 value。

2.7 HashMap 的坑

坑1：key 必须重写 hashCode 和 equals

// 用自定义类做 key，不重写 hashCode 和 equals
Map<Student, Integer> map = new HashMap<>();
Student s1 = new Student("张三", 20);
map.put(s1, 90);
Student s2 = new Student("张三", 20);
map.get(s2);  // null！s1和s2内容相同但地址不同

// 重写后：map.get(s2) → 90 ✅

坑2：HashMap 不是线程安全的

// 多线程 put 可能导致数据丢失、死循环（JDK 7 头插法）
// 解决方案：
// 1. Collections.synchronizedMap(new HashMap<>())  → 加锁，性能差
// 2. ConcurrentHashMap → 分段锁，性能好，推荐

坑3：null 的处理

HashMap<String, Integer> map = new HashMap<>();
map.put(null, 100);     // ✅ key 可以是 null（最多一个）
map.put("张三", null);  // ✅ value 可以是 null（多个）
map.get("不存在的key"); // null（和 value=null 分不清！）
map.containsKey("不存在的key"); // false（判断key是否存在用这个）

2.8 HashSet vs HashMap vs TreeSet vs LinkedHashMap

对比	HashSet	HashMap	TreeSet	LinkedHashMap
存储	单元素	键值对	单元素	键值对
有序性	无序	无序	排序	插入顺序
底层	HashMap	数组+链表+红黑树	TreeMap红黑树	HashMap+双向链表
null	可存1个null	key和value均可null	不允许null	key和value均可null
查找	O(1)	O(1)	O(log n)	O(1)
线程安全	❌	❌	❌	❌

---

三、Collections 工具类

3.1 是什么

java.util.Collections 是集合的工具类，提供排序、查找、同步包装等静态方法。

注意区分： Collection 是接口，Collections 是工具类！

3.2 排序相关

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));

// 升序排序
Collections.sort(list);  // [1, 1, 3, 4, 5, 9]

// 降序排序
Collections.sort(list, Comparator.reverseOrder());  // [9, 5, 4, 3, 1, 1]

// 自定义排序
Collections.sort(students, (s1, s2) -> s1.getAge() - s2.getAge());

// Java 8+ 推荐用 List 自带的 sort
list.sort(Comparator.naturalOrder());     // 升序
list.sort(Comparator.reverseOrder());     // 降序

3.3 查找与操作

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));

// 二分查找（必须先排序！）
Collections.sort(list);
int index = Collections.binarySearch(list, 4);  // 返回索引，未找到返回负数

// 最大值/最小值
Collections.max(list);  // 9
Collections.min(list);  // 1

// 反转
Collections.reverse(list);  // [9, 5, 1, 4, 1, 3]

// 打乱（随机洗牌）
Collections.shuffle(list);

// 填充（把所有元素替换为指定值）
Collections.fill(list, 0);  // [0, 0, 0, 0, 0, 0]

// 复制（目标list长度必须 ≥ 源list长度）
List<Integer> dest = new ArrayList<>(Collections.nCopies(list.size(), 0));
Collections.copy(dest, list);

// 交换
Collections.swap(list, 0, 1);  // 交换索引0和1的元素

// 频率
Collections.frequency(list, 1);  // 统计1出现的次数

3.4 不可变集合（Java 9+）

// Java 9+：List.of / Set.of / Map.of 创建不可变集合
List<String> list = List.of("A", "B", "C");   // 不可变！
Set<Integer> set = Set.of(1, 2, 3);            // 不可变！
Map<String, Integer> map = Map.of("A", 1, "B", 2);  // 不可变！

list.add("D");  // UnsupportedOperationException！

// Java 10+：从已有集合创建不可变副本
List<String> copy = List.copyOf(originalList);

面试题：“List.of 和 Arrays.asList 的区别？”

对比	Arrays.asList	List.of
Java版本	1.2+	9+
可修改元素	✅ set()可以	❌
可增删元素	❌	❌
null元素	✅ 允许	❌ 不允许
返回类型	Arrays内部类	不可变List

3.5 同步包装

// 线程安全的集合（加锁实现，性能差）
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// 面试建议：实际开发用 ConcurrentHashMap，不用 synchronizedMap

---

四、Arrays 工具类

4.1 是什么

java.util.Arrays 是数组的工具类，提供排序、查找、转换等静态方法。

4.2 常用方法

// 排序
int[] arr = {3, 1, 4, 1, 5, 9};
Arrays.sort(arr);  // [1, 1, 3, 4, 5, 9]

// 部分排序
Arrays.sort(arr, 1, 4);  // 只排索引 [1, 4) 的元素

// 二分查找（必须先排序！）
int index = Arrays.binarySearch(arr, 4);

// 数组转字符串
System.out.println(Arrays.toString(arr));  // [1, 1, 3, 4, 5, 9]

// 填充
int[] arr2 = new int[5];
Arrays.fill(arr2, 7);  // [7, 7, 7, 7, 7]

// 复制
int[] copy = Arrays.copyOf(arr, 10);       // 扩容复制，多余位补0
int[] copy2 = Arrays.copyOfRange(arr, 1, 4);  // 复制 [1, 4)

// 数组比较
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
a.equals(b);        // false！（数组用 == 比较）
Arrays.equals(a, b); // true ✅

// 多维数组比较
int[][] c = {{1, 2}, {3, 4}};
int[][] d = {{1, 2}, {3, 4}};
Arrays.equals(c, d);     // false！外层比较用 ==
Arrays.deepEquals(c, d); // true ✅

// 多维数组转字符串
System.out.println(Arrays.deepToString(c));  // [[1, 2], [3, 4]]

4.3 数组与集合互转

// 数组 → List
String[] arr = {"A", "B", "C"};
List<String> list = Arrays.asList(arr);  // ⚠️ 返回的是Arrays内部类，不能增删！

// 正确姿势：包一层 ArrayList
List<String> list2 = new ArrayList<>(Arrays.asList(arr));

// Java 8+ Stream 方式
List<String> list3 = Arrays.stream(arr).collect(Collectors.toList());

// List → 数组
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
String[] arr2 = list.toArray(new String[0]);  // 传入目标类型数组
// Java 11+ 
String[] arr3 = list.toArray(String[]::new);   // 函数式写法

面试题：“Arrays.asList 的坑？”

// 坑1：返回的List不能增删
List<String> list = Arrays.asList("A", "B", "C");
list.add("D");  // UnsupportedOperationException！

// 坑2：基本类型数组的陷阱
int[] arr = {1, 2, 3};
List<int[]> list = Arrays.asList(arr);  // 整个数组作为一个元素！size=1
// 因为 int[] 不能泛型化为 List<Integer>，要用 Integer[]
Integer[] arr2 = {1, 2, 3};
List<Integer> list2 = Arrays.asList(arr2);  // ✅ size=3

// 坑3：修改互相影响
String[] arr3 = {"A", "B", "C"};
List<String> list3 = Arrays.asList(arr3);
list3.set(0, "X");
System.out.println(arr3[0]);  // "X" ← 原数组也被改了！
// Arrays.asList 是数组的视图，不是副本

4.4 Arrays.sort 排序算法

数据类型	排序算法	时间复杂度	特点
基本类型（int/long/…）	双轴快排（Dual-Pivot Quicksort）	O(n log n)	不稳定排序
对象类型（Object[]）	TimSort（归并+插入混合）	O(n log n)	稳定排序

面试追问：“为什么基本类型用快排，对象用归并？”
→ 基本类型相等元素无区别，不稳定排序不影响结果，快排更快。对象可能有多个属性，稳定排序保证相等元素的相对顺序不变（比如先按年龄排，再按姓名排，第二次排序不会打乱第一次的顺序）。

---

五、面试高频题

Q1：HashMap 的 put 流程？

1. 计算 key 的 hash（扰动函数 hash ^ hash>>>16）
2. 计算数组下标 (n-1) & hash
3. 位置为空则直接插入；不为空则判断 key 是否相等（先比 hash，再调 equals）
4. key 相等则覆盖 value；不相等则追加到链表尾部或红黑树
5. 链表长度 ≥ 8 且数组长度 ≥ 64 时链表转红黑树
6. 插入后检查 size > capacity * 0.75 则扩容为 2 倍

Q2：HashMap 扩容机制？

默认容量 16，负载因子 0.75，当 size > 16*0.75=12 时扩容为 2 倍。新容量始终是 2 的幂次，便于用 (n-1) & hash 计算下标。扩容时所有元素重新计算位置（rehash），JDK 8 优化：元素在新数组的位置要么是原位置，要么是原位置+旧容量。

Q3：TreeSet 和 HashSet 怎么选？

需要排序用 TreeSet（红黑树，O(log n)查找），只需要去重用 HashSet（哈希表，O(1)查找）。TreeSet 不允许 null，HashSet 允许一个 null。绝大多数场景用 HashSet，只有需要自动排序时才用 TreeSet。

Q4：Collections 和 Collection 的区别？

Collection 是单列集合的顶层接口（List/Set 的父接口），Collections 是工具类（提供 sort/shuffle/reverse 等静态方法）。名字差一个 s，别搞混。

Q5：Arrays.asList 有什么坑？

三个坑：1）返回的 List 不能增删（UnsupportedOperationException）；2）基本类型数组会被当作一个整体元素；3）修改 List 会影响原数组（是视图不是副本）。正确做法：new ArrayList<>(Arrays.asList(arr))。

---

思维导图速览

Java集合进阶
├── TreeSet
│   ├── 底层TreeMap → 红黑树 → O(log n)
│   ├── 两种排序 → Comparable(内部) / Comparator(外部)
│   ├── 特有方法 → first/last/floor/ceiling/subSet
│   └── 坑 → 必须实现排序 / compareTo返回0=重复 / 不允许null
├── HashMap
│   ├── 底层 → 数组+链表+红黑树(JDK 8)
│   ├── put流程 → hash → 下标 → 判空 → 冲突处理 → 扩容
│   ├── 扩容 → 容量2的幂次 / 负载因子0.75 / 2倍扩容
│   ├── 遍历 → entrySet推荐 / keySet+get性能差
│   └── 坑 → key重写hashCode+equals / 非线程安全 / null处理
├── Collections工具类
│   ├── 排序 → sort / reverse / shuffle
│   ├── 查找 → binarySearch / max / min / frequency
│   ├── 不可变集合 → List.of / Set.of / Map.of (Java 9+)
│   └── 同步包装 → synchronizedList/Map（推荐用ConcurrentHashMap）
├── Arrays工具类
│   ├── 排序 → sort（基本类型快排/对象TimSort）
│   ├── 查找 → binarySearch
│   ├── 互转 → Arrays.asList坑多 / toArray
│   └── 坑 → asList不能增删 / 基本类型数组陷阱 / 视图非副本
└── 面试必背五题
    ├── HashMap put流程
    ├── HashMap扩容机制
    ├── TreeSet vs HashSet
    ├── Collections vs Collection
    └── Arrays.asList三个坑

---

写在最后

• TreeSet 补全了 Set 的排序能力，自然排序 vs 比较器排序是面试常考点
• HashMap 是 Java 集合的重中之重，put 流程和扩容机制几乎是逢面必问
• Collections/Arrays 是工具类，sort 和 asList 的坑点要记住