java - removeAll() 方法花费很长时间

Question

List<Batch> vAllBatchList = getAllBatchCollection().toList(); //Has 700k records
List<Batch> vKeepableBatchCollection = getKeepableBatchCollection(pDaysKeepHistory).toList(); //has 600k records
vAllBatchList.removeAll(vKeepableBatchCollection);

在上面的第 3 行中，removeAll 方法花费了太多时间才能完成。这里如何优化removeAll方法？

Answer 1

如果将要删除的元素的 List 转换为 Set，它应该会更快:

vAllBatchList.removeAll(new HashSet<>(vKeepableBatchCollection));

这是假设 Batch 类正确覆盖 hashCode 和 equals。

说明:ArrayList 的 removeAll (我假设您的 vAllBatchList List 是一个 ArrayList ) 迭代调用它的 List 的所有元素，并检查传递的 Collection 是否包含它们。如果传递的 Collection 是 Set，则 contains 将花费预期的恒定时间 (O(1))，而如果 Collection 是 List，则需要线性时间 (O(n))。

当然，如果你可以直接生成vKeepableBatchCollection元素的Set，而不是先创建一个List，然后将其转换为一个Set，那就更好了。