rex*_*rex 7 memory dictionary hashtable space-complexity data-structures
我一直在阅读一些有关哈希表、字典等的内容。我看过的所有文献和视频都暗示哈希表具有空间/时间权衡属性。
我很难理解为什么哈希表比具有相同总元素（值）数量的数组或列表占用更多的空间？它与实际存储散列密钥有关吗？
据我了解，用基本术语来说，哈希表采用一个键标识符（例如某个字符串），将其传递给某个哈希函数，该函数会生成数组或其他数据结构的索引。除了在数组或表中存储对象（值）时明显使用内存之外，为什么哈希表会占用更多空间？我觉得我错过了一些明显的东西......
就像你说的，这都是关于查找时间和空间之间的权衡。底层数据结构的空间（桶）数量越多，哈希函数可以存储每个项目的位置数量就越多，因此发生冲突的可能性就越大（因此比恒定时间性能更差）降低了。然而，拥有更多的桶显然意味着需要更多的空间。项目数与桶数的比率称为负载因子，在这个问题中有更详细的解释：HashMap 中负载因子的意义是什么？
在最小完美哈希函数的情况下，您可以实现在 n 个桶中存储 n 个项目（负载因子为 1）的 O(1) 性能。