怎么查看网站是哪个公司做的,wordpress懒加载插件,淘宝网页设计模板,wordpress调用产品图片引言
对于 Collection 集合及其实现类都有 removeAll(Collection? c)。
对于ArrayList 的实例对象#xff0c;在数据比较多的情况下#xff0c;方法 removeAll() 的传参 c 的类型是 HashSet会比是 ArrayList 的情况快的多。
原因
我们来细看一下ArrayList类的re…引言
对于 Collection 集合及其实现类都有 removeAll(Collection? c)。
对于ArrayList 的实例对象在数据比较多的情况下方法 removeAll() 的传参 c 的类型是 HashSet会比是 ArrayList 的情况快的多。
原因
我们来细看一下ArrayList类的removeAll()方法实现的伪代码。
如arrayList.removeAll(subList);// 遍历底层数组将不需要删除的元素放在数组前面后面的全部置为 null
// w 为要删除和不删除的分界线
int w 0;
for(var value in 该 arrayList 的底层数组){if(!subList.contains(value)){该 arrayList 的底层数组 [w] value;w;}
}这里影响速率关键的一步是subList.contains(value)
这是因为contains()方法在不同类中的实现是存在差异的。
对于 ArrayList.contains()它的实现是调用 indexOf()一个一个地遍历查找。最坏时间复杂度为O(总数据量)。
而对于 HashSet.contains()由于 HashSet 的底层是 HashMap因此实际调用的是 HashMap 的 containsKey()方法该方法是通过哈希计算的方式去查询的因此速度十分快。最坏的时间复杂度约为O(最长链表长度)而链表长度一般不会过大。
使用方法
在数据量比较大的的情况下使用arrayList.removeAll(subList)时可以将subList封装为HashSet
arrayList.removeAll(new HashSet(subList));速度实测
数据量ArrayListHashSetLinkedList10 万1094 毫秒6 毫秒1133 毫秒20 万4140毫秒8 毫秒4241 毫秒50 万51431毫秒30 毫秒34380 毫秒100 万140444 毫秒36 毫秒179465 毫秒500 万9130706 毫秒79 毫秒10549229 毫秒
测试用的代码
public class RemoveAllTest {public static void main(String[] args) {ArrayListInteger arrayList new ArrayList();for (int i 0; i 5000000; i) {arrayList.add(i);}ArrayListInteger subList new ArrayList();for (int i 0; i 5000000; i) {subList.add(i);i 2;}// 测试入参为 ArrayList 类型时 removeAll() 的性能long startTime System.currentTimeMillis();arrayList.removeAll(subList);long endTime System.currentTimeMillis();System.out.println(ArrayList 耗时 (endTime - startTime));// 测试入参为 HashSet 类型时 removeAll() 的性能ArrayListInteger arrayList2 new ArrayList();for (int i 0; i 5000000; i) {arrayList2.add(i);}startTime System.currentTimeMillis();arrayList2.removeAll(new HashSet(subList));endTime System.currentTimeMillis();System.out.println(HashSet 耗时 (endTime - startTime));// 测试将 ArrayList 类型转成 LinkedList 类型ArrayListInteger arrayList3 new ArrayList();for (int i 0; i 5000000; i) {arrayList3.add(i);}startTime System.currentTimeMillis();new LinkedList(arrayList3).removeAll(subList);endTime System.currentTimeMillis();System.out.println(LinkedList 耗时 (endTime - startTime));}
}HashSet 、LinkedList 中 removeAll() 方法的区别 不同类的 removeAll() 方法实现不同可以看到对于 HashSet 和 LinkedList他们的 removeAll() 方法是通过父类或超父类的迭代器进行实现的而 ArrayList 是自己通过 for 循环进行了实现。
HashSet 内部实现
依托于 AbstractSet 类的 removeAll(Collection? c) 方法实现的逻辑是
先调原集合对象 HashSet 和 removeAll(Collection? c) 方法中传入的参数 c 的 size() 方法用来判断谁包含的元素更多。 如果原集合对象的元素数量 c 中元素数量那么调用 c 的代器去遍历 c 查看元素是否包含在原集合中并使用原集合的 remove() 方法去删除元素。时间复杂度为 O(n)。 如果原集合对象的元素数量 c 中元素数量那么调用原集合对象的迭代器去遍历原集合检查元素是否包含在 c 中并调用原集合迭代器的 remove() 方法去删除元素。这里的时间复杂度与集合 c 的 contains() 方法的实现有关 如果 c 是一个 ArrayListcontains() 方法的时间复杂度是 O( m )。因此从集合 HashSet 中删除 ArrayList 中存在的所有元素的总体时间复杂度为 O( n * m )。 如果 c 再次是 HashSet则 contains() 方法的时间复杂度为 O(1)。因此从集合 HashSet 中删除 HashSet 中存在的所有元素的总体时间复杂度为 O( n )。
public boolean removeAll(Collection? c) {Objects.requireNonNull(c);boolean modified false;if (size() c.size()) {for (Iterator? i c.iterator(); i.hasNext(); )modified | remove(i.next());} else {for (Iterator? i iterator(); i.hasNext(); ) {if (c.contains(i.next())) {i.remove();modified true;}}}return modified;
}LinkedList 内部实现
public boolean removeAll(Collection? c) {Objects.requireNonNull(c);boolean modified false;Iterator? it iterator();while (it.hasNext()) {if (c.contains(it.next())) {it.remove();modified true;}}return modified;
}通过 contains() 方法来判断是否存在相同的元素效率与 c 的类型有关。
参考 为什么arrayList.removeAll(set)的速度远高于arrayList.removeAll(list) Java 中 HashSet 的 removeAll 性能分析
