java - 什么是最高效的 Java Collections 库？

Question

什么是最高效的 Java Collections 库？

几年前，我做了很多Java，当时的印象是trove是最好的(最有效的)Java Collections 实现。但是当我阅读问题“Most useful free Java libraries?”的答案时，我注意到 trove几乎没有提到。那么现在哪个 Java Collections 库最好呢？

更新:澄清一下，我主要想知道当我必须在哈希表等中存储数百万个条目时使用哪个库(需要小的运行时和内存占用)。

Answer 1

问题是(现在)关于存储大量数据的问题，这些数据可以使用诸如 int 之类的原始类型来表示。 ，在 map 中。在我看来，这里的一些答案非常具有误导性。让我们看看为什么。

我从 trove 修改了基准测量运行时和内存消耗。我还添加了 PCJ到这个基准，它是原始类型的另一个集合库(我广泛使用那个)。 '官方' trove 基准没有将 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 集合需要三倍以上的内存。 IE。您可以在内存中保留三倍的数据，而无需使用磁盘 IO，这会大大降低运行时性能。这很重要。阅读 highscalability找出原因。

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

所以:不，java.util 不是答案。在询问效率时，向 Java 集合“添加功能”并不是重点。此外，现代 JDK 集合不“甚至胜过专门的 Trove 集合”。

免责声明:这里的基准测试远非完整，也不完美。这是为了让我明白这一点，我在许多项目中都经历过。原始集合足以容忍可疑的 API - 如果您使用大量数据。