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

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()定义的键可以为空,但非空的键值必须是唯一的。

需要注意的是键的取值应该是不可变的。这是因为键映射在元素添加时被填入键值,而键值后续的变更将不会被检测到。然而,这并不是键集合所特有的问题,在SetMap,元素的键值也是不能变更的。如果你真的需要变更一个键的值,你可以使用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 翻译: ImportNew.com - 夏千林
译文链接: http://www.importnew.com/7528.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 夏千林

(新浪微博:@杂草千

查看夏千林的更多文章 >>



可能感兴趣的文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部