java - 以线性时间迭代数组时 HashMap 的空间复杂度

Question

我对程序的空间复杂度存有疑问。假设我正在迭代一个大小为 n(可能以十亿为单位)的数组(存储事件 ID)。我想跟踪每个事件 ID 的发生，所以我使用 HashMap 将事件 ID 存储为键，并将其发生计数器存储为值。

伪代码如下:

Map m =  HashMap<>
for i to n-1
  if m.contains(i)
     int prevCount =  m.get(i)
     m.put(i, prevCount +1)
  else
   m.put(i, 1)

空间复杂度是多少？

PS 这是我在 stackoverflow 中的第一个问题，如果它看起来重复，请引导我找到正确答案。

Answer 1

您的循环最多将 n-1 个键/值对添加到 HashMap。

因此，空间复杂度为O(n)，因为HashMap内部存储由一个数组组成，其大小将达到接近n的2的幂(假设你没有给 HashMap 一个比 n 大得多的初始容量，数组的每个元素都是一个链表，O(1 ) 平均元素数。