什么是最有效的Java Collections库?

什么是最有效的Java Collections库?

几年前,我做了很多Java,并且有一个印象,那就是这个库是最好的(最高效的)Java Collections实现。 但是当我阅读“ 最有用的免费Java库 ”的答案时,我注意到几乎没有提到这个库 。 那么现在哪个Java Collections库最好?

更新:为了澄清,我主要想知道什么库,当我必须存储数百万条目哈希表等(需要一个小的运行时间和内存占用)。

从检查看来,Trove看起来像是一个原始types的集合库,它并不像是在JDK的正常集合中添加大量的function。

个人(我有偏见),我喜欢番石榴 (包括前谷歌Java集合项目)。 它使得各种任务(包括集合)变得更容易,至less是合理有效的。 鉴于集合操作很less在我的代码中形成瓶颈(以我的经验),这比集合API“更好”,这可能更有效,但不会使我的代码可读。

鉴于Trove和番石榴之间的重叠几乎是零,也许你可以澄清你从collections库实际上寻找什么。

现在的问题是关于如何在Map中存储大量的数据,这些数据可以用像int这样的基本types来表示。 这里的一些答案在我看来是非常误导的。 让我们看看为什么。

我从trove修改了基准来测量运行时和内存消耗。 我还将PCJ添加到这个基准中,这是基本types的另一个集合库(我广泛使用它)。 “官方”的基准testing并没有将IntIntMaps与Java集合的Map<Integer, Integer> ,可能存储的是Integers而从技术的angular度来看,存储的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(); } 

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

运行时结果(当然没有gc()调用)在WinXP上,jdk1.6.0_10:

                       100000放置操作100000包含操作 
 java集合1938毫秒203毫秒
 trove 234 ms 125 ms
 pcj 516 ms 94 ms

虽然这可能看起来很激烈,但这不是使用这种框架的原因。

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

 Java集合在6644536和7168840字节之间振荡
 trove 1853296字节
 pcj 1866112字节

与原始集合框架相比,Java集合需要三倍以上的内存。 也就是说,您可以将内存中的数据保留三倍,而不必依靠磁盘IO来降低运行时性能。 这很重要。 阅读highscalability找出原因。

根据我的经验,高内存消耗是Java最大的性能问题,这当然也会导致运行时性能下降。 原始的集合框架可以真正帮助这里。

所以:不,java.util不是答案。 对Java集合的“添加function”并不是问及效率的关键。 而现代的JDK系列也不会 “甚至超出特定的Trove系列”。

免责声明:这里的基准很不完整,也不完美。 这是为了开启我在许多项目中经历的这一点。 如果您使用大量的数据,原始集合足以容忍可怕的API。

我知道这是一个旧的post,这里有很多答案。 但是,上面的答案在build议一个图书馆方面是肤浅的,过于简单的。 没有一个图书馆能够在这里介绍的各种基准方面做得很好。 我得出的唯一结论是,如果你关心性能和内存,特别是处理原始types,那么更值得关注非jdk的select。

就基准力学和所涉及的图书馆而言,这是一个更为合理的分析。 这是mahout开发人员列表中的一个线程。

涵盖的图书馆是

  • HPPC
  • 特罗韦
  • FastUtil
  • Mahout(Colt)
  • Java集合

2015年6月更新 :不幸的是,原来的基准testing已经不复存在,除了有点过时。 这是一个相当近期(2015年1月)由别人完成的基准。 它不是那么全面,也没有原始链接的互动探索工具。

正如其他评论家所注意到的那样,“高效”的定义构成了一个广泛的networking。 但是还没有人提到Javolution库 。

一些亮点:

  • Javolution类速度快,速度非常快(例如,标准的StringBuffer / StringBuilder,O [Log(n)]中的文本插入/删除,而不是O [n])。
  • 所有Javolution类都很难实时兼容,并具有高度确定性的行为(在微秒范围内)。 此外(与标准库不同),Javolution是RTSJ安全的(与Java实时扩展一起使用时没有内存冲突或内存泄漏)。
  • Javolution的实时集合类(地图,列表,表和集)可以用来代替大多数标准的集合类,并提供额外的function。
  • Javolution集合提供并发保证,使并行algorithm的实现更容易。

Javolution发行版包含一个基准testing套件,因此您可以看到它们如何与其他库/内置集合进行堆叠。

一些收集库要考虑:

  • java.util中的Java集合
  • 特罗韦
  • Google Collections库
  • Apache Commons集合
  • 从悬崖点击高级库
  • Doug Lea的集合 lib – 不再支持,而且大部分都是在JDK中重build的

我首先要到达JDK集合库。 它涵盖了你需要做的最常见的事情,显然已经提供给你。

Google Collections可能是JDK之外最好的高质量图书馆。 它被大量使用和很好的支持。

Apache Commons Collections比较老,从“太多厨师”的问题中受到一些困扰,但也有很多有用的东西。

Trove拥有非常专业化的集合,例如原始键/值。 现在我们发现,在现代JDK和Java 5+集合和并发用例中,JDK集合甚至超出了专门的Trove集合。

如果你有很高的并发使用情况,你应该检查像NonBlockingHashMap这样的高级lib,这是一个无锁的实现,并且可以在ConcurrentHashMap上跺脚,如果你有正确的用例。

java.util

对不起,很明显的答案,但对于大多数用途,默认的Java集合是绰绰有余的。

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

我是来自source-forge的开心collections的开发者

  1. 基于事件的集合
  2. 不可修改
  3. sorting列表
  4. 高速caching

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

每个数据结构在读,写,迭代,内存占用等方面都有自己的Big-Oh行为。一个库中的链表可能与其他库中的链表相同。 读取O(1)的哈希映射将比链接列表O(n)更快。

但是当我阅读“最有用的免费Java库?”这个问题的答案时 我注意到这个东西几乎没有提到。

这听起来不像“最高效”。 这听起来像对我来说是“最受欢迎”。

只是一些反馈 – 我从来没有听说过,我不知道谁使用过它。 内置于JDK,Google或Apache Commons中的集合是我所熟知的。

Trove提供了一些优势。

  • 更小的内存占用,它不使用Map.Entry对象
  • 你可以使用散列策略而不是键映射,这样可以节省内存,并且意味着你不需要在每次你想caching一个新的属性集合时定义一个新的键
  • 它有原始的集合types
  • 认为它有某种forms的内部迭代器

也就是说,自从编写了这个库以来,已经做了很多改进jdk集合的工作。

这是哈希的策略,使它吸引我,虽然…谷歌的宝库,并阅读他们的概述。

如果您计划在多个线程中使用HashMap,则应该提及ConcurrentHashMap和java.util.concurrent包。 小内存占用,因为这是标准的Java的一部分。

如果你想在散列表中存储数百万条logging,很可能会遇到内存问题。 例如,当我尝试创build一个包含230万个string对象的地图时,发生了这种情况。 我去了BerkeleyDB ,这是非常成熟,performance良好。 他们有一个包装Collections API的Java API,所以你可以很容易地创build任意大的地图,只占很less的内存空间。 虽然访问速度会更慢(因为它存储在磁盘上)。

后续问题 :是否有一个体面的(和高效的),维护良好的库不变的collections? Clojure对此有着出色的支持,并且对Java有类似的东西会很好。