当一个值被哈希到相同的值时，它被添加到哈希值引用的链表中。为什么哈希表的实现使用数组上的链表作为存储桶？
是因为数组在初始化时具有预定的大小，因此当向存储桶中添加太多元素时需要调整大小？
问问题
6417 次
2 回答
7
是的：通常，这是因为数组具有预定的大小。桶不需要使用链表或数组；一些狡猾的实现使用另一个哈希表，然后使用链表或数组作为它的桶！
如果使用数组，则哈希表对每个数组元素都有一个预先确定的大小。每个可能的存储桶都已分配，您的哈希表可能非常大。如果你有很多内存，或者你期望一个非常完整的哈希表，那可能没问题。您可以通过持有指向数组的指针并根据需要分配它来缓解这种情况。
数组可以被索引，所以你可以保持数组排序。然后，如果它变大，您可以进行二进制搜索以找到您想要的密钥。
如果使用链表，则必须遍历链表以线性查找所需的匹配项。这不是太有效，但它最大限度地减少了内存使用。
与所有数据结构问题一样，您必须考虑您将拥有哪些访问模式以及如何使用和填充结构；您想赢得哪些权衡，哪些是您不太关心的权衡？
于 2012-11-28T00:53:50.857 回答
4
他们没有。
声称“哈希表的实现”使用链表是一种过度概括。Java 可以。许多其他语言没有。例如，Python 使用开放散列，请参阅此问题的答案，如何实现 Python 的内置字典
通常，通用 API 的设计者面临着一个非常艰难的选择，因为他们不了解用户的用例。有不同的实现选择和不同的权衡，例如，如果你只添加元素但从不删除，则与经常变异的 hashmap 不同的选择适用。等等。
于 2012-11-28T00:58:25.113 回答