TreeMultiSet

基于TreeMap實現(xiàn)的支持可重復(fù)元素的TreeSet
github地址藻治，歡迎star

為什么要開發(fā)這個數(shù)據(jù)結(jié)構(gòu)

搞過java的人應(yīng)該都知道TreeSet，但是TreeSet是不支持重復(fù)元素的帝嗡。有人會說，那用ArrayList或LinkedList不就可以了嗎神妹？
確實雨饺，ArrayList或LinkedList天然不去重荐吉，可以滿足支持重復(fù)元素的需求。但是蝗拿，我不僅需要支持可重復(fù)元素晾捏，而且需要數(shù)據(jù)實時保持有序。
這里有人又會說了哀托，有序不很簡單么惦辛？我把數(shù)據(jù)插入到ArrayList或LinkedList中之后，調(diào)用sort不就完事了嗎仓手？
嗯胖齐，確實，如果你的列表不經(jīng)常發(fā)生變化（sort的次數(shù)非常非常少）嗽冒，那么你使用List+sort當(dāng)然沒問題咯呀伙。但是，如果數(shù)據(jù)是不斷發(fā)生變化的怎么辦呢添坊？
如果數(shù)據(jù)不斷發(fā)生變化剿另，而且又需要保證數(shù)據(jù)實時有序（比如有實時查詢最小和最大的需求），如果你使用List+sort的方式這樣的時間復(fù)雜度非常高：
大概是插入排序的思路，這樣的單次插入時間復(fù)雜度是O(n)雨女，如果有n個元素柬甥，則需要O(n²)嚼松。因此呢，如果我們要降低時間復(fù)雜度，就不能使用List滓技。
然后返劲，接下來又有人說了病苗，我直接用TreeMap似乎可以啊惩嘉。TreeMap的key是元素，value是key對應(yīng)元素出現(xiàn)的次數(shù)乱灵。這樣就可以滿足插入可重復(fù)且有序的需求了塑崖。
的的確確，這個確實可以大致滿足可重復(fù)且有序的需求痛倚。但是规婆，我這里舉幾個使用TreeMap來滿足可重復(fù)且有序需求的缺點：

1. 如果我們需要知道可重復(fù)元素集合的個數(shù)（重復(fù)元素算多個），使用TreeMap不能立馬且在O(1)時間復(fù)雜度之內(nèi)獲取到蝉稳，
   而需要for循環(huán)所有key抒蚜，然后計算所有value值之和。大致代碼如下：

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

這樣看起來是不是有點麻煩耘戚？獲取集合個數(shù)我們期望的應(yīng)該是下面這樣這樣簡潔（TreeMultiSet就能達(dá)到嗡髓，下面會介紹）：

    set.size();

2. 如果我們需要遍歷集合中的所有元素，重復(fù)元素需要遍歷多次（類似list的遍歷）收津。那么使用TreeMap來實現(xiàn)需要使用二重循環(huán)饿这，不太直觀。如下所示：

    for (Integer num : treeMap.keySet()) {
        int count = treeMap.get(num);
        while ((count--) > 0) {
            // 需要使用循環(huán)將num輸出count次
            System.out.println(num);
        }
    }

同樣撞秋，我們期望的應(yīng)該是一重循環(huán)搞定长捧，像下面這樣：

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

3. 如果我們需要刪除集合中指定個數(shù)的某個元素。舉個例子吻贿，集合[1, 2, 2, 3, 3串结，3]。我只想刪除兩個3舅列，TreeMap需要這么做：

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

同樣奉芦，我們期望的應(yīng)該是像下面這樣：

    set.remove(3, 2); // 第二個參數(shù)代表需要刪除的元素的個數(shù)

4. 如果我們需要往集合中添加指定數(shù)量的元素。舉個例子剧蹂，集合[1, 2, 2, 2, 4]，我們需要添加兩個4烦却，TreeMap需要這么做：

    treeMap.put(4, treeMap.getOrDefault(4, 0) + 2);

同樣宠叼，我們期望的應(yīng)該像下面這樣：

    set.add(4, 2); // 第二個參數(shù)代表需要插入的元素的個數(shù)

除此之外，TreeMap來實現(xiàn)可重復(fù)treeSet的功能還有一些不太優(yōu)雅的地方，這里就不一一列舉了冒冬。

因此伸蚯，基于以上原因，TreeMultiSet誕生了简烤。（不過聲明一下：不是重復(fù)造輪子剂邮，而是站在巨人的肩膀上，TreeMultiSet大部分是參考TreeSet來實現(xiàn)的横侦，
其實都是基于TreeMap挥萌，而TreeMap底層是通過紅黑樹(Red-Black-Tree)來實現(xiàn)的，這也正是TreeSet的remove操作可達(dá)到O(logN)時間復(fù)雜度的本質(zhì)原因枉侧，有興趣的同學(xué)可以去研究一下）

如何使用

gradle

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

allprojects {
    repositories {
        ...
        maven { url 'https://jitpack.io' }
    }
}

Step 2. Add the dependency in your app build.gradle:

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

功能列表

代碼演示

這里舉幾個覺得常用的一些方法的調(diào)用方式（當(dāng)然也可以直接閱讀TreeMultiSet源碼, 里頭有詳細(xì)的注釋)引瀑。

1) 新建一個自定義比較器的TreeMultiSet

    TreeMultiSet<Integer> set = new TreeMultiSet<>((o1, o2) -> o2 - o1); // 傳一個從大到小的比較器

2) foreach遍歷所有元素(包含重復(fù)元素)

    for (Integer num : set) {
        // TODO, 這里可輸出類似2, 2, 2, 3這樣的序列
    }

3) 獲取所有元素(包含重復(fù)元素)的正向迭代器

    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) 獲取所有元素的總個數(shù)(包含重復(fù)元素)

    set.size();

6) 獲取不同元素的個數(shù)

    set.diffElementSize();

7) 獲取第一個元素和最后一個元素

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

8) 添加指定數(shù)量的元素

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

9) 設(shè)置指定元素的數(shù)量

    set.setCount(2, 3); //設(shè)置集合里頭2的個數(shù)為3個

10) 獲取指定元素的個數(shù)

    set.count(2); //獲取2在集合中的個數(shù)

11) 刪除指定數(shù)量的元素

    set.remove(2, 3); //刪除3個2

12) 刪除指定數(shù)量的第一個元素

    set.pollFirst(2); //刪除2個第一個元素。如集合[1,1,1,2,2,3]榨馁，執(zhí)行這行代碼之后變成[1,2,2,3]

13) 刪除指定數(shù)量的最后一個元素

    set.pollLast(1); //刪除1個最后一個元素憨栽。如集合[1,1,1,2,3,3]，執(zhí)行這行代碼之后變成[1,1,1,2,2,3]

單元測試

已經(jīng)對TreeMultiSet的所有方法（包括構(gòu)造函數(shù)）都進(jìn)行了單元測試TreeMultiSetTest翼虫，測試覆蓋率達(dá)到100%屑柔。

Coverage

各種集合對比

說明，以下列舉的復(fù)雜度均指時間復(fù)雜度珍剑。并且以下插入刪除操作均指對中間元素的操作掸宛。同時，計算LinkedList的插入和刪除時間復(fù)雜度的時候考慮了查詢到要插入或刪除的位置的時間次慢。

由上表可以發(fā)現(xiàn)本庫實現(xiàn)的TreeMultiSet功能最強大旁涤，在保證可重復(fù)有序的情況下，持頻繁插入刪除操作的時間復(fù)雜度都可以達(dá)到O(log n)的級別迫像。當(dāng)然劈愚，應(yīng)該具體問題具體分析。比如闻妓，沒有remove中間某個元素且需要可重復(fù)元素有序的情況下菌羽，PriorityQueue(底層實現(xiàn)是堆)的性能最佳。

最后

覺得還不錯的話由缆，就點個star支持一下咯~