20. JDK的一次排序采坑记录
列表排序，我们可以说是用的比较多了，写起来也很溜，继承Comparable接口，实现compareTo方法，然后直接使用java.util.List#sort即可
虽说如此简单，今天却是一脚踩进去，花了不少时间才爬出来，下面复盘一下这个现场
I. 排序场景复现
背景比较简单，做一个新闻的聚合专栏，专栏内部的文章可以来自各个不同的来源，我们希望在专栏里面的文章，可以根据热度和发布时间进行排序，即热度高的放在前面，相同热度的文章，根据发布时间倒排
1. 模拟实现
针对上面这个场景，给出一个可以复现的代码实现，我们先定义一个ItemDO，表示专栏内部的文章，其中与排序相关的主要有两个字段，热度hot 和发布时间publishTime
public class ItemDO {
// msgId
private Integer msgId;
// 热度
private Integer hot;
// 发布时间， ms单位
private Long publishTime;
}
我们希望实现上面的排序，所以可直接让这个DO继承Compareable接口，内部实现排序的逻辑
@Data
public class ItemDO implements Comparable<ItemDO> {
private Integer msgId;
private Integer hot;
private Long publishTime;
@Override
public int compareTo(ItemDO o) {
if (hot < o.hot) {
return 1;
} else if (hot > o.hot) {
return -1;
}
if (o.getPublishTime() == 0) {
return -1;
}
if (publishTime == 0) {
return 1;
}
return (int) (o.getPublishTime() - publishTime);
}
}
看下我们上面的实现，我们在业务上已经能保证每个DO中的成员不会为null（因为直接从DB中获取，而db中不存null的字段）
首先根据sort进行排序，可以看到，hot大的，排在前面，hot小的往后排；如果hot相等，才会进入后面的时间比较；还特意加上了针对时间为0的特殊处理，然后捞了一批最近的数据，进行测试，发现一如预期，并没有什么问题
2. 坑在哪儿？
上面的实现，现在明确指出，有问题，会在什么地方呢？
return (int) (o.getPublishTime() - publishTime);
就在上面这一行，会有什么问题？看到类型转换，就会想到溢出的问题，如果两篇文章的发布时间，间隔长一点就会出现这个问题
文章a： 发布时间 2019-06-18 19:24:10 -> a = 1560857050000
文章b： 发布时间 2019-05-18 19:24:10 -> b = 1558178650000
a - b = 1560857050000 - 1558178650000 = 2678400000 > Integer.MAX_VALUE
所以说在时间跨度小的时候，没啥问题，但是时间跨度大一点，就会出现int溢出，导致compareTo的返回结果和我们预期的不一致
3. 修改
知道问题之后，就可以吭哧吭哧的修改了，方法一把ms转换成s再进行比较；方法二，用下面的比较方式
@Data
public class ItemDO implements Comparable<ItemDO> {
private Integer msgId;
private Integer hot;
private Long publishTime;
@Override
public int compareTo(ItemDO o) {
if (hot < o.hot) {
return 1;
} else if (hot > o.hot) {
return -1;
}
long sub = o.getPublishTime() - publishTime;
if (sub > 0) {
return 1;
} else if (sub < 0){
return -1;
} else {
return 0;
}
}
}
4. 测试验证
然后写几个简单的测试用例看一下是否和我们预期的一致
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
/**
* Created by @author yihui in 19:14 19/6/18.
*/
public class SortTest {
@Data
@NoArgsConstructor
@AllArgsConstructor
public static class ItemDO implements Comparable<ItemDO> {
private Integer msgId;
private Integer hot;
private Long publishTime;
@Override
public int compareTo(ItemDO o) {
if (hot < o.hot) {
return 1;
} else if (hot > o.hot) {
return -1;
}
long sub = o.getPublishTime() - publishTime;
if (sub > 0) {
return 1;
} else if (sub < 0){
return -1;
} else {
return 0;
}
}
}
@Data
@NoArgsConstructor
@AllArgsConstructor
public class ItemDOError implements Comparable<ItemDOError> {
private Integer msgId;
private Integer hot;
private Long publishTime;
@Override
public int compareTo(ItemDOError o) {
if (hot < o.hot) {
return 1;
} else if (hot > o.hot) {
return -1;
}
if (o.getPublishTime() == 0) {
return -1;
}
if (publishTime == 0) {
return 1;
}
return (int) (o.getPublishTime() - publishTime);
}
}
@Test
public void testSort() {
List<ItemDO> list = new ArrayList<>();
list.add(new ItemDO(1, 10, 100L));
list.add(new ItemDO(2, 10, 12333333333124L));
list.add(new ItemDO(3, 10, 0L));
list.add(new ItemDO(4, 3, 0L));
list.add(new ItemDO(5, 12, Long.MAX_VALUE));
list.add(new ItemDO(6, 10, (long) Integer.MAX_VALUE));
list.sort(null);
System.out.println(list);
List<ItemDOError> listError = new ArrayList<>();
listError.add(new ItemDOError(1, 10, 100L));
listError.add(new ItemDOError(2, 10, 12333333333124L));
listError.add(new ItemDOError(3, 10, 0L));
listError.add(new ItemDOError(4, 3, 0L));
listError.add(new ItemDOError(5, 12, Long.MAX_VALUE));
listError.add(new ItemDOError(6, 10, (long) Integer.MAX_VALUE));
listError.sort(null);
System.out.println(listError);
}
}
输出结果如下：
当然除了上面的比较的写法之外，更推荐的写法是直接使用 Long.compare(a, b)
5. 小结
虽然说在java中要想实现列表的排序比较简单，但是使用姿势一旦不对，同样会导致各种问题
在实现Compareable接口中的compareTo方法时
- 不推荐使用两个数值的差作为返回值（因为可能出现溢出）
- 推荐根据需要返回
1, 0, -1a.compareTo(b) == 1表示a往后排a.compareTo(b) == -1表示a往前排
- 数字的比较，推荐使用
Long.compare或者Integer.compare来实现