Java 容器类的选择

韩庆安 珠海世纪鼎利科技股份有限公司

关键字：Java 容器类

Java 容器类有两个基本的上层接口Collection 和Map，在两种上层接口的基础上，衍生了一系列的子接口以及其实现类。

Collection，独立元素的序列，这些元素都服从一条或多条规则。List、Set 都是Collection 的一种，List 强调顺序，而Set 不能有重复元素。Map 是键值对类型，允许用户通过键来查找对象。Hash 表允许使用另一个对象来查找某个对象。所有实现Collection 接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection 参数的构造函数用于创建一个新的Collection，这个新的Collection 与传入的Collection 有相同的元素。后一个构造函数允许用户复制一个Collection。

List 是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引来访问List 中的元素，除了具有Collection 接口必备的iterator()方法外，List 还提供一个listIterator()方法，返回一个ListIterator 接口，和标准的Iterator接口相比，ListIterator 多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

实现List 接口的常用类有LinkedList，ArrayList 和Vector。

ArrayList 实现了可变大小的数组。它允许所有元素，包括null。ArrayList 没有同步。size，isEmpty，get，set 方法运行时间为常数。但是add 方法开销为分摊的常数，添加n 个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList 实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity 方法来增加ArrayList 的容量以提高插入效率。

LinkedList 实现了List 接口，允许null 元素。此外LinkedList提供额外的get，remove，insert 方法在LinkedList 的首部或尾部。这些操作使LinkedList 可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意，ArrayList 和LinkedList 都是线程不安全的。如果遇到多线程的环境，则必须自己实现访问同步。例如：List list =Collections.synchronizedList(new LinkedList(...))；

Vector 也是List 接口的一个实现类，但是Vector 是线程安全的。

Set 是Collection 的另一个子接口，它不允许放入重复的元素，即任意的两个元素e1 和e2 都有e1.equals(e2)=false，关于null 元素，Set 接口的实现类也只能允许存入一次。

Set 接口的典型实现类，有HashSet 和TreeSet。

Map 也是一个接口，而且是需要重点强调的接口，它在实战编程中使用的频率非常高。Map 的特点是用键值对的形式来存放数据，即Key-Value。其中，key 不能重复，Value 可以重复。根据这一特点，在实际编码中，经常用Map 来完成“以键查值”的情况。

Map 接口有两个典型的实现类，HashMap 和TreeMap。其中HashMap 的使用频率更高一些。但HashMap 也是线程不安全的，如果涉及到并发编程，应使用ConcurrentHashMap 代替。

数据元素在内存中的存放有两种方式：

顺序存储。相邻的数据元素存放于相邻的内存地址中，整块内存地址是连续的。可以根据元素的位置直接计算出内存地址，直接进行读取。读取一个特定位置元素的平均时间复杂度为O(1)。基于数组实现的集合，才有这种特性。比如ArrayList。

链式存储。每一个数据元素，在内存中都不要求处于相邻的位置，每个数据元素包含它下一个元素的内存地址。读取一个特定位置元素的平均时间复杂度为O(n)。以链表为代表，比如LinkedList。

在选择容器类的时候，对容器类的遍历，是一个重要的考虑因素。因为不同的遍历方式，会给编码带来不一样的难度，同时也会影响一些执行效率。每一个具体实现的数据集合，一般都需要提供相应的Iterator。相比于传统for 循环，Iterator 取缔了显式的遍历计数器。所以基于顺序存储集合的Iterator 可以直接按位置访问数据。而基于链式存储集合的Iterator，正常的实现，都是需要保存当前遍历的位置。然后根据当前位置来向前或者向后移动指针。

迭代器是容器类对其数据通用的遍历方式，除Set 接口下的容器必须是用迭代器遍历之外，其他容器并不推荐使用这种方式。目前比较流行的是foreach 循环，写法简单，执行起来也比较快。foreach内部也是采用了Iterator 的方式实现，只不过Java 编译器帮我们生成了这些代码。

除foreach 循环之外，使用传统的for 循环也是一种选择，写法上比foreach 循环稍麻烦一些。传统的for 循环遍历，基于计数器的。遍历者自己在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后，停止。主要就是需要按元素的位置来读取元素。

对于Map 的遍历，首先可以获取所有的key，按照key 来遍历，也就是通过key 来寻找value。其次，也可以通过迭代器来遍历，即申请一个Map 类型的Iterator，比如Iterator＜Map.Entry＜Integer,String＞＞ it，然后去遍历这个it。

各遍历方式的适用于什么场合？

1、传统的for 循环遍历，基于计数器的：

顺序存储：读取性能比较高。适用于遍历顺序存储集合。

链式存储：时间复杂度太大，不适用于遍历链式存储的集合。

2、迭代器遍历，Iterator：

顺序存储：如果不是太在意时间，可以使用此方式。

链式存储：平均时间复杂度降为O(n)，推荐此种方式。

3、foreach 循环遍历：

foreach 只是让代码更加简洁了，但是他有一些缺点，就是遍历过程中不能操作数据集合（删除等），所以有些场合不使用。