br> 许多程序员永远不需要实现他们自己的 对象集 类。用本课程上面所描述的实现，你可以做得非常好。然而，有一天，你可能发现你要编写一个你自己的核心 对象集 接口的实现。用由java平台提供的 abstract implementations（抽象实现），这一点很容易办到。但是，在我们要讨论如何编写一个实现之前，让我们先讨论一下为什么你要做这样一件事。
编写你自己的实现的原因
以下列举了几种你可能要实现的对象集，但这并不是全部。
持久的(persistent): 所有的内置 对象集 实现驻留在主存储器，而在vm退出时则消失。 假设你需要一个 对象集，它能在下一次vm启动时仍然存在。实现这样一个 对象集 的途径是在外部数据库之上建立一个虚饰板（veneer）。这样一个 对象集 可能会并发地接受多个vms的访问，因为它驻留在vm之外。
与特定应用相关的（application-specific）: 这是一个非常广阔的范畴。一个例子是包含实时遥感勘测数据的一个不可更改的 map 。键可能代表位置，而值可能被从这些位置上的传感器上读取以响应 get 操作。
高并发的（highly concurrent）: 内置 对象集 未被设计为支持高并发性。同步包装器（和早期实现）锁定整个（ entire） 对象集 （在每次它被访问时）。假设你正在建立一个服务器，并且需要一个可被许多线程并发访问的 map 实现。简单的办法就是建立一个可分别锁定每一个存储段的哈希表，并允许多线程对该表的并发访问(假设它们正在分布于不同存储段中的键)。
高性能、特殊目的（high-performance, special-purpose）: 有许多数据结构利用有限的用法，以提供可能比用通用实现更好的性能。例如，考虑一个 set， 它的元素被限定在一个小的、固定的领域。这样的一个 set 可被表示为一个 bit-vector, 它可提供令人眼花缭乱的快速性能以及低内存占用。 另一个例子涉及到包含长期相同元素值的 list。这样的列表（它经常出现在文本处理中）可能是游长编码的（run-length encoded）: 运行可被表示为一个单一的对象，该对象包含重复的元素和连续重复的次数。这个例子很有趣，因为它交替使用了两个方面的性能：它要求比一个 arraylist 小得多的空间，但更多的时间。
高性能、通用的（high-performance, general-purpose）: 设计 对象集 架构 的工程师试图为每一 涌诙继峁┳詈玫耐ㄓ檬迪? 但是有许多许多数据结构可能被使用，并且每天都在发明新的。也许你能带来什么更快的东西!
增强功能(enhanced functionality）: 假设你需要一个 map (或 set) 实现，它即可提供不变时间存取又可提供插入顺序迭代。这种性能的结合可用哈希表获得，它的所有元素被进一步以插入顺序连接到一个双向链表中（doubly-linked）。另外，作为一种替代选择，假设你需要一种有效的 bag 实现(也称作 multiset)-- 一个可提供不变时间访问同时允许复制元素的 collection。 那么，在hashmap上实现这样的一个collection是非常简单明了的。
便利性（convenience）: 你可能需要由java平台提供的那些实现之外的附加便利实现。例如，你可能经常需要一个代表单独键-值映射的不变 map 对象、或代表一个连续的整数局域的 list 对象或者其他什么东西。
适配器（adapter）: 假设你正在使用某些有着自己特别的collectioon api 的早期api。你可以编写一个适配器（adapter） 实现，它使那些 对象集 可以在 java collections framework 上进行操作。一个适配器实现是一个薄的虚饰板，它可以包装一个类型的对象，并使其表现得象另一个类型的对象。这是通过将后一类型的操作转化到前一类型的结果。
如何编写一个定制实现
借助java平台上的抽象实现（abstract implementations） 来编写定制实现出奇地简单。抽象实现是 核心 对象集 接口 的骨干实现，它明显地是为便于定制实现的编写而设计的。我们以一个例子开始，以下是一个 arrays.aslist的实现：
public static list aslist(object[] a) {
return new arraylist(a);
}
private static class arraylist extends abstractlist
implements java.io.serializable
{
private object[] a;
arraylist(object[] array) {
a = array;
}
public object get(int index) {
return a[index];
}
public object set(int index, object 元素) {
object oldvalue = a[index];
a[index] = 元素;
return oldvalue;
}
public int size() {
return a.length;
}
}
相信不相信？这几乎就是包含在jdk中的实现。它是那样的简单! 你只提供构造函数、 get、 set 和 size 方法, 其余的都由 abstractlist 来做。而你免费获得了 listiterator, 批量操作、搜索操作、哈希代码计算、比较和串表示法等。
假设你要使这个实现再快一点。api有关抽象实现的文本精确地描述了每一种方法是如何被实现的。于是，你将知道要覆盖哪个方法，以得到你所需要的性能。上面提到的这些实现是很好的，但还能做些改进。特别是，toarray 方法在 list 上迭代，每次拷贝一个元素。假如在内部是这样表示的，那么直接克隆这个数组则要快得多--那样才是明智的:
public object[] toarray() {
return (object[]) a.clone();
}
随着这个覆盖（override）和类似的 toarray(object[])的增加，这个实现完全是 jdk中的形象了。为了全面展现jdk，你还要坚持一下去使用其它抽象实现，它们要求你编写你自己的迭代器，但是，它仍然不是那么难。 抽象实现的小结如下:
abstractcollection: 一个既不是set也不是 list的 collection。如：一个元包（bag）。 最低限度下，你必须提供 iterator 和 size 方法。
abstractset : 一个 set. 用法与 abstractcollection 相同。
abstractlist : 一个由随机存取数据存储(如一个数组)所支持的 list 。 最低限度下，你必须提供定位存取方法 (get(int) 和可选择的 set(int), remove(int), 以及add(int)) 和 size 方法。抽象类负责维护listiterator (和 iterator).
abstractsequentiallist : 一个由顺序-存取数据存储（如一个链接的列表）所支持的 list。最低限度下，你必须提供 listiterator 和 size 方法。抽象类负责维护该定位存取方法 (这与 abstractlist是相对的) 。
abstractmap : 一个 map。 最低限度下，你必须提供 entryset 视图。这是用 abstractset 类典型地实现的。如果该 map 是可更改的，你还必须提供 put 方法。
编写一个定制实现的过程，小结如下:
1.从上面的列表中选择适当的抽象实现类。
2.为所有这些类的抽象方法提供实现。如果你的定制对象集 将是可更改的，你必须覆盖一个或几个具体方法。有关抽象实现类的api文本将告诉你覆盖哪个方法。
3.测试 并（ 如果需要）调试实现。你现在已经有了一个工作的定制 对象集 实现!
4.如果你关心性能, 阅读抽象实现类的api文本。如果某一种方法太慢，覆盖它。如果你覆盖了哪个方法，确认衡量一下覆盖前后的性能! 你在性能上的付出将与你在功能上的收获成正比！（通常，这一步被忽略）
编写你自己的实现的原因
以下列举了几种你可能要实现的对象集，但这并不是全部。
持久的(persistent): 所有的内置 对象集 实现驻留在主存储器，而在vm退出时则消失。 假设你需要一个 对象集，它能在下一次vm启动时仍然存在。实现这样一个 对象集 的途径是在外部数据库之上建立一个虚饰板（veneer）。这样一个 对象集 可能会并发地接受多个vms的访问，因为它驻留在vm之外。
与特定应用相关的（application-specific）: 这是一个非常广阔的范畴。一个例子是包含实时遥感勘测数据的一个不可更改的 map 。键可能代表位置，而值可能被从这些位置上的传感器上读取以响应 get 操作。
高并发的（highly concurrent）: 内置 对象集 未被设计为支持高并发性。同步包装器（和早期实现）锁定整个（ entire） 对象集 （在每次它被访问时）。假设你正在建立一个服务器，并且需要一个可被许多线程并发访问的 map 实现。简单的办法就是建立一个可分别锁定每一个存储段的哈希表，并允许多线程对该表的并发访问(假设它们正在分布于不同存储段中的键)。
高性能、特殊目的（high-performance, special-purpose）: 有许多数据结构利用有限的用法，以提供可能比用通用实现更好的性能。例如，考虑一个 set， 它的元素被限定在一个小的、固定的领域。这样的一个 set 可被表示为一个 bit-vector, 它可提供令人眼花缭乱的快速性能以及低内存占用。 另一个例子涉及到包含长期相同元素值的 list。这样的列表（它经常出现在文本处理中）可能是游长编码的（run-length encoded）: 运行可被表示为一个单一的对象，该对象包含重复的元素和连续重复的次数。这个例子很有趣，因为它交替使用了两个方面的性能：它要求比一个 arraylist 小得多的空间，但更多的时间。
高性能、通用的（high-performance, general-purpose）: 设计 对象集 架构 的工程师试图为每一 涌诙继峁┳詈玫耐ㄓ檬迪? 但是有许多许多数据结构可能被使用，并且每天都在发明新的。也许你能带来什么更快的东西!
增强功能(enhanced functionality）: 假设你需要一个 map (或 set) 实现，它即可提供不变时间存取又可提供插入顺序迭代。这种性能的结合可用哈希表获得，它的所有元素被进一步以插入顺序连接到一个双向链表中（doubly-linked）。另外，作为一种替代选择，假设你需要一种有效的 bag 实现(也称作 multiset)-- 一个可提供不变时间访问同时允许复制元素的 collection。 那么，在hashmap上实现这样的一个collection是非常简单明了的。
便利性（convenience）: 你可能需要由java平台提供的那些实现之外的附加便利实现。例如，你可能经常需要一个代表单独键-值映射的不变 map 对象、或代表一个连续的整数局域的 list 对象或者其他什么东西。
适配器（adapter）: 假设你正在使用某些有着自己特别的collectioon api 的早期api。你可以编写一个适配器（adapter） 实现，它使那些 对象集 可以在 java collections framework 上进行操作。一个适配器实现是一个薄的虚饰板，它可以包装一个类型的对象，并使其表现得象另一个类型的对象。这是通过将后一类型的操作转化到前一类型的结果。
如何编写一个定制实现
借助java平台上的抽象实现（abstract implementations） 来编写定制实现出奇地简单。抽象实现是 核心 对象集 接口 的骨干实现，它明显地是为便于定制实现的编写而设计的。我们以一个例子开始，以下是一个 arrays.aslist的实现：
public static list aslist(object[] a) {
return new arraylist(a);
}
private static class arraylist extends abstractlist
implements java.io.serializable
{
private object[] a;
arraylist(object[] array) {
a = array;
}
public object get(int index) {
return a[index];
}
public object set(int index, object 元素) {
object oldvalue = a[index];
a[index] = 元素;
return oldvalue;
}
public int size() {
return a.length;
}
}
相信不相信？这几乎就是包含在jdk中的实现。它是那样的简单! 你只提供构造函数、 get、 set 和 size 方法, 其余的都由 abstractlist 来做。而你免费获得了 listiterator, 批量操作、搜索操作、哈希代码计算、比较和串表示法等。
假设你要使这个实现再快一点。api有关抽象实现的文本精确地描述了每一种方法是如何被实现的。于是，你将知道要覆盖哪个方法，以得到你所需要的性能。上面提到的这些实现是很好的，但还能做些改进。特别是，toarray 方法在 list 上迭代，每次拷贝一个元素。假如在内部是这样表示的，那么直接克隆这个数组则要快得多--那样才是明智的:
public object[] toarray() {
return (object[]) a.clone();
}
随着这个覆盖（override）和类似的 toarray(object[])的增加，这个实现完全是 jdk中的形象了。为了全面展现jdk，你还要坚持一下去使用其它抽象实现，它们要求你编写你自己的迭代器，但是，它仍然不是那么难。 抽象实现的小结如下:
abstractcollection: 一个既不是set也不是 list的 collection。如：一个元包（bag）。 最低限度下，你必须提供 iterator 和 size 方法。
abstractset : 一个 set. 用法与 abstractcollection 相同。
abstractlist : 一个由随机存取数据存储(如一个数组)所支持的 list 。 最低限度下，你必须提供定位存取方法 (get(int) 和可选择的 set(int), remove(int), 以及add(int)) 和 size 方法。抽象类负责维护listiterator (和 iterator).
abstractsequentiallist : 一个由顺序-存取数据存储（如一个链接的列表）所支持的 list。最低限度下，你必须提供 listiterator 和 size 方法。抽象类负责维护该定位存取方法 (这与 abstractlist是相对的) 。
abstractmap : 一个 map。 最低限度下，你必须提供 entryset 视图。这是用 abstractset 类典型地实现的。如果该 map 是可更改的，你还必须提供 put 方法。
编写一个定制实现的过程，小结如下:
1.从上面的列表中选择适当的抽象实现类。
2.为所有这些类的抽象方法提供实现。如果你的定制对象集 将是可更改的，你必须覆盖一个或几个具体方法。有关抽象实现类的api文本将告诉你覆盖哪个方法。
3.测试 并（ 如果需要）调试实现。你现在已经有了一个工作的定制 对象集 实现!
4.如果你关心性能, 阅读抽象实现类的api文本。如果某一种方法太慢，覆盖它。如果你覆盖了哪个方法，确认衡量一下覆盖前后的性能! 你在性能上的付出将与你在功能上的收获成正比！（通常，这一步被忽略）
闽公网安备 35060202000074号