为什么当 Comparator.compare 相等时我们需要返回 0

Question

我知道当实现Comparator接口的compare方法时我们需要返回如果 o1 > o2，+1-1 如果 o1 < o20 如果 o1 == o2我的问题是为什么当两者相等时我们需要返回 0？用例是什么或在哪里使用？如果我们考虑当o2大于o1或o2等于o1时排序不会改变它的位置。谁能来解释一下实际用例吗？Java 文档说比较其两个参数的顺序。当第一个参数小于、等于或大于第二个参数时，返回负整数、零或正整数。这是否意味着 return -1 或 return 0 具有相同的影响？零或正整数 @Override    public int compare(Test f1, Test f2) {        if (f1.getId() > f2.getId()) {            return 1;        } else if (f1.getId() < f2.getId()) {            return -1;        } else {            return 0;        }    }

Answer 1

当您排序时，-1和0本质上对排序列表的排序有非常相似的影响，因为评估compareTo为 0 的项目将被分组在一起。

您“实际上”会在其他场景中使用此比较，例如您可能不想将复杂对象重复添加到列表中（是的，您也可以通过使用 a 来实现此场景）set。

假设我们有一个对象Book如下：

import java.util.Comparator;

public class Book implements Comparable {

  String isbn;

  String title;

  public Book(String id, String title) {

    this.isbn = id;

    this.title = title;

  }

  String getIsbn() {

    return isbn;

  }

  String getTitle() {

    return title;

  }

  @Override

  public int compareTo(Object o) {

    return Comparator

            .comparing(Book::getIsbn)

            .thenComparing(Book::getTitle)

            .compare(this, (Book) o);

  }

  @Override

  public  String toString() {

    String output = new StringBuilder()

            .append(isbn).append(":").append(title)

            .toString();

    return output;

  }

}

在这里，我们重写了compareToof book 以创建自定义比较，首先检查书籍的 isbn，然后检查其标题。

假设（例如）您有一个图书馆，里面有书籍。您可能想阻止您的用户在该图书馆中添加重复的书籍......

public class Library {

  public static void main(String [] args) {

    List<Book> library = new ArrayList<>();

    library.add(new Book("9780593098240", "Children of Dune"));

    library.add(new Book("9780593098233", "Dune Messiah"));

    library.add(new Book("9780441172719", "Dune"));

    // Just to show the sorting, based on multiple attributes.

    Collections.sort(library);

    System.out.println("Books in library: " + Arrays.toString(library.toArray()));

    // You would obviously have some code for entering a book here, but easier to just create the object for an example. 

    Book newBook = new Book("9780593098240", "Children of Dune");

    for (Book bookInLibrary : library) {

        if (bookInLibrary.compareTo(newBook) == 0) {

            System.out.println("We already have that book in the library.");

            break;

        }

    }

  }

}

Answer 2

如果当比较的两个值相等时返回 -1，compare(f1,f2)并且compare(f2,f1)都将返回-1。这意味着元素的顺序将不一致。它可能会破坏一些排序算法。

这就是为什么总合同compare要求：

sign(compare(f1,f2)) = -sign(compare(f2,f1))

这意味着当两个值相等时必须返回 0。

Answer 3

您可以考虑具有以下实现的二分搜索算法：

function binary_search(A, n, T):

    L := 0

    R := n − 1

    while L <= R:

        m := floor((L + R) / 2)

        if A[m] < T:

            L := m + 1

        else if A[m] > T:

            R := m - 1

        else:

            return m

    return unsuccessful

假设有一个Comapator对于相等和更少的情况返回相同的值：

public int compare(Test f1, Test f2) {

        if (f1.getId() > f2.getId()) {

            return 1;

        } else {

            return -1; 

}

现在A[m] < T或A[m].compareTo(T) < 0，将是true当T等于A[m]和当A[m]小于时T。

所以在这种情况下：

1 2 3 4 // array and A[m] is 2

2 // target T

2.compareTo(2)返回-1使得算法进入下一次执行L = m + 1 -> 而不是返回正确的值。

事实上，二分查找会陷入不定式循环，从 2.compareTo(2)and跳转3.compareTo(2)。我希望这有帮助。