|
|
作者：时时
15.3.3 HashSet类
HashSet扩展AbstractSet并且实现Set接口。它创建一个类集，该类集使用散列表进行存
储。正像大多数读者很可能知道的那样，散列表通过使用称之为散列法的机制来存储信息。
在散列（hashing）中，一个关键字的信息内容被用来确定唯一的一个值，称为散列码（hash
code）。而散列码被用来当做与关键字相连的数据的存储下标。关键字到其散列码的转换
是自动执行的??你看不到散列码本身。你的程序代码也不能直接索引散列表。散列法的
优点在于即使对于大的集合，它允许一些基本操作如add( )，contains( )，remove( )和size( )
方法的运行时间保持不变。
下面的构造函数定义为：
HashSet( )
HashSet(Collection c)
HashSet(int capacity)
HashSet(int capacity, float fillRatio)
第一种形式构造一个默认的散列集合。第二种形式用c中的元素初始化散列集合。第三
种形式用capacity初始化散列集合的容量。第四种形式用它的参数初始化散列集合的容量和
填充比（也称为加载容量）。填充比必须介于0.0与1.0之间，它决定在散列集合向上调整大
小之前，有多少能被充满。具体的说，就是当元素的个数大于散列集合容量乘以它的填充
比时，散列集合被扩大。对于没有获得填充比的构造函数，默认使用0.75。
HashSet没有定义任何超过它的超类和接口提供的其他方法。
重要的是，注意散列集合并没有确保其元素的顺序，因为散列法的处理通常不让自己
参与创建排序集合。如果需要排序存储，另一种类集??TreeSet将是一个更好的选择。
这里是一个说明HashSet的例子。
// Demonstrate HashSet.
import java.util.*;
class HashSetDemo {
public static void main(String args[]) {
// create a hash set
HashSet hs = new HashSet();
// add elements to the hash set
hs.add("B");
hs.add("A");
hs.add("D");
hs.add("E");
hs.add("C");
hs.add("F");
System.out.println(hs);
}
}
下面是该程序的输出：
[A, F, E, D, C, B]
如上面解释的那样，元素并没有按顺序进行存储。
15.3.4 TreeSet类
TreeSet为使用树来进行存储的Set接口提供了一个工具，对象按升序存储。访问和检索
是很快的。在存储了大量的需要进行快速检索的排序信息的情况下，TreeSet是一个很好的
选择。
下面的构造函数定义为：
TreeSet( )
TreeSet(Collection c)
TreeSet(Comparator comp)
TreeSet(SortedSet ss)
第一种形式构造一个空的树集合，该树集合将根据其元素的自然顺序按升序排序。第
二种形式构造一个包含了c的元素的树集合。第三种形式构造一个空的树集合，它按照由
comp指定的比较函数进行排序（比较函数将在本章后面介绍）。第四种形式构造一个包含
了ss的元素的树集合
这里是一个说明TreeSet的例子。
// Demonstrate TreeSet.
import java.util.*;
class TreeSetDemo {
public static void main(String args[]) {
// Create a tree set
TreeSet ts = new TreeSet();
// Add elements to the tree set
ts.add("C");
ts.add("A");
ts.add("B");
ts.add("E");
ts.add("F");
ts.add("D");
System.out.println(ts);
}
}
这个程序的输出如下所示：
[A, B, C, D, E, F]
正如上面解释的那样，因为TreeSet按树存储其元素，它们被按照排序次序自动安排，
如程序输出所示。
15.4 通过迭代函数访问类集
通常希望循环通过类集中的元素。例如，可能会希望显示每一个元素。到目前为止，
处理这个问题的最简单方法是使用iterator，iterator是一个或者实现Iterator或者实现
ListIterator接口的对象。Iterator可以完成循环通过类集，从而获得或删除元素。ListIterator
扩展Iterator，允许双向遍历列表，并可以修改单元。Iterator接口说明的方法总结在表15-4
中。ListIterator接口说明的方法总结在表15-5中。
表15-4 由Iterator 定义的方法
方法描述
boolean hasNext( ) 如果存在更多的元素，则返回true，否则返回false
Object next( ) 返回下一个元素。如果没有下一个元素，则引发NoSuchElementException异常
void remove( ) 删除当前元素，如果试图在调用next( )方法之后，调用remove( )方法，则引发
IllegalStateException异常
表15-5 由ListIterator 定义的方法
方法描述
void add(Object obj) 将obj插入列表中的一个元素之前，该元素在下一次调用next( )方法时，被返
回
boolean hasNext( ) 如果存在下一个元素，则返回true；否则返回false
boolean hasPrevious( ) 如果存在前一个元素，则返回true；否则返回false
Object next( ) 返回下一个元素，如果不存在下一个元素，则引发一个NoSuchElement
Exception异常
int nextIndex( ) 返回下一个元素的下标，如果不存在下一个元素，则返回列表的大小
Object previous( ) 返回前一个元素，如果前一个元素不存在，则引发一个NoSuchElement
Exception异常
int previousIndex( ) 返回前一个元素的下标，如果前一个元素不存在，则返回-1
void remove( ) 从列表中删除当前元素。如果remove( )方法在next( )方法或previous( )方法调
用之前被调用，则引发一个IllegalStateException异常
void set(Object obj) 将obj赋给当前元素。这是上一次调用next( )方法或previous( )方法最后返回的
元素
15.4.1 使用迭代函数
在通过迭代函数访问类集之前，必须得到一个迭代函数。每一个Collection类都提供一
个iterator( )函数，该函数返回一个对类集头的迭代函数。通过使用这个迭代函数对象，可
以访问类集中的每一个元素，一次一个元素。通常，使用迭代函数循环通过类集的内容，
步骤如下：
1. 通过调用类集的iterator( )方法获得对类集头的迭代函数。
2. 建立一个调用hasNext( )方法的循环，只要hasNext( )返回true，就进行循环迭代。
3. 在循环内部，通过调用next( )方法来得到每一个元素。
对于执行List的类集，也可以通过调用ListIterator来获得迭代函数。正如上面解释的那
样，列表迭代函数提供了前向或后向访问类集的能力，并可让你修改元素。否则，ListIterator
如同Iterator功能一样。
这里是一个实现这些步骤的例子，说明了Iterator和ListIterator。它使用ArrayList对象，
但是总的原则适用于任何类型的类集。当然，ListIterator只适用于那些实现List接口的类集。
// Demonstrate iterators.
import java.util.*;
class IteratorDemo {
public static void main(String args[]) {
// create an array list
ArrayList al = new ArrayList();
// add elements to the array list
al.add("C");
al.add("A");
al.add("E");
al.add("B");
al.add("D");
al.add("F");
// use iterator to display contents of al
System.out.print("Original contents of al: ");
Iterator itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
// modify objects being iterated
ListIterator litr = al.listIterator();
while(litr.hasNext()) {
Object element = litr.next();
litr.set(element + "+");
}
System.out.print("Modified contents of al: ");
itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
System.out.println();
314 第2 部分Java 库
// now, display the list backwards
System.out.print("Modified list backwards: ");
while(litr.hasPrevious()) {
Object element = litr.previous();
System.out.print(element + " ");
}
System.out.println();
}
}
程序的输出如下所示：
Original contents of al: C A E B D F
Modified contents of al: C+ A+ E+ B+ D+ F+
Modified list backwards: F+ D+ B+ E+ A+ C+
特别值得注意的是：列表是如何被反向显示的。在列表被修改之后，litr指向列表的末
端（记住，当到达列表末端时，litr.hasNext( )方法返回false）。为了以反向遍历列表，程序
继续使用litr，但这一次，程序检测它是否有前一个元素。只要它有前一个元素，该元素就
被获得并被显示出来。
|