良好的编码风格和完善统一的规约是最高效的方式。

前言

本篇汲取了本书中较为精华的知识要点和实践经验加上读者整理，作为本系列里的第四篇章第三节：数据结构与集合的元素的比较篇。

本系列目录：

元素的比较

Comparable

Java中两个对象相比较的方法通常用在元素排序中，常用的两个几口分别是Comparable和Comparator，前者是自己和自己比；后者是第三方比较器，类似于平台性质的比较器。

我们熟知的Integer和String实现的就是Comparable的自然排序。

假设在一个搜索列表中进行排序时，先根据相关度排序，然后再根据浏览数排序，那么可以利用Comparable这样写：

public class SearchResult implements Comparable<EzCodingTest>{

    // 相关度
    int relativeRatio;
    long count;
    int recentOrders;

    public SearchResult(int relativeRatio, long count) {
        this.relativeRatio = relativeRatio;
        this.count = count;
    }

    @Override
    public int compareTo(EzCodingTest o) {
        if (this.relativeRatio != o.relativeRatio) {
            return this.relativeRatio > o.relativeRatio ? 1 : -1;
        }
        if (this.count != o.count) {
            return this.count > o.count ? 1 : -1;
        }
        return 0;
    }

    public static void main(String[] args) {

        EzCodingTest result1 = new EzCodingTest(10, 100);
        EzCodingTest result2 = new EzCodingTest(20, 1);
        System.out.println(result1.compareTo(result2));
    }

}

在实现Comparable时，我们发现了需要加上泛型限定，public class EzCodingTest implements Comparable<EzCodingTest>，这样的话，可以在编译阶段就判断是否符合该定义的对象。当排序方法不符合当前的业务要求，重写该比较方法compareTo，因为开闭原则的关系，已交付的类进行修改是有很大风险的。所以我们需要在外部定义比较器：Comparator。

Comparator

假如你写完上面的代码准备下班去食堂吃阿姨做的🦆鸭头时，产品狗过来和宁说：现在搜索的权重改辣！现在最近的订单数的权重最高，抓紧改吧，加班搞完半夜上线~！

这时候你应该怎么做呢，继续修改刚才的代码？不，正确的做法是：

对产品狗使用神の救♂济。

vans之后我们害是得van成任务，所以俺们可以搞个外部比较器SearchResultComparator剥离出来。

public class SearchResultComparator implements Comparator<EzCodingTest>{

    // 相关度
    int relativeRatio;
    long count;
    int recentOrders;
  
    public SearchResultComparator(int relativeRatio, long count) {
        this.relativeRatio = relativeRatio;
        this.count = count;
    }
  
    @Override
    public int compare(EzCodingTest o1, EzCodingTest o2) {
      
        if (o1.recentOrders != o2.recentOrders) {
            return o1.recentOrders > o2.recentOrders ? 1 : -1;
        }

        if (o1.relativeRatio != o2.relativeRatio) {
            return o1.relativeRatio > o2.relativeRatio ? 1 : -1;
        }

        if (o1.count != o2.count) {
            return o1.count > o2.count ? 1 : -1;
        }
        return 0;
    }
  
    public static void main(String[] args) {

        EzCodingTest result1 = new EzCodingTest(70, 100);
        EzCodingTest result2 = new EzCodingTest(20, 1);
        System.out.println(result1.compare(result1, result2));
    }
}

约定俗成，不管是Comparable还是Comparator，小于的情况返回-1，等于的情况返回0，大于的情况返回1。

排序

既然是比较，那么比较完了之后肯定有个排序工作，例如二维数组、一维数组的倒序、String类型的数组在Arrays.sort()中常常使用。

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

上面的代码是sort方法，比较器参数的<? super T>为下限通配。但是基本类型的数组不能用包装类型的比较器，例如以下想实现数组的倒序排序是不行的。

int[] tmp = new int[]{1, 2, 3, 4, 5, 6};
Arrays.sort(tmp, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return Integer.compare(o2, o1);
    }
});

TimSort

sort()方法中用的TimSort算法是一种混合算法，归并和插入优化过的缝合怪。JDK7之后就取代了原来的归并排序。

部分排序的数组，时间复杂度最优为 $O(n)$

随机排序的数组，时间复杂度为 $O(nlogn)$

hashCode和equals

hashCode和equals用来标识对象，两个方法协同工作可用来判断两个对象是否相等。

利用Object.hashCode()生成哈希值，分散在各地；
既然用哈希算法，就会有哈希冲突的情况，所以需要调用equals方法进行一次值的比较。

Object类定义中对hashCode和equals的要求如下

如果两个对象的equals的结果是相同的，那么这两个对象hashCode的返回结果也必须是相同的；
任何时候覆写equals，都必须同时覆写hashCode。

很经典的HashMap，内部数据结构是数组 + 链表（当链表长度大于8时，会变成红黑树）。当调用get方法时，会先判断hashCode的值，如果没有，直接return null，如果有的话，则执行equals方法，去比较值再返回。

因为哈希冲突的缘故，可能存在值不相同但是hashCode相同的情况，这时候就需要红黑树出场了。

假如有一个Set<Object>集合，集合的类型是一个拥有N多属性的类，但是我们仅仅将这些对象添加到HashSet中，并不能实现「去重」的效果。我们必须要覆写这个类「相同」的代码逻辑（hashCode和equals方法）。

《码出高效》系列笔记（四）：元素的比较

向代码致敬，寻找你的第[83]行。

前言

元素的比较

Comparable

Comparator

排序

TimSort

hashCode和equals

CATALOG

FEATURED TAGS

FRIENDS