使用Key Collection提高Java集合操作效率，collectionjava

使用Key Collection提高Java集合操作效率，collectionjava

Java Collections框架中的类应该是整个JDK中使用频率最高的。然而，Java Collections中的接口和实现存在着一些疏漏和弊端，大量的第三方库都致力于解决这些问题。

Brownies Collections已经提供了一个轻量高效的List实现——GapList（详情见 java.dzone.com/articles/gaplist-lightning-fast-list）。GapList是ArrayList 和LinkedList的替代选择，旨在解决一些已知的性能问题。

由于GapList能提升应用的性能，这里引入的键集合（Key Collections）将会提升开发者的工作效率。为了实现这一目标，这些集合中集成了键和约束的概念，并能以一种正交和声明式的方式使用。

听上去很有趣，但是不是太理论化了？我们来看一个例子。

第一个例子

比方说，我们需要用一个List按照下面的要求表示表格的列：

• 列是有序的
• 列名必须唯一
• 能够通过下标（Index）和名称快速访问列

这样的话，我们应该选择什么集合呢？一个支持下标快速访问的List。如果你确定元素的数量一直很少，我们能够用遍历的方式实现根据名称访问元素（同时需要用遍历的方式检查名称的唯一性），但这明显需要实现一个不能扩展的解决方案。对于一个可扩展的解决方案，我们需要同步一个List和一个Map。这并不是一个不能完成的任务，但是通常情况下会花费很大的工作量。

输入我们的键集合。只用一条语句就能创建满足需求的集合：

Key1List<Column,String> columns = new Key1List.Builder<Column,String>.
withKey1Map(Column.Mapper).withKey1Null(false).
withKey1Duplicates(false).build()

这段代码简单易懂：创建一个用于存储列对象的List，允许通过指定Mapper所定义的字符串类型的键访问元素。键不能为空且不能重复。

要了解完整的示例代码，请看下面的Column类和Mapper的定义：

class Column {
    static Mapper<Column,String> Mapper = new Mapper<Column,String>() {
        String getKey(Column col) {
            return col.getName();
        }
    };

    private String name;

    public String getName() { return name; }
}

起初，你可能会认为这种集合创建的方式很笨拙，但如果不这么做，想想你需要耗费的代码量吧。此外，Java 8中引入的Lambda表达式将能用方法引用替代Mapper的显式定义。

键

在看完第一个例子之后，我们来看看关于键更详细的定义和功能：键是从集合内的某个元素中提取出的一个值。它用于访问元素和定义约束。我们把集合内提取出的所有键值称为键映射（Key Map）。每个集合可以有一个或多个键映射，并且元素本身也能够作为键，我们把这种集合称作元素集（Element Set）。

对于每一个键映射，可以定义如下行为：

• 空值：允许插入空值（默认）或者通过withKeyNull()方法禁止插入空值。
• 重复值：允许插入重复值（默认）或者通过withKeyDuplicates ()方法禁止插入重复值。还存在一种模式，禁止插入重复值，但是空值可以重复插入。
• 排序顺序：键的顺序可以是随机的（默认）或是有序的。可以通过withKeySort()方法实现键按照自然序或者其他自定义比较器产生的顺序有序。

如果你设定了一个键映射的排序顺序，你同样能够通过withKeyOrderBy()方法指定整个集合的顺序。

如果你有一个后台数据库，这些概念对你来说听起来很熟悉。在我们的例子中，我们定义了列名作为集合的主键。如果想要让主键变得更明显或是更简短，我们可以使用withPrimarKey()设定主键。还可以使用另一个方法withUniqueKey()，withUniqueKey()定义的键可以为空，但非空的键值必须是唯一的。

需要注意的是键的取值应该是不可变的。这是因为键映射在元素添加时被填入键值，而键值后续的变更将不会被检测到。然而，这并不是键集合所特有的问题，在Set和Map中，元素的键值也是不能变更的。如果你真的需要变更一个键的值，你可以使用invalidateKey()方法更新键集合的内部状态。

约束

对空值和重复值的限制已经展示出约束的力量。不幸的是，JDK类库中并没有约束集合的概念。尽管有些类（如Set）具有内部约束，但没有一种通用的方式去设定集合的约束。更重要的是，这些类的设计并不具备扩展性，因此实现一个约束会涉及到很多方法的重写。

也许你不知道为什么我们无论如何都需要带约束的集合，但对于优秀的API来说，这是一个至关重要的功能。我们设想这样一个场景，我们的类需要维护一个任务列表，任务可能不为空。客户端代码能够通过所提供的API对这些任务进行读写操作，但是必须保证只有非空任务才能被添加到任务列表中。

class Task {
    List<Task> tasks;
    List<Task> getTasks() { return tasks; }
}

上面的代码很明显是不安全的：客户端拥有不受限的列表写权限，这样她就能轻松地插入插入空值。我们可以用一个略有修改的版本来获得一个较好的只读接口：

List<Task> getTasks() { return Collections.unmodifiableList(tasks); }

但是我们还是需要完善API写操作的部分。这里有两种选择：

懒惰的开发者会只提供一套精简的API:

void addTask(int index, Task task) {
    checkTask(task);
    tasks.add(index, task);
}

void setTask(int index, Task task) {
    checkTask(task);
    tasks.set(index, task);
}

勤劳的开发者会实现所有Mutator方法（两种add()方法，两种addAll()方法，set()方法）。或者她只提供一个方法。

void setTasks(List<Task> tasks) {
    checkTasks(tasks);
    this.tasks = tasks;
}

采用这种实现方式，我们必须在每次变更操作之后检查所有任务的合法性。在元素数量较少并且检查操作相对简单（如检查空值）的时候，这或许不是问题，但很明显这种实现方式不具备扩展性。

然而，当使用可约束的集合时，我们的API变得如此简单：

List<Task> getTasks() { return constraintTasks; }

因为列表本身可以检查元素的合法性。

因此，键集合提供了一个通用的概念队存储在集合中的元素建立约束。默认情况下，键集合就像Collection和List一样允许插入空值和重复值。与此同时，禁止插入空值（使用withElemNull()方法）和重复值（使用withElemDuplicates ()方法）也很容易。

你也可以使用withConstraint()方法定义一个谓词约束，谓词约束用于判断一个新元素是否能加入集合。如果元素不满足谓词约束，该操作将以抛异常的形式被取消。

最后，还有一种约束可以使用。你可以通过定义集合的最大尺寸限制集合中元素的数量（使用withMaxSize()方法）：试图加入更多元素的操作将以抛异常的形式被拒绝。如果你的集合是List类型，你还可以定义一个窗口尺寸（使用withWindowSize ()方法）：窗口尺寸同样用于限制元素的最大数量，不同之处在于，新元素加入后，如果元素数量超出了窗口尺寸，集合的第一个元素将会被自动删除。

类

下表中的类提供键和约束的功能：

类	描述
KeyCollection<E>	维护一个元素集合，提供对元素的快速访问。
Key1Collection<E,K1>	带有一个附加键的键集合，提供对键的快速访问，也可以提供对元素本身的快速访问。
Key2Collection<E,K1,K2>	带有两个附加键的键集合，提供对键的快速访问，也可以提供对元素本身的快速访问。
KeyList<E>	维护一个元素列表，可以提供对元素本身的快速访问。
Key1List<E,K1>	带有一个附加键的键列表，提供对键的快速访问，也可以提供对元素本身的快速访问。
Key2List<E,K1,K2>	带有两个附加键的键列表，提供对键的快速访问，也可以提供对元素本身的快速访问。

键集合的代码实现中使用了JDK提供的集合类：使用HashSet/TreeSet实现元素集（Element Set），使用HashMap/TreeMap实现键映射（Key Map）。

下图说明了键集合如何运用不同的组件来存储带有两个键的元素：

KeyCollection，Key1Collection和Key2Collection实现了Collection接口。默认情况下，元素的顺序由Set组件决定，但也可以按照键映射的顺序排列。

KeyList，Key1List和Key2List实现了List接口，因此元素的顺序始终由List决定。不过，列表中的元素也可以按照元素集或者键映射的顺序排列。

这些方法可以用于访问键映射中的键值： containsKey()、getByKey()、getAllByKey()、 getCountByKey()、getDistinctKeys()、removeByKey()、removeAllByKey()和indexOfKey() （仅用于List）。

这些方法可以用于访问元素集：getAll()、getCount()、removeAll()和getDistinct()。

你也可以通过asSet()和asMap()方法获得JDK接口类型的对象来访问元素集和键映射中的值。

键列表

所有的非有序键列表用键值删除元素会比较慢，这是由于非有序键列表只能通过遍历的方式找到待删除元素。因此，你应该仅在元素数量较小并且只用下标删除元素时使用键列表。

有序键列表

有关“为什么Java语言没有有序列表”的讨论很多。反对的理由主要有两点：第一点出于设计理念的考虑，有序列表违背了List.add()的设计理念，因为元素并没有从列表的尾端加入；第二点出于性能的考虑，以随机顺序向有序列表添加元素的性能开销会比较大。

尽管这两个理由都是对的，但有序键列表仍然会被使用，因为它方便使用。然而，你必须明白的是，有序键列表内部是基于一个有序Map实现的，以随机顺序向有序键列表添加元素的效率将会一直很低，因为元素添加的过程中必须移动内存中的其他元素。

更多的例子

最后，让我们用一些展现键集合力量的例子来对本文做个总结：

一个车票集合，每张票有一个强制的内部ID和一个可选的外部ID：

Key2Collection<Ticket,String,String> coll =
new Key2Collection.Builder<Ticket,String,String>.
withKey1Map(Ticket.dMapper).withPrimaryKey().
withKey2Map(Ticket.ExtIdMapper).withUniqueKey2().build()

一个按列名排序的列表：

Key1List<Column,String> list = new Key1List<Column,String>.
withKey1Map(Column.Mapper).withKey1Sort(true).withKey1OrderBy(true).withPrimaryKey1().build()

一个有序的原生类型（primitive）的整数列表：

需要注意的是，列表支持使用原生类型数值进行排序：

KeyList<Integer> list = new KeyList<Integer>.withElemOrderBy(int.class).build()

KeyList的内部使用IntObjGapList存储列表元素。因此，存储1,000,000个元素只需要4 Mbytes内存空间，而标准的实现方式至少需要44 Mbytes。

Set<Integer> set = new HashSet<Integer>()

但是，要想获得这样的性能收益，你需要在你的数据加入列表之前，对它们进行排序。

带约束的List:

KeyList<String> = new KeyList<String>.withConstraint(uppercasePredicate).build()

带约束的Set:

KeyCollection<String> = new KeyCollection<String>.withConstraint(uppercasePredicate).build().asSet()

带约束的Map:

Key1Collection<Column,String> = new Key1Collection<Column,String>.
withKey1Map(nameMapper).withConstraint(uppercasePredicate).
build().asMap1()

现在，从www.magicwerk.org/collections下载最新版本的Brownies Collections，享受它带来的效率提升。

原文链接： dzone 翻译： Wld5.com - 夏千林
译文链接： http://www.wld5.com/7528.html
[ 转载请保留原文出处、译者和译文链接。]