HashSet vs TreeSet

HashSet 和 TreeSet 是 Java 集合框架中 Set 接口的两个核心实现类。Set 的特点是不允许重复元素。理解两者的实现原理和性能差异，是正确选择使用场景的关键。

一、Set 接口概述

1.1 Set 的特点

特点	说明
不重复	不允许存储重复元素
无索引	没有提供通过索引访问元素的方法
最多一个 null	最多允许一个 null 元素（TreeSet 不允许）

public interface Set<E> extends Collection<E> {
    // 基本操作
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    
    // 批量操作
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    
    // 集合运算
    // 并集：addAll
    // 交集：retainAll
    // 差集：removeAll
}

1.2 Set 实现类一览

                    ┌─────────────┐
                    │    Set<E>   │
                    └──────┬──────┘
                           │
        ┌──────────────────┼──────────────────┐
        │                  │                  │
  ┌─────┴─────┐      ┌─────┴─────┐      ┌─────┴─────┐
  │  HashSet  │      │  TreeSet  │      │LinkedHashSet│
  └───────────┘      └───────────┘      └───────────┘
  哈希表实现          红黑树实现           哈希表+链表
  无序                有序                插入顺序
  O(1)                O(log n)            O(1)

二、HashSet

2.1 底层实现

HashSet 基于 HashMap 实现，元素存储在 HashMap 的 key 中，value 是一个固定的 PRESENT 对象。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    
    // 内部使用 HashMap
    private transient HashMap<E,Object> map;
    
    // 虚拟值，作为 HashMap 的 value
    private static final Object PRESENT = new Object();
    
    // 构造器
    public HashSet() {
        map = new HashMap<>();
    }
    
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
}

2.2 核心方法

// 添加元素：调用 HashMap 的 put
public boolean add(E e) {
    retu

ConcurrentHashMap Queue vs Stack