HashSet 与 TreeSet 对比分析

1. 引言

本文将深入对比 Java 中 java.util.Set 接口的两种主流实现——HashSet 和 TreeSet。作为资深开发者，你需要掌握它们的本质差异和应用场景。

2. 核心差异

HashSet 和 TreeSet 虽同属 Set 家族，但在关键特性上存在明显区别。

2.1 元素排序机制

HashSet 无序存储元素，TreeSet 则按自然顺序排列。看个例子就明白了：

@Test
public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add("Awesome");
 
    assertEquals(3, set.size());
    assertTrue(set.iterator().next().equals("Awesome"));
}

在 TreeSet 中，尽管 "Awesome" 是最后添加的，但遍历时却第一个出现。而 HashSet 的元素顺序则完全不可预测，可能随时变化。

2.2 null 值处理

HashSet 允许存储 null，TreeSet 则会抛出异常：

@Test(expected = NullPointerException.class)
public void givenTreeSet_whenAddNullObject_thenNullPointer() {
    Set<String> set = new TreeSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
}

@Test
public void givenHashSet_whenAddNullObject_thenOK() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("is");
    set.add(null);
 
    assertEquals(3, set.size());
}

⚠️ 注意：Java 7 曾允许 TreeSet 存在唯一 null 元素，但后续版本已严格禁止。

2.3 性能表现

简单粗暴：HashSet 比 TreeSet 快得多！

✅ HashSet：add()/remove()/contains() 操作时间复杂度 O(1)
❌ TreeSet：相同操作时间复杂度 O(log n)

实测显示，向 TreeSet 添加元素耗时通常远超 HashSet。不过要注意 JVM 预热状态可能影响测试结果，严谨的微基准测试可参考这里。

2.4 功能丰富度

TreeSet 提供了更多实用方法：

方法	功能说明
`pollFirst()`	返回并移除首元素，空集返回 null
`pollLast()`	返回并移除末元素，空集返回 null
`first()`	获取首元素
`last()`	获取末元素
`ceiling()`	返回≥指定元素的最小值
`lower()`	返回<指定元素的最大值

这些特性让 TreeSet 在有序集合操作上完胜 HashSet。

3. 共性特征

3.1 元素唯一性

两者都严格保证元素不重复，这是 Set 接口的核心契约：

@Test
public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    set.add("Baeldung");
 
    assertTrue(set.size() == 1);
        
    Set<String> set2 = new TreeSet<>();
    set2.add("Baeldung");
    set2.add("Baeldung");
 
    assertTrue(set2.size() == 1);
}

3.2 非线程安全

两者都不是线程安全的实现。当多线程并发访问且至少一个线程修改集合时，必须外部同步。

3.3 快速失败迭代器

两者的迭代器都是 fail-fast 机制：

@Test(expected = ConcurrentModificationException.class)
public void givenHashSet_whenModifyWhenIterator_thenFailFast() {
    Set<String> set = new HashSet<>();
    set.add("Baeldung");
    Iterator<String> it = set.iterator();

    while (it.hasNext()) {
        set.add("Awesome"); // 迭代中修改集合
        it.next();
    }
}

迭代过程中修改集合会立即抛出 ConcurrentModificationException。

4. 如何选择实现

根据实际需求选择合适实现：

✅ 需要排序 → 选 TreeSet
✅ 追求性能 → 选 HashSet
✅ 内存敏感 → 选 TreeSet（内存占用更优）
✅ 访问相邻元素 → 选 TreeSet（局部性更好）
✅ 需调优性能 → 选 HashSet（可配置 initialCapacity/loadFactor）
✅ 需保留插入顺序 → 选 LinkedHashSet（不在本文讨论范围）

5. 总结

本文系统对比了 HashSet 和 TreeSet 的异同点。作为开发者，理解这些底层差异能帮你避免踩坑，写出更高效的代码。

本文示例代码已托管至 GitHub，欢迎查阅实践。

Persistence

REST

Security