大数组元素差异比较下的removeAll和Map效率对比

　　考虑这样一个场景，对两个列表对象，listA 和 listB，比较二者差异，找出只在 listA 中出现的元素列表 onlyListA，找出只在 listB 中出现的元素列表 onlyListB。removeAll实现
　　很容易想到借助 removeAll 实现，代码如下。List listA = new ArrayList<>(); List listB = new ArrayList<>();   //仅在数组A中出现的元素 List onlyListA = new ArrayList<>(listA); onlyListA.removeAll(listB);  //仅在数组B中出现的元素 List onlyListB = new ArrayList<>(listB); onlyListB.removeAll(listA); 复制代码
　　当数组元素较少时，借助 removeAll 实现并没有任何问题。不过在数组元素较大时，removeAll 方法耗时会较大。执行如下测试方法，对数组元素个数为1000，1W，10W，100W 的场景进行测试。public class ListDiffTest {      public static void main(String[] args) {         testRemoveAllCostTime(1000);         testRemoveAllCostTime(10000);         testRemoveAllCostTime(100000);         testRemoveAllCostTime(1000000);     }          public static void testRemoveAllCostTime(int size) {          List listA = dataList(size);         listA.add(＂onlyAElement＂);          List listB = dataList(size + 3);          long startTime = System.currentTimeMillis();          //仅在数组A中出现的元素         List onlyListA = new ArrayList<>(listA);         onlyListA.removeAll(listB);          //仅在数组B中出现的元素         List onlyListB = new ArrayList<>(listB);         onlyListB.removeAll(listA);          System.out.println(＂仅在集合A中出现的元素：＂ + onlyListA);         System.out.println(＂仅在集合B中出现的元素：＂ + onlyListB);         System.out.println(＂元素个数 = ＂ + size + ＂时，比对耗时：＂ +  (System.currentTimeMillis() - startTime) + ＂ 毫秒＂);     }      private static List dataList(int size) {         List dataList = new ArrayList<>();         for (int i = 0; i < size; i++) {             dataList.add(＂＂ + i);         }         return dataList;     } } 复制代码
　　测试结果如下仅在集合A中出现的元素：[onlyAElement] 仅在集合B中出现的元素：[1000, 1001, 1002]  元素个数 = 1000时，比对耗时：19 毫秒    元素个数 = 10000时，比对耗时：299 毫秒   #1W  元素个数 = 100000时，比对耗时：24848 毫秒   #10W  元素个数 = 1000000时，比对耗时：3607607 毫秒   #100W 约60m 复制代码
　　可以看到，当数组元素达到百万级时，耗时将达60min上下。借助Map实现
　　此处给出一种优化方式，借助 Map 计数，将 List 集合中的元素作为 Map 的 key，元素出现的次数作为 Map 的 value。代码实现如下。import io.vavr.Tuple2;  public class ListDiffTest {      public static void main(String[] args) {         testDifferListByMapCostTime(1000);         testDifferListByMapCostTime(10000);         testDifferListByMapCostTime(100000);         testDifferListByMapCostTime(1000000);     }       public static void testDifferListByMapCostTime(int size) {          List listA = dataList(size);         listA.add(＂onlyAElement＂);          List listB = dataList(size + 3);          long startTime = System.currentTimeMillis();          //仅在数组A中出现的元素         List onlyListA = tuple2._1;;          //仅在数组B中出现的元素         List onlyListB = tuple2._2;          System.out.println(＂仅在集合A中出现的元素：＂ + onlyListA);         System.out.println(＂仅在集合B中出现的元素：＂ + onlyListB);         System.out.println(＂元素个数 = ＂ + size + ＂时，比对耗时：＂ +  (System.currentTimeMillis() - startTime) + ＂ 毫秒＂);       }       /**      * 通过Map计数方式 比较两个数组之间的差异      *      * @param listA 数组A      * @param listB 数组B      * @param  元素类型      * @return Tuple2对象 onlyAList-只在数组A存在的元素  onlyBList-只在数组B存在的元素      */     public static  Tuple2, List> getDiffListBtMapCompare(List listA, List listB) {         ValidateUtils.validateNotNull(listA, ＂listA＂);         ValidateUtils.validateNotNull(listB, ＂listB＂);          List onlyAList = new ArrayList<>();         List onlyBList = new ArrayList<>();          if (CollectionUtils.isEmpty(listA)) {             return Tuple.of(onlyAList, listB);         } else if (CollectionUtils.isEmpty(listB)) {             return Tuple.of(listA, onlyBList);         }          /**          * listA中元素 初始化计数 = 1          * listB中元素 初始化计数 = -2          * 遍历累加后          * 相同元素 计数 = 2          * 仅A中出现元素  计数 = 1          * 仅A中出现元素  计数 = -1          */         Map countMap = new HashMap<>(Math.max(listA.size(), listB.size()));         for (E eleA : listA) {             countMap.put(eleA, 1);         }          for (E eleB : listB) {             countMap.put(eleB, 1 + countMap.getOrDefault(eleB, -2));         }          countMap.forEach((k, v) -> {             //获取不同元素集合             if (v == 1) {                 onlyAList.add(k);             } else if (v == -1) {                 onlyBList.add(k);             }         });          return Tuple.of(onlyAList, onlyBList);     } } 复制代码
　　测试结果如下仅在集合A中出现的元素：[onlyAElement] 仅在集合B中出现的元素：[1000, 1002, 1001]  元素个数 = 1000时，比对耗时：8 毫秒  元素个数 = 10000时，比对耗时：19 毫秒   #1W  元素个数 = 100000时，比对耗时：28 毫秒  #10W  元素个数 = 1000000时，比对耗时：96 毫秒  #100W  元素个数 = 10000000时，比对耗时：5320 毫秒  #1000W  复制代码removeAll耗时分析
　　最后，来分析下为什么在大数组元素比较时，removeAll 性能较差。removeAll 方法中，先进行判空，然后调用 batchRemove() 方法    public boolean removeAll(Collection<?> c) {         Objects.requireNonNull(c);         return batchRemove(c, false);     } 复制代码batchRemove() 方法中，使用 for 循环对集合进行遍历。第 1 层循环需要执行 listA.size() 次。循环体中调用了 contains() 方法来确定集合 B 是否含有该元素。    private boolean batchRemove(Collection<?> c, boolean complement) {         final Object[] elementData = this.elementData;         int r = 0, w = 0;         boolean modified = false;         try {             for (; r < size; r++)                 if (c.contains(elementData[r]) == complement)                     elementData[w++] = elementData[r];         } finally {             // Preserve behavioral compatibility with AbstractCollection,             // even if c.contains() throws.             if (r != size) {                 System.arraycopy(elementData, r,                                  elementData, w,                                  size - r);                 w += size - r;             }             if (w != size) {                 // clear to let GC do its work                 for (int i = w; i < size; i++)                     elementData[i] = null;                 modCount += size - w;                 size = w;                 modified = true;             }         }         return modified;     } 复制代码contains() 方法的实现如下，内部又调用了 indexOf() 方法。indexOf() 方法内部又进行了一层 for 循环遍历。    public boolean contains(Object o) {         return indexOf(o) >= 0;     }      public int indexOf(Object o) {         if (o == null) {             for (int i = 0; i < size; i++)                 if (elementData[i]==null)                     return i;         } else {             for (int i = 0; i < size; i++)                 if (o.equals(elementData[i]))                     return i;         }         return -1;     } 复制代码至此，可以看到，按照平均每次遍历要进行 list.size() / 2 次计算，假设集合 A 的元素个数为 m，集合 B 的元素个数为 n，则两重 for 循环下，会执行 m*n/2次。对于两个千万量级的数组，将执行 100 亿次计算！！！
　　由此给出一个结论，对于大数组元素差异比较，不建议使用 removeAll，可以借助 Map 实现。
　　原文链接：https://juejin.cn/post/7208099962911752247