- 論壇徽章:
- 0
|
Java中容器分兩類，一種是單值的Collection，一種是儲存鍵-值對的Map
Collection
又分兩種，Set和List，區(qū)別在于Set是不可重復(fù)的，而List是可重復(fù)的
Set
常用有兩種：HashSet和TreeSet，其內(nèi)部實現(xiàn)是一個Map，它的元素就相當于Map中的Key，而Value是一個Object常量- private transient HashMap<E,Object> map;
- private static final Object PRESENT = new Object();
- public HashSet() {
- map = new HashMap<E,Object>();
- }
- private transient NavigableMap<E,Object> m;
- private static final Object PRESENT = new Object();
- public TreeSet() {
- this(new TreeMap<E,Object>());
- }
List
對Collection接口進行了簡單的擴充，你可以將任何對象放到放到一個List容器中，并在需要時從中取出。
常用的有ArrayList和LinkedList，都是有順序，可重復(fù)的集合類型
ArrayList：顧名思義，數(shù)據(jù)列表，其實就是封裝了一個數(shù)組，因此它的訪問速度極快- private transient Object[] elementData;
- private int size;
說到ArrayList不得不提下Arrays類和數(shù)組[]
ArrayList可以儲存不同類型的對象（雖然一般不推薦這樣做），而數(shù)組只能是同一類型
ArrayList可以動態(tài)增加長度，但效率不高，而數(shù)組只能是固定長度，卻十分高效。每當執(zhí)行add/insert等添加元素的方法，都會先檢查數(shù)組長度是否足夠，如果是，它就會以當前容量的3/2倍+1來重新構(gòu)建一個數(shù)組，將舊元素Copy到新數(shù)組中，然后丟棄舊數(shù)組，在這個臨界點的擴容操作，應(yīng)該來說是比較影響效率的。
ArrayList提供常用方法，add/get/indexOf/remove等，而相應(yīng)的Arrays沒有提供add和remove方法，查詢元素索引要先sort再binarySearch
ArrayList排序需外部方法Collections.sort(..),數(shù)組排序則使用Arrays.sort(..)，二者都可以使用自然順序（實現(xiàn)Comparable）或用Comparator指定
LinkedList：很顯然的是鏈表，內(nèi)部實現(xiàn)是帶頭結(jié)點的雙向鏈表，適合于在鏈表中間需要頻繁進行插入和刪除操作- private transient Entry<E> header = new Entry<E>(null, null, null);
- private transient int size = 0;
- private static class Entry<E> {
- E element;
- Entry<E> next;
- Entry<E> previous;
- //..
- }
是一種把鍵和值對象進行關(guān)聯(lián)的容器，類比Collection，可以這樣說：Collection對象中某個值的ID是它在容器中的索引值，而在Map中，某個值的ID是它對應(yīng)的鍵。這樣我們使用Map時就不用局限于int型的索引值，可以用任何類型的對象作索引。正是由于Key的索引特性，Map中不允許有同值的Key存在（前文講到Set內(nèi)部實現(xiàn)是Map中的Key的集合，所以Set的元素不能重復(fù)）。當然，Value是可以重復(fù)的，甚至可以是同一個Reference。Map在處理相同的Key時，將新值存入，舊值被替換并返回。
HashMap：采用Hash算法，以便快速查找某個元素。
將鍵的哈希值作為內(nèi)存索引依據(jù)，內(nèi)部實現(xiàn)是一個適當長度的鏈式數(shù)組，由Key的Hash值對應(yīng)數(shù)組下標，再間接對應(yīng)內(nèi)存，是一種比較高效的存取方式。Key的hashCode()相同的情況下，放在同一個單項鏈表結(jié)構(gòu)中。
一個HashMap中Key的類型應(yīng)該重寫hashCode()方法，保證在兩個對象equals為true時返回相同的值，否則在重復(fù)性檢查時會直接被當做不同的鍵，造成不可預(yù)期的后果。
Hash容器中判斷重復(fù)的方式：
先比較hash(key.hashCode())是否相同，hash(int)是一個內(nèi)部算法，具體細節(jié)不作討論
不同，則不重復(fù)
相同，則
比較兩個Key是否是同一引用
是，則重復(fù)
不是，再調(diào)用equals方法
返回true則重復(fù)
返回false則不重復(fù)
TreeMap：采用樹型儲存結(jié)構(gòu)按序存放，因此它便有一些擴展的方法，比如firstKey(),lastKey()等，你還可以從TreeMap中指定一個范圍以取得其子Map。
內(nèi)部實現(xiàn)是一顆二叉排序樹，其中序遍歷結(jié)果為遞增序列。所以要求他的Key必須是Comparable或者創(chuàng)建TreeMap的時候指定Comparator。
當Key實現(xiàn)Comparable<E>接口時，必須實現(xiàn)comparaTo(E e)方法，當使用外部比較器（Comparator<T>）時，需實現(xiàn)Comparator<T>的compare(T t1, T t2)方法
相關(guān)知識
泛型(Generic)
泛型允許Coding的時候可以定義一些可變的類型，但必須在使用前進行聲明具體是哪種類型- class testGeneric<T> {
- T t;
- testGeneric(T t) {
- this.t = t;
- }
- }
- class test {
- testGeneric<String> tgs = new testGeneric("Hi,Gineric!");
- testGeneric<Integer> tgi = new testGeneric(100);//AutoBoxing
- {
- System.out.println(tgs.t);//Output:Hi,Gineric!
- System.out.println(tgi.t);//AutoUnBoxing&Output:100
- }
- }
迭代器(Iterator)
提供一種方法訪問一個容器（container）對象中各個元素，而又不需暴露該對象的內(nèi)部細節(jié)。
對于遍歷一個容器中所有的元素，Iterator模式是首選的方式
Collection定義了Iterator<E> iterator()方法，子類都各自實現(xiàn)了該方法，我們直接調(diào)用即可
Map中雖沒有定義，我們可以利用map.entrySet()的iterator()方法-
- Iterator i = someMap.entrySet().iterator();
- while(i.hasNext()) {
- Map.Entry entry = (Map.Entry) i.next();
- Object key = i.getKey();
- Object value = i.getValue();
- //something TODO
- }
- Set<Map.Entry> entrySet = someMap.entrySet();
- for(Map.Entry entry : entrySet){
- Object key = entry.getKey();
- Object value = entry.getValue();
- //something TODO
- }
需要注意的是，調(diào)用Iterator的remove方法，刪除的是最后一次調(diào)用next()（or previous(),if possible）所返回的元素
如果進行迭代時用調(diào)用此方法之外的其他方式修改了該迭代器所指向的 collection，則迭代器的行為是不確定的。
也就是說，調(diào)用Iterator時，最好不要調(diào)用Collection的add/remove等方法
另：容器類的toString()方法也是通過調(diào)用iterator()方法來實現(xiàn)遍歷
對集合使用增強的for循環(huán)也是隱式地調(diào)用iterator()方法
還有Stack、Queue等結(jié)構(gòu)，操作簡單，不作贅述 |
|
免費注冊
發(fā)表于 2010-10-26 16:30
發(fā)表于 2010-10-28 08:41
