Java 容器知識整理

一圖勝千言

其中用綠色填充的為常用的類，需重點掌握。

接口簡介

Java容器的最上層都是以接口的形式出現,具體實現由子接口完成。舉個栗子，常見的如

Map<Integer,String> map = new HashMap<Integer, String>();

Iterator

迭代器,用于遍歷容器，JDK源碼如下：

package java.util;
import java.util.function.Consumer;
public interface Iterator<E> {
  boolean hasNext();
  E next();
  default void remove() {
    throw new UnsupportedOperationException("remove");
  }
  default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (hasNext())
      action.accept(next());
  }
}

Iterator iter = l.iterator();
  while(iter.hasNext()){
   String str = (String) iter.next();
   System.out.println(str);
  }

Collection

存放獨立元素的序列。Collection下又有三個子接口，List,Set,Queue。

List

一個有序的Collection（也稱序列），元素可以重復。確切的講，列表通常允許滿足 e1.equals(e2) 的元素對 e1 和 e2，并且如果列表本身允許 null 元素的話，通常它們允許多個 null 元素。實現List的有：ArrayList、LinkedList、Vector、Stack等。

Set

一個不包括重復元素（包括可變對象）的Collection，是一種無序的集合。Set不包含滿 a.equals(b) 的元素對a和b，并且最多有一個null。實現Set的接口有：EnumSet、HashSet、TreeSet等。

Queue

一種隊列則是雙端隊列，支持在頭、尾兩端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、 LinkedList。另一種是阻塞式隊列，隊列滿了以后再插入元素則會拋出異常，主要包括ArrayBlockQueue、 PriorityBlockingQueue、LinkedBlockingQueue。

Map

存放key-value型的元素對。

常見容器與工具類

ArrayList

數據結構采用的是鏈表，優勢是刪除和添加的效率很高，但隨機訪問元素時效率較ArrayList類低。

LinkedList

數據結構采用的是線性表，優勢是訪問和查詢十分方便，但添加和刪除的時候效率很低。

HashSet

數據結構采用的是散列表，主要是設計用來做高性能集運算的，例如對兩個集合求交集、并集、差集等。集合中包含一組不重復出現且無特性順序的元素。其值是不可重復與無序的。

TreeSet

數據結構使用的是紅黑樹，性能上低于HashSet，用于排序。

HashMap

數據結構使用的是散列表，是最常用的是Collection

TreeMap

與TreeSet同理，用于排序。

Arrays、Collections

這兩者可以理解成工具類，提供一些處理容器類靜態方法，比如二分查找，排序等等。

常見的容器比較

ArrayList VS Vector

• ArrayList在內存不夠時默認是擴展50% + 1個，Vector是默認擴展1倍。
• Vector提供indexOf(obj, start)接口，ArrayList沒有。
• Vector屬于線程安全級別的，但是大多數情況下不使用Vector，因為線程安全需要更大的系統開銷。

沒特殊需求，一般用ArrayList

ArrayList VS LinkedList

• 因為Array是基于索引(index)的數據結構，它使用索引在數組中搜索和讀取數據是很快的。Array獲取數據的時間復雜度是O(1),但是要刪除數據卻是開銷很大的，因為這需要重排數組中的所有數據。

• 相對于ArrayList，LinkedList插入是更快的。因為 LinkedList不像ArrayList一樣，不需要改變數組的大小，也不需要在數組裝滿的時候要將所有的數據重新裝入一個新的數組，這是 ArrayList最壞的一種情況，時間復雜度是O(n)，而LinkedList中插入或刪除的時間復雜度僅為O(1)。ArrayList在插入數據 時還需要更新索引（除了插入數組的尾部）。

• 類似于插入數據，刪除數據時，LinkedList也優于ArrayList。

• LinkedList需要更多的內存，因為ArrayList的每個索引的位置是實際的數據，而LinkedList中的每個節點中存儲的是實際的數據和前后節點的位置。

HashTable VS HashMap

• 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中的元素次序是不變的。