Java中的集合类

为什么要使用集合类 当你事先不知道要存放数据的个数， 或者你需要一种比数组下标存取 机制 更灵活的方法时，你就需要用到集合类。理解集合类集合类存放于 java.util 包中。集合类存放的都是对象的引用，而非对象本身，出于表达上的便利， 我们称 集合中的对象就是指集合中对象的引用（ reference） 。集合类型主要有3种：set （集）、list （列表）和map （映射）。（1）集集（set）是最简单的一种集合，它的对象不按特定方式排序，只是简单的 把对象加入集合中，就像往口袋里放东西。对集中成员的访问和操作是通过集中对象的引用进行的， 所以集中不 能有 重复对象。集也有多种变体，可以实现排序等功能，如TreeSet,它把对象添加到集 中的操作将变为按照某种比较规则将其插入到有序的对象序列 中。它实现的 是 SortedSet 接口，也就是加入了对象比较的方法。 通过对集中的对象迭 代，我们可以得到一个升序的对象集合。（2）列表列表的主要特征是其对象以线性方式存储， 没有特定顺序， 只有一个 开头 和一个结尾，当然，它与根本没有顺序的集是不同的。列表在数据结构中分别表现为：数组和向量、链表、堆栈、队列。关于实现列表的集合类， 是我们日常工作中经常用到的， 将在后边的笔记详细介绍(3)映射映射与集或列表有明显区别，映射中每个项都是成对的。映射中存储的每 个对象都有一个相关的关键字( Key )对象，关键字决定了对象在映射中的 存储位置，检索对象时必须提供相应的关键字，就像在字 典中查单词一 样。关键字应该是唯一的。关键字本身并不能决定对象的存储位置，它需要 对过一种散列(hashing)技术来处理，产生一个被称作散列码(hash code) 的整数值，散列码通常用作一个偏置量，该偏置量是相对于分配给 映射的内 存区域起始位置的，由此确定关键字/ 对象对的存储位置。理想 情况 下，散列处理应该产生给定范围内均匀分布的值，而且每个关键字应 得到不同的散列码。集合类简介java.util 中共有 13 个类可用于管理集合对象，它们支持集、列表或映 射等集合，以下是这些类的简单介绍集：HashSet ： 使用 HashMap 的一个集的实现。虽然集定义成无序，但必须 存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集 的存储和检索操作是在固定时间内实现的. TreeSet ： 在集中以升序对对 象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按 升序提供对象。 TreeSet 类使用 了一个 TreeMap.列表：Vector ： 实现一个类似数组一样的表，自动增加容量来容纳你所需的元 素。使用下标存储和检索对象就象在一个标准的数组中一样。你 也可以用 一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类 ?当两个或多个线程同时访问时也是性能良好的。Stsck: 这个类从 Vector 派生而来，并且增加了方法实现栈?一种后 进 先出的存储结构。LinkedList: 实现一个链表。由这个类定义的链表也可以像栈或队列一样 被使用。ArrayList: 实现一个数组，它的规模可变并且能像链表一样被访问。它提供的功能类似 Vector 类但不同步。映射：HashTable ：实现一个映象，所有的键必须非空。为了能高效的工作，定义键的类必须实现hashcode()方法和equal()方法。这个类是前面 java 实现的一个继承，并且通常能在实现映象的其他类中更好的使用。HashMap ： 实现一个映象，允许存储空对象，而且允许键是空(由于键必 须是唯一的，当然只能有一个) 。WeakHashMap ： 实现这样一个映象：通常如果一个键对一个对象而言不再 被引用，键/对象对将被舍弃。这与HashMap形成对照，映象中的键维 持键 / 对象对的生命周期，尽管使用映象的程序不再有对键的引用，并且 因此不能检索对象。TreeMap ： 实现这样一个映象，对象是按键升序排列的。Set 和 List 都是由公共接口 Collection 扩展而来，所以它们都可以使 用一个类型为 Collection 的变量来引用。这就意味着任何列表或集构成 的集合都可以用这种方式引用，只有映射类除外 (但也不是完 全排除在 外，因为可以从映射获得一个列表。 )所以说，把一个列表或集传递给方法 的标准途径是使用Collection类型的参数。Vector 还是 ArrayList ，哪一个更好，为什么？要回答这个问题不能一 概而论，有时候使用Vector比较好；有时是ArrayList，有时候这两个 都不是最好的选择。你别指望能够获得一个简单肯定答案，因为这要看你 用它们干什么。下面有 4 个要考虑的因素：(1) API(2) 同步处理(3) 数据增长性(4) 使用模式下面针对这4 个方面进行一一探讨API在由 Ken Arnold 等编著的Java Programming Language (Addison-Wesley, June 2000) 书中有这样的描述，Vector类似于 ArrayList. 。所有从 API 的角度来看这两个类非常相似。但他们之间也 还是有一些主要的区别的。同步性Vector是同步的。这个类中的一些方法保证了 Vector中的对象是线 程 安全的。而ArrayList则是异步的，因此ArrayList中的对象并不 是线 程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安 全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步 带来的不必要的性能开销。数据增长 从内部实现机制来讲 ArrayList 和 Vector 都是使用数组 (Array) 来控 制集合中的对象。 当你向这两种类型中增加元素的时候， 如果元素的 数目超出了内部数组目前的长度它们都需要扩展内部数组的长 度， Vector 缺省情况下自动增长原来一倍的数组长度， ArrayList 是原 来 的 50%, 所以最后你获得的这个集合所占的空间总是比你实际需要的 要 大。所以如果你要在集合中保存大量的数据那么使用 Vector 有一 些优 势，因为你可以通过设置集合的初始化大小来避免不必要的资源 开销。 使用模式 在 ArrayList 和 Vector 中，从一个指定的位置(通过索引)查找数 据或 是在集合的末尾增加、 移除一个元素所花费的时间是一样的， 这 个时间我 们用 O(1) 表示。但是，如果在集合的其他位置增加或移除 元素那么花费 的时间会呈线形增长： O(n-i) ，其中 n 代表集合中元素 的个数， i 代 表元素增加或移除元素的索引位置。为什么会这样呢？ 以为在进行上述操作 的时候集合中第 i 和第 i 个元素之后的所有元素 都要执行位移的操作。这 一切意味着什么呢？ 这意味着， 你只是查找特定位置的元素或只在集合的末端增加、 移除 元素，那么使用 Vector 或 ArrayList 都可以。如果是其他操作，你 最 好选择其他的集合操作类。比如， LinkList 集合类在增加或移除集 合中 任何位置的元素所花费的时间都是一样的 O(1) ，但它在索引一 个元素 的使用缺比较慢一0(i)，其中i是索引的位置.使用ArrayList也 很容易， 因为你可以简单的使用索引来代替创建it era tor对象的操作。LinkList也会为每个插入的元素创建对象，所有你要明白它也会 带来额外的开销。最后，在Practical Java一书中Peter Haggar建议使用一个简单的数组( Array )来代替 Vector 或 ArrayList 。尤其是对于执行效率要求高的程序更应如此。因为使用数组(Array)避免了同步、额外的方法调用 和不必要的重新分配空间的操作。在 java.util 中共有 9 个类可以用来管理对象集合描述类 HashSet 使用 HashMap 的一个集的实现。虽然集定义成无序，但 必 须 存在 某 种 方法 能 相 当高 效 地 找到 一 个 对 象 。 使 用 一 个 HashMap 对象实现集的存储和检索操作是在固定时间内实现的. TreeSet 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得 第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap.表 Vector 实现一个类似数组一样的表，自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你 也可以用 一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器 类 ?当两个或多个线程同时访问时也是性能良好的。Stsck 这个类从 Vector 派生而来，并且增加了方法实现栈?一种后 进 先出的存储结构。LinkedList 实现一个链表。由这个类定义的链表也可以像栈或队列一样被 使用。ArrayList 实现一个数组，它的规模可变并且能像链表一样被访问。它提 供的功能类似 Vector 类但不同步。映 象 HashTable 实现一个映象，所有的键必须非空。为了能高效的工 作，定义键的类必须实现hashcode()方法和equal()方法。这个类是 前面java实现的一个继承，并且通常能在实现映象的其他类中更好的使 用。HashMap 实现一个映象，允许存储空对象，而且允许键是空 (由于键必 须是唯一的，当然只能有一个) 。WeakHashMap 实现这样一个映象：通常如果一个键对一个对象而言不再被 引用，键/对象对将被舍弃。这与HashMap形成对照，映象中的键维持 键 / 对象对的生命周期，尽管使用映象的程序不再有对键的引用，并且因 此不能检索对象。TreeMap 实现这样一个映象，对象是按键升序排列的。Java.util 包中的迭代器( Iteraor )接口描述了三种方法：方法描述Next()从第一个开始返回一个Object类型的对象，并且设置迭代器对象 在下次调用该方法时返回下一个对象。若这个方法没有对象返回，则抛出一 个 NoSuchElementException 异常。HasNext()若调用next()方法检索到下一个对象，则返回ture.Remove。在提供迭代器对象的集合中删除由next()方法返回的最后一 个对象。若没有调用next()或调用next()后你调用了两次remove。， 则会抛出IllegaStateException异常。不是所有的迭代器都支持这个方 法，如果不支持，你却调用了该方法，会抛出UnsupportedOperation异 常。