Kotlin 中的 Hashset toList() 时间复杂度，它是否恒定？

Question

我想它可能是 O(1)，但在网上找不到任何信息。

Answer 1

这里是相关的实现：

public fun <T> Iterable<T>.toList(): List<T> {
    if (this is Collection) {
        return when (size) {
            0 -> emptyList()
            1 -> listOf(if (this is List) get(0) else iterator().next())
            else -> this.toMutableList()
        }
    }
    return this.toMutableList().optimizeReadOnlyList()
}

看起来它归结为 toMutableList 中使用的 ArrayList(elements: Collection<E>) 构造函数的用法。 ArrayList 由一个数组支持，该数组在 creating the array 时产生 O(n) 时间。请记住，这最终取决于所使用的列表实现。现在是 ArrayList.

Kotlin 中的 Hashset toList() 时间复杂度，它是否恒定？

Hashset toList() time complexity in kotlin, is it constant or not?

time

hashset