Java 集合类、Skip 列表以及 Google

阅读数:663 2007 年 10 月 14 日

话题:JavaDevOps语言 & 开发架构

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

其中尤其引发他兴趣的是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,随机的……
  • IteratorsIterables - 基于 Element 的结构,循环,连接,分割,通过条件过滤,使用函数进行转换
  • Lists,SetsMaps - 过多的方便的工厂方法及其他
  • PrimitiveArrays - 原始数组的“装箱”/“拆箱”
  • Object.equals 和 hashCode - 提供内建的对 null 的处理

Public Object 使用 Google 的 Collection 库编写了大量的示例。这些示例 中包含使用 Java Collections/Utilities 的代码片段,也包含当使用 Google 的 Collection 库时的代码样式。对于如何使用这个类库,MultiMapObjects.equal 和 hashCode 提供了很好的范例。

Google 的 Collection 库遵守 JDK 接口,现在是用 1.5 的 JDK 进行开发,并在考虑未来对 JDK1.6 的支持。这里是完整的 APIFAQ

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