考虑这样一个场景，对两个列表目标，listA 和 listB，比较二者差异，找出只在 listA 中呈现的元素列表 onlyListA，找出只在 listB 中呈现的元素列表 onlyListB。
removeAll完成
很容易想到凭借 removeAll 完成，代码如下。
List<String> listA = new ArrayList<>();
List<String> listB = new ArrayList<>();
//仅在数组A中呈现的元素
List<String> onlyListA = new ArrayList<>(listA);
onlyListA.removeAll(listB);
//仅在数组B中呈现的元素
List<String> 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<String> listA = dataList(size);
listA.add("onlyAElement");
List<String> listB = dataList(size + 3);
long startTime = System.currentTimeMillis();
//仅在数组A中呈现的元素
List<String> onlyListA = new ArrayList<>(listA);
onlyListA.removeAll(listB);
//仅在数组B中呈现的元素
List<String> 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<String> dataList(int size) {
List<String> 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<String> listA = dataList(size);
listA.add("onlyAElement");
List<String> listB = dataList(size + 3);
long startTime = System.currentTimeMillis();
//仅在数组A中呈现的元素
List<String> onlyListA = tuple2._1;;
//仅在数组B中呈现的元素
List<String> 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 <E> 元素类型
* @return Tuple2目标 onlyAList-只在数组A存在的元素 onlyBList-只在数组B存在的元素
*/
public static <E> Tuple2<List<E>, List<E>> getDiffListBtMapCompare(List<E> listA, List<E> listB) {
ValidateUtils.validateNotNull(listA, "listA");
ValidateUtils.validateNotNull(listB, "listB");
List<E> onlyAList = new ArrayList<>();
List<E> 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<E, Integer> 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 完成。
参阅 Java高效找出两个大数据量List调集中的不同元素
