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

Question

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

我很难理解为什么哈希表比具有相同数量的总元素（值）的数组或列表占用更多空间？它与实际存储散列键有关吗？

据我所知，在基本术语中，哈希表需要一个键标识符（比如一些字符串），通过一些哈希函数传递它，该函数会输出一个数组或其他数据结构的索引。除了将对象（值）存储在数组或表中的明显内存使用之外，为什么哈希表会占用更多空间？我觉得我错过了一些明显的东西......

Answer 1

就像你说的，这完全是关于查找时间和空间之间的权衡。底层数据结构具有的空间（桶）数量越多，散列函数可以存储每个项目的位置数量就越多，因此发生冲突的可能性就越大（因此比恒定时间性能更差）降低了。然而，拥有更多的桶显然意味着需要更多的空间。项目数与桶数之比称为负载因子，在这个问题中有更详细的解释：HashMap 中负载因子的意义是什么？

在最小完美散列函数的情况下，您可以实现在 n 个桶中存储 n 个项目的 O(1) 性能（负载因子为 1）。