hashmap - 为什么 LinkedList 作为 HashMap 的存储桶实现而不是另一个 Hashmap？

Question

有谁知道为什么选择通过 LinkedList 而不是另一个 Hashmap 来实现 HashMap 的存储桶。如果桶本身变成了 HashMap，那么 contains 或 get 的时间复杂度似乎是 O(1)，而不是摊销 O(1)。

Answer 1

想象一下桶是使用 HashMap 实现的，然后会出现很多冲突。一个好的哈希函数应该尝试消除冲突，但我们正在考虑大量的元素。冲突现在将存储在存储桶的 HashMap 实现中。这个 HashMap 应该有空间来容纳它自己的存储桶。如果元素数量如此之多以至于该 HashMap 的存储桶内也发生了多次冲突怎么办？即使有一个非常好的哈希函数，在某个地方，存储桶 HashMap 的存储桶(例如 B)将开始干扰 HashMap A 的存储桶，该 HashMap A 有多个存储桶，其中一个存储桶是由 B 实现的。

LinkedList不会有这个问题。还要记住，一旦将存储桶分配给 HashMap，内存就会被阻止到外部 - 即使它是空的。 LinkedList 将动态增长，并且不需要比条目数量更多的内存。

总而言之，您当然可以实现任何您想要的。您可以使用 ArrayList 或仅使用数组。但它们也有自己的问题(删除会导致 O(n) 调整时间复杂度，并且数组必须具有固定大小)。因此，考虑到所有权衡，LinkedList 被认为是最好的选择。