java - Trove Collection 如何比标准 Java Collection 更高效？

Question

在最近的一次采访中，有人问我 HashMap 在 Java 中是如何工作的，我能够很好地解释它并解释在最坏的情况下 HashMap 可能会由于链接而退化为列表。我被要求想出一种方法来提高这种表现，但在面试中我无法做到。面试官让我查“Trove”。

我相信他指的是 this page .我已阅读该页面上提供的说明，但仍然无法弄清楚它是如何克服 java.util.HashMap 的限制的。

即使是提示，我们也将不胜感激。谢谢!!

Answer 1

那里的关键词是开放寻址。所有条目都在一个大数组中，而不是散列到一组桶中。当您添加一个元素时，如果它的空间已被使用，您只需向下移动数组以找到可用空间。

只要数组保持比条目数足够大并且散列函数分布良好，就有可能使平均查找时间保持较小。通过拥有一个阵列，您可以获得更好的性能 - 它对缓存更友好。

但是，如果(比方说)每个键都散列为相同的值，它仍然具有最坏情况下的线性行为，因此它无法避免该问题。