大家好, 这里是 K 字的研究.
今天我们研究下 java 中的集合框架里的一个接口Collection.removeAll(Collection c)的源码.
起因
偶然看到一个讲最佳实践(best practice)的帖子, 举了一个反模式(anti-pattern): 不要在循环中调用List.contains方法.说的是, 这段代码, 在 List 比较长的时候, 会很慢.
首先, 这个说法是完全正确的.
在一个长度为 的列表里, 这段用了迭代器的代码等效于:
for (int i = 0; i < m; i++) {}
时间复杂度是
然而,其实List.contains里有一个隐藏复杂度,对列表而言contains方法是 的. 在循环里调用这个代码, 外部循环本身就是 复杂度了. 相当于:
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
}
}
这里会带来 的复杂度. 解决方案也很简单, 消掉这个内部隐藏的复杂度.
判断是否包含, 能够做到的方法是Hash技术, 按图索骥就行.Java 里, Hash有好几个:
-
HashMap -
HashSet -
etc.
List.contains,并不是List独有的接口,而是继承自Collection的接口.
这里用HashSet就可以仍然提供contains接口,这个复杂度就消掉了.多花点内存,加快速度,典型的空间换时间.
new HashSet(list2)
这个例子看完应该给人的收获 注意代码里方法的隐藏复杂度
进一步探究这个反模式
那么, 我为啥要写这篇呢? 人家一张图不都讲完了吗.我这全是废话研究啥呢?
其实, 我主要是想借着这张图, 延续下这个话题.这个示例代码上可不只是这个list.contains可能会有问题.
循环中删除列表元素
因为图里代码只有部分,先来试着补全下这个代码.
public void method(List<Integer> lists, List<Integer> list2) {
Iterator<Integer> it = lists.iterator();
while (it.hasNext()) {
Integer next = it.next()
if (list2.contains(next)) {
it.remove();
}
}
}
这段代码的意思是:遍历第一个列表里的元素, 检查是否在第二个黑名单列表里.在的话就删除掉. 切换完类型到HashSet后的代码可以写成:
public void method(List<Integer> lists, HashSet<Integer> list2) {
//...
}
改变类型,带来 1 个两难问题.
-
这里只改了一行代码,现在黑名单已经是 HashSet类型了, 为什么还叫list2. -
如果改名字, 会涉及到下面循环里的代码. 代码修改的局部性就没了.
这个问题的起因在哪里? 变量名.
变量名要有意义,而不是单纯的把类型带在上面.
比如这段代码里, 按照代码逻辑上表现出来的, 是个黑名单,原来他叫deniedValues的话, 改动什么类型, 都不会影响到具体代码.
public void method(List<Integer> lists, HashSet<Integer> deniedValues);
把类型带到名字类,那是一般的弱类型语言使用者, 怕用着用着忘了用的什么类型, 才做的事情. Java 这么厉害的强类型语言翘楚, 你带上类型名字, 看不起谁呢?
日常写 java 时候, 经常按照这个写法来声明列表.
List<Integer> list2 = new ArrayList<>();
为什么不写成
ArrayList<Integer> list2 = new ArrayList<>();
因为用List接口,可以灵活切换实现, 不想具体绑定在ArrayList还是LinkedList上.
在这里也是一样的. 对于一个黑名单而言, 他只要保证可以迭代就行了. 根本用不到List这么具体的接口. 一开始, 这个地方的写法, 如果说接收的变量是Collection. 那这里做优化,其实根本不需要改动. 比如:
public void method(List<Integer> lists, Collection<Integer> deniedValues) {
java 官方对 API 的设计, 推荐是:
-
入参要松 能用抽象的就不用具体的 -
出参要紧 构造一个对象,比如 sortedSet 之类的,挺不容易的,不要丢掉了类型.
如果说, 原来的接口,本身就是用了Collection做参数, 那我们怎么优化呢? 可以这样:
public void method(List<Integer> lists, Collection<Integer> deniedValues) {
deniedValues = new HashSet<>(deniedValues);
//... 直接入参转换下就行
}
然后呢, 有一个新的问题.
有时候调用者很确定自己的黑名单很小, 平白无故转一次参数, 丧失了调用者的控制权. 为了少数参数比较长的使用者影响所有人, 划不来. 这个该怎么办呢?
自适应大法好.
可以采取自适应策略: 传进来的黑名单短, 就保持原样. 长, 就转成HashSet. 自己来适应参数的大小. 用了自适应以后, 得到的版本就是这样了.
public void method(List<Integer> lists, Collection<Integer> deniedValues) {
if(deniedValues.size()>10){//具体阈值可以再定
deniedValues = new HashSet<>(deniedValues);
}
//...
}
这个代码的前几行的优化完了. 然后问题来了, 虽然这个迭代器用的很标准, 但是这个代码真的有必要存在吗?
Collection.removeAll
Collection标准接口可不只是有一个contains. 他是一大套的标准化接口, 甚至包含了:Collection.removeAll(Collection c).
Collection.removeAll是用来对两个 Collection 做差的. 不能望文生义, 并不是把整个集合清空, 清空那是Collection.clear的活儿.
用上这个东西, 原来的方法可以改造成:
public void method(List<Integer> lists,Collection<Integer> deniedValues) {
if(deniedValues.size()>10){
deniedValues = new HashSet<>(deniedValues);
}
lists.removeAll(deniedValues);
}
其实,如果不考虑刚刚我们加上的自适应优化的话, 这里甚至可以写成:
lists.removeAll(deniedValues);
是的, 整个方法都被删掉了.
for循环+contains,其实是标准库里removeAll的写法, 人家就是这么实现的. 这里也是一个要注意的隐藏复杂度.如果传进去的参数是List, 这个方法就是 的. 注意使用removeAll方法时候, 自由裁量到底用什么类型做参数.
嗯, 其实我是嫌弃他的例子写的复杂了. 隐藏复杂度的最好例子其实是标准库.
不要乱用不熟悉的标准库方法,他们可能并不像表面上看上去那样.
ArrayList<Integer> lists = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5))
List<Integer> list2 = Arrays.asList(2, 3, 4);
lists.removeAll(list2);
//or
lists.removeAll(new HashSet<Integer>(list2))
再探迭代删除
原来的实现, 一个一个的删除元素,其实在标准库里也有.而且, 就在removeAll里. 大多数的Collection使用的removeAll,都是继承自:java.util.AbstractCollection#removeAll的.没什么问题.
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;
}
不过呢, 今天既然说到隐藏复杂度的问题了. 在这个代码里,我们来看一个隐藏更深的复杂度.
虽然用迭代器删东西没毛病, 但是对于ArrayList而言, 最好别这样. 上时序图.
这里, 对ArrayList的迭代器而言, 每调用一次it.remove, 都会调用ArrayList.remove. 而ArrayList是用数组实现的. 数组最不怕的是随机访问(RandomAccess). 而最怕的,就是remove.
时序图告诉我们,ArrayList的迭代器,每调用一次remove,就会调用System.arraycopy.在性能上来说,这个隐藏复杂度, 可能一点都不比:List.contains小.
ArrayList.removeAll
那么, ArrayList.removeAll呢? 继续看时序
他把只是在删除的最后做了一次复制.在我看了代码以后,发现,这个还是异常流程里的复制,在抛异常时候,为了保证和上面用迭代器的实现表现一致,才用了一次. 正常流程里,不抛异常,连这个复制都没有.
什么叫优雅?什么叫优雅?
如何实现 ArrayList.removeAll
下面就差不多可以开始本篇的正文了. 这么优雅的 removeAll, 怎么实现的?
不过先介绍另一个函数, Collection.retainAll.
a removeAll b 是 从 a 中去掉 b 中存在的 a retainAll b 是 从 a 中去掉 b 中不存在的
就像removeAll是求余集,retainAll 是求子集.他们俩是如此的对称, 以至于在 ArrayList 中他们的实现是同一个:batchRemove(Collection c, boolean complement)
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;
}
代码是如此简单, 却又不太好看懂他在干嘛. 先从最简单的部分开始.
维护可用栏位数和 list 长度
ArrayList是数组实现的, 会自动扩容.里面的数组一般来说, 是比实际放的东西要多的.
-
里面存放了一个数组 elementData来当酒店. -
使用了一个 size来记录当前住了多少人 -
用一个 modCount来记录修改数
所以, 假如我从[1,2,3,4,5].removeAll([2,3,4]),那么总房间数其实没变, size-3码,就对应着:
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null; //这个是针对gc优化
modCount += size - w; //记录
size = w; //新的数组大小
modified = true;
}
往上一点, 就是复制发生的场景了. 一般是因为,传进去的集合,不支持null值之类的原因.为了保持和迭代器的版本一致做的兼容.可以暂时跳过.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
正常流程
最上面的try里是主逻辑, 就一个循环. 贼简洁,但是,其实挺不好懂的.
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
幸好,我们有Processing. 先来可视化一下try里面这个流程. 白色方框前面的,都是需要保留的内容.
假设原列表是[1,2,3,4,5], 黑名单列表是[2,3,4].
运行的效果是这样的
为了避免太快看不清. 我把每一帧都输出出来..
纯静态的图是这样的.
这个白色的, 就是前面我们说的w.表示要留下的元素的数量,和r一起从0开始.r是一直在增长, w是遇到需要保留的元素才增长.
r==w时候, 这个流程, 其实相当于把数组复制了一遍: a[0]=a[0]
那么一旦r和w不相等时候, 必然是w遇到了一个不再被需要的位置. 比如图中的 2, 因为在被拉了黑名单, 当 w 走到他上面时候, 就停下来了. 当 r 重新遇到了一个需要保留的数字, a[w++]=a[r]占掉这个不被需要的w位置即可.
如何保证 w++之后所指向的位置, 数字也是不需要的呢?
其实这个很简单,
-
如果这个数字是不需要的, 覆盖即可. -
如果这个数字是需要保留, 那么在前面的循环中,一定已经被复制到了正确的地方.
异常流程
正常流程中, 进入finally里, r===size.
但是在ArrayList这个删除场景里, 如果中间报了错, w确实会不同于size.而且, 数组中间还会留下一些已经应该被删除的数字.
比如,上图,如果删完 2 在数字 3 的位置异常了. 2 其实并没有被覆盖掉.. 数组里还是可以读出来 2. 所以, 这里把报错位置开始的数组内容,整体往前复制了一下, 挤掉了已经应该被删除的 2.
这个代码里, 用了一个很奇葩的小技巧:try{}finally{}不使用catch. 还是很有趣的.
好了, 今天的源码赏析就写到这里.
最后放一张, 的图, 来感觉一下上面提到的内容.
我是老K. 一个喜欢瞎研究的人.
原文始发于微信公众号（K字的研究）：java.util.Collection.removeAll源码解析
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/24598.html
