java - 给定基于 Map 的 Comparator 时，比较方法违反了其一般契约

Question

我一直在努力解决这个问题:以下代码实现了一个基于 Map 的比较器。 Map 将 Comparable 类型的对象映射为 Integer 值。给定两个可比较的对象，比较器会比较映射中这些对象的值。如果任何对象不在映射的键集中，则比较器返回 0。

所以比较器应该是传递和自反的。然而，当我运行下面的测试用例以对整数 vector 进行排序时，出现以下错误:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeHi(TimSort.java:868)
at java.util.TimSort.mergeAt(TimSort.java:485)
at java.util.TimSort.mergeCollapse(TimSort.java:410)
at java.util.TimSort.sort(TimSort.java:214)
at java.util.TimSort.sort(TimSort.java:173)
at java.util.Arrays.sort(Arrays.java:659)
at java.util.Collections.sort(Collections.java:217) 
    at IndexComparatorTest.testSort(IndexComparatorTest.java:45)

我尝试通过从列表和 HashMap 中排除一些元素来进一步减少这个问题，但删除任何元素会使问题消失。我也开始研究 Timsort.java，但这有点难以理解。

有什么想法吗？

import org.junit.Test;

import java.util.*;

class MyComparator<N extends Comparable<N>> implements Comparator<N> {

    private final Map<N, Integer> node2index;

    public MyComparator(Map<N, Integer> node2Index) {
        this.node2index = node2Index;
    }

    @Override
    public int compare(N o1, N o2) {
        if (! node2index.containsKey(o1)) return 0;
        if (! node2index.containsKey(o2)) return 0;
        int result = Integer.compare(node2index.get(o1), node2index.get(o2));
        return result;
    }
}

public class IndexComparatorTest {

    @Test
    public void testSort() {
        Vector<Integer> toBeSorted = new Vector<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31));
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 5);
        hashMap.put(14, 6);
        hashMap.put(15, -2);
        hashMap.put(16, 4);
        hashMap.put(17, 1);
        hashMap.put(18, 8);
        hashMap.put(19, -12);
        hashMap.put(21, -3);
        hashMap.put(22, -13);
        hashMap.put(24, -19);
        hashMap.put(25, 2);
        hashMap.put(27, 7);
        hashMap.put(28, -6);
        hashMap.put(31, 0);
        hashMap.put(30, -4);
        Collections.sort(toBeSorted, new MyComparator<>(hashMap));
    }

}

Answer 1

正如您所发现的，该比较器违反了其契约(Contract)。例如。它告诉你0=1, 1=14, 0<14 ，这不符合要求“实现者必须确保compare(x, y)==0意味着sgn(compare(x, z))==sgn(compare(y, z))对于所有z。” 修复方法是用此实现替换比较方法:

@Override
public int compare(N o1, N o2) {
    if (!node2index.containsKey(o1) && !node2index.containsKey(o2)) return 0;
    if (!node2index.containsKey(o1)) return -1;
    if (!node2index.containsKey(o2)) return +1;
    int result = Integer.compare(node2index.get(o1), node2index.get(o2));
    return result;
}

根据您希望非映射元素大于还是小于映射元素，您可能需要交换 -1和+1 .