一个排序引发的BUG （下）-阿里云开发者社区

一个排序引发的BUG （下）

2022-04-28 121

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 一个排序引发的BUG （下）

来个例子演示一下：

左边是测试用例，右边是排序规则，下面是输出结果。

从输出结果可以看到，最终的 Filter 链取决于 list 的添加顺序。

这也就是 7757 这个 issues 说的：

list 的遍历顺序会影响到排序的顺序。

好，现在我们把排序顺序改回来，同样的测试用例再跑一次，就稳定了：

眼睛尖的朋友可能还发现了一个问题。

这个地方还有一次提交：

第一种判断：return o1.getSimpleName().compareTo(o2.getSimpleName())

第二种判断：return o1.getSimpleName().compareTo(o2.getSimpleName()) > 0 ? 1 : -1;

你说这是在干啥？

第一种判断还疏忽了这样的一种情况，包名不同但是类名相同的情况：

com.why.a.whyFilter

com.why.b.whyFilter

这个时候 o1.getSimpleName().compareTo(o2.getSimpleName()) 返回的是 0。

返回 0 会发生啥？

直接吞掉一个 Filter 你信不信？

比如你的集合是 HashSet，或者是 TreeMap。

这就巧了，Dubbo 用的就是 TreeMap。

来个测试用例演示一下。

如果采用第一种判断，最后 TreeMap 里面只有一个 Filter 了：

如果采用第二种判断，最后 TreeMap 里面会有两个 Filter ：

细节，魔鬼都在细节里面。

哎呀，真的是防不胜防啊。

好了，比较器我就说完了，但是你发现没有，我到现在都还没给你说排序过程不稳定这个 BUG 到底是啥，只是给你引申了一个其他的 BUG 出来。

莫慌，这不是我还没想好怎么给你描述嘛。

这个过程其实比较复杂，涉及到 Timsort 排序方法，就这方法就得另起一篇文章才能说清楚。

所以，我换了一个思路，主要给你看比较的过程，至于这个过程背后的原因。

就是 Timsort 在搞鬼，欢迎你自己去探索一番。

那过程是啥呢？

我在比较方法的入口处加上这样的输出语句：

测试用例是这样的：

@Test
public void whyTest(){
    List<Class> filters = new ArrayList<>();
    filters.add(Filter4.class);
    filters.add(Filter3.class);
    filters.add(Filter2.class);
    filters.add(Filter1.class);
    filters.add(Filter5.class);
    Collections.sort(filters, ActivateComparator.COMPARATOR);
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < filters.size(); i++) {
        builder.append(filters.get(i).getSimpleName()).append("->");
    }
    System.out.println(builder.toString());
}