TreeSet排序异常：LRU缓存实现中Comparator不符合预期问题

我在实现LRU缓存时，尝试用TreeSet存储唯一key并根据插入时间排序，但TreeSet未按照定义的Comparator返回预期顺序。

实现代码 #

LRUCache类 #

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));
    }
}

Pair类 #

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 +
                '}';
    }
}

问题现象 #

预期添加(3,3)后删除时间戳更早的(2, -2147483647)，但实际TreeSet元素顺序为[Pair{x=1, y=3}, Pair{x=2, y=-2147483647}, Pair{x=3, y=-2147483645}]，不符合按y值排序的预期。

单独测试示例 #

TreeSet测试代码 #

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);
        }
    }
}

测试用Pair类 #

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 +
                '}';
    }
}

该测试示例的排序符合预期，但LRU缓存实现中却出现异常。

核心需求与疑问 #

• 核心需求：TreeSet中Pair元素需基于x判断唯一性（Set特性），基于y排序（Tree特性）。
• 疑问：TreeSet在Comparator返回0时判定元素相等，是否应调用equals方法？

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