数组与其它容器的区别体现在三个方面:效率,类型识别以及可以持有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 里存数据的常用算法。有时你会需要知道散列算法的工作
细节,所以我们会稍后再讲。 |