您的位置: 网站首页 > 程序开发 > Java程序设计 > 第6章 Java的数据结构 > 【6.2 集 合 简 介】

6.2 集 合 简 介

 

6.2 

一个抽象数据类型是一个仅由保存的数据类型和可能在这个数据类型上进行的操作定义的。开发者只能通过抽象数据类型的操作方法来访问抽象数据类型的属性,而且他们不会知道这个数据类型内部各种操作是如何实现的。

Java中,常常使用一个接口来给出一个操作集合而不需要透露这些操作实现的细节。记住一个接口定义了一个方法集,而Java类必须实现这个集合以便满足它的强制性条件,或者实现这个接口的一个实例。

当谈论抽象数据类型的时候,经常会说到线性表、堆栈和队列,但是不会讨论这些数据结构的细节,而会讨论为什么它们被称为抽象数据类型。

一个线性表是有限个元素的集合,其元素以线性的方式进行排列并提供对它的元素的直接访问。一个堆栈是一个后进先出(LIFO)的有序线性表,元素从堆栈头加入,并从堆栈头取出。一个队列是一个先进先出FIFO的有序线性表,元素从队列尾加入,并从队列头取出。

线性表、堆栈和队列的内部结构可以用许多方式实现。例如,可以使用一个有序数组或者一个链表来实现每个结构。关键的一点是:不论如何实现其内部结构,它对外的接口总是不变的。这使得用户能够修改或者升级底层的实现过程而不需要改变公共接口部分。

Java2SDK提供了一些类来支持大多数常用的抽象数据类型。这些类被称为Java集合类,它们协同工作从而形成Java 集合架构。这个集合架构提供了一套将数据表示成所谓的集合抽象数据的接口和类。

6.2.1  Java集合接口

Java集合框架提供了一套核心接口,包括CollectionSetListSortedSetMap SortedMap

Collection接口在集合框架层次中处于根的地位,它描述了一组对象(或者称作元素)。Java集合框架没有提供对Collection接口的直接实现,只有对Collection接口的子接口的实现。Collection接口有两个子接口:SetList

Set接口描述的是由一些元素组成的集合,而且不容许元素重复。Set接口使用自己内部的排列规则安排元素。通过Set接口可以快速查找数据结构而不需要知道具体的排列方式。

List接口描述一个集合,集合元素允许重复,以元素安插的次序来放置元素,不会重新排列。通过List接口可以精确地控制访问数据结构的顺序和位置。

Map接口用于维护键/值对(key/valuepairs),描述了从不重复的键到值的映射。Map接口不允许键重复。它拥有自己的内部排列规则。

SortedSet接口进一步扩充了Set接口。同样,SortedMap接口则是对Map接口的扩充。对SortedSet接口和SortedMap接口的实现必须实现分类,即排序。

6.2.2  Java集合实现

上面介绍了Java集合框架的接口,下面介绍的是Java集合框架中对这些接口的实现。

Set接口的实现有HashSet TreeSetLinkedHashSetTreeSet 实现了SortedSet

List接口的实现包括ArrayListLinkedList

可用的Map接口的实现有HashMapTreeMapLinkedHashMapIdentityHashMapWeakHashMapTreeMap实现了SortedMapLinkedHashMap继承自HashMap

LinkedHashSetLinkedHashMapJDK 1.4以后才引入的,它们内部自动维护了在增添、搜索和删除操作后的元素顺序。JDK 1.4中另一个实现是IdentityHashMap,它用“==”代替了equals( )来进行等比较。对于在WeakReference感兴趣的人来说,还有一个映射WeakHashMap,它可以把WeakReference用作键(Key)。因而,如果是通过键作为值(Value)的唯一引用,将会丢弃该键-值对。

在设计之初,集合框架是非线程安全的。多线程的同步访问安全性需要用一个线程安全的包装器(Wrapper)来达到。Java中还有一个“不可改变”包装器,这个包装器取消了更改集合的功能,其方法是截取所有那些要更改对象集的操作,并抛出一个Unsupported OperationException

6.2.3  Java集合的发展历史

Java诞生之初,Java核心类库仅支持几种数据结构,包括数组(Array)、向量(Vector和哈希表(Hash Table),而不支持另一些重要的数据结构,比如平衡树(Balanced Tree)、优先队列(Priority Queue)等,但是这些都可以自己来构建。因而,有一些开发者在类库中加入了他们自己的数据结构。

早期的Java程序员是由C++程序员转变而来。他们习惯于使用C++Standard Template Library (STL) 进行开发,因此他们模仿STL创立了一套Java类库。但该类库对算法和数据结构的支持极其缺乏,一家公司(Object Space)决定将STL接入Java,于是Java Generic Library (JGL) 1996年发布。JGL流行一时,事实上成为早期Java的一个标准。在几次修订之后,JGL 3.1版本在1997年发布。

JDK 1.2 是在199812月发布的,它包括了一组称为Java集合框架的类,用来操作数据集合。可以说JGLSTL的替代品,而Java集合框架则不是。习惯使用C++Java开发者倾向于使用JGL,因为他们已经很熟悉STL了。JGL大约有130个类和接口,而Java集合框架约是JGL20%