列表排序,我们可以说是用的比较多了,写起来也很溜,继承Comparable
接口,实现compareTo
方法,然后直接使用java.util.List#sort
即可
虽说如此简单,今天却是一脚踩进去,花了不少时间才爬出来,下面复盘一下这个现场
I. 排序场景复现
背景比较简单,做一个新闻的聚合专栏,专栏内部的文章可以来自各个不同的来源,我们希望在专栏里面的文章,可以根据热度和发布时间进行排序,即热度高的放在前面,相同热度的文章,根据发布时间倒排
1. 模拟实现
针对上面这个场景,给出一个可以复现的代码实现,我们先定义一个ItemDO
,表示专栏内部的文章,其中与排序相关的主要有两个字段,热度hot
和发布时间publishTime
1 2 3 4 5 6 7 8
| public class ItemDO { private Integer msgId; private Integer hot; private Long publishTime; }
|
我们希望实现上面的排序,所以可直接让这个DO继承Compareable
接口,内部实现排序的逻辑
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
| @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. 坑在哪儿?
上面的实现,现在明确指出,有问题,会在什么地方呢?
1
| return (int) (o.getPublishTime() - publishTime);
|
就在上面这一行,会有什么问题?看到类型转换,就会想到溢出的问题,如果两篇文章的发布时间,间隔长一点就会出现这个问题
1 2 3 4 5
| 文章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再进行比较;方法二,用下面的比较方式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| @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. 测试验证
然后写几个简单的测试用例看一下是否和我们预期的一致
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor; import org.junit.Test;
import java.util.ArrayList; import java.util.List;
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); } }
|
输出结果如下:
5. 小结
虽然说在java中要想实现列表的排序比较简单,但是使用姿势一旦不对,同样会导致各种问题
在实现Compareable
接口中的compareTo
方法时
- 不推荐使用两个数值的差作为返回值(因为可能出现溢出)
- 推荐根据需要返回
1, 0, -1
a.compareTo(b) == 1
表示a往后排
a.compareTo(b) == -1
表示a往前排
II. 其他
一灰灰的个人博客,记录所有学习和工作中的博文,欢迎大家前去逛逛
2. 声明
尽信书则不如,已上内容,纯属一家之言,因个人能力有限,难免有疏漏和错误之处,如发现bug或者有更好的建议,欢迎批评指正,不吝感激
3. 扫描关注
一灰灰blog
知识星球