hashtable - 哈希表问题

Question

当面试官问我哈希表的缺点是什么时。他暗示我哈希表在初始化时占用了大量空间。这意味着，我们需要为哈希表(桶)预先分配内存。即使我们实际上不需要那么多内存，我们也没有那么多条目。

这样合理吗？

因为我查了维基百科，文章中没有讨论这个缺点。

谢谢!

Answer 1

这取决于实现。实现哈希表的一种方法是使初始表不太大，如果负载因子(已用元素与可用槽的比率)增加超过阈值，则增加表大小(有几种方法可以做到这一点，所有详细信息都在 wikipedia article you discussed 中)。

在某些条件下(初始表大小很大，插入的元素很少)，您提到的情况当然是可能的，但这很可能是数据结构选择不当的结果。