search

MaxList以及Set模块

MaxList模块主要是对Java集合大数据去重的相关介绍。

背景: 最近在项目中遇到了List集合中的数据要去重，大概一个2500万的数据，开始存储在List中，需要跟一个2万的List去去重。

hashtag
直接两个List去重

说到去重，稍微多讲一点啊，去重的时候有点小伙伴可能直接对2500万List foreach循环后直接删除,其实这种是错误的(java.util.ConcurrentModificationException)，大家可以自己去试一下；(注: for循环遍历删除不报错，但是效率低，不推荐使用)首先你需要去看下foreach和迭代器的实现。foreach的实现就是用到了迭代器，所以你在foreach的时候对list进行删除操作，迭代器Iterator无法感知到list删除了，所以会报错。直接贴代码解释下。

ArrayList中Iterator的实现:

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迭代器的实现我们可以看到:基本上ArrayList采用size属性来维护自已的状态，而Iterator采用cursor来来维护自已的状态。当你直接在foreach里面对list进行删除操作，size出现变化时，cursor并不一定能够得到同步，除非这种变化是Iterator主动导致的。(调用list.iterator()方法的原因)

从上面的代码可以看到当Iterator.remove方法导致ArrayList列表发生变化时，他会更新cursor来同步这一变化。但其他方式导致的ArrayList变化，Iterator是无法感知的。ArrayList自然也不会主动通知Iterator们，那将是一个繁重的工作。Iterator到底还是做了努力：为了防止状态不一致可能引发的无法设想的后果，Iterator会经常做checkForComodification检查，以防有变。如果有变，则以异常抛出，所以就出现了上面的异常。如果对正在被迭代的集合进行结构上的改变（即对该集合使用add、remove或clear方法），那么迭代器就不再合法（并且在其后使用该迭代器将会有ConcurrentModificationException异常被抛出）。

如果使用迭代器自己的remove方法，那么这个迭代器就仍然是合法的。

hashtag
List结合Set去重

hashtag
List结合Set去重(不是直接对list进行删除，而是组装新list，考虑到list删除效率低)

hashtag
遍历过程中去重

个人最为推荐的一种,因为效率最高，也能达到功能的需要。

hashtag
测试结果如下

hashtag
总结

通过上述测试我们可以看出，有时候我们排重的时候，不一定要拍完重再对排重后的数据进行遍历，可以在遍历的过程中进行排重，注意用来排重的那个集合放到Set中，可以是HashSet,或者其他Set(推荐使用HashSet),因为Set的contains效率更高，比list高很多。

然后考虑到如果非要拿到去重后的list，考虑使用方案3《List结合Set去重(不是直接对list进行删除，而是组装新list，考虑到list删除效率低)》，通过测试，这种方法效率也是非常的高。与方案4相比，稍微慢一点点。

对于上述方案1，测试也使用过组装新list的方式，而不是list.remove。但是效率还是比较慢。

这是实际工作中总结出来的经验。希望对大家有帮助！ 欢迎大家来交流！

Previouskafka_1Next书籍总结

Last updated