当前页面: 开发资料首页 → Java 专题 → Java集合框架 (二)

Java集合框架 (二)

摘要: Java集合框架 (二)

2.2.AbstractList和AbstractSequentialList抽象类
有两个抽象的 List 实现类：AbstractList 和 AbstractSequentialList。像
AbstractSet 类一样，它们覆盖了 equals() 和 hashCode() 方法以确保两个相等
的集合返回相同的哈希码。若两个列表大小相等且包含顺序相同的相同元素，则这
两个列表相等。这里的 hashCode() 实现在 List 接口定义中指定，而在这里实现。
除了equals()和hashCode()，AbstractList和AbstractSequentialList实现了其余
List 方法的一部分。因为数据的随机访问和顺序访问是分别实现的，使得具体列表
实现的创建更为容易。需要定义的一套方法取决于您希望支持的行为。您永远不必
亲自提供的是 iterator方法的实现。
2.3. LinkedList类和ArrayList类
在“集合框架”中有两种常规的 List 实现：ArrayList 和 LinkedList。使用两种
List 实现的哪一种取决于您特定的需要。如果要支持随机访问，而不必在除尾部的
任何位置插入或除去元素，那么，ArrayList 提供了可选的集合。但如果，您要频
繁的从列表的中间位置添加和除去元素，而只要顺序的访问列表元素，那么，
LinkedList 实现更好。
『ArrayList 和 LinkedList 都实现 Cloneable 接口，都提供了两个构造函数，一
个无参的，一个接受另一个Collection』
2.3.1. LinkedList类
LinkedList类添加了一些处理列表两端元素的方法。
(1) void addFirst(Object o): 将对象o添加到列表的开头
void addLast(Object o)：将对象o添加到列表的结尾
(2) Object getFirst(): 返回列表开头的元素
Object getLast(): 返回列表结尾的元素
(3) Object removeFirst(): 删除并且返回列表开头的元素
Object removeLast():删除并且返回列表结尾的元素
(4) LinkedList(): 构建一个空的链接列表
LinkedList(Collection c): 构建一个链接列表，并且添加集合c的所有元素
『使用这些新方法，您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面
向端点的数据结构。』
2.3.2. ArrayList类
ArrayList类封装了一个动态再分配的Object[]数组。每个ArrayList对象有一个
capacity。这个capacity表示存储列表中元素的数组的容量。当元素添加到
ArrayList时，它的capacity在常量时间内自动增加。
在向一个ArrayList对象添加大量元素的程序中，可使用ensureCapacity方法增加
capacity。这可以减少增加重分配的数量。
(1) void ensureCapacity(int minCapacity): 将ArrayList对象容量增加
minCapacity
(2) void trimToSize(): 整理ArrayList对象容量为列表当前大小。程序可使用这
个操作减少ArrayList对象存储空间。
2.3.2.1. RandomAccess接口
一个特征接口。该接口没有任何方法，不过你可以使用该接口来测试某个集合
是否支持有效的随机访问。ArrayList和Vector类用于实现该接口。
3.Set接口
Set 接口继承 Collection 接口，而且它不允许集合中存在重复项，每个具体的
Set 实现类依赖添加的对象的 equals()方法来检查独一性。Set接口没有引入新方
法，所以Set就是一个Collection，只不过其行为不同。
3.1. Hash表
Hash表是一种数据结构，用来查找对象。Hash表为每个对象计算出一个整数，
称为Hash Code(哈希码)。Hash表是个链接式列表的阵列。每个列表称为一个
buckets(哈希表元)。对象位置的计算　index = HashCode % buckets (HashCode
为对象哈希码，buckets为哈希表元总数)。
当你添加元素时，有时你会遇到已经填充了元素的哈希表元，这种情况称为Hash
Collisions(哈希冲突)。这时，你必须判断该元素是否已经存在于该哈希表中。
如果哈希码是合理地随机分布的，并且哈希表元的数量足够大，那么哈希冲突的数
量就会减少。同时，你也可以通过设定一个初始的哈希表元数量来更好地控制哈希
表的运行。初始哈希表元的数量为　buckets = size * 150% + 1 (size为预期元素的数量)。
如果哈希表中的元素放得太满，就必须进行rehashing(再哈希)。再哈希使哈希表元
数增倍，并将原有的对象重新导入新的哈希表元中，而原始的哈希表元被删除。
load factor(加载因子)决定何时要对哈希表进行再哈希。在Java编程语言中，加载
因子默认值为0.75，默认哈希表元为101。
3.2. Comparable接口和Comparator接口
在“集合框架”中有两种比较接口：Comparable接口和Comparator接口。像String
和Integer等Java内建类实现Comparable接口以提供一定排序方式，但这样只能实现
该接口一次。对于那些没有实现Comparable接口的类、或者自定义的类，您可以通
过Comparator接口来定义您自己的比较方式。
3.2.1. Comparable接口
在java.lang包中，Comparable接口适用于一个类有自然顺序的时候。假定对象集合
是同一类型，该接口允许您把集合排序成自然顺序。
(1) int compareTo(Object o): 比较当前实例对象与对象o，如果位于对象o之前，
返回负值，如果两个对象在排序中位置相同，则返回0，如果位于对象o后面，则返回正值
在 Java 2 SDK版本1.4中有二十四个类实现Comparable接口。下表展示了8种基本类
型的自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。 类
排序
BigDecimal,BigInteger,Byte, Double, Float,Integer,Long,Short
按数字大小排序
Character
按 Unicode 值的数字大小排序
String
按字符串中字符 Unicode 值排序
利用Comparable接口创建您自己的类的排序顺序，只是实现compareTo()方法的问题
。通常就是依赖几个数据成员的自然排序。同时类也应该覆盖equals()和hashCode
()以确保两个相等的对象返回同一个哈希码。
3.2.2. Comparator接口
若一个类不能用于实现java.lang.Comparable，或者您不喜欢缺省的Comparable行
为并想提供自己的排序顺序(可能多种排序方式)，你可以实现Comparator接口，从
而定义一个比较器。
(1)int compare(Object o1, Object o2): 对两个对象o1和o2进行比较，如果o1位
于o2的前面，则返回负值，如果在排序顺序中认为o1和o2是相同的，返回0，如果o1
位于o2的后面，则返回正值
『与Comparable相似，0返回值不表示元素相等。一个0返回值只是表示两个对象排
在同一位置。由Comparator用户决定如何处理。如果两个不相等的元素比较的结果
为零，您首先应该确信那就是您要的结果，然后记录行为。』
(2)boolean equals(Object obj): 指示对象obj是否和比较器相等。
『该方法覆写Object的equals()方法，检查的是Comparator实现的等同性，不是处
于比较状态下的对象。』
3.3. SortedSet接口
“集合框架”提供了个特殊的Set接口：SortedSet，它保持元素的有序顺序。
SortedSet接口为集的视图(子集)和它的两端（即头和尾）提供了访问方法。当您处
理列表的子集时，更改视图会反映到源集。此外，更改源集也会反映在子集上。发
生这种情况的原因在于视图由两端的元素而不是下标元素指定，所以如果您想要一
个特殊的高端元素（toElement）在子集中，您必须找到下一个元素。
添加到SortedSet实现类的元素必须实现Comparable接口，否则您必须给它的构
造函数提供一个Comparator接口的实现。TreeSet类是它的唯一一份实现。
『因为集必须包含唯一的项，如果添加元素时比较两个元素导致了0返回值（通过
Comparable的compareTo()方法或Comparator的compare()方法），那么新元素就没
有添加进去。如果两个元素相等，那还好。但如果它们不相等的话，您接下来就应
该修改比较方法，让比较方法和 equals() 的效果一致。』
(1) Comparator comparator(): 返回对元素进行排序时使用的比较器，如果使用
Comparable接口的compareTo()方法对元素进行比较，则返回null
(2) Object first(): 返回有序集合中第一个(最低)元素
(3) Object last(): 返回有序集合中最后一个(最高)元素
(4) SortedSet subSet(Object fromElement, Object toElement): 返回从
fromElement(包括)至toElement(不包括)范围内元素的SortedSet视图(子集)
(5) SortedSet headSet(Object toElement): 返回SortedSet的一个视图，其内各
元素皆小于toElement
(6) SortedSet tailSet(Object fromElement): 返回SortedSet的一个视图，其内
各元素皆大于或等于fromElement
3.4. AbstractSet抽象类
AbstractSet类覆盖了Object类的equals()和hashCode()方法，以确保两个相等的集
返回相同的哈希码。若两个集大小相等且包含相同元素，则这两个集相等。按定义
，集的哈希码是集中元素哈希码的总和。因此，不论集的内部顺序如何，两个相等
的集会有相同的哈希码。
3.4.1. Object类
(1) boolean equals(Object obj): 对两个对象进行比较，以便确定它们是否相同
(2) int hashCode(): 返回该对象的哈希码。相同的对象必须返回相同的哈希码
3.5. HashSet类类和TreeSet类
“集合框架”支持Set接口两种普通的实现：HashSet和TreeSet(TreeSet实现
SortedSet接口)。在更多情况下，您会使用 HashSet 存储重复自由的集合。考虑到
效率，添加到 HashSet 的对象需要采用恰当分配哈希码的方式来实现hashCode()方
法。虽然大多数系统类覆盖了 Object中缺省的hashCode()和equals()实现，但创建
您自己的要添加到HashSet的类时，别忘了覆盖 hashCode()和equals()。
当您要从集合中以有序的方式插入和抽取元素时，TreeSet实现会有用处。为了能顺
利进行，添加到TreeSet的元素必须是可排序的。
3.5.1.HashSet类
(1) HashSet(): 构建一个空的哈希集
(2) HashSet(Collection c): 构建一个哈希集，并且添加集合c中所有元素
(3) HashSet(int initialCapacity): 构建一个拥有特定容量的空哈希集
(4) HashSet(int initialCapacity, float loadFactor): 构建一个拥有特定容量
和加载因子的空哈希集。LoadFactor是0.0至1.0之间的一个数
3.5.2. TreeSet类
(1) TreeSet():构建一个空的树集
(2) TreeSet(Collection c): 构建一个树集，并且添加集合c中所有元素
(3) TreeSet(Comparator c): 构建一个树集，并且使用特定的比较器对其元素进行排序
『comparator比较器没有任何数据，它只是比较方法的存放器。这种对象有时称为
函数对象。函数对象通常在“运行过程中”被定义为匿名内部类的一个实例。』
TreeSet(SortedSet s): 构建一个树集，添加有序集合s中所有元素，并且使用与有
序集合s相同的比较器排序
↑返回目录
前一篇: Java集合框架(三)
后一篇: Java多线程学习笔记(二)