TreeMultiSet

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

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

搞過java的人應(yīng)該都知道TreeSet，但是TreeSet是不支持重復(fù)元素的。有人會(huì)說，那用ArrayList或LinkedList不就可以了嗎？
確實(shí)，ArrayList或LinkedList天然不去重，可以滿足支持重復(fù)元素的需求。但是，我不僅需要支持可重復(fù)元素，而且需要數(shù)據(jù)實(shí)時(shí)保持有序。
這里有人又會(huì)說了，有序不很簡(jiǎn)單么？我把數(shù)據(jù)插入到ArrayList或LinkedList中之后，調(diào)用sort不就完事了嗎？
嗯，確實(shí)，如果你的列表不經(jīng)常發(fā)生變化（sort的次數(shù)非常非常少），那么你使用List+sort當(dāng)然沒問題咯。但是，如果數(shù)據(jù)是不斷發(fā)生變化的怎么辦呢？
如果數(shù)據(jù)不斷發(fā)生變化，而且又需要保證數(shù)據(jù)實(shí)時(shí)有序（比如有實(shí)時(shí)查詢最小和最大的需求），如果你使用List+sort的方式這樣的時(shí)間復(fù)雜度非常高：
大概是插入排序的思路，這樣的單次插入時(shí)間復(fù)雜度是O(n)，如果有n個(gè)元素，則需要O(n²)。因此呢，如果我們要降低時(shí)間復(fù)雜度，就不能使用List。
然后，接下來又有人說了，我直接用TreeMap似乎可以啊。TreeMap的key是元素，value是key對(duì)應(yīng)元素出現(xiàn)的次數(shù)。這樣就可以滿足插入可重復(fù)且有序的需求了。
的的確確，這個(gè)確實(shí)可以大致滿足可重復(fù)且有序的需求。但是，我這里舉幾個(gè)使用TreeMap來滿足可重復(fù)且有序需求的缺點(diǎn)：

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

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

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

    set.size();

2. 如果我們需要遍歷集合中的所有元素，重復(fù)元素需要遍歷多次（類似list的遍歷）。那么使用TreeMap來實(shí)現(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. 如果我們需要?jiǎng)h除集合中指定個(gè)數(shù)的某個(gè)元素。舉個(gè)例子，集合[1, 2, 2, 3, 3，3]。我只想刪除兩個(gè)3，TreeMap需要這么做：

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

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

    set.remove(3, 2); // 第二個(gè)參數(shù)代表需要?jiǎng)h除的元素的個(gè)數(shù)

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

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

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

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

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

因此，基于以上原因，TreeMultiSet誕生了。（不過聲明一下：不是重復(fù)造輪子，而是站在巨人的肩膀上，TreeMultiSet大部分是參考TreeSet來實(shí)現(xiàn)的，
其實(shí)都是基于TreeMap，而TreeMap底層是通過紅黑樹(Red-Black-Tree)來實(shí)現(xiàn)的，這也正是TreeSet的remove操作可達(dá)到O(logN)時(shí)間復(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'
}

功能列表

代碼演示

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

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

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

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

    set.size();

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

    set.diffElementSize();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

單元測(cè)試

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

Coverage

各種集合對(duì)比

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

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

最后

覺得還不錯(cuò)的話，就點(diǎn)個(gè)star支持一下咯~