Java TreeMultiSet-为什么要开发这个数据结构???

Java架构没有996
• 阅读 1262

TreeMultiSet

基于TreeMap实现的支持可重复元素的TreeSet

搞过java的人应该都知道TreeSet,但是TreeSet是不支持重复元素的。有人会说,那用ArrayList或LinkedList不就可以了吗? 确实,ArrayList或LinkedList天然不去重,可以满足支持重复元素的需求。但是,我不仅需要支持可重复元素,而且需要数据实时保持有序。 Java TreeMultiSet-为什么要开发这个数据结构???

这里有人又会说了,有序不很简单么?我把数据插入到ArrayList或LinkedList中之后,调用sort不就完事了吗? 嗯,确实,如果你的列表不经常发生变化(sort的次数非常非常少),那么你使用List+sort当然没问题咯。但是,如果数据是不断发生变化的怎么办呢?【参考文献】

如果数据不断发生变化,而且又需要保证数据实时有序(比如有实时查询最小和最大的需求),如果你使用List+sort的方式这样的时间复杂度非常高: 大概是插入排序的思路,这样的单次插入时间复杂度是O(n)O(n),如果有n个元素,则需要O(n^2)O(n 2 )。因此呢,如果我们要降低时间复杂度,就不能使用List。


接下来又有人说了,我直接用TreeMap似乎可以啊。TreeMap的key是元素,value是key对应元素出现的次数。这样就可以满足插入可重复且有序的需求了。【参考文献】 的的确确,这个确实可以大致满足可重复且有序的需求。但是,我这里举几个使用TreeMap来满足可重复且有序需求的缺点:

如果我们需要知道可重复元素集合的个数(重复元素算多个),使用TreeMap不能立马且在O(1)O(1)时间复杂度之内获取到, 而需要for循环所有key,然后计算所有value值之和。大致代码如下:

 int size = 0;
    for (Integer num : treeMap.keySet()) {
        size += treeMap.get(num);
    }

这样看起来是不是有点麻烦?获取集合个数我们期望的应该是下面这样这样简洁(TreeMultiSet就能达到,下面会介绍):

    set.size();

如果我们需要遍历集合中的所有元素,重复元素需要遍历多次(类似list的遍历)。那么使用TreeMap来实现需要使用二重循环,不太直观。如下所示:

    for (Integer num : treeMap.keySet()) {
        int count = treeMap.get(num);
        while ((count--) > 0) {
            // 需要使用循环将num输出count次
            System.out.println(num);
        }
    }

同样,我们期望的应该是一重循环搞定,像下面这样:

    for (Integer num : set) {
        System.out.println(num);
    }

如果我们需要删除集合中指定个数的某个元素。举个例子,集合[1, 2, 2, 3, 3, 3]。我只想删除两个3,TreeMap需要这么做:

    if (treeMap.containsKey(3)) {
        treeMap.put(2, treeMap.get(3) - 2);
    }

同样,我们期望的应该是像下面这样:

    set.remove(3, 2); // 第二个参数代表需要删除的元素的个数
//如果我们需要往集合中添加指定数量的元素。举个例子,集合[1, 2, 2, 2, 4],我们需要添加两个4,TreeMap需要这么做:
//加入Java开发交流君样:756584822一起吹水聊天
    treeMap.put(4, treeMap.getOrDefault(4, 0) + 2);
//同样,我们期望的应该像下面这样:


    set.add(4, 2); // 第二个参数代表需要插入的元素的个数

除此之外,TreeMap来实现可重复TreeSet的功能还有一些不太优雅的地方,这里就不一一列举了。

因此,基于以上原因,TreeMultiSet诞生了。(不过声明一下:不是重复造轮子,而是站在巨人的肩膀上,TreeMultiSet大部分是参考TreeSet来实现的,【参考文献】 其实都是基于TreeMap,而TreeMap底层是通过红黑树(Red-Black-Tree)来实现的,这也正是TreeSet的remove操作可达到O(logN)时间复杂度的本质原因,有兴趣的同学可以去研究一下)

如何使用

gradle

Step 1. Add the JitPack repository in your root build.gradle at the end of repositories:


allprojects {
    repositories {
        ...
        maven { url 'https://jitpack.io' }
    }
}//加入Java开发交流君样:756584822一起吹水聊天
Step 2. Add the dependency in your app build.gradle:


dependencies {
    implementation 'com.github.yuruiyin:TreeMultiSet:1.0.1'
}

功能列表

无参构造函数 TreeMultiSet()
带比较器参数的构造函数 TreeMultiSet(Comparator<? super E> comparator)
带集合参数构造函数 TreeMultiSet(Collection<? extends E> c)
带SortedSet参数构造函数 TreeMultiSet(SortedSet<E> s)
返回所有元素(重复元素要next多次)的正向迭代器 Iterator<E> iterator()
返回所有元素(重复元素要next多次)的反向迭代器 Iterator<E> descendingIterator()
返回所有不相同元素的正向迭代器 Iterator<E> diffIterator()
返回所有不相同元素的反向迭代器 Iterator<E> diffDescendingIterator()
返回逆序Set NavigableSet<E> descendingSet()
返回指定头尾元素的连续子集 NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
返回头部连续子集 NavigableSet<E> headSet(E toElement, boolean inclusive)
返回尾部连续子集 NavigableSet<E> tailSet(E fromElement, boolean inclusive)
返回比较器 Comparator<? super E> comparator()
返回总的元素个数(重复算多个) int size()
返回不同的元素个数 int diffElementSize()
获取第一个元素 E first()
获取最后一个元素 E last()
判断是否包含某个元素 boolean contains(Object o)
清空所有元素 void clear()
添加指定元素(1个) boolean add(E e)
添加指定个数的特定元素 boolean add(E e, int count)
设置指定元素的数量 void setCount(E e, int count)
获取指定元素的个数 int count(E e)
删除1个指定元素 boolean remove(Object e)
删除count个指定元素 boolean remove(E e, int count)
删除所有的指定元素(不同于clear()) boolean removeAll(Object e)
返回比给定元素严格小的最大元素 E lower(E e)
返回小于或等于给定元素的最大元素 E floor(E e)
返回比给定元素严格大的最小元素 E higher(E e)
返回大于或等于给定元素的最小元素 E ceiling(E e)
删除指定count的第一个元素 E pollFirst(int count)
删除1个第一个元素 E pollFirst()
删除所有count的第一个元素 E pollFirstAll()
删除1个最后一个元素 E pollLast()
删除指定count的最后一个元素 E pollLast(int count)
删除所有count的最后一个元素 E pollLastAll()
TreeMultiSet浅拷贝 Object clone()

代码演示

这里举几个觉得常用的一些方法的调用方式

1) 新建一个自定义比较器的TreeMultiSet

    TreeMultiSet<Integer> set = new TreeMultiSet<>((o1, o2) -> o2 - o1); // 传一个从大到小的比较器

2) foreach遍历所有元素(包含重复元素)

    for (Integer num : set) {
        // TODO, 这里可输出类似2, 2, 2, 3这样的序列
    }

3) 获取所有元素(包含重复元素)的正向迭代器

    Iterator<Integer> iterator = set.iterator();
    while (iterator.hasNext()) {
        arr[i++] = iterator.next();
    }

4) 获取不同元素的正向迭代器

    Iterator<Integer> diffIterator = set.diffIterator();
    while (diffIterator.hasNext()) {
        arr[i++] = diffIterator.next();
    }

5) 获取所有元素的总个数(包含重复元素)

    set.size();

6) 获取不同元素的个数

    set.diffElementSize();

7) 获取第一个元素和最后一个元素

    set.first();
    set.last();

8) 添加指定数量的元素

    set.add(2, 3); //往集合里头添加3个2

9) 设置指定元素的数量

    set.setCount(2, 3); //设置集合里头2的个数为3个

10) 获取指定元素的个数

    set.count(2); //获取2在集合中的个数

11) 删除指定数量的元素

    set.remove(2, 3); //删除3个2

12) 删除指定数量的第一个元素

 set.pollFirst(2); //删除2个第一个元素。如集合[1,1,1,2,2,3],执行这行代码之后变成[1,2,2,3]

13) 删除指定数量的最后一个元素

    set.pollLast(1); //删除1个最后一个元素。如集合[1,1,1,2,3,3],执行这行代码之后变成[1,1,1,2,2,3]

单元测试

已经对TreeMultiSet的所有方法(包括构造函数)都进行了单元测试TreeMultiSetTest,测试覆盖率达到100%。

各种集合对比

说明,以下列举的复杂度均指时间复杂度。并且以下插入删除操作均指对中间元素的操作。同时,计算LinkedList的插入和删除时间复杂度的时候考虑了查询到要插入或删除的位置的时间。 Java TreeMultiSet-为什么要开发这个数据结构???

最新2021整理收集的一些高频面试题(都整理成文档),有很多干货,包含mysql,netty,spring,线程,spring cloud、jvm、源码、算法等详细讲解,也有详细的学习规划图,面试题整理等,需要获取这些内容的朋友请加Q君样:756584822 Java TreeMultiSet-为什么要开发这个数据结构???

Java TreeMultiSet-为什么要开发这个数据结构???

点赞
收藏
评论区
推荐文章
技术小男生 技术小男生
4个月前
linux环境jdk环境变量配置
1:编辑系统配置文件vi/etc/profile2:按字母键i进入编辑模式,在最底部添加内容:JAVAHOME/opt/jdk1.8.0152CLASSPATH.:$JAVAHOME/lib/dt.jar:$JAVAHOME/lib/tools.jarPATH$JAVAHOME/bin:$PATH3:生效配置
光头强的博客 光头强的博客
4个月前
Java面向对象试题
1、请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
4个月前
css问题
1、在IOS中图片不显示(给图片加了圆角或者img没有父级)<div<imgsrc""/</divdiv{width:20px;height:20px;borderradius:20px;overflow:h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
小森森 小森森
4个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本欢迎添加左边的微信一起探讨!项目地址:(https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n)\2.Bug修复更新日历2.情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意),\\和注意
Stella981 Stella981
1年前
50道Java集合经典面试题(收藏版)
前言来了来了,50道Java集合面试题来了!1\.Arraylist与LinkedList区别可以从它们的底层数据结构、效率、开销进行阐述哈ArrayList是数组的数据结构,LinkedList是链表的数据结构。随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而
Wesley13 Wesley13
1年前
Java入门第五篇:Java集合框架的Collection、List、Set、Map接口
【java的集合框架】 Collection:      1.List        ①ArrayList        ②LinkedList      2.set        ①HashSet        ②LinkedHashSet        ③TreeSetMap:       1.HashMap 
Wesley13 Wesley13
1年前
Java集合面试题
CollectionSet和hashCode以及equals方法的联系Set内存放的元素为什么不可以重复,内部是如何保证和实现的?List和Set区别List和Map区别Arraylist与LinkedList区别ArrayList与Vector区别Arraylist与LinkedList默认空间是
Wesley13 Wesley13
1年前
Java 集合线程安全
线程不安全的的集合有(HashSet,TreeSet,ArrayList,ArrayDeque,LinkedList,HashMap,TreeMap);线程安全的集合有(Vector,HashTable);Java(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Flib.csd
Stella981 Stella981
1年前
HashSet和TreeSet
 Set是java中一个不包含重复元素的collection。更正式地说,set不包含满足e1.equals(e2)的元素对e1和e2,并且最多包含一个null元素。正如其名称所暗示的,此接口模仿了数学上的_set_抽象。HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的子接口Sor
Stella981 Stella981
1年前
ArrayList源码分析(JDK1.8)
概述ArrayList底层是基于 数组实现的,并且支持 动态扩容 的动态数组(变长的集合类)。ArrayList允许空值和重复的元素,当向ArrayList中添加元素数量大于其底层数组容量时,会通过 扩容机制 重新生成一个容量更大的数组。另外,由于ArrayList底层数据结构是数组,所以保证了在O(1)复杂度下完成随机查