TreeMap 详解

public interface Comparable<T> {
    int compareTo(T o);
    // 返回负整数：this < o
    // 返回 0：     this == o
    // 返回正整数：this > o
}

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    // 返回负整数：o1 < o2
    // 返回 0：     o1 == o2
    // 返回正整数：o1 > o2
}

TreeMap<Employee, String> bySalary =
    new TreeMap<>((a, b) -> Double.compare(a.getSalary(), b.getSalary()));

import java.util.*;

/**
 * 场景：大翔要求在年终调薪报表中，按薪资从低到高查看所有员工信息。
 * 白歌选择了 TreeMap，以便同时获取最低薪资和最高薪资员工。
 * 小崔负责实现排序逻辑，孔蓝验证了各种边界情况。
 */
public class FeiXiangSalaryTreeMap {
    // 键：薪资（Double），值：员工姓名
    // 使用自然排序（Double 实现了 Comparable）
    public static void main(String[] args) {
        // ========== 1. 创建 TreeMap（自然排序：按薪资升序） ==========
        TreeMap<Double, List<String>> salaryMap = new TreeMap<>();

        // 因为相同薪资的员工可能存在多个，用 List 存储同名员工
        addEmployee(salaryMap, 80000.0, "大翔");
        addEmployee(salaryMap, 35000.0, "白歌");
        addEmployee(salaryMap, 12000.0, "小崔");
        addEmployee(salaryMap, 15000.0, "孔蓝");
        addEmployee(salaryMap, 22000.0, "Frank");
        addEmployee(salaryMap, 18000.0, "黄俪");
        addEmployee(salaryMap, 35000.0, "赵鸣");  // 与白歌相同薪资
        addEmployee(salaryMap, 12000.0, "孙鹤");  // 与小崔相同薪资

        // ========== 2. 展示全部排序结果 ==========
        System.out.println("=== 飞翔科技薪资排名（从低到高） ===");
        int rank = 1;
        for (Map.Entry<Double, List<String>> entry : salaryMap.entrySet()) {
            for (String name : entry.getValue()) {
                System.out.printf("  第%d名: %s → ¥%.0f%n", rank++, name, entry.getKey());
            }
        }

        // ========== 3. 导航方法 ==========
        System.out.println("\n=== 导航查询 ===");
        System.out.println("最低薪资员工: " + salaryMap.firstEntry().getValue()
            + " → ¥" + salaryMap.firstKey());
        System.out.println("最高薪资员工: " + salaryMap.lastEntry().getValue()
            + " → ¥" + salaryMap.lastKey());

        // lowerKey：严格小于
        System.out.println("\n薪资严格低于 ¥20000 的最高薪资: ¥" + salaryMap.lowerKey(20000.0));
        // floorKey：小于等于
        System.out.println("薪资 ≤ ¥20000 的最高薪资: ¥" + salaryMap.floorKey(20000.0));
        // ceilingKey：大于等于
        System.out.println("薪资 ≥ ¥20000 的最低薪资: ¥" + salaryMap.ceilingKey(20000.0));
        // higherKey：严格大于
        System.out.println("薪资严格高于 ¥20000 的最低薪资: ¥" + salaryMap.higherKey(20000.0));

        // ========== 4. 范围查询 ==========
        System.out.println("\n=== 范围查询 ===");
        // subMap: [15000, 35000) —— 左闭右开
        SortedMap<Double, List<String>> midRange = salaryMap.subMap(15000.0, 35000.0);
        System.out.println("薪资在 [¥15000, ¥35000) 范围内:");
        for (Map.Entry<Double, List<String>> entry : midRange.entrySet()) {
            System.out.println("  ¥" + entry.getKey() + " → " + entry.getValue());
        }

        // headMap: < 20000
        System.out.println("\n薪资 < ¥20000 的员工:");
        salaryMap.headMap(20000.0).forEach((salary, names) ->
            System.out.println("  ¥" + salary + " → " + names)
        );

        // tailMap: >= 30000
        System.out.println("\n薪资 >= ¥30000 的员工:");
        salaryMap.tailMap(30000.0).forEach((salary, names) ->
            System.out.println("  ¥" + salary + " → " + names)
        );

        // ========== 5. 逆序视图 ==========
        System.out.println("\n=== 逆序视图（从高到低） ===");
        NavigableMap<Double, List<String>> descending = salaryMap.descendingMap();
        for (Map.Entry<Double, List<String>> entry : descending.entrySet()) {
            for (String name : entry.getValue()) {
                System.out.println("  " + name + " → ¥" + entry.getKey());
            }
        }

        // ========== 6. pollFirstEntry / pollLastEntry：取出并移除 ==========
        TreeMap<Double, String> copyMap = new TreeMap<>();
        copyMap.put(80000.0, "大翔");
        copyMap.put(12000.0, "小崔");
        copyMap.put(35000.0, "白歌");

        System.out.println("\n=== 取出最值（poll） ===");
        Map.Entry<Double, String> lowest = copyMap.pollFirstEntry();
        System.out.println("取出最低: " + lowest.getKey() + " → " + lowest.getValue());
        System.out.println("剩余: " + copyMap);

        Map.Entry<Double, String> highest = copyMap.pollLastEntry();
        System.out.println("取出最高: " + highest.getKey() + " → " + highest.getValue());
        System.out.println("剩余: " + copyMap);
    }

    /** 向 TreeMap 添加员工，处理同薪资多人情况 */
    private static void addEmployee(TreeMap<Double, List<String>> map, double salary, String name) {
        map.computeIfAbsent(salary, k -> new ArrayList<>()).add(name);
    }
}

import java.util.*;
import java.text.SimpleDateFormat;

/**
 * 场景：Frank 负责的市场部需要查询指定日期范围内的客户订单。
 * 白歌建议使用 TreeMap 以日期为键，利用 subMap 快速定位范围。
 * 小崔实现了自定义 Comparator，支持逆序和范围查询。
 */
public class FeiXiangOrderDateQuery {
    static SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");

    /** 订单实体 */
    static class Order {
        final String orderId;
        final String customer;
        final double amount;

        Order(String orderId, String customer, double amount) {
            this.orderId = orderId;
            this.customer = customer;
            this.amount = amount;
        }

        @Override
        public String toString() {
            return String.format("%s | %s | ¥%.0f", orderId, customer, amount);
        }
    }

    public static void main(String[] args) throws Exception {
        // ========== 1. 按日期自然排序的 TreeMap ==========
        TreeMap<Date, List<Order>> orderMap = new TreeMap<>();

        addOrder(orderMap, "2024-01-05", new Order("ORD001", "大客户A", 50000));
        addOrder(orderMap, "2024-01-15", new Order("ORD002", "大客户B", 35000));
        addOrder(orderMap, "2024-02-01", new Order("ORD003", "大客户C", 120000));
        addOrder(orderMap, "2024-02-10", new Order("ORD004", "大客户A", 80000));
        addOrder(orderMap, "2024-03-05", new Order("ORD005", "大客户B", 65000));
        addOrder(orderMap, "2024-03-20", new Order("ORD006", "大客户C", 42000));

        // ========== 2. 展示全部订单（按日期排序） ==========
        System.out.println("=== 飞翔科技 2024 Q1 订单（按日期排序） ===");
        for (Map.Entry<Date, List<Order>> entry : orderMap.entrySet()) {
            System.out.println("\n  " + sdf.format(entry.getKey()) + ":");
            for (Order o : entry.getValue()) {
                System.out.println("    " + o);
            }
        }

        // ========== 3. 范围查询：查询 1 月份的订单 ==========
        Date jan1 = sdf.parse("2024-01-01");
        Date feb1 = sdf.parse("2024-02-01");
        System.out.println("\n=== 范围查询：2024年1月订单 [1/1, 2/1) ===");
        SortedMap<Date, List<Order>> janOrders = orderMap.subMap(jan1, feb1);
        for (Map.Entry<Date, List<Order>> entry : janOrders.entrySet()) {
            for (Order o : entry.getValue()) {
                System.out.println("  " + sdf.format(entry.getKey()) + " → " + o);
            }
        }

        // ========== 4. 范围查询：查询 2 月及以后的订单 ==========
        System.out.println("\n=== 范围查询：2024年2月及以后 [2/1, ...) ===");
        SortedMap<Date, List<Order>> febOnwards = orderMap.tailMap(feb1);
        for (Map.Entry<Date, List<Order>> entry : febOnwards.entrySet()) {
            for (Order o : entry.getValue()) {
                System.out.println("  " + sdf.format(entry.getKey()) + " → " + o);
            }
        }

        // ========== 5. 查询特定日期前后最近的订单 ==========
        Date target = sdf.parse("2024-02-05");
        System.out.println("\n=== 导航查询：以 " + sdf.format(target) + " 为基准 ===");
        System.out.println("该日期之前最近的订单日期: " + sdf.format(orderMap.lowerKey(target)));
        System.out.println("该日期之后最近的订单日期: " + sdf.format(orderMap.higherKey(target)));

        // ========== 6. 逆序：最近订单在前 ==========
        System.out.println("\n=== 逆序视图（最新订单在前） ===");
        NavigableMap<Date, List<Order>> reversed = orderMap.descendingMap();
        for (Map.Entry<Date, List<Order>> entry : reversed.entrySet()) {
            for (Order o : entry.getValue()) {
                System.out.println("  " + sdf.format(entry.getKey()) + " → " + o);
            }
        }

        // ========== 7. 使用自定义 Comparator 按金额排序 ==========
        System.out.println("\n=== 自定义排序：按订单金额从高到低 ===");
        TreeMap<Double, Order> byAmount = new TreeMap<>(
            Comparator.reverseOrder()  // 降序
        );
        for (List<Order> orders : orderMap.values()) {
            for (Order o : orders) {
                byAmount.put(o.amount, o);
            }
        }
        byAmount.forEach((amount, order) ->
            System.out.println("  ¥" + amount + " → " + order)
        );
    }

    private static void addOrder(TreeMap<Date, List<Order>> map, String dateStr, Order order)
            throws Exception {
        Date date = sdf.parse(dateStr);
        map.computeIfAbsent(date, k -> new ArrayList<>()).add(order);
    }
}

// ❌ 错误：Comparator 仅按部门比较，同部门的员工会互相覆盖！
TreeMap<String, String> deptMap = new TreeMap<>(
    (a, b) -> {
        // a = "EMP001-技术部-白歌" 格式的字符串
        String deptA = a.split("-")[1];
        String deptB = b.split("-")[1];
        return deptA.compareTo(deptB);  // 同部门返回 0 → 视为相同键！
    }
);

deptMap.put("EMP001-技术部-白歌", "白歌信息");
deptMap.put("EMP002-技术部-小崔", "小崔信息");
System.out.println(deptMap.size());  // 1！小崔覆盖了白歌！

// ✅ 正确：Comparator 必须处理所有可能情况，不能轻易返回 0
TreeMap<String, String> deptMap = new TreeMap<>(
    (a, b) -> {
        String deptA = a.split("-")[1];
        String deptB = b.split("-")[1];
        int cmp = deptA.compareTo(deptB);
        if (cmp != 0) return cmp;
        // 同部门时，用完整字符串区分（保证不同键肯定不返回 0）
        return a.compareTo(b);
    }
);

deptMap.put("EMP001-技术部-白歌", "白歌信息");
deptMap.put("EMP002-技术部-小崔", "小崔信息");
System.out.println(deptMap.size());  // 2 —— 正确！

// ❌ 错误：TreeMap 不允许 null 键
TreeMap<String, String> map = new TreeMap<>();
map.put("A", "1");
map.put(null, "2");  // NullPointerException！
// TreeMap.put 内部调用 compareTo/compare，null.compareTo() 或 comparator.compare(null, obj) 抛 NPE

// ✅ 如果确实需要表示"空键"，使用特殊标记值
TreeMap<String, String> map = new TreeMap<>();
map.put("A", "1");
map.put("__NULL_KEY__", "2");  // 用特殊字符串代替 null
// 或者在插入前做 null 检查

// ❌ 错误：向 subMap 视图中插入超出边界范围的元素
TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A"); map.put(3, "C"); map.put(5, "E");

SortedMap<Integer, String> sub = map.subMap(1, 5);  // [1, 5)
System.out.println(sub);  // {1=A, 3=C}

sub.put(6, "F");  // IllegalArgumentException: key out of range!
// subMap 有边界检查，超出 [1, 5) 范围的插入会拒绝

// ✅ 向 subMap 插入时确保在边界范围内
sub.put(2, "B");  // 在范围内，OK
sub.put(4, "D");  // 在范围内，OK
System.out.println(sub);  // {1=A, 2=B, 3=C, 4=D}
System.out.println(map);  // {1=A, 2=B, 3=C, 4=D, 5=E} —— 原 map 也被修改了！

// ❌ 错误：compareTo 只用部分字段，信息丢失
class Employee implements Comparable<Employee> {
    String name;
    double salary;

    @Override
    public int compareTo(Employee o) {
        return Double.compare(this.salary, o.salary);  // 只用薪资比较
    }
}

TreeMap<Employee, String> map = new TreeMap<>();
map.put(new Employee("小崔", 12000), "dept");
map.put(new Employee("孙鹤", 12000), "dept");  // 被认为与"小崔"是同一键！
System.out.println(map.size());  // 1 —— 孙鹤丢失！