debug底层java代码，对list中的数据去重的正确姿势，及对比java list remove正确使用方法与错误使用

2022-10-23 22:38:57

前言

List中主要有2种数据结构的实现，一种是数组，另一种是链表。

数组，均实现RandomAccess类

数组的实现有ArrayList、Vector、Stack、CopyOnWriteArrayList他们都继承了AbstractList，AbstractList实现了List中的部分接口，并且实现了数组结构的遍历，也就是上边说到的迭代器设计模式中Iterator部分，Stack实现了一个LIFO，Vector实现了线程安全，CopyOnWriteArrayList则是线程安全的一个变体，读的操作没有锁性能会更好，而写的时候存在锁并且在写的时候copy元数据，在新的数据上做修改，然后在同步回元数据，从而实现了在遍历的时候，可以对其进行修改而不会抛出CurrentModificationException异常。

链表，未实现RandomAccess类

LinkedList底层使用Entry类来存放数据元素。链表，就是手拉手，通过一个元素可以知道上一个元素和下一个元素，链表的遍历方式实现和数组是不一样的，构造方法中初始化了next的值，if（int < (size >> 1)）这里介绍下>>和>>>符号，>>代表向右移位。

例如3>>1则代表二进制0011向右移动1位，则是0001最终结果就是1，8>>>3代表8除以2的3次方最终结果则是1。

这里的if(int < (size >> 1))，主要是为了判断这个元素时在前半段还是在后半段，size >> 1相当于size/2，主要是为了更快的定位链表中第index元素的位置，不用从头遍历，这就是迭代器设计模式的好处，隐藏了内部实现的细节，对不同的数据结构提供了统一的迭代接口。

准备测试list的主方法

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        for (int i = 0; i < 10000; i++) {
            list.add("shanghai");
            list.add("shanghai");
            list.add("guangzhou");
            list.add("shenzhen");
            list.add("shanghai");
            list.add("hangzhou");
            list.add("shanghai");
            list.add("beijing");
            list.add("shanghai");
            list.add("shanghai");
            list.add("guangzhou");
            list.add("shenzhen");
            list.add("shanghai");
            list.add("hangzhou");
            list.add("shanghai");
        }

//        print(list);
        System.out.println("\n");
        removeSetRepeat(list); // 9ms  25ms
//        removeStrRepeat(list);  //19ms  78ms
        System.out.println("\n");
//        removeRowRepeat(list);  //9ms  24ms
    }

    private static void print(List<String> list) {
        System.out.print("item:");
        for (String item : list) {
            System.out.print(item+"：");
        }
    }

for循环去重对比

StringBuilder拼接去重

    /*
     * 正确 StringBuilder去重
     */
    public static void removeStrRepeat(List<String> list){
        StopWatch sw = new StopWatch();
        sw.start();
        StringBuilder stringBuilder = new StringBuilder("x");
        for(int i = list.size() - 1; i >= 0; i--){
            String item = list.get(i);
            if(item == null || stringBuilder.toString().contains(item)){
                list.remove(i);
                continue;
            }
            stringBuilder.append(item).append("x");
        }
        print(list);
        sw.stop();
        System.out.println("----：" + sw.getTotalTimeMillis()+"ms");
    }

StringBuilder去重 14万条数据19ms，140万条数据 78ms

ArrayList去重

    /*
     * 正确 ArrayList去重 14万条数据9ms，140万条数据 24ms
     */
    public static void removeRowRepeat(List<String> list){
        StopWatch sw = new StopWatch();
        sw.start();
        List<String> rowx = new ArrayList<>();
        for(int i = list.size() - 1; i >= 0; i--){
            String item = list.get(i);
            if(item == null || rowx.contains(item)){
                list.remove(i);
                continue;
            }
            rowx.add(item);
        }
        print(list);
        sw.stop();
        System.out.println("----：" + sw.getTotalTimeMillis()+"ms");
    }

ArrayList数组去重 14万条数据9ms，140万条数据 24ms。

set去重

/*
     * 正确 HashSet去重 14万条数据9ms，140万条数据 25ms
     */
    public static void removeSetRepeat(List<String> list){
        StopWatch sw = new StopWatch();
        sw.start();
        Set<String> set = new HashSet<>(list);
        print(new ArrayList<>(set));
        sw.stop();
        System.out.println("----：" + sw.getTotalTimeMillis()+"ms");
    }

Set去重 14万条数据9ms，140万条数据 25ms，与ArrayList数组for循环去重不相上下。

for循环size类型的remove

错误案例

IndexOutOfBoundsException索引越界

 public static void remove11(List<String> list, String target) {
        int size = list.size();
        for (int i = 0; i < size; i++) {
            String item = list.get(i);
            if (target.equals(item)) {
                list.remove(item);
            }
        }
        print(list);
    }

index从0开始，remove不能完全删除目标关键词shanghai----逆行撞车

由于index一直增加，而list中删除一次，list的size减小，导致list.get(i)可能忽略其中一个元素

  /*
     * 错误  index从0开始，remove不能完全删除目标关键词shanghai
     * 由于index一直增加，而list中删除一次，list.get(i)可能忽略其中一个元素
     */
    public static void remove12(List<String> list, String target) {
        //item:beijing：shanghai：shanghai：guangzhou：shenzhen：hangzhou：
        for (int i = 0; i < list.size(); i++) {
            String item = list.get(i);
            System.out.println("----：" + item);
            if (target.equals(item)) {
                list.remove(item);
            }
        }
        print(list);
    }

正确案例

相向而行--list.remove，不会出错

size 倒着衰减，index 也是从最大值开始衰减，两者相向而行，故list.remove，不会出错

public static void remove13(List<String> list, String target) {
        int size = list.size();
        for (int i = size - 1; i >= 0; i--) {
            String item = list.get(i);
            if (target.equals(item)) {
                list.remove(item);
            }
        }
        print(list);
    }

public static void remove14(List<String> list, String target){
        for(int i = list.size() - 1; i >= 0; i--){
            String item = list.get(i);
            if(target.equals(item)){
                list.remove(item);
            }
        }
        print(list);
}

对象遍历list--foreach 写法--for(String item : list)

错误-->for(String item : list)进行remove造成ConcurrentModificationException

对象遍历list，list.remove，造成list 对象的 modCount 值进行了修改，而 list 对象的迭代器的 expectedModCount 值未进行修改，因此抛出了ConcurrentModificationException异常。

    /*
     * 错误 对象遍历list,list 对象的 modCount 值进行了修改，而 list 对象的迭代器的 expectedModCount 值未进行修改，因此抛出了ConcurrentModificationException异常。
     */
    public static void remove21(List<String> list, String target){
        for(String item : list){
            System.out.print(item+"：");
            if(target.equals(item)){
                list.remove(item);
            }
        }
        print(list);
    }

正确-->`CopyOnWriteArrayList` 解决了 List的并发问题

public static void remove22(ArrayList<String> list, String target) {
        final CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<String>(list);
        for (String item : cowList) {
            if (item.equals(target)) {
                cowList.remove(item);
            }
        }
        print(cowList);
    }

每个CopyOnWriteArray List对象，里面有一个array 数组对象用来存放具体元素， ReentrantLock 独占锁对象，用来保证同时只有一个线程对 array进行修改。

并发包中的并发List只有CopyOnWriteArrayList，CopyOnWriteArrayList是一个线程安全的ArrayList，对其进行的修改操作，都是在底层的一个复制的数组（快照）上进行的，也就是使用了写时复制策略（add/set/remove（修改）时，复制新数组进行操作）。

原理：采用每add一个元素，则复制出一个新数组，此时如果多线程下，add/set/remove操作时，用新数组，get操作用旧数组，这样就不用对get进行加锁，但add/set/remove还是要加锁的（独占锁lock）。此时就形成了所谓的读写分离的状态。

CopyOnWriteArrayList的复制操作，导致了其存在以下问题：

存在内存占用的问题，因为每次对容器结构进行修改的时候，都要对容器进行复制，这么一来我们就有了旧有对象和新入的对象，会占用两份内存。如果对象占用的内存较大，就会引发频繁的垃圾回收行为，降低性能；
CopyOnWrite只能保证数据最终的一致性，不能保证数据的实时一致性。

比如：一个线程正在对容器进行修改，另一个线程正在读取容器的内容，这其实是两个容器数组，那么读线程读到的是旧数据

所以CopyOnWriteArrayList 集合比较适用于读操作远远多于写操作的场景。

list.iterator迭代遍历

错误案例 list.iterator删除报ConcurrentModificationException

  /*
     * 错误案例  list.iterator删除报ConcurrentModificationException
     */
    public static void remove31(List<String> list, String target){
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            String item = iter.next();
            if (item.equals(target)) {
                list.remove(item);
            }
        }
        print(list);
    }

产生java.util.ConcurrentModificationException异常。list.iterator写法实际上是对的 Iterable、hasNext、next方法的简写。因此我们从list.iterator()着手分析，跟踪iterator()方法，该方法返回了 Itr 迭代器对象。

正确案例--用list.iterator中的内部类Itr进行删除

   /*
     * 正确 用list.iterator中的内部类Itr进行删除
     */
    public static void remove32(List<String> list, String target){
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            String item = iter.next();
            if (item.equals(target)) {
                iter.remove();
            }
        }
        print(list);
    }

用list.iterator中的内部类Itr进行删除，不会修改ArrayList的modCount的值，故而modCount != expectedModCount永远为false

码农公寓

前言