有谁知道为什么选择 HashMap 的存储桶通过 LinkedList 而不是另一个 Hashmap 来实现。如果桶本身变成了 HashMap，那么 contains 或 get 似乎是 O(1) 而不是摊销 O(1)。
问问题
251 次
2 回答
1
如果 HashMap 在另一个 HashMap 中实现为存储桶，它们仍将摊销 O(1)。假设两个字符串在 HashMap 的内部数据结构中被散列到同一个索引。如果该索引包含另一个 HashMap，则这两个字符串将再次散列到同一个索引，但也在桶 HashMap 中。然后你必须决定如何处理桶 HashMap 中的冲突。因此，使用 HashMap 作为存储桶来实现 HashMap 会产生两个冲突，而不是一个。此外，对于给定的数据集，HashMaps 比 LinkedLists 使用更多的内存。它们需要比数据条目更多的内存槽来保证分摊的 O(1) 运行时间。
是的，LinkedLists 不适合存储桶，因为它需要 O(n) 的时间来获取存储桶的正确值。不过，LinkedList 存储桶不应该变得非常大，因为 HashMap 应该足够大，以使冲突频率最小化。
于 2015-04-19T03:41:28.730 回答
1
想象一下桶是使用 HashMap 实现的，然后有很多冲突。一个好的散列函数应该尽量消除冲突，但我们正在考虑大量的元素。冲突现在将存储在存储桶的 HashMap 实现中。这个 HashMap 应该有空间来容纳它自己的桶。如果有如此多的元素，以至于这个 HashMap 在它的桶中也有几次冲突怎么办？即使有一个非常好的哈希函数，在某个地方，桶 HashMap 的桶（例如 B）将开始干扰具有多个桶的 HashMap A 的桶，其中一个由 B 实现。
LinkedList 不会有这个问题。还要记住，一旦一个桶被分配给一个 HashMap，它就是被外部阻塞的内存——即使它是空的。LinkedList 将动态增长，并且不需要比条目数更多的内存。
总而言之，您当然可以实现任何您想要的。您可以使用 ArrayList 或仅使用数组。但是它们也有自己的问题（删除会导致 O(n) 调整时间复杂度，并且数组必须具有固定大小）。所以考虑到所有的权衡，LinkedList 被发现是最好的选择。
于 2015-04-19T03:45:10.890 回答