java - 数组声明是线性时间运算还是常数时间运算？

Question

这个问题已经有答案了:

Java: what's the big-O time of declaring an array of size n? (4 个回答)

已关闭 4 年前。

boolean[] arr = new boolean[n];

上述初始化的时间复杂度是多少？是 O(1) 还是 O(n) ？我认为它是 O(1)，因为程序只是向 JVM 请求大小为 n 的内存块。在这种情况下，JVM(热点)实际上是如何分配内存的？

到目前为止，我已经查找了以下链接，但我不清楚答案:

Thread-1 Thread-2

Answer 1

我认为一般来说它是O(n)，因为声明的数组需要为零并具有默认值，在您的情况下为false.

但是虚拟机也可以证明该数组不是立即读取的，即有人首先将所有元素写入其中，然后才读取它们。在这种情况下，复杂性将是 O(1)，因为您实际上并没有做任何事情(没有默认值放置在数组本身内部) - 因此是恒定的。

例如，这就是 java-11 中使用 Collection::toArray 发生的情况，通过:

default <T> T[] toArray(IntFunction<T[]> generator) {
    return toArray(generator.apply(0));
} 

所以当你有类似的东西时:

List.of(1, 2, 3, 4)
    .toArray(x -> new Integer[x]);

该实现实际上会执行new Integer[0]，并将其与一些System.arrayCopy结合使用，而不是推断的new Integer[4]。这样做是因为 VM 可以 prove不需要归零，因此完全跳过它。