大數(shù)據(jù)List去重

MaxList模塊主要是對Java集合大數(shù)據(jù)去重的相關(guān)介紹外遇。

背景: 最近在項目中遇到了List集合中的數(shù)據(jù)要去重注簿，大概一個2500萬的數(shù)據(jù)，開始存儲在List中臀规，需要跟一個2萬的List去去重滩援。

直接兩個List去重

說到去重，稍微多講一點啊塔嬉，去重的時候有的小伙伴可能直接對2500萬List foreach循環(huán)后直接刪除,
其實這種是錯誤的(java.util.ConcurrentModificationException)玩徊，大家可以自己去試一下；(注: for循環(huán)遍歷刪除不報錯谨究，但是效率低恩袱，不推薦使用)
首先你需要去看下foreach和迭代器的實現(xiàn)。foreach的實現(xiàn)就是用到了迭代器胶哲，所以你在foreach的時候?qū)ist進(jìn)行刪除操作畔塔，
迭代器Iterator無法感知到list刪除了，所以會報錯鸯屿。直接貼代碼解釋下澈吨。

ArrayList中Iterator的實現(xiàn):

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

通過上述的ArrayList里面的Iterator迭代器的實現(xiàn)我們可以看到:
基本上ArrayList采用size屬性來維護(hù)自已的狀態(tài)，而Iterator采用cursor來來維護(hù)自已的狀態(tài)寄摆。
當(dāng)你直接在foreach里面對list進(jìn)行刪除操作谅辣，size出現(xiàn)變化時，cursor并不一定能夠得到同步婶恼，除非這種變化是Iterator主動導(dǎo)致的桑阶。(調(diào)用list.iterator()方法的原因)

從上面的代碼可以看到當(dāng)Iterator.remove方法導(dǎo)致ArrayList列表發(fā)生變化時，他會更新cursor來同步這一變化勾邦。但其他方式導(dǎo)致的ArrayList變化蚣录，Iterator是無法感知的。ArrayList自然也不會主動通知Iterator們眷篇，那將是一個繁重的工作萎河。Iterator到底還是做了努力：為了防止?fàn)顟B(tài)不一致可能引發(fā)的無法設(shè)想的后果，Iterator會經(jīng)常做checkForComodification檢查，以防有變公壤。如果有變换可，則以異常拋出，所以就出現(xiàn)了上面的異常厦幅。
如果對正在被迭代的集合進(jìn)行結(jié)構(gòu)上的改變（即對該集合使用add沾鳄、remove或clear方法），那么迭代器就不再合法（并且在其后使用該迭代器將會有ConcurrentModificationException異常被拋出）.
如果使用迭代器自己的remove方法确憨，那么這個迭代器就仍然是合法的译荞。

public static void deWeightList(List<String> des, List<String> sourse){
        if(sourse == null || sourse.size() <= 0){
            return;
        }l
        Iterator<String> listStr = sourse.iterator();
        while (listStr.hasNext()){
            String item = listStr.next();
            for (String ditem: des) {
                if(item.equals(ditem)){
                    listStr.remove();
                    break;
                }
            }

        }
        logger.info("after deWight list size: " + sourse.size());
}

List結(jié)合Set去重

public static void deWeightList(Set<String> des, List<String> sourse) {
        if (sourse == null || sourse.size() <= 0) {
            return;
        }
        Iterator<String> listStr = sourse.iterator();
        while (listStr.hasNext()) {
            String item = listStr.next();
            if (des.contains(item)) {
                listStr.remove();
            }
        }
        logger.info("after deWight list size: " + sourse.size());
}

List結(jié)合Set去重(不是直接對list進(jìn)行刪除，而是組裝新list休弃，考慮到list刪除效率低)

public static void deWeightListByNewList(Set<String> des, List<String> sourse) {
    if (sourse == null || sourse.size() <= 0) {
        return;
    }
    Iterator<String> listStr = sourse.iterator();
    List<String> existList = new ArrayList<String>();
    while (listStr.hasNext()) {
        String item = listStr.next();
        if(!des.contains(item)){
            //TODO 對去重后的數(shù)據(jù)進(jìn)行邏輯操作吞歼，不一定要刪除，可以換個思路（是否可以直接邏輯操作塔猾，不一定非要再把數(shù)據(jù)寫進(jìn)集合后篙骡，然后遍歷集合在進(jìn)行邏輯操作）
            existList.add(item); //改成添加進(jìn)新的list，考慮到list的刪除效率慢(非要得到刪除后的集合的情況下丈甸，否則走else)
        }
//            if (des.contains(item)) {
//                //listStr.remove(); //考慮到list的刪除效率慢糯俗，此種方法對于大數(shù)據(jù)集合來說不合適
//            }
    }
    sourse.clear();
    sourse = existList;
    logger.info("after deWight list size: " + sourse.size());
}

遍歷過程中去重

個人最為推薦的一種,因為效率最高，也能達(dá)到功能的需要睦擂。

for (String item: maxArrayList) {
    if(testSet.contains(item)){
        //TODO
    }
}

測試結(jié)果如下


下面是1000萬的list和20000的list去重兩種方式所花的時間,可以看出使用set去重的效率要高很多得湘。

1.list結(jié)合list去重時間:
14:52:02,408 INFO  [RunTest:37] start test list:17-11-07 14:52:02
14:59:49,828 INFO  [ListUtils:66] after deWight list size: 9980000
14:59:49,829 INFO  [RunTest:39] end test list:17-11-07 14:59:49

2.list結(jié)合set去重時間:
14:59:53,226 INFO  [RunTest:44] start test set:17-11-07 14:59:53
15:01:30,079 INFO  [ListUtils:80] after deWight list size: 9980000
15:01:30,079 INFO  [RunTest:46] end test set:17-11-07 15:01:30

下面是2500萬的list和20000的list去重兩種方式所花的時間,可以看出使用set去重的效率要更加的高，(數(shù)據(jù)量越大越明顯)顿仇。
個人對set的大小為1500萬也進(jìn)行了測試淘正，方案3,4的效率也是非常的高。

1.list結(jié)合list去重時間:
15:17:47,114 INFO  [RunTest:35] start test list, start time: 17-11-07 15:17:47
15:49:04,876 INFO  [ListUtils:57] after deWight list size: 24980000
15:49:04,877 INFO  [RunTest:39] end test list, end time: 17-11-07 15:49:04

2.list結(jié)合set去重時間:
15:49:17,842 INFO  [RunTest:44] start test set, start time: 17-11-07 15:49:17
15:53:22,716 INFO  [ListUtils:71] after deWight list size: 24980000
15:53:22,718 INFO  [RunTest:48] end test set, end time: 17-11-07 15:53:22

3. List結(jié)合Set去重(不是直接對list進(jìn)行刪除臼闻，而是組裝新list鸿吆，考慮到list刪除效率低)
17:18:44,583 INFO  [RunTest:57] start test set, start time: 17-11-22 17:18:44
17:18:54,628 INFO  [ListUtils:92] after deWight list size: 23500000
17:18:54,628 INFO  [RunTest:61] end test set, end time: 17-11-22 17:18:48

4.遍歷過程中結(jié)合set去重:(個人最為推薦的原因之一，效率高到令人爽到不行)
15:17:45,762 INFO  [RunTest:24] start test foreach list directly, start time: 17-11-07 15:17:45
15:17:47,114 INFO  [RunTest:32] end test foreach list directly, end time: 17-11-07 15:17:47

總結(jié)

通過上述測試我們可以看出述呐，有時候我們排重的時候伞剑，不一定要拍完重再對排重后的數(shù)據(jù)進(jìn)行遍歷，可以在遍歷的過程中進(jìn)行排重市埋，注意用來排重的那個集合放到Set中，
可以是HashSet,或者其他Set(推薦使用HashSet),因為Set的contains效率更高恕刘，比list高很多缤谎。

然后考慮到如果非要拿到去重后的list，考慮使用方案3《List結(jié)合Set去重(不是直接對list進(jìn)行刪除褐着，而是組裝新list坷澡，考慮到list刪除效率低)》，通過測試含蓉，這種方法效率也是非常的高频敛。
與方案4相比项郊，稍微慢一點點。

對于上述方案1斟赚，測試也使用過組裝新list的方式着降，而不是list.remove。但是效率還是比較慢拗军。

這是實際工作中總結(jié)出來的經(jīng)驗任洞。希望對大家有幫助！
歡迎大家來交流发侵！

Github地址

下載地址(JavaBigData)

原博客地址

tommyyang的博客