chapter13集合類(lèi)PartI

1、Chater13 集合框架集合框架1 1、集合框架概述、集合框架概述2 2、CollectionCollection接口接口3 List3 List接口接口方法名方法名說(shuō)說(shuō) 明明boolean add(Object o)在列表的末尾順序添加元素，起始索引位置從0開(kāi)始void add(int index,Object o)在指定的索引位置添加元素。索引位置必須介于0和列表中元素個(gè)數(shù)之間int size()返回列表中的元素個(gè)數(shù)Object get(int index)返回指定索引位置處的元素。取出的元素是Object類(lèi)型，使用前需要進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換boolean contains(Object o

2、)判斷列表中是否存在指定元素boolean remove(Object o)從列表中刪除元素Objectremove(int index)從列表中刪除指定位置元素，起始索引位置從0開(kāi)始具體參看具體參看jdk文檔文檔3.1 ArrayList3.1 ArrayListArrayList list = new ArrayList(); / 創(chuàng)建創(chuàng)建ArrayList集合集合list.add(stu1); / 向集合中添加元素list.add(stu2);list.add(stu3);list.add(stu4);System.out.println(集合的長(zhǎng)度： + list.size(); Sy

3、stem.out.println(第2個(gè)元素是： + list.get(1); 注意：（1）ArrayList特點(diǎn)：底層使用數(shù)組保存元素，增加刪除指定位置的元素時(shí)，會(huì)導(dǎo)致創(chuàng)建新的數(shù)組，效率較低，因此不適合做大量的增刪操作，但是查詢(xún)速度較快。（2）用ArrayList時(shí)，盡量指定類(lèi)型（或者泛型），避免安全隱患，如下：ArrayList list = new ArrayList; 3.2 LinkedList3.2 LinkedList針對(duì)ArrayList的優(yōu)缺點(diǎn)，LinkedList如下：（1）LinkedList為雙向循環(huán)鏈表機(jī)制，每個(gè)元素都通過(guò)引用的方式來(lái)記住它的前一個(gè)和后一個(gè)元素。插入（

4、刪除）元素時(shí)，修改元素間的引用關(guān)系。因此LinkedList對(duì)增刪操作有很高效率。（2）特有方法如下：方法名方法名說(shuō)說(shuō) 明明voidaddFirst(Object o)在列表的首部添加元素voidaddLast(Object o)在列表的末尾添加元素ObjectgetFirst()返回列表中的第一個(gè)元素ObjectgetLast()返回列表中的最后一個(gè)元素ObjectremoveFirst()刪除并返回列表中的第一個(gè)元素ObjectremoveLast()刪除并返回列表中的最后一個(gè)元素LinkedList link = new LinkedList; link.add(stu1);link.a

5、dd(stu2);link.add(stu3);link.add(stu4);/取出并打印該集合中的元素System.out.println(link.toString(); /向該集合中指定位置插入元素link.add(3, Student);/向該集合第一個(gè)位置插入元素link.addFirst(First); System.out.println(link);/取出該集合中第一個(gè)元素System.out.println(link.getFirst(); /移除該集合中指定位置的元素link.remove(3); /移除該集合中第一個(gè)元素link.removeFirst(); System

6、.out.println(link);3.3 Iterator3.3 Iterator接口接口Collection和Map接口主要用于存儲(chǔ)元素，Iterator接口主要用于迭代訪(fǎng)問(wèn)（遍歷）元素，因此稱(chēng)為迭代器。ArrayList list = new ArrayList(); list.add(data_1); list.add(data_2);list.add(data_3);list.add(data_4);Iterator it = list.iterator();/判斷判斷ArrayList集合中是否存在下一個(gè)元素集合中是否存在下一個(gè)元素while (it.hasNext() /取出取

7、出ArrayList集合中的元素集合中的元素 Object obj = it.next(); System.out.println(obj);注意：使用Iterator迭代訪(fǎng)問(wèn)元素時(shí)，如果調(diào)用集合容器對(duì)象的remove方法刪除某個(gè)元素，會(huì)出現(xiàn)異常。如下：ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (

8、Annie.equals(obj) list.remove(obj); System.out.println(list);解決方法1：如果只是想刪除某學(xué)生，則刪除完之后直接break，不要再遍歷ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (Annie.equals(obj) list.remove(

9、obj); break； System.out.println(list);解決方法2：刪除后，仍然想要遍歷，則需要使用迭代器的刪除方法。即調(diào)用迭代器對(duì)象remove方法刪除元素后導(dǎo)致的迭代次數(shù)變換，對(duì)于迭代器對(duì)象本身可以預(yù)知。ArrayList list = new ArrayList(); list.add(Jack);list.add(Annie);list.add(Rose);list.add(Tom);Iterator it = list.iterator(); while (it.hasNext() Object obj = it.next(); if (Annie.equals(

10、obj) it.remove(obj); System.out.println(list);3.4 ListIterator3.4 ListIterator接口接口Iterator接口：迭代方向是正向迭代，即從第一個(gè)到最后一個(gè)。ListIterator接口：實(shí)現(xiàn)反向迭代，從最后一個(gè)到第一個(gè)。方法：add、hasPrevious、previous、removeArrayList list = new ArrayList();list.add(data_1);list.add(data_2);list.add(data_3);System.out.println(list);/list.size作

11、為參數(shù)，說(shuō)明當(dāng)前的迭代指針位置，從哪往前遍歷，不包括本索引/也可以用其他整數(shù)，比如本例中使用1，注意觀察ListIterator it = list.listIterator(list.size();while (it.hasPrevious() Object obj = it.previous(); System.out.print(obj + ); 3.5 Vector3.5 Vector和和EnumerationEnumerationVector:用法與ArrayList完全相同，Vector是線(xiàn)程安全的，ArrayList是線(xiàn)程不安全的。Enumeration接口：JDK1.2前實(shí)現(xiàn)迭

12、代的接口，目前還在用，和Iterator相同方法：hasMoreElements、nextElementVector v = new Vector(); v.add(Jack); v.add(Rose);v.add(Tom);Iterator it = v.iterator();while (it.hasNext() Object o = it.next(); System.out.println(o);Vector v = new Vector(); v.add(Jack); v.add(Rose);v.add(Tom);Enumeration en = v.elements(); whil

13、e (en.hasMoreElements() Object obj = en.nextElement(); System.out.println(obj);4. Set4. Set接口接口Set接口的方法與Collection接口基本一致。與List接口不同：Set接口的元素?zé)o序，通過(guò)某種規(guī)則保證存入的元素不重復(fù)不重復(fù)。主要實(shí)現(xiàn)類(lèi)：HashSet和TreeSet（1）HashSet主要通過(guò)哈希值來(lái)確定元素在集合中的存儲(chǔ)位置，具有較好的存取和查找性能。（哈希值是通過(guò)哈希算法對(duì)對(duì)象的內(nèi)存地址值進(jìn)行計(jì)算得到的一個(gè)整數(shù)值，可以理解為一個(gè)數(shù)字標(biāo)識(shí)。不同對(duì)象的哈希值是有可能相同的）（2）TreeSet則

14、是以二叉樹(shù)的方式來(lái)存儲(chǔ)元素，可以實(shí)現(xiàn)對(duì)集合中的元素進(jìn)行排序。4.1 HashSet4.1 HashSetString str1 = new String(aa);String str2 = new String(aa);if (str1=str2) System.out.println(value is not equal);if (str1.hashCode()=str2.hashCode() System.out.println(hashcode is equal); HashSet set = new HashSet();set.add(str1);set.add(str2);set.a

15、dd(bb);set.add(cc);set.add(dd);Iterator iterator = set.iterator();while (iterator.hasNext() String temp = (String)iterator.next();System.out.println(temp);System.out.println(set);注意輸出情況：注意輸出情況：（1 1）和存入順序不一致，）和存入順序不一致，無(wú)序的無(wú)序的（2 2）沒(méi)有重復(fù)的）沒(méi)有重復(fù)的bbbb，元素，元素不重復(fù)不重復(fù)此外注意此外注意（1 1）基礎(chǔ)數(shù)據(jù)類(lèi)型變量和）基礎(chǔ)數(shù)據(jù)類(lèi)型變量和字符串變量，如果值相等，字

16、符串變量，如果值相等，則計(jì)算出來(lái)的哈希值相等。則計(jì)算出來(lái)的哈希值相等。（2 2）對(duì)象即使內(nèi)部值相等，）對(duì)象即使內(nèi)部值相等，但是哈希值也可能不相等但是哈希值也可能不相等（3 3）不同對(duì)象的哈希值可）不同對(duì)象的哈希值可能相同能相同4.1 HashSet4.1 HashSet通過(guò)add方法向HashSet存入元素調(diào)用存儲(chǔ)對(duì)象的hashCode方法獲得對(duì)象的哈希值根據(jù)對(duì)象的哈希值計(jì)算對(duì)象的存儲(chǔ)位置該位置是否有對(duì)象存在舍棄該對(duì)象是將該對(duì)象存入集合調(diào)用eauals比較對(duì)象是否相等否是否算法過(guò)程算法過(guò)程參見(jiàn)案例參見(jiàn)案例1010和和11114.2 TreeSet4.2 TreeSet注意：注意：TreeSet

17、TreeSet內(nèi)部使用的算法是平衡排序二叉樹(shù)，使用的是中序遍歷，內(nèi)部使用的算法是平衡排序二叉樹(shù)，使用的是中序遍歷，即首先訪(fǎng)問(wèn)左子樹(shù)，然后遍歷根結(jié)點(diǎn)，最后遍歷右子樹(shù)1 1、二叉排序樹(shù)、二叉排序樹(shù)（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；（3）左、右子樹(shù)也分別為二叉排序樹(shù)；（4）沒(méi)有鍵值相等的節(jié)點(diǎn)。2 2、平衡二叉樹(shù)、平衡二叉樹(shù)平衡二叉樹(shù)又被稱(chēng)為AVL樹(shù)，具有以下性質(zhì)：（1）它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1（2）左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。4.2 TreeSet4.2 TreeSet例如數(shù)列13、8、17、17、1、11、15、25，使用平衡二叉樹(shù)存儲(chǔ)時(shí)，如下圖，同時(shí)存儲(chǔ)過(guò)程中，去掉重復(fù)元素。具體插入順序過(guò)于復(fù)雜，此處略去。TreeSet ts = new TreeSet(); ts.add(Jack); ts.add(Helena);ts.add(Helena);ts.add(Eve);Iterator it = ts.iterator(); while(it.hasNext() System.out.println(i