哈希表问题

Question

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

这是否合理呢？

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

谢谢!

Answer 1

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

在某些情况下(初始表大小较大，插入的元素很少)，您提到的情况肯定是可能的，但这很可能是由于数据结构选择不当造成的。

Answer 2

根据您如何实现哈希表以及最初有多少个存储桶，这可能是一个合理的缺点。哈希表需要大约一半(或更多)的存储桶为空，否则冲突的可能性会更大。所有的存储桶最初都是空的，但在将项添加到哈希表之后，大多数实现都会扩展存储桶的数量，因此至少有一半是空闲的。这意味着您有O(n)个空的存储桶。这是否重要取决于你有多少物品和桶有多大。如果存储桶是结构化的，那么它们可能会非常大，因为它们需要存储散列值以及指向键和值的指针(如果不是实际的键和值)。更常见的情况是，存储桶是指向存储散列的容器的指针，以及指向键和值的指针。然后，每个存储桶的大小取决于指针的大小。这几乎总是32位或64位(除非您使用的是嵌入式处理器)。

因此，假设最好的情况是每个存储桶有4个字节，那么对于一个包含500,000个对象的哈希表，您最终将使用4MB的内存(请记住:大约一半的存储桶是空的)。另外，这50万个使用的存储桶中的每个都有一个节点，其中包含指向实际数据的指针。这将为每个值使用另外12个字节(尽管有内存对齐限制，但更像是16个字节)。那将是另外的8MB，不包括任何实际数据！

另一方面，大多数数据结构都有很大的内存开销。二进制搜索树的每个节点有四个指针(一个用于键，一个用于值，两个用于子节点)。在32位系统上，每个节点16字节，这与哈希表相当(至少在一个数量级内)。

如果存储的都是字符，那么与实际数据相比，这些数据结构的开销可能会很大，但在实践中，除非使用巨大的数据集和极其低效的哈希表实现，否则应该不会有太大问题。