哈希表、数组、数组列表、链表等的空间复杂度是什么？

Question

我想了解一些流行编程语言中基本数据结构的空间复杂度。

Answer 1

几乎所有大小不小的数据结构，其大小都是在 n 的范围内。

• 数组 = 正好是 n
• 数组列表 = 在 n 和 k*n 之间（默认 k=2）
• 链表 = 正好是 n
• 哈希表 = 最坏情况下是 n/k（默认 k 是 0.75）

Answer 2

对于Java来说：（大致估算）

            Memory O(x) | General Case
Array     |       n     |    n
ArrayList |       n     |    2 * n
LinkedList|       n     |    n * (node size)
HashTable |       n     |    ~n
Map       |       n     |    (n * key_size) + n

Answer 3

这些东西的空间复杂度都是 O(n)。唯一不同的就是系数，这完全取决于具体的实现方式。尤其是当你开始考虑像预先分配空间来减少时间复杂度时，这一点就更明显了。

举个例子，数组列表结构通常会预先分配一些额外的空间。因此，它们对于一定数量的对象的确切复杂度其实是一个范围，这完全依赖于具体的实现以及它们是如何被创建和使用的。比如，如果我写一个数组列表，每次需要更多空间时总是分配三个额外的空间，而当有超过五个空闲空间时总是缩减到三个空闲空间，那么对于 n 的实际复杂度将是 [n, n + 5] + overhead。

在编程时选择这些东西的主要区别通常在于使用的方便程度，以及它们与你的使用方式的契合度。例如，链表在随机访问时表现很糟糕，但在迭代时却非常出色。