java中的集合類有以下所屬關系:
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
Collection接口
Collection是最基本的集合接口,一個Collection代表一組Object,即Collection的元素(Elements)。一些 Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類,Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
所有實現Collection接口的類都必須提供兩個標準的構造函數:無參數的構造函數用于創建一個空的Collection,有一個 Collection參數的構造函數用于創建一個新的Collection,這個新的Collection與傳入的Collection有相同的元素。后 一個構造函數允許用戶復制一個Collection。
如何遍歷Collection中的每一個元素?不論Collection的實際類型如何,它都支持一個iterator()的方法,該方法返回一個迭代子,使用該迭代子即可逐一訪問Collection中每一個元素。典型的用法如下:
Iterator it = collection.iterator(); // 獲得一個迭代子 while(it.hasNext()) { Object obj = it.next(); // 得到下一個元素 }
由Collection接口派生的兩個接口是List和Set。
所謂框架就是一個類庫的集合。集合框架就是一個用來表示和操作集合的統一的架構, 包含了實現集合的接口與類。
List接口
List是有序的Collection,使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引(元素在List中的位置,類似于數組下標)來訪問List中的元素,這類似于Java的數組。
和下面要提到的Set不同,List允許有相同的元素。
除了具有Collection接口必備的iterator()方法外,List還提供一個listIterator()方法,返回一個 ListIterator接口,和標準的Iterator接口相比,ListIterator多了一些add()之類的方法,允許添加,刪除,設定元素, 還能向前或向后遍歷。
實現List接口的常用類有LinkedList,ArrayList,Vector和Stack。
LinkedList類
LinkedList實現了List接口,允許null元素。此外LinkedList提供額外的get,remove,insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧(stack),隊列(queue)或雙向隊列(deque)。
注意LinkedList沒有同步方法。如果多個線程同時訪問一個List,則必須自己實現訪問同步。
一種解決方法是在創建List時構造一個同步的List:
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList類
ArrayList實現了可變大小的數組。它允許所有元素,包括null。ArrayList沒有同步。
size,isEmpty,get,set方法運行時間為常數。但是add方法開銷為分攤的常數,添加n個元素需要O(n)的時間。其他的方法運行時間為線性。
每個ArrayList實例都有一個容量(Capacity),即用于存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加,但是增長算法 并沒有定義。當需要插入大量元素時,在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率。
和LinkedList一樣,ArrayList也是非同步的(unsynchronized)。
Vector類
Vector非常類似ArrayList,但是Vector是同步的。由Vector創建的Iterator,雖然和 ArrayList創建的Iterator是同一接口,但是,因為Vector是同步的,當一個Iterator被創建而且正在被使用,另一個線程改變了 Vector的狀態(例如,添加或刪除了一些元素),這時調用Iterator的方法時將拋出 ConcurrentModificationException,因此必須捕獲該異常。
Stack 類
Stack繼承自Vector,實現一個后進先出的堆棧。Stack提供5個額外的方法使得Vector得以被當作堆棧使用?;镜膒ush和pop 方法,還有peek方法得到棧頂的元素,empty方法測試堆棧是否為空,search方法檢測一個元素在堆棧中的位置。Stack剛創建后是空棧。
Set接口
Set是一種不包含重復的元素且無序的Collection,即任意的兩個元素e1和e2都有e1.equals(e2)=false,Set最多有一個null元素。
很明顯,Set的構造函數有一個約束條件,傳入的Collection參數不能包含重復的元素。
請注意:必須小心操作可變對象(Mutable Object)。如果一個Set中的可變元素改變了自身狀態導致Object.equals(Object)=true將導致一些問題。
Map接口
請注意,Map沒有繼承Collection接口,Map提供key到value的映射。一個Map中不能包含相同的key,每個key只能映射一個 value。Map接口提供3種集合的視圖,Map的內容可以被當作一組key集合,一組value集合,或者一組key-value映射。
Hashtable類
Hashtable繼承Map接口,實現一個key-value映射的哈希表。任何非空(non-null)的對象都可作為key或者value。
添加數據使用put(key, value),取出數據使用get(key),這兩個基本操作的時間開銷為常數。
Hashtable通過initial capacity和load factor兩個參數調整性能。通常缺省的load factor 0.75較好地實現了時間和空間的均衡。增大load factor可以節省空間但相應的查找時間將增大,這會影響像get和put這樣的操作。
使用Hashtable的簡單示例如下,將1,2,3放到Hashtable中,他們的key分別是”one”,”two”,”three”:
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一個數,比如2,用相應的key:
Integer n = (Integer)numbers.get(“two”);
System.out.PRintln(“two = ” + n);
由于作為key的對象將通過計算其散列函數來確定與之對應的value的位置,因此任何作為key的對象都必須實現hashCode和equals方 法。hashCode和equals方法繼承自根類Object,如果你用自定義的類當作key的話,要相當小心,按照散列函數的定義,如果兩個對象相 同,即obj1.equals(obj2)=true,則它們的hashCode必須相同,但如果兩個對象不同,則它們的hashCode不一定不同,如 果兩個不同對象的hashCode相同,這種現象稱為沖突,沖突會導致操作哈希表的時間開銷增大,所以盡量定義好的hashCode()方法,能加快哈希 表的操作。
如果相同的對象有不同的hashCode,對哈希表的操作會出現意想不到的結果(期待的get方法返回null),要避免這種問題,只需要牢記一條:要同時復寫equals方法和hashCode方法,而不要只寫其中一個。
Hashtable是同步的。
HashMap類
HashMap和Hashtable類似,不同之處在于HashMap是非同步的,并且允許null,即null value和null key。,但是將HashMap視為Collection時(values()方法可返回Collection),其迭代子操作時間開銷和HashMap 的容量成比例。因此,如果迭代操作的性能相當重要的話,不要將HashMap的初始化容量設得過高,或者load factor過低。
public static void main(String[] args) { Map map = new HashMap(); map.put("What", "chenyz"); map.put("You", "chenyz"); map.put("Don't", "chenyz"); map.put("Know", "chenyz"); map.put("About", "chenyz"); map.put("Geo", "chenyz"); map.put("APIs", "chenyz"); map.put("Can't", "chenyz"); map.put("Hurt", "chenyz"); map.put("you", "chenyz"); map.put("google", "chenyz"); map.put("map", "chenyz"); map.put("hello", "chenyz"); }
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{ int threshold; final float loadFactor; transient Entry[] table; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int DEFAULT_INITIAL_CAPACITY = 16; public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); System.out.println(key+"-->hash值:"+i);//這就是剛才程序打印出來的key對應hash值 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordaccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); }
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
public K next() { return nextEntry().getKey(); } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; }
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
WeakHashMap類
WeakHashMap是一種改進的HashMap,它對key實行“弱引用”,如果一個key不再被外部所引用,那么該key可以被GC回收。
總結
如果涉及到堆棧,隊列等操作,應該考慮用List,對于需要快速插入,刪除元素,應該使用LinkedList,如果需要快速隨機訪問元素,應該使用ArrayList。
如果程序在單線程環境中,或者訪問僅僅在一個線程中進行,考慮非同步的類,其效率較高,如果多個線程可能同時操作一個類,應該使用同步的類。
要特別注意對哈希表的操作,作為key的對象要正確復寫equals和hashCode方法。
盡量返回接口而非實際的類型,如返回List而非ArrayList,這樣如果以后需要將ArrayList換成LinkedList時,客戶端代碼不用改變。這就是針對抽象編程。
同步性
Vector是同步的。這個類中的一些方法保證了Vector中的對象是線程安全的。而ArrayList則是異步的,因此ArrayList中的對象并 不是線程安全的。因為同步的要求會影響執行的效率,所以如果你不需要線程安全的集合那么使用ArrayList是一個很好的選擇,這樣可以避免由于同步帶 來的不必要的性能開銷。
數據增長
從內部實現機制來講ArrayList和Vector都是使用數組(Array)來控制集合中的對象。當你向這兩種類型中增加元素的時候,如果元素的數目 超出了內部數組目前的長度它們都需要擴展內部數組的長度,Vector缺省情況下自動增長原來一倍的數組長度,ArrayList是原來的50%,所以最 后你獲得的這個集合所占的空間總是比你實際需要的要大。所以如果你要在集合中保存大量的數據那么使用Vector有一些優勢,因為你可以通過設置集合的初 始化大小來避免不必要的資源開銷。
使用模式
在ArrayList和Vector中,從一個指定的位置(通過索引)查找數據或是在集合的末尾增加、移除一個元素所花費的時間是一樣的,這個時間我們用 O(1)表示。但是,如果在集合的其他位置增加或移除元素那么花費的時間會呈線形增長:O(n-i),其中n代表集合中元素的個數,i代表元素增加或移除 元素的索引位置。為什么會這樣呢?以為在進行上述操作的時候集合中第i和第i個元素之后的所有元素都要執行位移的操作。這一切意味著什么呢?
這意味著,你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以。如果是其他操作,你最好選擇其他 的集合操作類。比如,LinkList集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的?O(1),但它在索引一個元素的使用缺比較慢 -O(i),其中i是索引的位置.使用ArrayList也很容易,因為你可以簡單的使用索引來代替創建iterator對象的操作。LinkList也 會為每個插入的元素創建對象,所有你要明白它也會帶來額外的開銷。
最后,在《Practical Java》一書中Peter Haggar建議使用一個簡單的數組(Array)來代替Vector或ArrayList。尤其是對于執行效率要求高的程序更應如此。因為使用數組 (Array)避免了同步、額外的方法調用和不必要的重新分配空間的操作。
相互區別
Vector和ArrayList
1,vector是線程同步的,所以它也是線程安全的,而arraylist是線程異步的,是不安全的。如果不考慮到線程的安全因素,一般用
arraylist效率比較高。
2,如果集合中的元素的數目大于目前集合數組的長度時,vector增長率為目前數組長度的100%,而arraylist增長率為目前數組長度
的50%.如過在集合中使用數據量比較大的數據,用vector有一定的優勢。
3,如果查找一個指定位置的數據,vector和arraylist使用的時間是相同的,都是0(1),這個時候使用vector和arraylist都可以。而
如果移動一個指定位置的數據花費的時間為0(n-i)n為總長度,這個時候就應該考慮到使用linklist,因為它移動一個指定位置的數據
所花費的時間為0(1),而查詢一個指定位置的數據時花費的時間為0(i)。
ArrayList 和Vector是采用數組方式存儲數據,此數組元素數大于實際存儲的數據以便增加和插入元素,都允許直接序號索引元素,但是插入數據要設計到數組元素移動 等內存操作,所以索引數據快插入數據慢,Vector由于使用了synchronized方法(線程安全)所以性能上比ArrayList要 差,LinkedList使用雙向鏈表實現存儲,按序號索引數據需要進行向前或向后遍歷,但是插入數據時只需要記錄本項的前后項即可,所以插入數度較快!
arraylist和linkedlist
1.ArrayList是實現了基于動態數組的數據結構,LinkedList基于鏈表的數據結構。
2.對于隨機訪問get和set,ArrayList覺得優于LinkedList,因為LinkedList要移動指針。
3.對于新增和刪除操作add和remove,LinedList比較占優勢,因為ArrayList要移動數據。
這一點要看實際情況的。若只對單條數據插入或刪除,ArrayList的速度反而優于LinkedList。但若是批量隨機的插入刪除數 據,LinkedList的速度大大優于ArrayList. 因為ArrayList每插入一條數據,要移動插入點及之后的所有數據。
HashMap與TreeMap
1、HashMap通過hashcode對其內容進行快速查找,而TreeMap中所有的元素都保持著某種固定的順序,如果你需要得到一個有序的結果你就應該使用TreeMap(HashMap中元素的排列順序是不固定的)。
2、在Map 中插入、刪除和定位元素,HashMap 是最好的選擇。但如果您要按自然順序或自定義順序遍歷鍵,那么TreeMap會更好。使用HashMap要求添加的鍵類明確定義了hashCode()和 equals()的實現?! ∵@個TreeMap沒有調優選項,因為該樹總處于平衡狀態。
結過研究,在原作者的基礎上我還發現了一點,二樹map一樣,但順序不一樣,導致hashCode()不一樣。
同樣做測試:
在hashMap中,同樣的值的map,順序不同,equals時,false;
而在treeMap中,同樣的值的map,順序不同,equals時,true,說明,treeMap在equals()時是整理了順序了的。
hashtable與hashmap
一.歷史原因:Hashtable是基于陳舊的Dictionary類的,HashMap是Java 1.2引進的Map接口的一個實現
二.同步性:Hashtable是線程安全的,也就是說是同步的,而HashMap是線程序不安全的,不是同步的
三.值:只有HashMap可以讓你將空值作為一個表的條目的key或value
新聞熱點
疑難解答