[XMLer的生活]可使用基本类型作为键值的Java集合类－Trove 集合类

[XMLer的生活]可使用基本类型作为键值的Java集合类－Trove 集合类

lemann 发表于 2004-10-27 10:15:00 性能观察: Trove 集合类 更小、更普通、更易上手 级别: 中级 Jack Shirazi （[e-mail]） , 董事, JavaPerformanceTuning.com Kirk Pepperdine （[e-mail]） , CTO, JavaPerformanceTuning.com 2004 年 10 月 Trove 是一种开放源代码的 Java 集合包，提供了核心 Java 集合类的高效替代品，特别针对于实现其键或值是基本类型的集合。本期 性能观察文章中，性能优化专家 Jack Shirazi 和 Kirk Pepperdine 考察了 Trove 类与传统的 Java 集合的区别，以及何时使用 Trove 类。 几年前，也就是 2001 年后期，我们收到了 Eric Friedman 的电子邮件。他说他已经决定构造一组开放源代码的集合类，用于取代 java.util 类。而且这些类执行速度更快、更轻巧、更灵活。是的，Eric 要创建 Six Million Dollar 集合！ 事实上，当时我们对是否能够直接取代 Java 平台的集合类并不特别感兴趣。Joshua Bloch 的工作做得很好，创建的通用集合框架非常有用、快捷而且能够扩展。但是通用与高效常常是互斥的两个目标。创建专门的 集合类来处理 int 或 boolean 这类基本类型，对于我们而言即使在 2001 年也不是多么不寻常的事。否则，在 Java 平台通用集合框架中存储基本类型的集合都需要通过 Integer 和 Boolean 之类的包装器类进行包装和解包，这样做不但非常麻烦，而且大量的包装和解包很容易成为性能瓶颈。 这样说有点离题了。 美梦还是恶梦？ Eric 建议创建不通过包装和解包就直接处理数据原型的集合类。这是性能优化人员的梦想，而且可以改进类型安全性，但却是架构师的恶梦。比方说 Map 吧，它包括键和值，每个键或者值都可以是 Object 或者 8 种基本数据类型之一：byte、short、char、int、long、float、double 和 boolean。 这样就有 9 种键和 9 种值，组成 81 种不同类型的 Map！更糟的是，只要其中一个存在缺陷，就意味着其他 80 种很可能也存在缺陷，而能够共用的代码很有限，因为为了有效地处理每种数据类型，需要分别实现算法，从而，维护的工作量太大了。我非常钦佩 Eric，但是并不期望这种集合能够很快出现，因为开发和调试需要大量的时间。 在 2001 年，我们为 Eric 提供的支持很少。在“Java Performance Tuning” 12 号时事通讯中（请参阅 参考资料），我们看到了 Eric 关于 Trove 项目的宣告。除了偶尔的 bug 修复外，Eric 都是一个人在所有这些不同的集合版本中埋头苦干。他做了一项了不起的工作，今天我们可以欣然享受他艰苦劳作的成果了。Trove 集合可以使用了，而且确实非常有用。 许许多多的集合 好了，上面是一段小插曲，您到底能够从 Trove 中得到什么呢？许许多多的高效集合。除了那 81 种不同的 HashMap 版本之外（比如 TIntIntHashMap、TIntObjectHashMap 等），还有 List 和 Set 类可以存储基本类型（如 TIntHashSet、TFloatArrayList 等）。这种体系结构甚至允许您插入自己的散列策略，以便选择对您的数据集而言可能更有效（或者更灵活）的算法。当然，支持灵活的散列算法也要付出性能代价 —— 如果散列映射成为瓶颈，很可能是因为大量地使用它，这意味着散列函数被反复不断地调用。因此，散列函数中每一点多余的开销都可能成为瓶颈。（顺便说一下，如果散列函数足够简单，JIT 编译器就可能将其编译成内联函数，这样在支持灵活的散列策略的同时又不会带来额外的开销 —— 真是免费的午餐！） 此外，Eric 还实现了 Smalltalk 范型，就是说集合能够对自己的元素执行过程。这种处理不同于 Java 平台中一般的集合元素遍历，需要稍微讨论一下。在 Java 编程中，如果需要处理集合中的所有元素，通常要有一个迭代器（Iterator）来访问和处理每个元素，如清单 1 所示： 清单 1. 集合的遍历 Iterator iterator = collection.iterator(); while (iterator.hasNext()) { Object o = iterator.next(); ... //do something with 'o' } Trove 也支持这种迭代模式，但是还支持向集合传递过程，然后集合在内部迭代每个元素，依次将该过程应用于每个元素。尽管这种技术不一定能提高效率 —— 如果迭代器对象不能像集合本身那样高效地遍历元素，则可以提高效率 —— 但是有助于提高清晰性和灵活性。清单 2 是上述例子改写后的版本： 清单 2. 向集合传递过程 Procedure procedure = new DoSomethingWithOProcedure(); collection.forEach(procedure); 开放选址 Trove 映射是采用开放选址而不是链接来实现的。在 Java 核心集合类中，多数映射都是使用链接实现，就是说如果多个键映射到表中的同一索引位置，则索引位置保存一个链表，其中存放映射到该位置的所有元素。开放选址映射则假设表中邻近的位置存在没有使用的索引。如果目标位置已经被占用，映射实现就查看附近的几个位置找到一个没有使用的位置。这种方法不需要链表节点，因此 Trove 映射和相同的核心集合类相比占用的内存更少。使用开放选址必须保证有足够的空闲索引，否则可能影响性能。（Trove 保持装载因子小于 0.5。）否则的话，开放选址的效率与链接基本相当，但多数情况下要好于后者。 开放选址的另一个优点是实现中不需要链表节点对象，链表节点需要靠链接来实现。为什么特别强调这一点呢？基本上每个 JVM 版本都会改进对象创建和无用单元回收的性能，但是较多的对象总会带来更多的开销。对于任何特定的问题，Java 编程中能够减少对象数量的解决方案通常都有更好的效率，这是一个标准的性能权衡问题，每个有经验的性能优化人员都知道。开放选址使用更少的对象来维护映射结构，这意味着 Trove 映射在多数情况下比核心 Java 映射更有效，也更小。值得一提的是，最近越来越多的 Java 核心 Map 实现开始使用开放选址（比如 IdentityHashMap 类）。现有的其他核心 Java Map 实现最终也可能改为使用开放选址，虽然我们可能不那么关心，因为如果需要开放选址的实现，使用 Trove 就可以了。 Trove 本身提供了一个小的基准测试，用于跟核心 Java 集合进行性能比较。Dion Almaer 所进行的独立比较测试（请参阅 参考资料）说明了 Trove 在性能和大小上的优势。结果表明，Trove 执行 Map.put() 操作的速度要*倍，而占用的内存只有核心 Map 所需要的一半。 自动装箱 Java 5.0 平台引入了泛化（generics）和自动装箱机制（Autoboxing）。这意味着您可以编写下面这样的代码： 清单 3. 使用自动装箱机制 mymap.put("201",201); mymap.put("202",202); int sum = mymap.get("201") + mymap.get("202") mymap.put("sum",sum); 注意，通过使用泛化，mymap 甚至可以限制为仅保存 Integer 对象。但是也要注意在幕后仍然会进行自动装箱，清单 3 代码中的所有 int 都在运行时使用 Integer 对象包装（通常每次都使用新的对象），并使用存取方法来访问（虽然 JIT 编译器可能将访问编译成内联函数）。 需要强调指出：Java 5.0 平台中的自动装箱可能造成高效的假象。在代码层上看起来基本数据类型的使用效率很高，但是在运行时，基本数据包装器类型的使用效率则会变得很低。Heinz Kabutz 博士最近撰文表明，如果不小心在循环中使用自动装箱机制，有可能使性能降低一个数量级（请参阅 参考资料）。 自动装箱的效率比不上使用直接保存基本数据类型的集合，比如值为 int、键为 Object 的 Trove TObjectIntHashMap 类型不需要包装和解包 int 值。对于其他基本数据类型和集合组合，Trove 都有等价的集合，如 TIntIntHashMap（int 键和 int 值）、TLongArrayList（保存 long 的列表）、TIntSet（保存 int 的集合）等等。Dion Almaer 对 TIntIntHashMap 和 HashMap 的比较测试也表明 Trove 的速度要快一个数量级。 结束语 将 Trove 加到您的项目中吧。我们并不建议在每个需要集合的地方都使用 Trove，因为 Trove 毕竟还年轻，使用的还不多，所以很可能会出现一些 bug。但是 Trove 提供了一种选择，如果需要效率更高的类，就可以使用它，当您在调优应用程序时会遇到这种情况。 参考资料 您可以参阅本文在 developerWorks 全球站点上的 英文原文。 Trove 是一个开放源代码项目，可以从 SourceForge 下载。 Dion Almaer 是 TheServerSide.com 的首席架构师，提供了 Trove 性能测试。 Heinz Kabutz 博士在一篇论文中探讨了自动装箱的性能问题。 Java Performance Tuning 新闻邮件 12 号 宣告了 Trove 的诞生。 了解各种性能优化问题，请阅读 Jack Shirazi 撰写的 Java Performance Tuning, 2nd Edition（O'Reilly 2003）。 关于 Collections Framework 的详细介绍请参阅 Java 集合框架教程。 经过扩展，Collections Framework 还包含一些并发集合类。 关于 JDK 5.0 中新出现的 Generics 和 Autoboxing 特性，请参阅 generics prototype。 在 developerWorks Java 技术专区可以找到数百篇关于 Java 编程方方面面的文章。 Developer Bookstore 提供了完整的技术书籍清单，包括数百本和 Java 有关的书籍。 作者简介 Jack Shirazi 是 JavaPerformanceTuning.com 的董事， Java Performance Tuning, 2nd Edition (O'Reilly) 一书的作者。 Kirk Pepperdine 是 Java Performance Tuning.com 的首席技术官，过去 15 年中一直专注于对象技术和性能优化。 Kirk 是 Ant Developer's Handbook (MacMillan) 一书的作者之一。