Java容器類型使用總結
最近抽空把java.lang下面常用的那些容器類型（數據結構）復習了一下，這些東西是基礎，平時使用的時候也可以很容易查得到，有些方法大概知 道，但是總是弄混，如果可以記住那些重要方法，并且能夠熟練使用的話，還是可以讓編碼過程變得容易很多。另外一個是實現機制，對于常用數據結構的實現機 制，應該說是必須要熟知的。
另外，并發容器我之前整理過，放在這篇文章里。
Queue
- add和offer的區別在于達到上限時add拋出異常，offer返回false；
- remove和poll的區別在于，隊列為空時前者拋出異常，后者返回空；
- element和peek都返回隊列頭部元素，但是前者失敗不拋出異常，后者返回空。 </ol>
boolean add(E e); boolean offer(E e);E remove(); E poll();
E element(); E peek();</pre>
PriorityQueue，內部實現是一個Object[] queue承載的堆。
Deque，雙端隊列（double-ended queue），在Queue基礎上，增加了這樣幾個方法：
void addFirst(E e); void addLast(E e);boolean offerFirst(E e); boolean offerLast(E e);
E removeFirst(); E removeLast();
E pollFirst(); E pollLast();
E getFirst(); E getLast();
E peekFirst(); E peekLast();
boolean removeFirstOccurrence(Object o); boolean removeLastOccurrence(Object o);</pre>
ArrayDequeue：數組實現，擴容策略是容量翻倍。
List
boolean add(E e); boolean remove(Object o); E get(int index); E set(int index, E element); void add(int index, E element); E remove(int index);ArrayList，擴容策略是(oldCapacity * 3)/2 + 1。
LinkedList，它除了實現自List接口外，還實現了Deque接口。
Vector，實現自List接口，內部實現是個數組，線程安全，擴容策略是(capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2)。
Stack是Vector的子類，增加了一些棧的方法：
E push(E item) E pop() E peek() boolean empty()Map
boolean containsKey(Object key); boolean containsValue(Object value);V get(Object key); V put(K key, V value); V remove(Object key);
Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet();</pre>
SotedMap接口，key是有序的map：
SortedMap<K, V> subMap(K paramK1, K paramK2); SortedMap<K, V> headMap(K paramK); SortedMap<K, V> tailMap(K paramK);K firstKey(); K lastKey();</pre>
子接口NavigableMap，提供了一些根據某個key尋找它前面或者后面的key的方法。其中floorKey/celingKey表示的關系是小于等于/大于等于，lower/higher表示的關系是嚴格的小于/大于：
Map.Entry<K,V> floorEntry(K key) K floorKey(K key) Map.Entry<K,V> ceilingEntry(K key) K ceilingKey(K key)Map.Entry<K,V> lowerEntry(K key) K lowerKey(K key) Map.Entry<K,V> higherEntry(K key) K higherKey(K key)</pre>
TreeMap是NavigableMap的直接實現子類，內部實現是一個紅黑樹。
EnumMap，結構是<K extends Enum<K>, V>，內部是通過一個K[] keyUniverse和一個Object[] vals來實現的。
HashMap，內部是數組+鏈表實現的，達到threshold = capacity * loadFactor時，擴容策略為：numKeysToBeAdded / loadFactor + 1。
HashTable，實現自Dictionary和Map，方法都是 線程安全的。HashTable的put方法，value不可以為空，這是它和HashMap的一個不同；再有二者找桶的hash方法不同；最后則是 threshold計算邏輯相同，但它的擴容策略不同：oldCapacity * 2 + 1。HashTable、HashMap和HashSet經常被放到一起比較。
Properties，是HashTable的子類，方法線程安全。
IdentityHashMap，比較key不是使用equals來比較，而是使用“==”來比較，只要地址不等（即不是同一個對象）即可共存，也就是說，key是可以重復的。
LinkedHashMap，在HashMap的基礎上，又單獨維護 了一個雙向循環鏈表。有一個重要參數是accessOrder，accessOrder為true時，每次調用get方法訪問行為發生后，會把最近訪問的 對象移動到頭部，而超出容量移除對象時，是從尾部開始的，利用它并且覆寫boolean removeEldestEntry方法可以實現一個LRU的隊列。
WeakHashMap，但是key是weak引用，在不被使用時自 動清除，擴容策略：tab.length * 2。原理上看：Entry<K,V> extends WeakReference<K> implements Map.Entry<K,V>，因此entry是弱引用的實現類，關鍵方法是expungeStaleEntries，它在對這個map各種 操作的時候都會被調用到，而這個方法里面也是靠監聽key的ReferenceQueue這個隊列的狀態來確定是否真的沒有對象引用了。
Set
boolean contains(Object o); boolean add(E e); boolean remove(Object o);SortedSet，接口方法和SortedMap類似：
SortedSet<E> subSet(E fromElement, E toElement); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement);E first(); E last();</pre>
相應地，NavigableSet和NavigableMap類似，方法就不列出了。
TreeSet則和TreeMap類似，其實內部實現就是一個TreeMap。
HashSet，尤其注意的是，有兩種實現，當構造方法參數小于3個時，內部使用HashMap，否則，使用LinkedHashMap。
RegularEnumSet和JumboEnumSet，前者是普通的枚舉set（用位移來表示各種組合的可能，達到空間占用最小，最大不能超過64個枚舉值），后者適合數量較大的枚舉set（老老實實地使用對象數組）。
LinkedHashSet，其實和LinkedHashMap是一個東西。
BitSet，叫set但是沒有實現set的接口。用比特位來存放某個數是否存在，比如僅僅一個long，64位，就可以存放0~63的數，內部實際的數據類型是long[]。
void flip(int bitIndex); void flip(int fromIndex, int toIndex);void set(int bitIndex); void set(int fromIndex, int toIndex, boolean value);
void clear(int bitIndex);
int length(); int size();</pre>
其中size方法返回實際使用了的比特位數目；length方法返回邏輯意義上的長度（比如表示的數里面最大是80，那么加上0，它的邏輯意義上的長度就是81）。
擴容策略：Math.max(2 * words.length, wordsRequired)。
Dictionary
Enumeration<K> keys(); Enumeration<V> elements();V get(Object key); V put(K key, V value); V remove(Object key);</pre>
已經被廢棄了，用Map來實現相同功能。
最后這張圖來自這個網站，對于從宏觀上把握這些容器類型實在是太有幫助了：
來源：四火的嘮叨
