为什么哈希表比其他数据结构占用更多的内存？

Question

我一直在阅读哈希表，字典等相关内容。所有我看过的文献和视频都暗示哈希表具有空间/时间权衡属性。

我不明白为什么哈希表占用的空间比相同数量元素（值）的数组或列表更多？这与实际存储散列键有关吗？

据我所知，在基本术语中，哈希表使用键标识符（例如某些字符串），通过某些哈希函数将其传递，该函数会输出数组或其他数据结构的索引。除了显而易见的内存使用来存储数组或表中的对象（值）外，为什么哈希表会占用更多的空间？我感觉自己漏掉了一些明显的东西...

- rex

Answer 1

正如你所说，这一切都是关于查找时间和空间之间的权衡。底层数据结构拥有的空间（桶）越多，哈希函数可以潜在地存储每个项的位置就越多，因此碰撞的机会（因此性能不如常数时间）就减少了。然而，拥有更多的桶显然意味着需要更多的空间。项目数量与桶数量的比率称为负载因子，并在此问题中详细解释：HashMap中负载因子的重要性是什么？ 在最小完美哈希函数的情况下，您可以在n个桶中存储n个项目，从而实现O（1）性能（负载因子为1）。

- mtripp100

---

抱歉，我觉得我有点笨，但是在最坏的情况下（对于空间而言），每个桶只存储1个项目。这不是有效地像一个数组，因此与数组相同大小而不是更大吗？ - rex

是的，在理想情况下，每个桶都恰好存储1个项目，因此N个项目映射到N个桶。然而，在实践中，这几乎从未发生，因为随着占用的桶数增加，任何明智的哈希表实现都会“增长”底层数据结构以包括更多的桶，以最小化两个项目散列到相同空间的可能性。如果空间比时间更重要，则哈希表可能不是您想要的东西。 - mtripp100

但是所有桶中的总项目数仍将为N，那么为什么这会占用比N个项的数组更多的空间呢？ - rex

你是在暗示我们添加额外的桶，这些桶可以保持为空，与这些桶相关的开销是哈希表占用的额外内存吗？ - rex

@ArmenSafieh-Garabedian 是的，这是额外使用的主要原因，尽管您可能还需要考虑由碰撞解决方法（例如链表）使用的额外内存。 - mtripp100

Answer 2

正如您所提到的，哈希表的底层结构是一个数组，这是数据结构世界中最基本的类型。

为了使哈希表快速支持O(1)操作，底层数组的容量必须足够大。它使用“负载因子”这个术语来评估这一点。 “负载因子”是哈希表中元素数量与哈希表中所有单元格数量的比率。它评估哈希表有多空。

为了使哈希表运行快速，“负载因子”不能大于某个阈值。例如，在“二次探测”冲突解决方法中，负载因子不应大于0.5。当向哈希表插入新元素时，如果负载因子接近0.5，则需要重新哈希表以满足要求。

因此，哈希表在运行时方面的高性能基于更多的空间使用。这是时间和空间的权衡。

- Chris Bao