|
Array是數(shù)組,不在集合框架范疇之內(nèi),一旦選定了,它的容量大小就不能改變了,所以通常在編程中不選用數(shù)組來存放. 集合 : 集合對(duì)象：用于管理其他若干對(duì)象的對(duì)象 數(shù)組：長(zhǎng)度不可變 List: 有順序的，元素可以重復(fù) 遍歷：for 迭代 排序：Comparable Comparator Collections.sort() ArrayList：底層用數(shù)組實(shí)現(xiàn)的List 特點(diǎn)：查詢效率高，增刪效率低 輕量級(jí) 線程不安全 LinkedList：底層用雙向循環(huán)鏈表 實(shí)現(xiàn)的List 特點(diǎn)：查詢效率低，增刪效率高 Vector: 底層用數(shù)組實(shí)現(xiàn)List接口的另一個(gè)類 特點(diǎn)：重量級(jí)，占據(jù)更多的系統(tǒng)開銷 線程安全 Set：無順序的，元素不可重復(fù)（值不相同） 遍歷：迭代 排序：SortedSet HashSet：采用哈希算法來實(shí)現(xiàn)Set接口 唯一性保證：重復(fù)對(duì)象equals方法返回為true 重復(fù)對(duì)象hashCode方法返回相同的整數(shù) 不同對(duì)象 哈希碼 盡量保證不同（提高效率） SortedSet：對(duì)一個(gè)Set排序 TreeSet：在元素添加的同時(shí)，進(jìn)行排序。也要給出排序規(guī)則 唯一性保證：根據(jù)排序規(guī)則，compareTo方法返回為0，就可以認(rèn)定兩個(gè)對(duì)象中有一個(gè)是重復(fù)對(duì)象。 Map：元素是鍵值對(duì) key：唯一，不可重復(fù) value：可重復(fù) 遍歷：先迭代遍歷key的集合，再根據(jù)key得到value HashMap:輕量級(jí) 線程不安全 允許key或者value是null Hashtable：重量級(jí) 線程安全 不允許key或者value是null Properties：Hashtable的子類，key和value都是String SortedMap：元素自動(dòng)對(duì)key排序 TreeMap： 集合是指一個(gè)對(duì)象可以容納了多個(gè)對(duì)象（不是引用），這個(gè)集合對(duì)象主要用來管理維護(hù)一系列相似的對(duì)象。 集合接口類層次 : 位于package java.util.*; Collection ↑ |ˉˉˉˉˉˉ| Set List Map ↑ ↑ | | SortedSet SortedMap 1) Set: 集合類中不允許有重復(fù)對(duì)象; 2) SortedSet: 和Set接口同，但元素按升序排列; 3) List: 元素加載和移出時(shí)按照順序，可以保存重復(fù)對(duì)象。 4) Map: (key-value對(duì))存儲(chǔ)了唯一關(guān)鍵字辨識(shí)和對(duì)應(yīng)的值。 5) SortedMap: 和Map類同，但對(duì)象按他們關(guān)鍵字的升序排列。 集合類層次 : （注：JAVA1.5對(duì)JAVA1.4的最大改進(jìn)就是增加了對(duì)范型的支持） Collection ↑ |ˉˉˉˉˉˉ| HashSet LinkedList Hashtable (Set) Vector, ArrayList Hashmap (List) (Map) ↑ ↑ | | TreeSet TreeMap (SortedSet) (SortedMap) Collection接口的方法： add(Object o) addAll(Collection c) contains(Object o) containsAll(Collection c) remove(Object o) removeAll(Collection c) clear() equals(Object o) isEmpty() iterator() size() toArray() toArray(Object[] o) 五個(gè)最常用的集合類之間的區(qū)別和聯(lián)系: 1．ArrayList: 元素單個(gè)，效率高，多用于查詢 2．Vector: 元素單個(gè)，線程安全，多用于查詢 3．LinkedList:元素單個(gè)，多用于插入和刪除 4．HashMap: 元素成對(duì)，元素可為空 5．HashTable: 元素成對(duì)，線程安全，元素不可為空 ArrayList 底層是Object數(shù)組，所以ArrayList具有數(shù)組的查詢速度快的優(yōu)點(diǎn)以及增刪速度慢的缺點(diǎn)。 而在LinkedList的底層是一種雙向循環(huán)鏈表。在此鏈表上每一個(gè)數(shù)據(jù)節(jié)點(diǎn)都由三部分組成：前指針（指向前面的節(jié)點(diǎn)的位置），數(shù)據(jù)，后指針（指向后面的節(jié)點(diǎn)的位置）。最后一個(gè)節(jié)點(diǎn)的后指針指向第一個(gè)節(jié)點(diǎn)的前指針，形成一個(gè)循環(huán)。 雙向循環(huán)鏈表的查詢效率低但是增刪效率高。 ArrayList和LinkedList在用法上沒有區(qū)別，但是在功能上還是有區(qū)別的。 LinkedList 經(jīng)常用在增刪操作較多而查詢操作很少的情況下：隊(duì)列和堆棧。 隊(duì)列：先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。 棧：后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。 注意：使用棧的時(shí)候一定不能提供方法讓不是最后一個(gè)元素的元素獲得出棧的機(jī)會(huì)。 Vector （與ArrayList相似，區(qū)別是Vector是重量級(jí)的組件，使用使消耗的資源比較多。） 結(jié)論：在考慮并發(fā)的情況下用Vector（保證線程的安全）。 在不考慮并發(fā)的情況下用ArrayList（不能保證線程的安全）。 java.util.stack（stack即為堆棧）的父類為Vector?？墒莝tack的父類是最不應(yīng)該為Vector的。因?yàn)閂ector的底層是數(shù)組，且Vector有g(shù)et方法（意味著它可能訪問到并不屬于最后一個(gè)位置元素的其他元素，很不安全）。 對(duì)于堆棧和隊(duì)列只能用push類和get類。 Stack類以后不要輕易使用。 實(shí)現(xiàn)棧一定要用LinkedList。 （在JAVA1.5中，collection有queue來實(shí)現(xiàn)隊(duì)列。） Set-HashSet實(shí)現(xiàn)類： 遍歷一個(gè)Set的方法只有一個(gè)：迭代器（interator）。 HashSet中元素是無序的（這個(gè)無序指的是數(shù)據(jù)的添加順序和后來的排列順序不同），而且元素不可重復(fù)。 在Object中除了有finalize()，toString()，equals()，還有hashCode()。 HashSet底層用的也是數(shù)組。 當(dāng)向數(shù)組中利用add(Object o)添加對(duì)象的時(shí)候，系統(tǒng)先找對(duì)象的hashCode： int hc=o.hashCode(); 返回的hashCode為整數(shù)值。 Int I=hc%n;（n為數(shù)組的長(zhǎng)度），取得余數(shù)后，利用余數(shù)向數(shù)組中相應(yīng)的位置添加數(shù)據(jù)，以n為6為例，如果I=0則放在數(shù)組a[0]位置，如果I=1,則 放在數(shù)組a[1]位置。如果equals()返回的值為true，則說明數(shù)據(jù)重復(fù)。如果equals()返回的值為false，則再找其他的位置進(jìn)行比 較。這樣的機(jī)制就導(dǎo)致兩個(gè)相同的對(duì)象有可能重復(fù)地添加到數(shù)組中，因?yàn)樗麄兊膆ashCode不同。 如果我們能夠使兩個(gè)相同的對(duì)象具有相同hashcode，才能在equals()返回為真。 在實(shí)例中，定義student對(duì)象時(shí)覆蓋它的hashcode。 因?yàn)镾tring類是自動(dòng)覆蓋的，所以當(dāng)比較String類的對(duì)象的時(shí)候，就不會(huì)出現(xiàn)有兩個(gè)相同的string對(duì)象的情況。 現(xiàn)在，在大部分的JDK中，都已經(jīng)要求覆蓋了hashCode。 結(jié)論：如將自定義類用hashSet來添加對(duì)象，一定要覆蓋hashcode()和equals()，覆蓋的原則是保證當(dāng)兩個(gè)對(duì)象hashcode返回相同的整數(shù)，而且equals()返回值為True。 如果偷懶，沒有設(shè)定equals()，就會(huì)造成返回hashCode雖然結(jié)果相同，但在程序執(zhí)行的過程中會(huì)多次地調(diào)用equals()，從而影響程序執(zhí)行的效率。 我們要保證相同對(duì)象的返回的hashCode一定相同，也要保證不相同的對(duì)象的hashCode盡可能不同（因?yàn)閿?shù)組的邊界性，hashCode還是可能相同的）。 例子： public int hashCode(){ return name.hashcode()+age; } 這個(gè)例子保證了相同姓名和年齡的記錄返回的hashCode是相同的。 使用hashSet的優(yōu)點(diǎn)： hashSet的底層是數(shù)組，其查詢效率非常高。而且在增加和刪除的時(shí)候由于運(yùn)用的hashCode的比較開確定添加元素的位置，所以不存在元素的偏移，所以效率也非常高。因?yàn)閔ashSet查詢和刪除和增加元素的效率都非常高。 但是hashSet增刪的高效率是通過花費(fèi)大量的空間換來的：因?yàn)榭臻g越大，取余數(shù)相同的情況就越小。HashSet這種算法會(huì)建立許多無用的空間。 使用hashSet類時(shí)要注意，如果發(fā)生沖突，就會(huì)出現(xiàn)遍歷整個(gè)數(shù)組的情況，這樣就使得效率非常的低。 1.1.4. 比較 Collections類（工具類―――全是static 方法） Public static int binarySearch(List list,Object key) Public static void Sort(List list,Comparator com) Public static void sort(List list) 方法一： Comparator接口 Int compare(Object a,Object b) Boolean equals(Object o) 例子： import java.util.*; public class Test { public static void main(String[] arg) { ArrayList al = new ArrayList(); Person p1 = new Person("dudi"); Person p2 = new Person("cony"); Person p3 = new Person("aihao"); al.add(p1); al.add(p2); al.add(p3); Collections.sort(al,p1); for(Iterator it = al.iterator();it.hasNext();){ Person p = (Person)it.next(); System.out.println(p.name); } } } class Person implements java.util.Comparator { public String name; public Person(String name){ this.name = name; } public int compare(Object a,Object b){ if(a instanceof Person&&b instanceof Person){ Person pa = (Person)a; Person pb = (Person)b; return pa.name.compareTo(pb.name); } return 0; } public boolean equals(Object a){return true;} } 方法二 Java.lang.Comparable Public int compareTo(Object o) Class Person implements java.lang.Comparable{ Public int compareTo(Object o){ Comparable c1=(Comparable)this; Comparable c2=(Comparable)o; Return c1.name.compareTo(c2.name ); } } ………………………………. } |
|
|
