javaGrowing

数组与其它容器的区别体现在三个方面：效率，类型识别以及可以持有primitives.

数组是java提供的，是能随机存储和访问reference序列的诸多方法中，最高效的一种。数组是线形序列，所以它可以快速访问其中的元素，但速度是有代价的，当你创建了一个数组之后它的容量就固定了，而且在其生命周期里不能改变。也许你会提议先创建一个数组，等到快不够用的时候，再创建一个新的，然后将旧数组里的reference 全部导到新的里面。其实ArrayList 就是这么做的。但是这种灵活性所带来的开销，使得ArrayList 的效率比       起数组有了明显下降。      

在我们写程序的时候往往不知道要用多少对象，或者要用一种更复杂方式来存储对象情况。为此，Java 提供了“容器类(container class)”。其基本类型有List, Set 和Map。有了这些工具，你就能解决很多问题了。它们还有一些别的特性。比方说Set 所持有的对象，个个都不同，Map则是一个“关联性数组(associative array)”，它能在两个对象之间建立联系。此外，与数组不同，它们还能自动调整大小，所以你可以往里面放任意数量的对象。这样写程序的时候，就不用操心要开多大的空间了。

 

Java2 的容器类要解决“怎样持有对象”，而它把这个问题分成两类：

1. Collection: 通常是一组有一定规律的独立元素。List 必须按照特定的顺序持有这些元素，而Set 则不能保存重复的元素。(bag没有这个限制，但是Java的容器类库没有实现它，因为List 已经提供这种功能了。)

2. Map: 一组以“键——值”(key-value)形式出现的pair。初看上去，它应该是一个pair的Collection，但是真这么去做的话，它就会变得很滑稽，所以还是把这个概念独立列出来为好。退一步说，真的要用到Map 的某个子集的时候，创建一个Collection 也是很方便的。Map可以返回“键(key)的”Set，值的Collection，或者pair的Set。和数组一样，Map 不需要什么修改，就能很容易地扩展成多维。你只要直接把Map 的值设成Map 就可以了(然后它的值再是Map，以此类推)。我们先来看看容器的一般特性，然后深入细节，最后再看什么会有这么多版本，以及如何进行选择。

 

List 会老老实实地持有你所输入的所有对象，既不做排序也不做编辑。Set 则每个对象只接受一次，而且还要用它自己的规则对元素进行重新排序(一般情况下，你关心的只是Set 包没包括某个对象，而不是它到底排在哪里——如果是那样，你最好还是用List)。而Map 也不接收重复的pair，至于是不是重复，要由key来决定。此外，它也有它自己的内部排序规则，不会受输入顺序影响。如果插入顺序是很重要的，那你就只能使用LinkedHashSet 或LinkedHashMap 了。

第一眼看到这张图的时候，你会觉得很震撼。不过你马上就会知道，实际上只有三种容器组件——Map，List 和Set，而每种又有两到三个实现。最常用的几个容器已经用粗黑线框了起来。看到这里，这张图就不再那么令人望而生畏了。
用点号框起来的是interface，用虚线框起来的是abstract 类，实线
则表示普通的(“实体concrete”)类。点线的箭头表示类实现了这个interface(或者，abstract 类表示部分实现了这个interface)。实线
箭头表示这个类可以制造箭头所指的那个类的对象。比如，Collection
能制造Iterator，而List 还能制造ListIterator(也能制造Iterator，因为List 是继承自Collection 的)。
与存放对象有关的接口包括Collection，List，Set 和Map。在理想情况下，绝大多数代码应该只同这些接口打交道，只是在创建容器的时候才要精确地指明它的确切类型。所以你可以这样创建一个List。
List x = new LinkedList( );

当然，你也可以选择让x 成为LinkedList(而不是泛型的List)，这样x 就带上了准确的类型信息interface 的优雅 (同时也是它的本意)就在于，你想修改具体的实现的时候，只要改一下创建的声明就可以了，就
像这样：
List x = new ArrayList( );
无需惊动其它代码(用迭代器也能获得一些这种泛型性)。这个类系里面有很多以“Abstract”开头的类，初看起来这可能会让人有点不明白。实际上它们只是一些部分实现某个接口的办成品。假如你要编一个你自己的Set，不要从Set 接口开始挨个实现它的方法；相反你最好继承AbstractSet，这样就能把编程的工作量压缩到最低了。但是，实际上容器类库的功能已经够强的了，我们要求的事情它几乎都能做
到。所以对我们来说，你完全可以忽略以“Abstract”开头的类。

List 的功能
正如你从ArrayList 那里所看到的，List 的基本用法是相当简单的。虽然绝大多数时候，你只是用add( )加对象，用get( )取对象，用iterator( )获取这个序列的Iterator，但List 还有一些别的很有用的
方法。
实际上有两种List：擅长对元素进行随机访问的，较常用的ArrayList，和更强大的LinkedList。LinkedList 不是为快速的随机访问而设计的，但是它却有一组更加通用的方法。

List (接口)	List 的最重要的特征就是有序；它会确保以一定的顺序保存元素。List 在Collection 的基础上添加了大量方法，使之能在序列中间插入和删除元素。(只对LinkedList 推荐使用。)List 可以制造ListIterator 对象，你除了能用它在List 的中间插入和删除元素之外，还能用它沿两个方向遍历List。
ArrayList*	一个用数组实现的List。能进行快速的随机访问， 但是往列表中间插入和删除元素的时候比较慢。ListIterator 只能用在反向遍历ArrayList 的场 合，不要用它来插入和删除元素，因为相比LinkedList，在ArrayList 里面用ListIterator 的系统开销比较高。
LinkedList	对顺序访问进行了优化。在List 中间插入和删除元 素的代价也不高。随机访问的速度相对较慢。(用ArrayList 吧。)此外它还有addFirst( )， addLast( )，getFirst( )，getLast( )， removeFirst( )和removeLast( )等方法(这些 方法，接口和基类均未定义)，你能把它当成栈(stack)，队列(queue)或双向队列(deque)来用。 下面这段程序把各种操作都集中到方法里面：List 都能作的事(basicTest( ))，用Iterator 在列表中移动(iterMotion( ))，修改 列表的元素(iterManipulation( ))，查看List 的操作结果(testVisual( ))，以及LinkedList 所独有的方法。

Set 的功能
Set 的接口就是Collection 的，所以不像那两个List，它没有额外的
功能。实际上Set 确确实实就是一个Collection——只不过行为方式不
同罢了。(这是继承和多态性的完美运用：表达不同地行为。)Set 会拒绝
持有多个具有相同值的对象的实例(对象的“值”又是由什么决定的呢？
这个问题比较复杂，我们以后会讲的)。

Set (接口)	加入Set 的每个元素必须是唯一的；否则， Set 是不会把它加进去的。要想加进Set， Object 必须定义equals( )，这样才能标明对象的唯一性。Set 的接口和Collection 的 一模一样。Set 的接口不保证它会用哪种顺序来存储元素。
HashSet*	为优化查询速度而设计的Set。要放进HashSet 里面的Object 还得定义hashCode( )。
TreeSet	是一个有序的Set，其底层是一棵树。这样你 就能从Set 里面提取一个有序序列了。
LinkedHashSet	(JDK 1.4) 一个在内部使用链表的Set，既有HashSet 的查询速度，又能保存元素被加进去的顺序(插入顺序)。用Iterator 遍历Set 的时候， 它是按插入顺序进行访问的。

Map 的功能
ArrayList 能让你用数字在一个对象序列里面进行选择，所以从某种意义上讲，它是将数字和对象关联起来。但是，如果你想根据其他条件在一个对象序列里面进行选择的话，那又该怎么做呢？从概念上讲，它看上去像是一个ArrayList，但它不用数字，而是用另一个对象来查找对象！这是一种至关重要的编程技巧。这一概念在Java 中表现为Map。put(Object key, Object value)方法会往Map 里面加一个值，并且把这个值同键(你查找时所用的对象)联系起来。给出键之后，get(Object key)就会返回与之相关联的值。
你也可以用containsKey( ) 和 containsValue( )测试Map 是否包含有某个键或值。
Java 标准类库里有好几种Map：HashMap，TreeMap， LinkedHashMap，WeakHashMap，IdentityHashMap。
它们都实现了Map 的基本接口，但是在行为方式方面有着明显的差异。这些差异体现在，效率，持有和表示对象pair 的顺序，持有对象的时间长短，以及如何决定键的相等性。性能是Map 所要面对的一个大问题。如果你知道get( )是怎么工作的，你就会发觉(比方说)在ArrayList 里面找对象会是相当慢的。而这
正是HashMap 的强项。它不是慢慢地一个个地找这个键，而是用了一种被称为hash code的特殊值来进行查找的。散列(hash)是一种算法，它会从目标对象当中提取一些信息，然后生成一个表示这个对象的“相对
独特”的int。hashCode( )是Object 根类的方法，因此所有Java对象都能生成hash code。HashMap 则利用对象的hashCode( )来进行快速的查找。这样性能就有了急剧的提高。

Map (接口)	维持键－值的关联(即pairs)，这样就能用键来找值了。
HashMap*	基于hash表的实现。(用它来代替Hashtable。)提供时间恒定的插入与查询。在构造函数中可以设置 hash表的capacity 和load factor。可以通过构造 函数来调节其性能。
LinkedHashMap	(JDK 1.4) 很像HashMap，但是用Iterator 进行 遍历的时候，它会按插入顺序或最先使用 的顺序(least-recently-used (LRU) order)进行访问。除了用Iterator 外， 其他情况下，只是比HashMap 稍慢一 点。用Iterator 的情况下，由于是使用 链表来保存内部顺序，因此速度会更快。
TreeMap	基于红黑树数据结构的实现。当你查看键 或pair 时，会发现它们是按顺序 (根据Comparable 或Comparator，我们过 一会讲)排列的。TreeMap 的特点是，你 所得到的是一个有序的Map。TreeMap 是Map 中唯一有subMap( )方法的实 现。这个方法能让你获取这个树中的一部 分。
WeakHashMap	一个weak key的Map，是为某些特殊问 题而设计的。它能让Map 释放其所持有的 对象。如果某个对象除了在Map 当中充当 键之外，在其它地方都没有其reference 的话，那它将被当作垃圾回收。
IdentityHashMap	(JDK 1.4) 一个用==，而不是equals( )来比较键 的hash map。不是为我们平常使用而设 计的，是用来解决特殊问题的。 散列是往Map 里存数据的常用算法。有时你会需要知道散列算法的工作 细节，所以我们会稍后再讲。