HashSet 与 TreeSet 底层原理：Map 的「马甲」

// 底层存储：所有元素都作为 key 存入这个 HashMap
private transient HashMap<E, Object> map;

// 占位 value —— 所有 entry 共享同一个对象引用
private static final Object PRESENT = new Object();

// add：元素作为 key，PRESENT 作为 value
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// remove：直接调用 HashMap 的 remove
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// contains：直接调用 HashMap 的 containsKey
public boolean contains(Object o) {
    return map.containsKey(o);
}

// size：直接返回 HashMap 的 size
public int size() {
    return map.size();
}

public HashSet() { map = new HashMap<>(); }          // 默认 16 容量、0.75 负载因子
public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); }

// 用集合初始化：按 0.75 负载因子反推容量，避免 addAll 过程中扩容
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16));
    addAll(c);
}

// 迭代 = 遍历 HashMap 的 keySet 视图
public Iterator<E> iterator() { return map.keySet().iterator(); }

// 返回：与 key 关联的【旧 value】；若此前没有该 key 的映射，返回 null
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 统计独立访客：add 返回 true 才代表一个新用户
Set<Long> seen = new HashSet<>();
for (Long uid : dailyLog) {
    if (seen.add(uid)) {   // 只有真正的新用户才计数
        uniqueCount++;
    }
}

// 第 1 步：hash(key) 定位桶 —— 只用 hashCode
if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null) {
    // 第 2 步：桶内用 == 或 equals 逐个比较 —— 只用 equals
    if (first.hash == hash && ((k = first.key) == key ||
        (key != null && key.equals(k))))
        return first;
    // ... 链表 / 红黑树中继续 equals 比较
}

public class User {
    private final Long id;
    private final String name;

    // equals 正确：按业务字段比较
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User u = (User) o;
        return Objects.equals(id, u.id) && Objects.equals(name, u.name);
    }
    // hashCode 没重写 —— 用的还是 Object 的身份哈希！

    public static void main(String[] args) {
        User a = new User(1L, "Alice");
        User b = new User(1L, "Alice");
        Set<User> set = new HashSet<>();
        set.add(a);
        set.add(b);                 // 你以为返回 false？实际返回 true！
        System.out.println(set.size()); // 2 —— 两个"相等"对象并存，去重失效
    }
}

// 扰动：让高 16 位也参与低 16 位运算，稀释低位的碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 寻址：i = (n - 1) & hash —— n 是 2 的幂，等价 hash % n 且更快

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;    // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;         // 负载因子
static final int TREEIFY_THRESHOLD = 8;                  // 链长 ≥ 8 → 尝试树化
static final int UNTREEIFY_THRESHOLD = 6;                // 树节点 ≤ 6 → 退化为链表
static final int MIN_TREEIFY_CAPACITY = 64;              // 树化前数组容量的下限

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, Serializable {

    // 底层存储：NavigableMap（通常是 TreeMap）
    private transient NavigableMap<E, Object> m;

    // 占位 value（同 HashSet 的 PRESENT）
    private static final Object PRESENT = new Object();

    // 默认构造：自然排序 → 元素必须实现 Comparable
    public TreeSet() { this(new TreeMap<>()); }

    // 自定义比较器
    public TreeSet(Comparator<? super E> comp) {
        this(new TreeMap<>(comp));
    }

    // 核心方法同样委托
    public boolean add(E e)    { return m.put(e, PRESENT) == null; }
    public boolean remove(Object o) { return m.remove(o) == PRESENT; }

    // TreeSet 独有的有序操作（TreeSet 有而 HashSet 没有）
    public E first()   { return m.firstKey(); }
    public E last()    { return m.lastKey(); }
    public E lower(E e)    { return m.lowerKey(e); }    // < e 的最大元素
    public E higher(E e)   { return m.higherKey(e); }   // > e 的最小元素
    public E ceiling(E e)  { return m.ceilingKey(e); }  // >= e 的最小元素
    public E floor(E e)    { return m.floorKey(e); }    // <= e 的最大元素
}

// 有外部 Comparator 用 Comparator，否则要求 key 实现 Comparable（自然排序）
final int compare(Object k1, Object k2) {
    return comparator == null
        ? ((Comparable<? super K>) k1).compareTo((K) k2)
        : comparator.compare((K) k1, (K) k2);
}

// put 中：cmp == 0 视为同一个 key —— 只覆盖 value，不新增节点
else return t.setValue(value);

// 子区间视图：包一层 NavigableSubMap，操作实时映射回原 TreeMap
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                               E toElement, boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
}

public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

// LinkedHashSet 的构造器，全部转发给 HashSet 的"特殊"构造器
public class LinkedHashSet<E> extends HashSet<E> {
    public LinkedHashSet() { super(16, .75f, true); }
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2 * c.size(), 11), .75f, true);
        addAll(c);
    }
}

// HashSet 里的"隐藏构造器"：第三个参数 dummy 只是占位，真正作用是换 Map 实现
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

// 收集所有不重复的用户 ID（O(1) 插入 + 自动去重）
Set<Long> uniqueUserIds = new HashSet<>(
    (int) (orderList.size() / 0.75f) + 1);   // 预估容量，避免扩容
for (Order order : orderList) {
    uniqueUserIds.add(order.getUserId());
}

// 按分数降序；分数相同按名字升序 —— 注意 TreeSet 以 compare 结果判重，
// 若只按分数比较，同分玩家会被当成"重复元素"吞掉！
TreeSet<Player> leaderboard = new TreeSet<>(
    Comparator.comparingInt(Player::getScore).reversed()
             .thenComparing(Player::getName)   // 决胜字段，保证唯一性
);
leaderboard.add(new Player("Alice", 2800));
leaderboard.add(new Player("Bob", 3200));
leaderboard.add(new Player("Carol", 2800)); // 与 Alice 同分，靠名字区分

Player top = leaderboard.first();                  // Bob（最高分）
Player second = leaderboard.lower(top);            // 第二名
// 区间查询：分数 ≥ 3000 的玩家（probe 对象模式，只用于比较）
NavigableSet<Player> highScores =
    leaderboard.tailSet(new Player("", 3000), true);

// 文章标签：去重且保持添加顺序，遍历输出稳定
Set<String> tags = new LinkedHashSet<>();
tags.add("Java");
tags.add("集合框架");
tags.add("面试");
tags.add("Java");  // 重复，忽略且不改变顺序
// 遍历顺序：Java → 集合框架 → 面试