TreeSet 中的排序不正确

Question

我正在尝试解决https://leetcode.com/problems/lru-cache/description/。

我使用树集来保存唯一键并根据插入时间对它们进行排序。树集没有按照我使用 Camparator 指定的方式返回元素。

class LRUCache {

    Map<Integer, Integer> keyValue;// ()
    TreeSet<Pair> keys; //key, timestamp (1,-1000)
    int capacity;//2
    int timestamp;
    public LRUCache(int capacity) {
        keyValue = new HashMap<>(capacity);
        keys = new TreeSet<>((Pair a,Pair b) -> {
            System.out.println("inside comparator implementation");
            int result = a.x == b.x ? 0 : a.y - b.y == 0 ? -1 : a.y - b.y;
            System.out.println("result: " + result);
            return result;
        });
        this.capacity = capacity;
    }

    public int get(int key) {

        timestamp++;
        Pair pair = new Pair(key, timestamp);
        boolean found = keys.contains(pair);
        if (found) {
            System.out.println("keys contains " + key + ". So, removing it to update");
            keys.remove(pair);
        } else {
            System.out.println("keys doesn't contains " + key + ". So, not removing it. Directly adding it");
        }

        boolean added = keys.add(pair);
        System.out.println("add status: " + added + " for: " + pair);

        return keyValue.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        int priority = Integer.MIN_VALUE + timestamp++;
        Pair pair = new Pair(key, priority);
        System.out.println("key: " + key + " priority: " + priority);
        boolean found = keys.contains(pair);
        if (!found) {
            System.out.println("keys doesn't " + key + " and " + value + ". So, adding to keys");
            keys.add(pair);
        } else {
            System.out.println("keys contains " + key + " and " + value + ". So, not adding to keys");
        }

        keyValue.put(key, value);
        if (keys.size() > capacity) {
            System.out.println("size > capacity");
            Pair remove = keys.first();
            System.out.println("removing: " + remove);
            keys.remove(remove);
            keyValue.remove(remove.x);
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        System.out.println();
        System.out.println("putting 1,1");
        lruCache.put(1, 1);

        System.out.println();
        System.out.println("putting 2,2");
        lruCache.put(2, 2);

        System.out.println();
        System.out.println("getting 1");
        System.out.println(lruCache.get(1));

        System.out.println();
        System.out.println("c");
        lruCache.put(3, 3);

        System.out.println();
        System.out.println("getting 2");
        System.out.println(lruCache.get(2));
    }
}

class Pair{
    int x;
    int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object o) {
        System.out.println("inside pair equals");
        if (this == o) {
            return true;
        }
        if (!(o instanceof Pair)) {
            return false;
        }
        return this.x == ((Pair) o).x;
    }

    public int hashCode() {
        return x;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

我期望 (2, -2147483647) 在添加 (3,3) 后被删除，因为 (2, -2147483647) 具有负时间戳。

这是在我预期 (2, -2147483647) 被删除之前打印的集合。

[Pair{x=1, y=3}, Pair{x=2, y=-2147483647}, Pair{x=3, y=-2147483645}]

为什么

Pair{x=1, y=3}

首先与

{x=2, y=-2147483647}

相比。 我编写了比较器以根据 y 值在树集中排序，为什么它按预期工作？

我尝试创建一个 TreeSetPractise

public class TreeSetPractise {
    public static void main(String[] args) {
        TreeSet<Pair> ts = new TreeSet<>(( a,  b) -> {
            System.out.println("inside comparator implementation");
            int result = a.x == b.x ? 0 : a.y - b.y == 0 ? -1 : a.y - b.y;
            System.out.println("result: " + result);
            return result;
        });
        ts.add(new Pair(1,10));
        ts.add(new Pair(2, -20));
        ts.add(new Pair(3, 30));
        System.out.println(ts);
        for (Pair i : ts) {
            System.out.println(i);
        }
    }
}

class Pair {
    int x;
    int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

这正在按预期工作。

这里的主要问题是，对于 TreeSet 的元素：Pair{x,y} 必须检查 x 上的相等性和 y 上的排序。 含义集合功能基于 x，树功能基于 y

Answer 1

查看比较器逻辑：

int result = a.x == b.x ? 0 : a.y - b.y == 0 ? -1 : a.y - b.y;

a.y - b.y == 0 ? -1 : a.y - b.y

有一些问题。

1. 如果

   a.y

   等于

   b.y

   那么它会考虑

   a < b

   ，这可能不是有意的。
2. 否则执行算术运算，当

   b.y

   可以是像

   Integer.MIN_VALUE

   这样的大负数时，可能会溢出，从而提供错误的结果。

如果目标是比较

y

如果

x

相同，您可以用

a.y - b.y == 0 ? 0 : (a.y < b.y) ? - 1 : 1

替换该部分。然而，更安全（不易出错）的方法是仅使用

Integer.compare

来比较

a.y

和

b.y

。

int result = a.x == b.x ? 0 : Integer.compare(a.y, b.y);