《码出高效》系列笔记(四):元素的比较

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

Posted by MatthewHan on 2020-03-19

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

前言

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

本系列目录

元素的比较

Comparable

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

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

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

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
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剥离出来。

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
32
33
34
35
36
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()中常常使用。

1
2
3
4
5
6
7
8
9
10
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>为下限通配。但是基本类型的数组不能用包装类型的比较器,例如以下想实现数组的倒序排序是不行的。

1
2
3
4
5
6
7
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的要求如下

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

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

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

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