1

此类是出现问题的示例：

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);
}

现在是我的问题，方法 1 在 Java 优化后是否具有与方法 2 相同的时间复杂度。（我使用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)。

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

4

3 回答 3

7

不，javac不会（也不能）优化它。需要将您在源代码中描述的字节码发送到此级别。而且 JVM 还不够智能，无法将其优化掉。它太可能有副作用来证明。

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

于 2013-02-14T14:24:37.113 回答
0

我能在这里说什么，但是创建一个新的 HashSet 并通过构造函数填充它是昂贵的！

Java 不会“优化”这项工作：即使您和我都知道它会给出与“通过” contains() 调用相同的结果，但 java 无法知道这一点。

于 2013-02-14T14:24:24.833 回答
0

不，这超出了优化范围。您返回了一个新对象，您可以在其他地方使用它，Java 不应该忽略它。将创建一个新的 HashSet。

退回副本不是一个好习惯。这不仅费时，而且费空间。正如肖恩所说，您可以使用 unmodifiableSet 进行包装，也可以将其包装在您自己的类中。

你可以试试这个：

public static Set<E> getMyHashSet() {
    return Collection.unmodifiableSortedSet(myHashSet);
}

注意：使用该方法将返回您的集合的视图，而不是副本。

于 2013-02-14T14:37:11.367 回答