|
|
作者：時(shí)時(shí)
15.3.3 HashSet類
HashSet擴(kuò)展AbstractSet并且實(shí)現(xiàn)Set接口。它創(chuàng)建一個(gè)類集，該類集使用散列表進(jìn)行存
儲(chǔ)。正像大多數(shù)讀者很可能知道的那樣，散列表通過(guò)使用稱之為散列法的機(jī)制來(lái)存儲(chǔ)信息。
在散列（hashing）中，一個(gè)關(guān)鍵字的信息內(nèi)容被用來(lái)確定唯一的一個(gè)值，稱為散列碼（hash
code）。而散列碼被用來(lái)當(dāng)做與關(guān)鍵字相連的數(shù)據(jù)的存儲(chǔ)下標(biāo)。關(guān)鍵字到其散列碼的轉(zhuǎn)換
是自動(dòng)執(zhí)行的??你看不到散列碼本身。你的程序代碼也不能直接索引散列表。散列法的
優(yōu)點(diǎn)在于即使對(duì)于大的集合，它允許一些基本操作如add( )，contains( )，remove( )和size( )
方法的運(yùn)行時(shí)間保持不變。
下面的構(gòu)造函數(shù)定義為：
HashSet( )
HashSet(Collection c)
HashSet(int capacity)
HashSet(int capacity, float fillRatio)
第一種形式構(gòu)造一個(gè)默認(rèn)的散列集合。第二種形式用c中的元素初始化散列集合。第三
種形式用capacity初始化散列集合的容量。第四種形式用它的參數(shù)初始化散列集合的容量和
填充比（也稱為加載容量）。填充比必須介于0.0與1.0之間，它決定在散列集合向上調(diào)整大
小之前，有多少能被充滿。具體的說(shuō)，就是當(dāng)元素的個(gè)數(shù)大于散列集合容量乘以它的填充
比時(shí)，散列集合被擴(kuò)大。對(duì)于沒(méi)有獲得填充比的構(gòu)造函數(shù)，默認(rèn)使用0.75。
HashSet沒(méi)有定義任何超過(guò)它的超類和接口提供的其他方法。
重要的是，注意散列集合并沒(méi)有確保其元素的順序，因?yàn)樯⒘蟹ǖ奶幚硗ǔ２蛔屪约?BR>參與創(chuàng)建排序集合。如果需要排序存儲(chǔ)，另一種類集??TreeSet將是一個(gè)更好的選擇。
這里是一個(gè)說(shuō)明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]
如上面解釋的那樣，元素并沒(méi)有按順序進(jìn)行存儲(chǔ)。
15.3.4 TreeSet類
TreeSet為使用樹(shù)來(lái)進(jìn)行存儲(chǔ)的Set接口提供了一個(gè)工具，對(duì)象按升序存儲(chǔ)。訪問(wèn)和檢索
是很快的。在存儲(chǔ)了大量的需要進(jìn)行快速檢索的排序信息的情況下，TreeSet是一個(gè)很好的
選擇。
下面的構(gòu)造函數(shù)定義為：
TreeSet( )
TreeSet(Collection c)
TreeSet(Comparator comp)
TreeSet(SortedSet ss)
第一種形式構(gòu)造一個(gè)空的樹(shù)集合，該樹(shù)集合將根據(jù)其元素的自然順序按升序排序。第
二種形式構(gòu)造一個(gè)包含了c的元素的樹(shù)集合。第三種形式構(gòu)造一個(gè)空的樹(shù)集合，它按照由
comp指定的比較函數(shù)進(jìn)行排序（比較函數(shù)將在本章后面介紹）。第四種形式構(gòu)造一個(gè)包含
了ss的元素的樹(shù)集合
這里是一個(gè)說(shuō)明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);
}
}
這個(gè)程序的輸出如下所示：
[A, B, C, D, E, F]
正如上面解釋的那樣，因?yàn)門(mén)reeSet按樹(shù)存儲(chǔ)其元素，它們被按照排序次序自動(dòng)安排，
如程序輸出所示。
15.4 通過(guò)迭代函數(shù)訪問(wèn)類集
通常希望循環(huán)通過(guò)類集中的元素。例如，可能會(huì)希望顯示每一個(gè)元素。到目前為止，
處理這個(gè)問(wèn)題的最簡(jiǎn)單方法是使用iterator，iterator是一個(gè)或者實(shí)現(xiàn)Iterator或者實(shí)現(xiàn)
ListIterator接口的對(duì)象。Iterator可以完成循環(huán)通過(guò)類集，從而獲得或刪除元素。ListIterator
擴(kuò)展Iterator，允許雙向遍歷列表，并可以修改單元。Iterator接口說(shuō)明的方法總結(jié)在表15-4
中。ListIterator接口說(shuō)明的方法總結(jié)在表15-5中。
表15-4 由Iterator 定義的方法
方法描述
boolean hasNext( ) 如果存在更多的元素，則返回true，否則返回false
Object next( ) 返回下一個(gè)元素。如果沒(méi)有下一個(gè)元素，則引發(fā)NoSuchElementException異常
void remove( ) 刪除當(dāng)前元素，如果試圖在調(diào)用next( )方法之后，調(diào)用remove( )方法，則引發(fā)
IllegalStateException異常
表15-5 由ListIterator 定義的方法
方法描述
void add(Object obj) 將obj插入列表中的一個(gè)元素之前，該元素在下一次調(diào)用next( )方法時(shí)，被返
回
boolean hasNext( ) 如果存在下一個(gè)元素，則返回true；否則返回false
boolean hasPrevious( ) 如果存在前一個(gè)元素，則返回true；否則返回false
Object next( ) 返回下一個(gè)元素，如果不存在下一個(gè)元素，則引發(fā)一個(gè)NoSuchElement
Exception異常
int nextIndex( ) 返回下一個(gè)元素的下標(biāo)，如果不存在下一個(gè)元素，則返回列表的大小
Object previous( ) 返回前一個(gè)元素，如果前一個(gè)元素不存在，則引發(fā)一個(gè)NoSuchElement
Exception異常
int previousIndex( ) 返回前一個(gè)元素的下標(biāo)，如果前一個(gè)元素不存在，則返回-1
void remove( ) 從列表中刪除當(dāng)前元素。如果remove( )方法在next( )方法或previous( )方法調(diào)
用之前被調(diào)用，則引發(fā)一個(gè)IllegalStateException異常
void set(Object obj) 將obj賦給當(dāng)前元素。這是上一次調(diào)用next( )方法或previous( )方法最后返回的
元素
15.4.1 使用迭代函數(shù)
在通過(guò)迭代函數(shù)訪問(wèn)類集之前，必須得到一個(gè)迭代函數(shù)。每一個(gè)Collection類都提供一
個(gè)iterator( )函數(shù)，該函數(shù)返回一個(gè)對(duì)類集頭的迭代函數(shù)。通過(guò)使用這個(gè)迭代函數(shù)對(duì)象，可
以訪問(wèn)類集中的每一個(gè)元素，一次一個(gè)元素。通常，使用迭代函數(shù)循環(huán)通過(guò)類集的內(nèi)容，
步驟如下：
1. 通過(guò)調(diào)用類集的iterator( )方法獲得對(duì)類集頭的迭代函數(shù)。
2. 建立一個(gè)調(diào)用hasNext( )方法的循環(huán)，只要hasNext( )返回true，就進(jìn)行循環(huán)迭代。
3. 在循環(huán)內(nèi)部，通過(guò)調(diào)用next( )方法來(lái)得到每一個(gè)元素。
對(duì)于執(zhí)行List的類集，也可以通過(guò)調(diào)用ListIterator來(lái)獲得迭代函數(shù)。正如上面解釋的那
樣，列表迭代函數(shù)提供了前向或后向訪問(wèn)類集的能力，并可讓你修改元素。否則，ListIterator
如同Iterator功能一樣。
這里是一個(gè)實(shí)現(xiàn)這些步驟的例子，說(shuō)明了Iterator和ListIterator。它使用ArrayList對(duì)象，
但是總的原則適用于任何類型的類集。當(dāng)然，ListIterator只適用于那些實(shí)現(xiàn)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 庫(kù)
// 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指向列表的末
端（記住，當(dāng)?shù)竭_(dá)列表末端時(shí)，litr.hasNext( )方法返回false）。為了以反向遍歷列表，程序
繼續(xù)使用litr，但這一次，程序檢測(cè)它是否有前一個(gè)元素。只要它有前一個(gè)元素，該元素就
被獲得并被顯示出來(lái)。
|