求助一个自己写程序中的关于TreeSet同时去重和按加入顺序存储的bug。

昨天在写一个题目其中一块的任务是:将一些字符串去重,并且按给你时候的顺序输出出来,我没有想到用LinkedHashSet,第一想到的是使用TreeSet,故构造一个带comparator的treeset,让俩东西相等时候输出0,表示重复,那么treeset应该会不添加这个新元素,其余情况输出1表示直接添加到末尾,不做交换。然鹅实际情况与我想象的不一样,重复元素出现在特定位置时候无法去除(这一部分我通过debug 自己定义的compartatoro1,o2进行了对比已经证实comparator书写正确,是没有进行全遍历而造成的无法识别重复)。为了简单复现这个问题,我书写了加入简单integer类型的treeset,代码如下

public class Tree {

    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                // TODO Auto-generated method stub
                if(o1.equals(o2))
                {
                    return 0;
                }
                return 1;
            }
        }); 
        treeSet.add(1);
        treeSet.add(2);
        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(4);
        treeSet.add(1);
        treeSet.add(5);
        treeSet.add(7);
        treeSet.add(1);
        treeSet.add(6);
        treeSet.add(7);
        treeSet.add(1);
        for(int i : treeSet)
        {
            System.out.println(i);
        }
    }
}

这个代码也许你以为会输出1,2,3,4,5,7,6
但是实际情况是
1
2
3
1
4
5
7
6
图片说明
根据debug结果可以发现在加入第二个1时候(也就是加入这个1之前是1,2,3),这时候我认为加入1之后o1一直作为1,去和剩余3个元素作对比,如果重复就不会添加,然鹅实际情况再一次不同,o1一直作为1,也就是新添加的元素,只与2,3做了对比(也就是o2元素只遍历了2,3这两个)就结束了,程序发现并没有重复,因为根本就没看开头位置的东西是1,当然认为无重复,就把1又加了进去。
这个同理可以验证到字符串上面,并且更多的试验表明在总长超过6之后下标为2的元素也不会被o2遍历到。
小弟长时间自己思考,百度源码结论都应该是冒泡逐个遍历,但是并没能解决,还请各位老师指点一二。非常感谢!

2个回答

因为treeSet的存储是使用treemap来实现的 结构为二叉树 你的例子中 在添加了 123三个数之后 根结点为2 左节点(比父节点小)为1 右节点为3 在这个时候插入1这个数 比较器先与2判断 返回1(新插入的1比2大) 则继续与3比较 也返回1 并没有去按照你所想的 先与1比较

也就是说 你所写的这个比较方法 插入同样的数 可能会因为不同的插入顺序 导致不同的结果。

weixin_42546808
weixin_42546808 老师你好,谢谢回答我的问题,我认真思考后觉得你说的在理,但是有个疑问:1,2,3进去之后是2为根节点而不是1为根节点吗,产生这样是因为红黑树的左右旋转关系吗
6 个月之前 回复

楼上说得差不多,你返回正数的时候就证明o1比o2大,则继续和大数比较,若你要实现功能的话,就需要多加判断条件,若o1>o2返回正数,o1<o2返回负数即可

weixin_42546808
weixin_42546808 回复weixin_44318483: 明白了 谢谢老师指点
6 个月之前 回复
weixin_44318483
weixin_44318483 回复weixin_42546808: 貌似也能实现,在每一次加入要和TreeSet里所有元素进行比较,也就是在compare里对treeset进行遍历比较,相等返回0,不等返回正数,不过效率低,毕竟每一次加入元素都要遍历集合,不建议使用
6 个月之前 回复
weixin_44318483
weixin_44318483 你硬要这么做,要写包装类包装treeset,然后重写toString方法,你单纯靠重写compare方法来顺序输出你的顺序估计实现不了的,TreeSet就是为了按某个规则顺序输出的,你却要打乱它的规则,等于你硬要用不适合这情况的方法来解决问题,显然会复杂或是多此一举
6 个月之前 回复
weixin_42546808
weixin_42546808 o1<o2就破坏了这个规则
6 个月之前 回复
weixin_42546808
weixin_42546808 老师你好,可是我当时做题的时候要求我按照输入顺序输出,我并不想改变他的排序,这边先假设我就只想用TreeSet解决(当时我并没有想到LinkedHashSet),哦
6 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!