?

java.util包中三個重要的接口及特點：List（列表）、Set（保證集合中元素唯一）、Map（維護多個key-value鍵值對，保證key唯一）。其不同子類的實現各有差異，如是否同步（線程安全）、是否有序。

常用類繼承樹：

以下結合源碼講解常用類實現原理及相互之間的差異。

Collection （所有集合類的接口）
List、Set都繼承自Collection接口，查看JDK API，操作集合常用的方法大部分在該接口中定義了。

?

Collections （操作集合的工具類）
對于集合類的操作不得不提到工具類Collections，它提供了許多方便的方法，如求兩個集合的差集、并集、拷貝、排序等等。
由于大部分的集合接口實現類都是不同步的，可以使用Collections.synchronized*方法創建同步的集合類對象。
如創建一個同步的List：
List synList = Collections.synchronizedList(new ArrayList());
其實現原理就是重新封裝new出來的對象，操作對象時用關鍵字synchronized同步。看源碼很容易理解。
Collections部分源碼：

static class SynchronizedCollection<e> implements Collection<e>, Serializable {final Collection<e> c; // Backing Collectionfinal Object mutex; // Object on which to synchronizeSynchronizedCollection(Collection<e> c) {if (c==null)throw new NullPointerException();this.c = c;mutex = this;}//...public boolean add(E e) {//操作集合時簡單調用原本的ArrayList對象，只是做了同步synchronized (mutex) {return c.add(e);}}//... }

List （列表）

ArrayList、Vector是線性表，使用Object數組作為容器去存儲數據的，添加了很多方法維護這個數組，使其容量可以動態增長，極大地提升了開發效率。它們明顯的區別是ArrayList是非同步的，Vector是同步的。不用考慮多線程時應使用ArrayList來提升效率。
ArrayList、Vector 部分源碼：

public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!//可以看出添加的對象放到elementData數組中去了elementData[size++] = e;return true; } //ArrayList.remove public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)//移除元素時數組產生的空位由System.arraycopy方法將其后的所有元素往前移一位，System.arraycopy調用虛擬機提供的本地方法來提升效率System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // Let gc do its workreturn oldValue; }//Vector add方法上多了synchronized關鍵字 public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true; }

LinkedList是鏈表，略懂數據結構就知道其實現原理了。鏈表隨機位置插入、刪除數據時比線性表快，遍歷比線性表慢。
雙向鏈表原理圖：

LinkedList部分源碼：

public class LinkedList<e> extends AbstractSequentialList<e> implements List<e>, Deque<e>, Cloneable, java.io.Serializable {//頭尾節點transient Node<e> first;transient Node<e> last; } //節點類private static class Node<e> {//節點存儲的數據E item;Node<e> next;Node<e> prev;Node(Node<e> prev, E element, Node<e> next) {this.item = element;this.next = next;this.prev = prev;} }

由此可根據實際情況來選擇使用ArrayList（非同步、非頻繁刪除時選擇）、Vector（需同步時選擇）、LinkedList（頻繁在任意位置插入、刪除時選擇）。

Map（存儲鍵值對，key唯一）

HashMap結構的實現原理是將put進來的key-value封裝成一個Entry對象存儲到一個Entry數組中，位置（數組下標）由key的哈希值與數組長度計算而來。如果數組當前下標已有值，則將數組當前下標的值指向新添加的Entry對象。
有點暈，看圖吧：

?

看完圖再看源碼，非常清晰，都不需要注釋。

public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {transient Entry<k,v>[] table;public V put(K key, V value) {if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);//遍歷當前下標的Entry對象鏈，如果key已存在則替換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;}}addEntry(hash, key, value, i);return null;} } static class Entry<k,v> implements Map.Entry<k,v> {final K key;V value;Entry<k,v> next;int hash; }

TreeMap是由Entry對象為節點組成的一顆紅黑樹，put到TreeMap的數據默認按key的自然順序排序，new TreeMap時傳入Comparator自定義排序。紅黑樹網上很多資料，我講不清，這里就不介紹了。

Set（保證容器內元素唯一性）
之所以先講Map是因為Set結構其實就是維護一個Map來存儲數據的，利用Map結構key值唯一性。
HashSet部分源碼：

public class HashSet<e> extends AbstractSet<e> implements Set<e>, Cloneable, java.io.Serializable { //無意義對象來作為Map的value private static final Object PRESENT = new Object();public boolean add(E e) {return map.put(e, PRESENT)==null;} }

HashMap 支持key=null 但是 Hashtable 不支持 key =null

HashMap和Hashtable的區別

HashMap和Hashtable都實現了Map接口，但決定用哪一個之前先要弄清楚它們之間的分別。主要的區別有：線程安全性，同步(synchronization)，以及速度。

HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。

HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。

另一個區別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當有其它線程改變了HashMap的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區別。

由于Hashtable是線程安全的也是synchronized，所以在單線程環境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。

HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

要注意的一些重要術語：

1) sychronized意味著在一次僅有一個線程能夠更改Hashtable。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。

2) Fail-safe和iterator迭代器相關。如果某個集合對象創建了Iterator或者ListIterator，然后其它的線程試圖“結構上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因為這并沒有從“結構上”更改集合。但是假如已經從結構上進行了更改，再調用set()方法，將會拋出IllegalArgumentException異常。

3) 結構上的更改指的是刪除或者插入一個元素，這樣會影響到map的結構。

我們能否讓HashMap同步？

HashMap可以通過下面的語句進行同步：
Map m = Collections.synchronizeMap(hashMap);

結論

Hashtable和HashMap有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java 5或以上的話，請使用ConcurrentHashMap吧。

HashSet、TreeSet分別默認維護一個HashMap、TreeMap。

---

匯總與網絡，供自己學習使用。

總結

以上是生活随笔為你收集整理的JAVA常用的数据结构集合框架总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。