Array声明是线性时间操作还是常数时间操作？

Question

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 不需要归零，因此完全跳过它。

Is Array declaration linear time operation or constant time operation?