java - Java数据结构的空间复杂度

Question

我一直在搜索许多包含 Java 数据结构空间复杂度信息的网站。我正在专门搜索 HashMap、ArrayList、Stack 和 LinkedList 的空间复杂度。我发现的一个网站很接近并且只有 Stack 和 LinkedList 上的信息是:http://bigocheatsheet.com/ ，但它只有最坏的情况。任何人都知道任何其他来源有关于 HashMap 或 ArrayList 的空间复杂性的信息，最好是平均情况和最坏情况吗？

Answer 1

它们在正常情况下的空间使用都是O(N)。 (我认为所有标准集合数据结构也是如此……)

当然，这并没有告诉您一些关于这些数据结构在实践中将使用多少空间的重要事实。例如:

• ArrayList 或HashMap 的空间使用与列表大小不成正比。两者都针对部分或全部空间利用采取了“满时双倍大小”的策略。

• 在最好的情况下，ArrayList 每个元素使用的空间比 LinkedList 少，而 LinkedList 每个元素使用的空间更少元素而不是 HashMap。

等等。

也很难量化最坏的情况……因为某些使用模式会导致空 ArrayList 或HashMap 占用空间大。对于这些数据结构，空间使用可能与最大N 值(到目前为止)而不是当前N 值成正比。

• 当元素被移除时，ArrayList 不会“归还”空间。

• 使用 HashMap，链占用的空间可以增长和缩小，但哈希数组只会增长。