哈希表的空间复杂度是多少？

Question

具有 32 位键和指向单独存储的值的 32 位指针的哈希表的大小是多少？

是 2^32 个槽 * (4 字节 (key) + 4 字节 (指向值的指针)) = 4 * 10^9 * (4 + 4) = 32GB ？

我想了解哈希表的空间复杂度。

Answer 1

我认为你问错了问题。数据结构的空间复杂度表示它占用的空间与其所容纳的元素数量相关。例如，O(1) 的空间复杂度意味着无论您在其中放入多少元素，数据结构始终消耗恒定空间。 O(n) 意味着空间消耗随着其中元素的数量线性增长。

哈希表的空间复杂度通常为O(n)。

因此，回答您的问题：这取决于它当前存储的元素数量，以及在现实世界中的实际实现。

哈希表的内存消耗下限是：（要存储的值的数量）*（值的大小）。因此，如果要在哈希表中存储 100 万个值，每个值占用 4 个字节，那么它将至少消耗 400 万个字节（大约 4MB）。通常，现实世界的实现会为基础设施使用更多的内存，但同样：这很大程度上取决于实际的实现，除了测量之外没有办法确定。

Answer 2

哈希表与哈希函数值和槽不匹配。哈希函数是以比哈希函数范围小得多的参考向量的大小为模来计算的。由于该值是固定的，因此在空间复杂度计算中不考虑它。

因此，每个合理哈希表的空间复杂度都是O(n)。

一般来说，这效果很好。虽然键空间可能很大，但要存储的值的数量通常很容易预测。当然，数据结构开销在功能上可接受的内存量通常是显而易见的。

这就是哈希表如此普遍的原因。它们通常为给定任务提供最佳数据结构，将严格限制的内存开销与优于 log₂ n 的时间复杂度混合在一起。我喜欢二叉树，但它们通常不会打败哈希表。

Answer 3

假设我们有一个简单的哈希表，其中存储桶的数量等于元素大小的两倍。即 O(2n) 元素数量为 O(n)。

当元素数量超过可用存储桶数量的一半时，您需要创建一个新的存储桶数组，将大小加倍，并将所有元素重新哈希到新存储桶数组中的新位置。

386  public V put(K key, V value) {
387      if (key == null)
388          return putForNullKey(value);
389      int hash = hash(key.hashCode());
390      int i = indexFor(hash, table.length);
391      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392          Object k;
393          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394              V oldValue = e.value;
395              e.value = value;
396              e.recordAccess(this);
397              return oldValue;
398          }
399      }
401      modCount++;
402      addEntry(hash, key, value, i);
403      return null;
404  }

768  void addEntry(int hash, K key, V value, int bucketIndex) {
769      Entry<K,V> e = table[bucketIndex];
770      table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
771      if (size++ >= threshold)
772          resize(2 * table.length);
773  }

471  void resize(int newCapacity) {
472      Entry[] oldTable = table;
473      int oldCapacity = oldTable.length;
474      if (oldCapacity == MAXIMUM_CAPACITY) {
475          threshold = Integer.MAX_VALUE;
476          return;
477      }
479      Entry[] newTable = new Entry[newCapacity];
480      transfer(newTable);
481      table = newTable;
482      threshold = (int)(newCapacity * loadFactor);
483  }

488  void transfer(Entry[] newTable) {
489      Entry[] src = table;
490      int newCapacity = newTable.length;
491      for (int j = 0; j < src.length; j++) {
492          Entry<K,V> e = src[j];
493          if (e != null) {
494              src[j] = null;
495              do {
496                  Entry<K,V> next = e.next;
497                  int i = indexFor(e.hash, newCapacity);
498                  e.next = newTable[i];
499                  newTable[i] = e;
500                  e = next;
501              } while (e != null);
502          }
503      }
504  }

参考资料：

HashMap.put
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.put%28java.lang.Object%2Cjava .lang.Object%29

Grepcode 已关闭，您可以在此处查看 openjdk 存储库作为更好的参考：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Answer 4

这个问题仍然没有完美的答案。我不确定占用的空间。
根据我对这个问题的理解。大小是动态的并且随着输入的大小而变化。

也就是说，我们从一个随机数开始，即哈希表大小，与哈希函数值相比要小得多。然后我们插入输入。现在，当冲突开始发生时，我们动态地将哈希表大小加倍。
我认为这就是 O(n) 复杂度的原因。如果我错了，请纠正我。