Java 集合类、Skip 列表以及 Google

虽然有时认为是理所当然，但 Java Collections API 无疑在每天的 Java 软件开发中扮演着重要的角色。然而 API 和相关的项目从未停止过发展。Alex Miller最近提到了 Java 6 中 API 的变化：

• 一个名为 Deque （发音“deck”）的双头队列接口，以及对应的并发接口 BlockingDeque ，实现类包括 ArrayDeque 和 LinkedBlockingDeque 。
• 名叫 NavigableSet 和 NavigableMap 的用于排序 set 和 map 的新改进接口，以及一些像 TreeSet 和 TreeMap 那样的实现类。
• 用于并发和排序的新组合的接口：ConcurrentNavigableSet 和 ConcurrentNavigableMap 。加上两个新的并发排序实现类名为 ConcurrentSkipListSet 和 ConcurrentSkipListMap 。

其中尤其引发他兴趣的是 SkipList ，它不像许多普通的 CS 数据接口，相对来说是个新的重新：

skip 列表是个概率性的的数据结构，由 William Pugh 在 1990 年发明，列表基于平行的链接列表，效率相对二叉搜索树（对于大多数操作平均需要 O(log n) 时间）有显著改善。

Google 也一直致力于 collections 领域的工作，并发布了一套建立于标准的 Java Collections Framework 的实现类。虽然还是 alpha 版本 ，但 Google 已经把它们使用在自己的许多服务中，比如 GMail，Reader 和 Blogger。除了专注于为既有的 Java Collections Framework 增加复杂性和灵活性以外，Google 也添加了许多的 collections 和工具类来使得编码变得更简单并提高代码可读性。 其中最值得注意的 collection 是：

• BiMap - 一个确保唯一值并支持反转视图的 Map
• Multiset - 一个可以像 List 那样包含重复的值，但又有像 Set 那样的独立顺序的 Collection。通常用于描绘柱状图。
• Multimap - 类似于 Map，但可以包含重复的键。拥有子类 SetMultimap 和 ListMultimap，提供更多特别的行为。
• ClassToInstanceMap - 一个特殊化的 Map，它的键是 class 而对应的值 class 的实例。

Google 还包含许多跟这些新的 collection 类配合使用的工具类。其中包含：

• Comparators - 自然顺序的，复合的，支持 null，随机的……
• Iterators和Iterables - 基于 Element 的结构，循环，连接，分割，通过条件过滤，使用函数进行转换
• Lists，Sets和Maps - 过多的方便的工厂方法及其他
• PrimitiveArrays - 原始数组的“装箱”/“拆箱”
• Object.equals 和 hashCode - 提供内建的对 null 的处理

Public Object 使用 Google 的 Collection 库编写了大量的示例。这些示例 中包含使用Java Collections/Utilities 的代码片段，也包含当使用Google 的Collection 库时的代码样式。对于如何使用这个类库， MultiMap 和 Objects.equal 和 hashCode 提供了很好的范例。Google 的 Collection 库遵守 JDK 接口，现在是用 1.5 的 JDK 进行开发，并在考虑未来对 JDK1.6 的支持。这里是完整的API 和 FAQ 。

查看英文原文： Java Collections, Skip Lists, and Google