周浩

Java 容器类学习心得

一心得

1.  接口
整个 Java 容器类的基础是容器接口（例如 Collection ， Map 等接口），而不是类。使用接口的最大好处在于将容器的实现与容器的接口分开，这就意味着你可以使用相同的方法访问容器而不用关心容器是由什么样的数据结构实现的。同样， Iterator 接口也使得用户可以使用相同的方法访问不同的容器类。以上这些是通用算法的基础。

1.1 Collection 接口
Collection 接口有如下基本方法：
boolean add(Object obj) ：如果添加对象后，集合确实发生了变化，则返回 true ；否则返回 false
Iterator iterator() ：返回一个实现了 Iterator 接口的对象
此外，还有
int size(),boolean isEmpty() ， boolean contains(Object obj) ， void clear() 等许多有用的方法

1.2 Map 接口
Map 用于存放关键字 / 值对。有如下基本方法：
Object get(Object key)
Object put(Object key,Object balue)
Set keySet()
Set entrySet()
此外，还有其他有用的方法。
需要注意的是，从表面看它似乎就是一种由键值对构成的集合，但实际上并不是这样。不过另一方面假如将 Map 的某一部分看作集合，有时候也还是显得非常方便的。换言之你可以创建一个集合用它来表达 Map 的那一部分。综上所述，一个 Map 可以返回的东西包括它的键值构成的一个 Set 、由它的值构成的一个集合或者由它的键值对构成的一个 Set 。

1.3 Iterator 接口
Iterator 接口有下面 3 个基本方法：
Object next() ：返回迭代器刚越过的元素的引用
boolean hasNext() ：判断容器内是否还有可供访问的元素
void remove() ：删除迭代器刚越过的元素
注意： Java 中的迭代器与 STL 中的迭代器在概念上有很重要的区别。在 STL 中，迭代器类似于数组的索引，使用这种迭代器可以查看存放在该位置上的元素（类似于通过数组索引 i 来访问 c[i] 一样）。 Java 中的迭代器并不这样运行。查看与位置的变化紧密的结合在一起。每次通过 next() 访问一个元素的同时，迭代器的位置会自动向前走一步。
这个问题可以这样理解： Java 中的迭代器指向的位置并不是元素，而是元素之间。这样，每次调用 next() 时，迭代器便越过下一个元素，同时返回它刚越过的那个元素的引用。
根据上面的说明，很容易得出下面的代码是错误的：
it.remove();
it.remove();
而下面的代码是正确的：
it.remove();
it.next();
it.remove();
迭代器的典型应用
Iterator it=c.iterator();
while(it.hasNext())
{
 Object obj=it.next();
 //do something with obj
}

1.4  子接口
1.4.1 List 接口
List 从 Collection 接口中分立出来是因为 List 的特点——有序的集合。这里指的有序并不是按照大小排好序的（ Sorted ），而是指集合是可以以确定的顺序访问的序列。针对 List 的这个特点，它比 Collection 接口增加了通过索引进行操作的方法。例如， add 、 remove 、 get 、 set 等方法的参数表中都可以加入索引的数值，从而操作处在索引位置处的元素。

1.4.2 Set 接口
Set 与 List 的不同，它里面的元素是无序的；所以，不能通过任何索引的方法来操作 Set 对象

1.4.3 ListIterator 接口
使用与 List 的迭代器，比 Iterator 接口增加了一些方法（例如 add() 等）。此外，由于 List 是双向表，所以还增加了 Object previous() 和 boolean hasPrevious() 方法，用法与 next() 和 hasNext() 一样。

1.4.4 SortedMap 接口
包含如下基本方法：
Comparator comparator()
Object firstKey()
Object lastKey()

2.  抽象容器类
2.1  抽象容器类包括 AbstractCollection ， AbstractList ， AbstractSet 等等

2.2  为什么要有抽象结合类？
例如 Collection 接口中定义了许多有用的方法，如果实现 Collection 接口的每个类都自行实现这么多的方法，那将是非常麻烦的。为了使实现 Collection 接口的类的实现更容易， AbstractCollection 类让一些基本方法（比如 add() 和 iterator() ）变成了抽象的方法，而利用这些基本方法的其他方法（例如 addAll() 等等）则具体实现了。

3.  具体的容器
3.1 ArrayList 与 LinkedList
都是实现了 List 接口的类，是有序集。 List 接口支持通过索引的方法来访问元素，对于这一点， ArrayList 没有任何问题；但是对于 LinkedList 则有很大的问题，链表本身不应该支持随机存储，但是作为 List 的一个实现，链表也提供了对随机访问的支持，但是效率很低。每次通过索引的方法都是进行一次遍历。我认为，其实就不应该让链表支持随机访问；而 Java 这样实现我想是因为整个集合框架的体系，使得链表与数组可以使用同样的方法使用。综上所述，对于 LinkedList 最好不使用随机访问，而使用迭代器。

3.2 TreeSet
3.2.1 TreeSet 是 SortedSet 的一个实现。根据数据结构的知识可以知道，树的效率非常高，而且 Java 标准库中有 TreeSet 这样的类，以后应该尽量使用 TreeSet 来提高程序的效率。
3.2.2  需要注意的是： TreeSet 作为有序集，它通过 compareTo 或者 Comparator 来将集合元素排序。任何具有相同比较值的元素（无论它们是否 equals() ），在 TreeSet 中都作为同一个元素，从而不能有重复。这样以来，即使是不同的对象也不能加入到集合中，这一点有时候很不方便。我在编写 A* 算法时，不同状态有时候对应着同一个启发函数值，那么这些不同的状态就无法加入到 TreeSet 中。

3.3 HashSet
3.3.1 HashSet 是非常高效的数据结构，与 TreeSet 不同， HashSet 是比较对象的 equals() 方法来区分不同的对象。这样只有真正不同的对象才能不被重复的加入到集合中。
3.3.2  需要注意的是： HashSet 效率非常高，但是对象的 hashCode 函数不好确定。一般默认的对象的 hashCode 函数是根据对象的内存地址得到的。好的 hashCode 函数是 HashSet 成功运用的关键。

4.  视图
4.1  什么是视图？
对映象类使用 keySet() 方法，仿佛该方法建立了一个新的集合，并将影响的所有关键字都填入这个集合。实际情况并非如此，对这个集合的任何操作都将反映到原始的映象对象上。
实际上， keySet() 返回的是一个实现 Set 接口的对象，对该对象的操作就是对映象的操作。这样的集合成为视图。
4.2  视图的应用
4.2.1  将现有的容器变为线程安全的容器：使用 Collections.synchronizedCollection(Collection c) 方法，在 SDK 文档中该方法的解释是“ Returns a synchronized (thread-safe) collection backed by the specified collection ”。
4.2.2  将现有的容器变为只读的容器：使用 Collections.unmodifiableCollection(Collection c) 方法，在 SDK 文档中该方法的解释是“ Returns an unmodifiable view of the specified collection. ”。
4.2.3  子范围
4.2.4 Arrays 类中的 asList() 方法

5.  通用算法
通用的集合接口带来的一大好处就是可以编写通用算法。可以使用 Collections 中的静态通用方法，也可以编写自己的通用方法。
（具体的算法的内容在此略去）

总结：千万记住这句话——没有最好的容器（数据结构），要根据不同的问题选择不同的容器，以此来达到功能的要求和效率的最优。

二、 Java2 中的容器类库

自 Java1.2 之后 Java 版本统称为 Java2 ， Java2 中的容器类库才可以说是一种真正意义上的集合框架的实现。基本完全重新设计，但是又对 Java1 中的一些容器类库在新的设计上进行了保留，这主要是为了向下兼容的目的，当用 Java2 开发程序时，应尽量避免使用它们， Java2 的集合框架已经完全可以满足你的需求。有一点需要提醒的是，在 Java1 中容器类库是同步化的，而 Java2 中的容器类库都是非同步化，这可能是对执行效率进行考虑的结果。
Java2 中的集合框架提供了一套设计优良的接口和类，使程序员操作成批的数据或对象元素极为方便。这些接口和类有很多对抽象数据类型操作的 API ，而这是我们常用的且在数据结构中熟知的。例如 Maps ， Sets ， Lists ， Arrays 等。并且 Java 用面向对象的设计对这些数据结构和算法进行了封装，这就极大的减化了程序员编程时的负担。程序员也可以以这个集合框架为基础，定义更高级别的数据抽象，比如栈、队列和线程安全的集合等，从而满足自己的需要。
Java2 的集合框架，抽其核心，主要有三类： List 、 Set 和 Map 。如下图所示：

从图上可以看出， List 和 Set 继承了 Collection ，而 Map 则独成一体。初看上去可能会对 Map 独成一体感到不解，它为什么不也继承 Collection 呢？但是仔细想想，这种设计是合理的。一个 Map 提供了通过 Key 对 Map 中存储的 Value 进行访问，也就是说它操作的都是成对的对象元素，比如 put() 和 get() 方法，而这是一个 Set 或 List 所不就具备的。当然在需要时，你可以由 keySet() 方法或 values() 方法从一个 Map 中得到键的 Set 集或值的 Collection 集。
1 、 Collection 接口提供了一组操作成批对象的方法，用 UML 表示的方法列表如下：
它提供了基本操作如添加、删除。它也支持查询操作如是否为空 isEmpty() 方法等。为了支持对 Collection 进行独立操作， Java 的集合框架给出了一个 Iterator ，它使得你可以泛型操作一个 Collection ，而不需知道这个 Collection 的具体实现类型是什么。它的功能与 Java1 中的 Enumeration 类似，只是更易掌握和使用，功能也更强大。在建立集合框架时， Sun 的开发团队考虑到需要提供一些灵活的接口，用来操作成批的元素，又为了设计的简便，就把那些对集合进行可选操作的方法与基本方法放到了一起。因为一个接口的实现者必须提供对接口中定义的所有方法的实现，这就需要一种途径让调用者知道它正在调用   的可选方法当前不支持。最后开发团队选择使用一种信号，也即抛出一种不支持操作例外 (UnsupportedOperationException) ，如果你在使用一个 Collection 中遇到一个上述的例外，那就意味着你的操作失败，比如你对一个只读 Collection 添加一个元素时，你就会得到一个不支持操作例外。在你实现一个集合接口时，你可以很容易的在你不想让用户使用的方法中抛出 UnsupportOperationException 来告诉使用者这个方法当前没有实现， UnsupportOperationException 是 RuntimeException 的一个扩展。
另外 Java2 的容器类库还有一种 Fail fast 的机制。比如你正在用一个 Iterator 遍历一个容器中的对象，这时另外一个线程或进程对那个容器进行了修改，那么再用 next() 方法时可能会有灾难性的后果，而这是你不愿看到的，这时就会引发一个 ConcurrentModificationException 例外。这就是 fail － fast 。
2 、 List 接口对 Collection 进行了简单的扩充，它的具体实现类常用的有 ArrayList 和 LinkedList 。你可以将任何东西放到一个 List 容器中，并在需要时从中取出。 ArrayList 从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而 LinkedList 的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的 Iterator 只能对容器进行向前遍历，而 ListIterator 则继承了 Iterator 的思想，并提供了对 List 进行双向遍历的方法。
3 、 Set 接口也是 Collection 的一种扩展，而与 List 不同的时，在 Set 中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个 Set 容器中。它的常用具体实现有 HashSet 和 TreeSet 类。 HashSet 能快速定位一个元素，但是你放到 HashSet 中的对象需要实现 hashCode() 方法，它使用了前面说过的哈希码的算法。而 TreeSet 则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类 Comparable 和 Comparator 。一个类是可排序的，它就应该实现 Comparable 接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现 Comparator 接口即可。
集合框架中还有两个很实用的公用类： Collections 和 Arrays 。 Collections 提供了对一个 Collection 容器进行诸如排序、复制、查找和填充等一些非常有用的方法， Arrays 则是对一个数组进行类似的操作。
4 、 Map 是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个 Map ，依次类推，这样就可形成一个多级映射。对于键对象来说，像 Set 一样，一个 Map 容器中的键对象不允许重复，这是为了保持查找结果的一致性 ; 如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。 Map 有两种比较常用的实现： HashMap 和 TreeMap 。 HashMap 也用到了哈希码的算法，以便快速查找一个键， TreeMap 则是对键按序存放，因此它便有一些扩展的方法，比如 firstKey(),lastKey() 等，你还可以从 TreeMap 中指定一个范围以取得其子 Map 。键和值的关联很简单，用 pub(Object key,Object value) 方法即可将一个键与一个值对象相关联。用 get(Object key) 可得到与此 key 对象所对应的值对象。

三、未来的 Java 容器类库

前面几部分对 Java 中容器类库的过去与现在的状况进行了讨论，然而就在写下此文时， Sun 已经开始通过某种途径分发 J2SE1.5 的 Alpha 测试版了。在今年的 JavaOne 大会上，诸多大师描绘了 Java 的美好未来与在下一个版本中即将加入的一些新特性，其中为容器类库加入的一个重要特性就是泛型。
其实泛型并不是什么新东西，在其它一些面向对象的语言中早已存在，如 C++ 。泛型的基本目标很简单：能够保证你使用一种类型安全的容器。那么到底怎样一种类型安全呢？我们先看下面这一段没有使用泛型特性的代码：

1.    import  java.util.*;

2.    public  class Generics{

3.        /**

4.         *  输出一个 String 类型的列表，假设所给参数 list 中所有元素都为 String 。

5.         */

6.        public static void printList(List list){

7.            for(int i=0;i<list.size();i++){

8.                System.out.println(((String)list.get(i)).toString());

9.            }

10.       }

11.       public static void main(String[] args){

12.           List list=new ArrayList();

13.           for(int i=0;i<9;i++){

14.               list.add("Number:"+Integer.toString(i));

15.           }

16.           //list.add(new Generics());  //(1)

17.           printList(list);

18.       }

19.   }

上面的代码很简单，定义了一个静态方法来打印一个元素为 String 类型的 List ，然而正如你看到的一样，如果你试着将 (1) 行中前面的注释去掉，你就会得到一个 ClassCastException 例外，因为 printList 会将 list 中的每个元素都转型为 String ，而在遇到最后一个元素时发现它是一个 Generics 类型从而无法完成转型，例外就被抛出。这种情况在 Java 编程中很容易出现，原因是 Java 的容器类库通常保存的是 Object 类型，而这是所有类的直接或间接超类，这就允许你将任何类型的元素添加到一个 List 中而不会给你任何提示，有经验的程序员可能会自己编写一个容器类来限制添加到其中的元素，这是一个编程技巧。但是现在我们就再也不用那样做了，泛型机制会为我们做好这件事。那就看一下用泛型机制对上面代码进行的改进：

1.    import  java.util.*;

2.    public  class Generics{

3.        /**

4.         *  输出一个 String 类型的列表，限制了所给参数 list 中所有元素都为 String

5.         */

6.        public static void printList(ArrayList<String> list){

7.            for(int i=0;i<list.size();i++){

8.                System.out.println(list.get(i).toString());

9.                //get() 返回的不再是 Object 类型，而是 String 类型

10.           }

11.       }

12.       public static void main(String[] args){

13.           ArrayList list=new ArrayList<String>(); // 注意此行中声明语法的变化

14.           for(int i=0;i<9;i++){

15.               list.add("Number:"+Integer.toString(i)); // 只能向其中添加 String 类型

16.           }

17.           list.add(new Generics());  // 无法通过，编译时错误

18.           printList(list);

19.       }

20. }
    正如在代码中所看到的，容器的声明有了变化，即在一个容器类后面用 <> 来说明你想要放入这个容器中的元素类型，那么接下来你只能向这个容器加那种类型，否则编译就无法通过。在 printList 中也省去了转型的麻烦。当然有了泛型，并不是说以前的声明方法不能用了，你完全可以还用以前的方法，这没有任何问题。其实根据 JSR 中对 for 语句功能的增强，遍历一个容器也会更加简单。
    当然泛型的使用方法不只如此，这里并没有对它进行完整描述，只想告诉你，泛型确实为我们编程提供了便利，但是仍然需要用心去学习和掌握。
    随着 Java 的进一步完善，它的功能和易用性也得到提高，我有理由相信 Java 在计算机语言中所占的位置也会更加牢固，让喜爱 Java 的人更加喜爱它。祝愿 Java 一路走好！