为什么哈希表在存储桶的数组上使用链表？

Question

当一个值被散列为相同的值时，它将被添加到该散列值引用的链接列表中。为什么哈希表的实现将数组上的链表用作存储桶？

是因为数组在初始化时具有预定的大小，所以在存储桶中添加太多元素时需要调整大小吗？

Answer 1

是的：通常，这是因为数组具有预定的大小。不需要为存储桶使用链接列表或数组；一些狡猾的实现使用另一个哈希表，该哈希表随后将一个链表或数组用于其存储桶！

如果您使用数组，则哈希表对于每个数组元素都具有预定的大小。每个可能的存储桶都已分配，您的哈希表可能很大。如果您有很多内存，或者期望哈希表非常完整，那可能没问题。您可以通过持有指向数组的指针并按需分配它来减轻这种情况。

可以为数组建立索引，因此您可以对数组进行排序。然后，如果它变大，则可以进行二进制搜索以找到所需的密钥。

如果使用链表，则必须遍历链表才能线性找到所需的匹配项。效率不是很高，但是可以最大程度地减少内存使用。

与所有数据结构问题一样，您必须考虑将拥有哪些访问模式以及如何使用和填充结构。您想赢得哪些权衡，哪些不是您最关心的权衡？