这个东西很多人一看就知道原理，哈哈，无奈在下菜菜一枚，记录下以加深印象吧！有不当之处，欢迎大牛批评指正~
其实看标题就知道二者肯定 HashSet更胜一筹，工作中经常遇到 大数据量的 removeAll()操作，以前习惯性用 list，后来数据量大的时候发现效率极低，下面是一些测试和源码分析。
采用 hashSet 代替 arrayList 进行稍大数据量 removeAll 的场景，依据如下：
a、进行了增量测试，测试数据集范围从 1000-->500000 观察 二者的耗时
| 数量 | arrayList耗时(ms) | hashSet耗时(ms) |
|---|---|---|
| 1000 | 13 | 0 |
| 10000 | 491 | 1 |
| 50000 | 2164 | 1 |
| 100000 | 44858 | 7 |
| 500000 | 544184 | 10 |
b、看一下二者 removeAll的操作源码
arrayList: A.removeAll(B)
(1) 遍历A
判断B.contains(A[i])
若不包含，则 A[w] = A[i] w从0递增
(2) 遍历完成则将 A[w]往后部分置为 null
(3) 看下上面(1)的B.contains(A[i])的逻辑：
遍历B，一个个匹配，匹配到则返回B的index
- 综上，arrayList的removeAll A的循环里面套B的循环，时间复杂度是：O(n*m)
hashSet: A.removeAll(B)
(1)若A.size > B.size 遍历 B
直接操作A的 hashMap.remove(B[i]) ---- （new hashSet<>时会同步生成对应的hashMap<> key则为set的元素，value为一个虚拟值）
看下hashMap的remove操作：
根据B[i] 计算hashcode，根据hashcode 直接在hashMap中找到对应的链表桶，会先定位到链表头，到这相当于直接找到落入的小组，极大缩小了检索范围，然后从链表头开始遍历链表，找到则返回
java8中对hashMap的链表长度做了优化，当链表长度大于设定的值后，则改链表的数据格式转为'红黑树'--一种遵循类似二叉树的原则：右子树比左子树数据大，但是二叉树容易存在不平衡性，所以红黑树是一种平衡的二叉树
由于红黑树是顺序性的，基本是二分查找，所以速率大大提升
(2) 若 A.size < B.size 遍历 A
判断B.contain(A[i]) 若true，则直接remove
进去contain方法，也是直接调用的 hashMap.containsKey()，方法逻辑同上一样
- 综上，hashSet的removeAll由于通过hashMap的遍历方法实现，时间复杂度是:O(n)
网友评论