Trove集合比标准Java集合更高效的原因是什么？

Question

最近在一次面试中，我被问到Java中HashMap的工作原理，并且我能够很好地解释说明，最坏情况下由于链表导致HashMap可能退化为列表。我被要求想出一种改进性能的方法，但是在面试期间我无法做到。面试官让我查找“Trove”。

我认为他指的是这个页面。我已经阅读了该页面提供的描述，但仍然无法弄清楚它如何克服java.util.HashMap的限制。

即使有提示也将不胜感激。谢谢！

- Kumud Sinha

---

Trove地图/集使用开放地址法，而不是JDK哈希表采用的链式方法。您还想了解什么？ - Thomas Jungblut

面试官通常有偏爱的话题。他们可能会阅读一些“酷”的东西，想知道有多少人听说过。我认为不了解Trove并不意味着一个人不能成为一名称职的Java开发人员；因此，这个特定的面试问题有点无意义。 - Dawood ibn Kareem

@ThomasJungblut - 我不知道开放地址和标记中没有看到任何强调。 - Kumud Sinha

@DavidWallace - 我同意你的观点。幸运的是，他们已经将我带入了下一轮面试。所以，也许这个问题只是在检查我是否听说过它。 - Kumud Sinha

恭喜@KumudSinha，并祝你在接下来的面试中好运。老实说，我认为你聪明、流畅地回答了这个问题。没听说过Trove不应该成为你申请这个职位的劣势。 - Dawood ibn Kareem

Answer 1

关键短语是“开放地址法”。它不是将哈希值映射到一个桶的数组中，而是将所有条目存储在一个大数组中。当您添加元素时，如果该空间已被使用，则只需向下移动数组以查找可用空间。

只要数组比条目数量大得足够多，并且哈希函数分布良好，就可以保持平均查找时间较短。并且通过使用一个数组，您可以获得更好的性能- 它更加缓存友好。

但是，如果每个键都哈希到相同的值（例如），则仍然会有最坏情况下的线性行为，因此它无法避免该问题。

- Alan Stokes

---

你忽略了许多不同的探测序列，选择了最糟糕的最坏情况行为——线性探测。线性探测查找并没有保持平均查找时间低，相反：它会退化成O(n)搜索，不仅在与分离链接相同的情况下（哈希冲突模表大小），而且在其他情况下也会发生（如聚类，即大量附近的哈希）。 - user395760

@DavidWallace 我读到的是：“当你添加一个元素时，如果它的空间已经被使用，你只需向下移动数组以找到一个空闲的空间。” 这意味着线性探测。 - user395760

@David 谢谢。我稍微调整了措辞。 - Alan Stokes

Delnan说，“向下移动数组”并不意味着“以线性方式逐个条目地向下移动数组”。不要在其中加入不存在的内容。 - Dawood ibn Kareem

@DavidWallace，也许是我的阅读理解出了问题，回想起来我不太确定——不要把那个理解为我同意你的观点；-）。或者Alan Stokes可以澄清一下吗？ - user395760

Answer 2

从Trove页面上看，我认为有两个主要的区别可以提高性能。

第一个是使用开放地址（http://en.wikipedia.org/wiki/Hash_table#Open_addressing）。这并不能避免冲突问题，但这意味着不需要为每个进入映射的项目创建“Entry”对象。

第二个重要的区别是能够提供自己的哈希函数，它与键的类提供的哈希函数不同。因此，如果有意义的话，您可以提供一个更快的哈希函数。

- Dawood ibn Kareem

Answer 3

Trove的一个优点是避免对象创建，尤其是针对原始类型而言。在嵌入式Java设备中使用大型哈希表时，这可以减少内存消耗。

另一个优点是它使用自定义的哈希代码/函数，无需覆盖hashcode（）方法。对于特定的数据集和擅长编写哈希函数的专家来说，这可以是一个优势。

- AlexWien

---

如果我使用Trove，那么通常是在处理原始集合/映射时。在这种情况下，差异确实是可衡量的，特别是在内存消耗方面。+1 - Marko Topolnik

谢谢Marko，我以前从未使用过Trove，但由于我从事嵌入式Java开发，这个Stack Overflow的问题让我阅读了Trove的概述。如果有一天我需要它，这是一个很好的了解。 - AlexWien