Collections.sort引发的线上问题及原理研究

目录

一、问题重现

二、Arrays.sort源码分析

三、TimSort

1、TimSort简介

2、TimSort原理

1）、二分插入排序

2）、minRunLength

3）、do-while循环

3、TimSort异常案例分析

四、总结

五、参考

一、问题重现

@Data
public class BusinessApplyDto implements Comparable<BusinessApplyDto>, Serializable {

    private static final long serialVersionUID = 7697030805482359129L;

    private String period;

    private Long businessId;

    @Override
    public int compareTo(BusinessApplyDto target) {
        String currentNo = this.period;
        String targetNo = target.getPeriod();
        if (currentNo == null) {
            return -1;
        } else if (targetNo == null) {
            return 1;
        }
        int sort = currentNo.compareTo(targetNo);
        if (sort == 0) {
            if (this.businessId == null) {
                return 1;
            } else if (target.businessId == null) {
                return -1;
            }
            return this.businessId.compareTo(target.businessId);
        }
        return -sort;
    }
}

        先仔细看下上面的代码，BusinessApplyDto实现了一个Comparable，然后重写了compareTo方法，compareTo方法通过比较两个字段的值来确定两个BusinessApplyDto的大小。然而compareTo方法过于复杂，初看代码不容易发现有bug，甚至上线后运行一段时间也不会有问题，因为如果没有特定的数据触发bug，线上一直都能正常运行。但是如果用下面数据进行运行，则会发生异常。

public class MainTest {

    public static void main(String[] args) {
        List<BusinessApplyDto> list = new ArrayList<>();
        BusinessApplyDto businessApplyDto1 = new BusinessApplyDto();
        businessApplyDto1.setPeriod("20210927");
        businessApplyDto1.setBusinessId(5L);
        list.add(businessApplyDto1);

        BusinessApplyDto businessApplyDto2 = new BusinessApplyDto();
        businessApplyDto2.setPeriod("20210927");
        list.add(businessApplyDto2);

        BusinessApplyDto businessApplyDto3 = new BusinessApplyDto();
        businessApplyDto3.setPeriod("20210927");
        list.add(businessApplyDto3);

        BusinessApplyDto businessApplyDto4 = new BusinessApplyDto();
        businessApplyDto4.setPeriod("20210927");
        list.add(businessApplyDto4);

        BusinessApplyDto businessApplyDto5 = new BusinessApplyDto();
        businessApplyDto5.setPeriod("20210927");
        list.add(businessApplyDto5);

        BusinessApplyDto businessApplyDto6 = new BusinessApplyDto();
        businessApplyDto6.setPeriod("20210927");
        list.add(businessApplyDto6);

        BusinessApplyDto businessApplyDto7 = new BusinessApplyDto();
        businessApplyDto7.setPeriod("20210927");
        list.add(businessApplyDto7);

        BusinessApplyDto businessApplyDto8 = new BusinessApplyDto();
        businessApplyDto8.setPeriod("20210927");
        businessApplyDto8.setBusinessId(2L);
        list.add(businessApplyDto8);

        BusinessApplyDto businessApplyDto9 = new BusinessApplyDto();
        businessApplyDto9.setPeriod("20210927");
        list.add(businessApplyDto9);

        BusinessApplyDto businessApplyDto10 = new BusinessApplyDto();
        businessApplyDto10.setPeriod("20210927");
        list.add(businessApplyDto10);

        BusinessApplyDto businessApplyDto11 = new BusinessApplyDto();
        businessApplyDto11.setPeriod("20210927");
        list.add(businessApplyDto11);

        BusinessApplyDto businessApplyDto12 = new BusinessApplyDto();
        businessApplyDto12.setPeriod("20210927");
        list.add(businessApplyDto12);

        BusinessApplyDto businessApplyDto13 = new BusinessApplyDto();
        businessApplyDto13.setPeriod("20210927");
        list.add(businessApplyDto13);

        BusinessApplyDto businessApplyDto14 = new BusinessApplyDto();
        businessApplyDto14.setPeriod("20210927");
        list.add(businessApplyDto14);

        BusinessApplyDto businessApplyDto15 = new BusinessApplyDto();
        businessApplyDto15.setPeriod("20210927");
        list.add(businessApplyDto15);

        BusinessApplyDto businessApplyDto16 = new BusinessApplyDto();
        businessA