Java是否将新的HashSet(someHashSet).contains()优化为O(1)？

Question

这个类是出现问题的一个例子:

public class ContainsSet {
    private static HashSet<E> myHashSet;

    [...]

    public static Set<E> getMyHashSet() {
        return new HashSet<E>(myHashSet);
    }

    public static boolean doesMyHashSetContain(E e) {
        return myHashSet.contains(e);
    }
}

现在想象两个可能的功能:

boolean method1() {
    return ContainsSet.getMyHashSet().contains(someE);
}
boolean method2() {
    return ContainsSet.doesMyHashSetContain(someE);
}

现在我的问题是,在方法2的Java优化之后,方法1是否具有相同的时间复杂度.(我使用HashSet而不仅仅是Set强调它myHashSet.contains(someE)具有复杂性O(1).)

如果没有优化,它就不会.虽然.contains()具有复杂性O(1),但是new HashSet<E>(myHashSet)具有复杂性O(n),这将使方法1具有复杂性O(n) + O(1) = O(n),这与心爱的人相比是可怕的O(1).

我导入此问题的原因是因为如果您不允许外部类更改其内容,我会被教导不返回列表或集合.返回副本是一个明显的解决方案,但它可能非常耗时.

Answer 1

不,javac不(并且不能)优化这一点.需要将源中描述的字节代码发送到此级别.并且JVM几乎不够智能,无法优化它.它太可能有副作用来证明.

HashSet如果您想要不变性,请不要返回副本.将其包装在不可修改的包装中:Collections.unmodifiableSet(myHashSet)