TreeMap自定义排序后为何出现键覆盖及重复键问题？

问题原因分析 #

1. Comparator 一致性破坏：你的 TreeMap 使用的比较器依赖外部 HashMap 的可变值，违反了 TreeMap 的核心要求——比较器必须与 equals() 保持一致且行为稳定。当你更新 HashMap 中的价格后，比较器对已有键的判断逻辑发生变化，导致 TreeMap 无法正确定位或删除旧条目。
2. 操作顺序错误：update 方法中先更新 HashMap 再删除 TreeMap 条目，此时比较器已使用新价格进行判断。尽管 containsKey() 返回 true，但 TreeMap 可能找不到旧条目（因为内部排序基于旧价格），最终导致旧条目残留、新条目重复插入，出现重复键。
3. TreeMap 无法动态重排序：即使修复操作顺序，TreeMap 也不会在 HashMap 值变化后自动重新排序，导致 firstKey()/lastKey() 返回的最小/最大值可能基于旧价格，结果错误。

修复方案 #

方案一：修正操作顺序（仅解决重复键，仍存在排序失效问题）

调整操作顺序，先删除 TreeMap 旧条目（此时 HashMap 未更新，比较器用旧价格），再更新 HashMap 并插入新条目：

public void update(int timestamp, int price) {
    System.out.println(treemap);
    latesttime = Math.max(latesttime, timestamp);
    // 先删除旧条目（基于旧价格比较）
    if (map.containsKey(timestamp)) {
        treemap.remove(timestamp);
    }
    // 更新HashMap
    map.put(timestamp, price);
    // 插入新条目
    treemap.put(timestamp, price);
}

注意：此方法仅解决重复键问题，但 TreeMap 排序不会随价格更新动态调整，minimum()/maximum() 仍可能返回错误结果。

方案二：使用优先队列替代 TreeMap（彻底解决问题）

用两个优先队列（最小堆、最大堆）存储所有价格更新，配合 HashMap 跟踪最新价格。获取最值时忽略堆中已过期的条目：

class StockPrice {
    private HashMap<Integer, Integer> priceMap;
    private PriorityQueue<int[]> minHeap;
    private PriorityQueue<int[]> maxHeap;
    private int latestTime;

    public StockPrice() {
        priceMap = new HashMap<>();
        minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 最小堆按价格升序
        maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]); // 最大堆按价格降序
        latestTime = -1;
    }

    public void update(int timestamp, int price) {
        latestTime = Math.max(latestTime, timestamp);
        priceMap.put(timestamp, price);
        minHeap.offer(new int[]{timestamp, price});
        maxHeap.offer(new int[]{timestamp, price});
    }

    public int current() {
        return priceMap.get(latestTime);
    }

    public int maximum() {
        // 移除堆中过期条目（价格与最新值不符）
        while (!maxHeap.isEmpty()) {
            int[] top = maxHeap.peek();
            if (priceMap.get(top[0]).equals(top[1])) {
                return top[1];
            }
            maxHeap.poll();
        }
        return -1; // 未调用update时返回默认值
    }

    public int minimum() {
        while (!minHeap.isEmpty()) {
            int[] top = minHeap.peek();
            if (priceMap.get(top[0]).equals(top[1])) {
                return top[1];
            }
            minHeap.poll();
        }
        return -1;
    }
}

此方案彻底避免了 TreeMap 的比较器一致性问题，能正确跟踪最新的最小/最大值。

内容的提问来源于stack exchange，提问作者Vishal Poddar