java – 为什么HashSet.removeAll需要二次量的操作？

我有这个代码生成一个HashSet并调用removeAll().我做了一个类A,它只是一个int的包装,它记录了等于被调用的次数 – 程序输出这个数字.

import java.util.*;

class A {
    int x;
    static int equalsCalls;

    A(int x) {
        this.x = x;
    }

    @Override
    public int hashCode() {
        return x;
    }

    @Override
    public boolean equals(Object o) {
        equalsCalls++;
        if (!(o instanceof A)) return false;
        return x == ((A)o).x;
    }

    public static void main(String[] args) {
        int setSize = Integer.parseInt(args[0]);
        int listSize = Integer.parseInt(args[1]);
        Set<A> s = new HashSet<A>();
        for (int i = 0; i < setSize; i ++)
            s.add(new A(i));
        List<A> l = new LinkedList<A>();
        for (int i = 0; i < listSize; i++)
            l.add(new A(i));
        s.removeAll(l);
        System.out.println(A.equalsCalls);
    }
}

事实证明,removeAll操作不是线性的,我会想到：

$java A 10 10
55
$java A 100 100
5050
$java A 1000 1000
500500

其实呢似乎是二次的.为什么？

替换行s.removeAll(l);与(A b：l)s.remove(b);修正它以我期望的方式行事：

$java A 10 10
10
$java A 100 100
100
$java A 1000 1000
1000

为什么？

这是一个显示二次曲线的图表：

x和y轴是Java程序的两个参数. z轴是A.equals调用的数量.

该图是由本Asymptote程序生成的：

import graph3;
import grid3;
import palette;

currentprojection=orthographic(0.8,1,1);

size(400,300,IgnoreAspect);

defaultrender.merge=true;

real[][] a = new real[][]{
  new real[]{0,0},new real[]{0,1},3,3},2,6,6},10,10},4,15,15},5,21,21},28,28},7,36,36},8,45,45},9,55,55},66,66},11,78,78},12,91,91},13,105,105},14,120,120},136,136},16,153,153},17,171,171},18,190,190},19,210},};


surface s=surface(a,(-1/2,-1/2),(1/2,1/2),Spline);
draw(s,mean(palette(s.map(zpart),Rainbow())),black);
//grid3(XYZgrid);

数组a由Haskell程序生成：

import System.Process
import Data.List

f :: Integer -> Integer -> IO Integer
f x y = fmap read $readProcess "/usr/bin/java" ["A",show x,show y] ""

g :: [[Integer]] -> [String]
g xss = map (xs -> "new real[]{" ++ intercalate "," (map show xs) ++ "},") xss

main = do
  let n = 20
  xs <- mapM (x -> mapM (y -> f x y) [0..n]) [0..n]
  putStrLn $unlines $g xs

解决方法

public boolean removeAll(Collection<?> 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;
}

可以看到,当HashSet和集合具有相同的大小时,它会迭代HashSet,并为每个元素调用c.contains.由于您使用LinkedList作为参数,所以这是每个元素的O(n)操作.由于需要为被删除的n个元素中的每一个执行此操作,所以结果是O(n2)操作.

如果将LinkedList替换为提供了更有效的包含内容的集合,那么removeAll的性能就会相应改善.如果使HashSet大于集合,性能也应该显着提高,因为它会遍历集合.

（编辑：鄂州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!