1、Java 高級高級 第十一章 集合框架 主要內(nèi)容：主要內(nèi)容：l 集合類框架的概念 l 集合類接口與類 l兩個特殊的集合類l Java1.0/1.1的集合類集合類框架的概念集合類和集合接口關系圖集合類和集合接口關系圖所謂框架就是一個類庫的集合。集合框架就是一個用來表示和操作集合的統(tǒng)一的架構(gòu)，包含了實現(xiàn)集合的接口與類。集合類和集合接口關系圖解讀集合類和集合接口關系圖解讀l實線框圖表示集合類；虛線框圖表示集合接口；l虛線連接的空心箭頭表示接口之間的繼承或類對接口的實現(xiàn)關系；實線表示類之間的繼承關系。l實心箭頭表示一個接口方法可以返回另一個接口可引用的實例。l圖中還展示了集合類相關的一些功能類如：Co

2、llections和Arrays,它們封裝有特定的集合操作功能。集合類接口 六大集合類接口之一六大集合類接口之一Collection接口接口 lcollection是集合類的基本接口，它用來說明作為一個集合類應有的特征屬性并為一組對象的操作提供了一些簡單的方法。l子接口有：List 和Setl它的實現(xiàn)類有： AbstractCollection,AbstractList,AbstractSet,ArrayList,BeanContextServicesSupport,BeanContextSupport,HashSet,LinkedHashSet,LinkedList,TreeSet,Vect

3、or。Collection接口提供的主要方法接口提供的主要方法boolean add(Object c)：用于向集合中添加一個新元素。boolean addAll(Collection c)：用于添加一組元素。boolean remove(Object o)：用于刪除一個元素。boolean removeAll(Collection c)：用于刪除一組元素。Object toArray()：把集合轉(zhuǎn)換成對象數(shù)組引用返回。Object toArray(Object a)：把集合轉(zhuǎn)換成對象數(shù)組引用返回。但是類型和參數(shù)a的類型是相同的。boolean isEmpty() ：用于判斷集合是否為空。It

4、erator iterator()：用于返回實現(xiàn)Iterator接口的對象。Collection接口的子接口接口的子接口lList 是Collection的子接口，它具有可以控制的順序，但并沒有定義或限制按什么排序。實現(xiàn)List接口的類是AbstractList, ArrayList, LinkedList, Vector。lSet 不能包含重復的元素。它的實現(xiàn)類有AbstractSet, HashSet, LinkedHashSet, TreeSet。lSortedSet是Set的子接口，在Set基礎上，要求其元素按照某種自然順序進行存儲。它的實現(xiàn)類有TreeSet。ArrayListl我們

5、可以將ArrayList看作是能夠自動增長容量的數(shù)組。l利用ArrayList的toArray()返回一個數(shù)組。lArrays.asList()用于返回一個列表。l迭代器(Iterator) 給我們提供了一種通用的方式來遍歷集合中的元素。方法名方法名說明說明boolean hasNext()判斷迭代器是否還存在下一個元素Object next()返回下一個元素的引用void remove()從集合中刪除迭代器指向的最后一個元素返回的元素刪除的元素next()remove()next()Collectionsl排序：Collections.sort() 自然排尋(natural ordering

6、 )； 實現(xiàn)比較器(Comparator)接口。l取最大/最小元素：Collections.max()、Collections.min()。l在已排序的List中搜索指定的元素：Collectons.binarySearch()。LinkedListl線性表：必存在唯一的稱為“第一個”和“最后一個”的數(shù)據(jù)元素；除第一個和最后一個元素外，每個元素都有且只有一個前驅(qū)元素，都有且只有一個后繼元素。線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。lLinkedList是采用雙向循環(huán)鏈表實現(xiàn)的。l利用LinkedList實現(xiàn)棧(stack)、隊列(queue)、雙向隊列(double-ended queue )。

7、單向鏈表的結(jié)構(gòu)單向鏈表的結(jié)構(gòu)datanextdatanextdatanext=nullhead節(jié)點l單向鏈表的插入與刪除datanextdatanextdatanextnullhead節(jié)點datanextdatanextdatanextdatanextnull循環(huán)鏈表的結(jié)構(gòu)循環(huán)鏈表的結(jié)構(gòu)datanextdatanextdatanexthead節(jié)點datanextdatanextdatanexthead節(jié)點previouspreviousprevious棧（棧（Stack）l棧(Stack)也是一種特殊的線性表，是一種后進先出(LIFO)的結(jié)構(gòu)。l棧是限定僅在表尾進行插入和刪除運算的線性表，表尾

8、稱為棧頂(top)，表頭稱為棧底(bottom)。l棧的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈式存儲結(jié)構(gòu)。棧底棧頂出棧進棧隊列（隊列（ Queue ）l隊列(Queue)是限定所有的插入只能在表的一端進行，而所有的刪除都在表的另一端進行的線性表。l表中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)。l隊列的操作是按先進先出(FIFO)的原則進行的。l隊列的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈式存儲結(jié)構(gòu)。隊頭隊尾出隊 入隊ArrayList和和LinkedList的比較的比較lArrayList底層采用數(shù)組完成，而LinkedList則是以雙向鏈表(double-li

9、nked list)完成，其內(nèi)每個對象除了數(shù)據(jù)本身外，還有兩個引用，分別指向前一個元素和后一個元素。l如果我們經(jīng)常在List的開始處增加元素，或者在List中進行插入和刪除操作，我們應該使用LinkedList，否則的話，使用ArrayList將更加快速。就ArrayList與Vector主要從三方面來說:l同步性:Vector是線程安全的，也就是說是同步的，而ArrayList是線程序不安全的，不是同步的。l數(shù)據(jù)增長:當需要增長時，Vector默認增長為原來一倍，而ArrayList卻是原來的一半。ArrayList和和Vector的比較的比較HashSetl實現(xiàn)Set接口，依靠HashMa

10、p來實現(xiàn)的。l我們通常應該為要存放到散列表的各個對象重新定義hashCode()和equals()。l散列表又稱為哈希表。散列表算法的基本思想是：以結(jié)點的關鍵字為自變量，通過一定的函數(shù)關系（散列函數(shù)）計算出對應的函數(shù)值，以這個值作為該結(jié)點存儲在散列表中的地址。TreeSetlTreeSet是依靠TreeMap來實現(xiàn)的。lTreeSet是一個有序集合，TreeSet中元素將按照升序排列，缺省是按照自然順序進行排列，意味著TreeSet中元素要實現(xiàn)Comparable接口。l我們可以在構(gòu)造TreeSet對象時，傳遞實現(xiàn)了Comparator接口的比較器對象。HashSet和和TreeSet的比較的

11、比較lHashSet是基于Hash算法實現(xiàn)的，其性能通常都優(yōu)于TreeSet。我們通常都應該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。六大集合類接口之二六大集合類接口之二Map接口接口lMap接口能夠?qū)⒁粋€鍵(Key)影射到一個值(Value),不允許有重復的鍵，每個鍵之多有一個與之對應的值。lMap 的實現(xiàn)類有： Hashtable、HashMaplSortedMap是Map的子接口，能使Key按照自然順序進行存儲。它的實現(xiàn)類有TreeMapl接口為我們提供了完成下面三種主要的功能的方法Map 改變：包括關鍵字/值對的刪除、更新和插入。Map 查詢：允許用戶從Ma

12、p中獲取關鍵字/值對。提供查詢Map元素內(nèi)容的方法，也有用來查詢整個Map對象的方法。Map接口的三種視圖接口的三種視圖lkeySet()方法獲取的是Map中的關鍵字的一個Set(唯一性)。因為map映射中的關鍵字是唯一，keySet()方法得到的正好是一個set。lvalues()方法返回映射中值的Collection(Collection是允許存儲重復元素的對象的集合)。因為Map中的值是可以重復的，values()方法得到的只能是一個collection而不是一個Set。lentrySet()方法返回Map.Entry的一個Set。即Map對象中所存儲的鍵值對的集合，也就是一個鍵值對構(gòu)成

13、的Set。HashMap和和TreeMap的比較的比較l和Set類似，HashMap的速度通常都比TreeMap快，只有在需要排序的功能的時候，才使用TreeMap。就HashMap與HashTable主要從三方面來說:l歷史原因:Hashtable是基于陳舊的Dictionary類的,HashMap是Java 1.2引進的Map接口的一個實現(xiàn)l同步性:Hashtable是線程安全的，也就是說是同步的，而HashMap是線程序不安全的，不是同步的l值:只有HashMap可以讓你將空值作為一個表的條目的key或value HashMap和和Hashtable的比較的比較六大集合類接口之三六大集合

14、類接口之三Enumeration接口接口lEnumeration接口是一個對集合類進行遍歷的接口。lEnumeration接口提供的方法：boolean hasMoreElements() ：檢索是否有下一個對象，如果有則返回ture；否則返回false。Object nextElement() ：在上一個方法為true的條件下，返回下一個Object類型的對象；如果上一個方法返回的結(jié)果為false，那么還調(diào)用此方法時會產(chǎn)生一個NoSuchElementException。六大集合類接口之四六大集合類接口之四Iteraor接口接口lIteraor接口提供了以下的方法：hasNext()：下一個

15、對象存在返回ture；否則返回false。next()：hasNext()為true時調(diào)用，返回Object類型的對象。remove()：在提供迭代器實現(xiàn)對象的集合中刪除由next()方法指向的一個對象。lIteraor接口的優(yōu)點：Iterator是用于遍歷集合類的標準訪問方法。每種集合類返回的Iterator對象類型可能不同，Array可能返回ArrayIterator，Set可能返回SetIterator，但是它們都實現(xiàn)了Iterator接口，因此用戶不需直接和集合類打交道。六大接口之五六大接口之五ListIterator接口接口lListIterator是Iterator的子接口。它對集

16、合遍歷時進行的更改，將直接影響原來的集合。對List來說，也可以通過listIterator()取得其迭代器。lIterator和ListIterator主要區(qū)別在以下方面：lListIterator和Iterator都有hasNext()和next()方法，可以實現(xiàn)順序向后遍歷，但是ListIterator有hasPrevious()和previous()方法，可以實現(xiàn)逆向（順序向前）遍歷。lListIterator有add()方法，可向List中添加對象。lListIterator可以定位當前的索引位置，nextIndex()和previousIndex()可以實現(xiàn)，Iterator沒有此

17、功能。l都可實現(xiàn)刪除對象，但是ListIterator可以實現(xiàn)對象的修改，此功能通過set()方法來實現(xiàn)。集合接口在使用時的注意事項集合接口在使用時的注意事項lEnumeration接口的nextElement方法和Iteraor接口的next()方法返回的對象用Object進行引用，在實際使用中，應根據(jù)對象的具體類型進行顯式的轉(zhuǎn)化（注意，要轉(zhuǎn)化成X類，條件是集合中所引用的對象原來就是X類型，或是X類型的子類，否則會產(chǎn)生類型轉(zhuǎn)化異常）。l一些集合對象，例如Hashtable、HashMap，它的鍵和其值的加入順序，與Iteraor遍歷順序，并不一定一致。六大接口之六六大接口之六Comparat

18、or接口接口lComparator是一個集合對象排序接口，某個類實現(xiàn)了這個接口，那么這個類的對象就可以進行排序，接口方法如下： public interface Comparator int compare(Object o1, Object o2); boolean equals(Object obj); l一般都只需要實現(xiàn)compare方法就行了,因為類都是默認從Object繼承，可使用Object的equals()方法。兩個特殊的集合類 StringTokenizer類類lStringTokenizer是以token為單元的字符串集合，它實現(xiàn)Enumeration接口，對其集合進行遍歷采

19、用Enumeration提供的方法，當然也可采用它自己的方法，例如：StringTokenizer st = new StringTokenizer(this is a test); while (st.hasMoreTokens() System.out.println(st.nextToken();l默認情況下，StringTokenizer用空格、制表符“t”、回車符、換行符、分頁符為標志進行token區(qū)分。l其他的構(gòu)造方法：public StringTokenizer(String str,String delim)public StringTokenizer(String str, String delim,boo