什么是最有效的 Java 集合库？

什么是最有效的 Java 集合库？

几年前，我做了很多 Java 工作，当时的印象是 Trove是最好(最有效)的 Java 集合实现。但是当我阅读问题“ 最有用的免费 Java 库？”的答案时，我注意到 Trove几乎没有被提及。那么现在哪个 Java 集合库最好呢？

更新: 为了澄清，我主要想知道当我必须在一个散列表中存储数百万条目时使用什么库(需要一个小的运行时和内存占用)。

72405 次浏览
小开
最佳答案

从检查来看，Trove 看起来只是一个基本类型的集合库——它并不意味着要在 JDK 中的普通集合之上添加很多功能。

就个人而言(我有偏见) ，我喜欢 番石榴(包括以前的 GoogleJavaCollectionsproject)。它使各种任务(包括集合)更加容易，至少在一定程度上是合理有效的。鉴于集合操作很少在我的代码中形成瓶颈(根据我的经验) ，这比集合 API 要“好”，后者可能更有效，但不会使我的代码具有可读性。

鉴于 Trove 和 Guava 之间的重叠几乎为零，也许您可以澄清一下实际上要从馆藏库中查找什么。

小开

java.util

对于这个显而易见的答案，我很抱歉，但是对于大多数应用来说，默认的 Java 收藏已经足够了。

小开

如果您计划在多个线程中使用 HashMap，那么应该提到 ConcurrentHashMap 以及 java.util.concurrent包。因为这是标准 Java 的一部分，所以占用的内存很少。

小开

这取决于我们如何定义“效率”。

每个数据结构都有自己的读、写、迭代、内存占用等行为。一个库中的链表可能与其他库中的链表相同。散列映射读取 O (1)比链表 O (n)更快。

但是当我读到“最有用的免费 Java 库?”我注意到宝藏很少被提及。

这听起来不像是“最有效率”，我听起来像是“最受欢迎”。

只是一些反馈-我从来没有听说过它，我不知道任何人使用它。我对 JDK、 Google 或 ApacheCommons 中内置的集合非常熟悉。

小开

宝藏有一些好处。

  • 更小的内存占用，它不使用 Map.Entry 对象
  • 你可以使用散列策略来代替映射的键，这样可以节省内存，并且意味着你不需要每次都定义一个新的键来缓存一个对象的属性
  • 它具有基元集合类型
  • 认为它有某种形式的内部迭代器

也就是说，自从 trove 被编写以来，已经做了很多改进 jdk 集合的工作。

正是这些散列策略吸引了我... ... 谷歌搜索和阅读他们的概述。

小开

正如其他评论员所注意到的，“高效”的定义撒下了一张大网。然而，还没有人提到 Javolution 图书馆。

其中一些亮点:

  • Javolution 类是快速的，非常快的(例如，在 O [ Log (n)]中的文本插入/删除代替了标准 StringBuffer/StringBuilder 中的 O [ n ])。
  • 所有 Javolution 类都是硬实时兼容的，并具有高度确定性的行为(在微秒范围内)。此外(与标准库不同) ，Javolution 是 RTSJ 安全的(与 JavaReal-Time 扩展一起使用时没有内存冲突或内存泄漏)。
  • Javolution 的实时集合类(map、 list、 table 和 set)可以替代大多数标准集合类，并提供额外的功能。
  • Javolution 集合提供了并发性保证，使并行算法的实现更加容易。

Javolution 发行版包含一个基准测试套件，这样您就可以看到它们是如何与其他库/内置集合进行比较的。

小开

需要考虑的一些收藏书目:

我将首先使用 JDK 集合库。它涵盖了您需要做的最常见的事情，并且显然您已经可以使用它了。

Google Collection 可能是 JDK 之外最好的高质量库，它得到了广泛的使用和良好的支持。

ApacheCommons 集合比较老，有点“太多厨师”的问题，但是也有很多有用的东西。

Trove 具有非常专门的集合，用于诸如基本键/值之类的情况。现在，我们发现在现代的 JDK 上，在 Java5 + 集合和并发用例中，JDK 集合的性能甚至超过了专门的 Trove 集合。

如果您有很高的并发性用例，那么您一定要检查高级库中的 NonBlockingHashMap 之类的东西，这是一个无锁实现，如果您有正确的用例，它可以跳过 ConcurrentHashMap。

小开

如果您想在一个散列表中存储数百万条记录，那么很可能会遇到内存问题。例如，当我试图用230万个 String 对象创建一个映射时，就发生了这种情况。我选择了 伯克利数据库，它非常成熟，表现也很好。它们有一个包装 CollectionsAPI 的 JavaAPI，因此您可以很容易地创建任意大小的映射，只占用很少的内存。但是访问速度较慢(因为它存储在磁盘上)。

后续问题 : 是否有一个像样的(和高效的)、维护良好的、用于不可变集合的库？Clojure 对此有很好的支持，如果能为 Java 提供类似的支持就好了。

小开

现在的问题是如何在 Map 中存储大量数据，这些数据可以使用类似 int的基本类型来表示。在我看来，这里的一些答案非常具有误导性。看看为什么。

我修改了来自 Trove的基准测试来度量运行时和内存消耗。我还将 PCJ添加到这个基准测试中，这是另一个用于基本类型的集合库(我广泛使用这个库)。“官方”的基准没有将 IntIntMaps 与 Java Collection 的 Map<Integer, Integer>进行比较，可能存储 Integers和存储 ints从技术角度来看是不一样的。但是用户可能不关心这些技术细节，他希望有效地存储 ints可表示的数据。

首先是守则的相关部分:

new Operation() {


private long usedMem() {
System.gc();
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}


// trove
public void ours() {
long mem = usedMem();
TIntIntHashMap ours = new TIntIntHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
ours.put(i, i);
}
mem = usedMem() - mem;
System.err.println("trove " + mem + " bytes");
ours.clear();
}


public void pcj() {
long mem = usedMem();
IntKeyIntMap map = new IntKeyIntOpenHashMap(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("pcj " + mem + " bytes");
map.clear();
}


// java collections
public void theirs() {
long mem = usedMem();
Map<Integer, Integer> map = new HashMap<Integer, Integer>(SET_SIZE);
for ( int i = dataset.size(); i-- > 0; ) {
map.put(i, i);
}
mem = usedMem() - mem;
System.err.println("java " + mem + " bytes");
map.clear();
}

我假设数据是原始的 ints，这看起来很正常。但是这意味着 java util 的运行时损失，因为自动装箱对于原始集合框架来说是不必要的。

WinXP jdk1.6.0 _ 10上的运行时结果(当然没有 gc()调用) :

100000 put operations      100000 contains operations
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

虽然这看起来可能已经很激烈，但这不是使用这样一个框架的理由。

原因是内存性能。包含100000个 int条目的 Map 的结果:

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

与原始集合框架相比，Java 集合需要 超过三次内存。也就是说，您可以在内存中保留三倍的数据，而不必求助于降低运行时性能的磁盘 IO。这很重要。阅读 高可伸缩性找出原因。

根据我的经验，高内存消耗是 Java 最大的性能问题，当然也会导致更差的运行时性能。原始收集框架在这方面真的很有帮助。

所以: 不，java.util 不是答案。并且“添加功能”到 Java 集合并不是问效率的关键。而且，现代 JDK 集合的 没有“性能甚至超过了专门的 Trove 集合”。

免责声明: 这里的基准远未完成，也不是完美的。这是为了把我在许多项目中经历过的问题说清楚。原始集合非常有用，足以容忍使用大量数据的可疑 API-如果。

小开

要在地图中存储数百万个 String，请看 http://code.google.com/p/flatmap

小开

我是 快乐——源泉——锻造的收藏快乐收藏的开发者

  1. 基于事件的集合
  2. 无法改变
  3. 分类列表
  4. 缓存
小开

我知道这是一个老职位，有一吨的答案在这里。 但是，上面的答案是肤浅的和过于简单的方面建议一个图书馆。没有一个库能够很好地跨越这里提供的各种基准测试。我得出的唯一结论是，如果您关心性能和内存，特别是处理基元类型，那么非 jdk 备选方案更值得一看。

这里有一个更合理的分析，关于基准测试机制和所涵盖的库。 这个 是 mahout dev 列表中的一个线程。

所涵盖的图书馆包括

  • HPPC
  • 宝藏
  • FastUtil
  • Mahout (Colt)
  • Java 收藏

二零一五年六月更新 : 不幸的是，最初的基准测试不再可用，而且有点过时。 这里 是其他人最近(2015年1月)完成的基准测试。它不像原来的链接那样全面，也没有交互式的探索工具。


提交答案