Java 集合
集合是對象的容器，定義了多個對象進行操作的常用方法，可實作數組的功能。
Java集合類庫所處位置：java.util.*。
與現代的資料結構類庫的常見做法一樣，Java集合類庫也将接口與實作分離開。
集合和數組的差別：
1.數組長度固定，集合長度不固定。
2.數組可以存儲基本類型和引用類型，集合隻能存儲引用類型。
Java 集合架構中的接口體系
Java集合架構中的重要接口
Java集合架構中，集合有兩個基本接口：Collection 和 Map。
Collection 接口
Collection 接口實作了Iterable 接口，我們來看看Iterable 接口的定義：
public interface Iterable<T> {
// 傳回一個T元素類型的疊代器
Iterator<T> iterator();
// 其他接口方法...
}
} 在Java 1.8幫助文檔中對Iterable 接口的說明是：實作此接口允許對象成為“for-each loop”語句的目标。
Collection 接口擴充了Iterable 接口。是以，對于标準類庫中的任何實作Collection 接口的集合都可以使用“for each”循環來周遊元素。
Iterable 接口中隻定義了一個抽象方法iterator()，該方法用于傳回一個實作了Iterator 接口的（疊代器）對象，可以使用這個疊代器對象依次通路集合中的元素。
Iterator 接口
我們來看看這個Iterator（疊代器）接口：
public interface Iterator<E> {
// 如果疊代具有更多元素，則傳回 true 。
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());
}
} 通過反複調用next方法，可以逐個通路集合中的每個元素。但是，如果到達了集合的末尾，next方法将抛出一個NoSuchElementException。是以，需要在調用next之前調用hasNext方法。如果疊代器對象還有多個供通路的元素，這個方法就傳回true。如果想要檢視集合中的所有元素，就請求一個疊代器，并在hasNext傳回true時反複地調用next方法。
我們來看一看案例：
public class TestList {
public static void main(String[] args) {
// 1.建立對象
List list = new ArrayList();
// 2.周遊元素
// 方法一：疊代器
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
// 方法二：for-each
for (Object object : list) {
System.out.println(object);
}
}
} 我們建立了一個擴充了Collection 接口的接口List 的實作類ArrayList的對象，并沒有添加元素，因為我們此刻的重點是看疊代器的具體使用。上面提到過，Collection 接口 擴充了 Iterable 接口，是以此集合也可以使用“for-each”循環來周遊。
元素被通路的順序取決于集合類型。如果對ArrayList進行疊代，疊代器将從索引0開始，每疊代一次，索引值加1。然而，如果通路HashSet中的元素，每個元素将會按照某種随機的次序出現。雖然可以确定在疊代過程中能夠周遊到集合中的所有元素，但卻無法預知元素被通路的次序。
Java集合類庫中的疊代器與其他類庫中的疊代器的差別
在傳統的集合類庫中，例如，C++的标準模版庫，疊代器是根據數組索引模組化的。如果給定這樣一個疊代器，就可以檢視指定位置上的元素，就像知道數組索引i就可以檢視數組元素a[i]一樣。不需要查找元素，就可以将疊代器向前移動一個位置。這與不需要執行查找操作就可以通過i++将數組索引向前移動一樣。
但是，Java疊代器并不是這樣操作的。查找操作與位置變更是緊密相連的。查找一個元素的唯一方法是調用next，而在執行查找操作的同時，疊代器的位置随之向前移動。是以，應該将Java疊代器認為是位于兩個元素之間。當調用next時，疊代器就越過下一個元素，并傳回剛剛越過的那個元素的引用。
Collection 接口中的方法
| 方法 | 描述 |
| boolean add(E e) | 確定此集合包含指定的元素。 |
| boolean addAll(Collection<? extends E> c) | 将指定集合中的所有元素添加到此集合。 |
| void clear() | 從此集合中删除所有元素。 |
| boolean contains(Object o) | 如果此集合包含指定的元素，則傳回 true 。 |
| boolean containsAll(Collection<?> c) | 如果此集合包含指定 集合中的所有元素，則傳回true。 |
| boolean equals(Object o) | 将指定的對象與此集合進行比較以獲得相等性。 |
| int hashCode() | 傳回此集合的哈希碼值。 |
| boolean isEmpty() | 如果此集合不包含元素，則傳回 true 。 |
| Iterator<E> iterator() | 傳回此集合中的元素的疊代器。 |
| boolean remove(Object o) | 從該集合中删除指定元素的單個執行個體（如果存在）。 |
| int size() | 傳回此集合中的元素數。 |
Collection 接口常用方法
這兒隻列出來了一些常用的方法，這些方法被Collection 下屬的三個集合接口List、Set、Queue所繼承，它們又繼承給自己打下屬接口。注意，此時并沒有實作這些方法，因為Java集合類庫是将接口和實作分離的，後續我們會講到方法的實作。
Map 接口
Map集合用于儲存具有映射關系的資料，存儲鍵(key)值(value)對，一對一對往裡存，保證鍵(key)的唯一性。
Map 接口中的方法
| 方法 | 描述 |
| boolean containsKey(Object key) | 如果此映射包含指定鍵的映射，則傳回 true 。 |
| void clear() | 從該地圖中删除所有的映射。 |
| boolean containsValue(Object value) | 如果此地圖将一個或多個鍵映射到指定的值，則傳回 true 。 |
| Set<Map.Entry<K,V>> entrySet() | 傳回此地圖中包含的映射的Set視圖。 |
| boolean equals(Object o) | 将指定的對象與此映射進行比較以獲得相等性。 |
| V get(Object key) | 傳回到指定鍵所映射的值，或 null如果此映射包含該鍵的映射。 |
| int hashCode() | 傳回此地圖的哈希碼值。 |
| boolean isEmpty() | 如果此地圖不包含鍵值映射，則傳回 true 。 |
| Set<K> keySet() | 傳回此地圖中包含的鍵的Set視圖。 |
| V put(K key, V value) | 将指定的值與該映射中的指定鍵相關聯。 |
| V remove(Object key) | 如果存在，從該地圖中删除一個鍵的映射。 |
| int size() | size()傳回此地圖中鍵值映射的數量。 |
| Collection<V> values() | 傳回此地圖中包含的值的Collection視圖。 |
Map接口常用方法
ListIterator 接口
ListIterator是一個功能更加強大的疊代器, 它繼承于Iterator接口,隻能用于各種List類型的通路。可以通過調用listIterator()方法産生一個指向List開始處的ListIterator, 除此以外還可以調用listIterator(n)方法建立一個一開始就指向清單索引為n的元素處的ListIterator。
ListIterator的特點:
(1) 雙向移動（向前/向後周遊）。
(2) 可以産生相對于疊代器在清單中指向的目前位置的前一個和後一個元素的索引。
(3) 可以使用set()方法替換它通路過的最後一個元素。
(4) 可以使用add()方法在next()方法傳回的元素之前或previous()方法傳回的元素之後插入一個元素。
Iterator和ListIterator差別
集合List和Set都有iterator()方法來取得其疊代器。對List來說，你也可以通過listIterator()取得其疊代器，兩種疊代器在有些時候是不能通用的，Iterator和ListIterator主要差別在以下方面：
① ListIterator有add()方法，可以向List中添加對象，而Iterator不能。
② ListIterator和Iterator都有hasNext()和next()方法，可以實作順序向後周遊，但是ListIterator有hasPrevious()和previous()方法，可以實作逆向（順序向前）周遊；Iterator就不可以。
③ ListIterator可以定位目前的索引位置，用nextIndex()和previousIndex()來實作，但是Iterator沒有此功能。
④ 都可實作删除對象，但是ListIterator可以實作對象的修改，使用set()方法實作，但是Iierator僅能周遊，不能修改。
RandomAccess 接口
實際中有兩種有序集合，其性能開銷有很大差異。由數組支援的有序集合可以快速地随機通路，是以适合使用List方法并提供一個整數索引來通路。與之不同，連結清單盡管也是有序的，但是随機通路很慢，是以最好使用疊代器來周遊。
為了避免對連結清單完成随機通路操作，Java SE 1.4引入了一個标記接口RandomAccess。這個接口不包含任何方法，不過可以用它來測試一個特定的集合是否支援高效的随機通路。
我們來看一看如何應用它：
if (o instanceof RandomAccess) {
System.out.println("o支援随機通路");
}else {
System.out.println("o不至此随機通路");
} Java集合架構中的實作類體系
與現代的資料結構類庫的常見做法一樣，Java集合類庫也将接口與實作分離開。我們來看看有哪些實作類：
Java 集合架構中的實作類
我們在上節看到的集合的幾種接口在上圖中都有其對應的抽象類，這些抽象類中實作了其子類共有的方法，繼承了接口中的其他方法。抽象類下面有各自具體的實作子類，在其中定義了各自特有的方法和實作。
我們來梳理一下集合具體實作類：
★ 集合中有兩大基本的接口：Collection 和 Map。
★ Collection 接口下有兩個重要集合：List 和 Set。
☆ List 集合的實作類有ArrayList、Vector 和 LinkedList。
☆ Set 集合的常用實作類有HashSet、TreeSet 和 LinkedHashSet。
★ Map 接口下隻有Map集合，Map集合重要的實作類有：HashMap、TreeMap 和 LinkedHashMap。
List 集合
List 是用于存放多個元素的容器，它允許有重複的元素，并保證元素之間的先後順序。List 有3個主要的實作類：ArrayList、Vector 和 LinkedList。
ArrayList
ArrayList 類又稱為動态數組，該容器類實作了清單的相關操作。ArrayList的内部資料結構由數組實作，是以可對容器内元素實作快速随機通路。但因為在ArrayList 中插入或删除一個元素需要移動其他元素，是以不适合在插入和删除操作頻繁的場景下使用 ArrayList。與此同時，ArrayList的容量可以随着元素的增加而自動增加，是以不用擔心ArrayList容量不足的問題。另外 ArrayList是非線程安全的。
ArrayList的常用方法總結如下:
添加元素
♦ boolean add(E e)：将指定的元素e添加到此清單的尾部。
♦ void add(int index,E element)：将指定的元素 element 插入此清單中的指定位置index.
♦ boolean addAll(Collection<? extends E> c)：将該Collection 中的所有元素添加到此清單的尾部。
♦ boolean addAll(int index,Collection<?extends E> c)：從指定的位置index開始，将指定Collection 中的所有元素插入此清單中。
删除元素
♦ E remove(int index)：移除此清單中指定位置index上的元素。
♦ boolean remove(Object o)：移除此清單中首次出現的指定元素。（如果存在的話）。
♦ void clear()：移除此清單中的所有元素。
查找元素
♦ boolean contains(Object o)：如果此清單中包含指定的元素o,則傳回true.
♦ E get(int index)：傳回此清單中指定位置index上的元素。
♦ int indexOf(Object o)：傳回此清單中首次出現的指定元素o的索引，或如果此清單不包含元素o,則傳回-1.
♦ boolean isEmpty()：如果此清單中沒有元素，則傳回true,否則傳回 false.
♦ int lastIndexOf(Object o)：傳回此清單中最後一次出現指定元素o的索引，如果此清單不包含則傳回-1.
其他方法
♦ E set(int index,E element)：用指定的元素element 替代此清單中指定位置index上的元素。注意它與 void add (int index,E element)方法的差別：add方法是添加一個元素，原來index 位置上的元素要向後移動；而set方法是将原來index 位置上的元素替換為element.
♦ int size()：傳回此清單中的元素數。
♦ Object[] toArray()：按适當順序（從第一個元素到最後一個元素）傳回包含此清單中所有元素構成的數組。
重點：ArrayList 的擴容機制
問題描述：
ArrayList list= new ArrayList(20); 在建立 list 時擴充容量幾次？
問題分析：
ArrayList 類又稱為動态數組，内部資料結構由數組實作，數組的容量可以自動增長，當數組容量不足以存放新增元素時，需要進行數組的擴容，擴容的基本政策如下：
每次向數組中添加元素時，要檢查添加元素後的容量是否超過目前數組的長度，如果沒有超過，則添加該元素，不做其他操作；如果超過，則數組就會進行自動擴容，每次擴充原容量的1.5倍。另外 ArrayList 提供了3個構造函數，在初始擴容時有略微不同，因為篇幅問題，在這不做過多闡述，具體請看這篇文章：淺談ArrayList的擴容機制。
問題結果：
擴容0次。
Vector
Vector類又稱為向量類，也實作了類似動态數組的功能，内部資料結構也由數組實作。與ArrayList 不同的是，Vector是線程安全的，它的方法都是同步方法，是以通路效率低于ArrayList。另外 Vector 是非泛型集合，可以往其中随意插入不同類的對象，不需要考慮類型和預先標明向量的容量，可友善地進行查找等操作。當然也可以使用Vector 的泛型取代非泛型類型（例如 Vectort<String>)。
Vector 的常用方法總結如下：
添加元素
♦ public synchronized boolean add(E e)：在最後位置新增元素e.
♦ public void add(int index, E element)：在具體的索引位置index 上添加元素 element,因為該函數内部調用了同步方法synchronized void insertElementAt(),是以該方法依然是同步的。
♦ public synchronized boolean addAll(Collection<?extends E>c)：将一個容器c的所有元素添加到向量的尾部。
删除元素
♦ public boolean remove(Object o)：删除元素o,方法内部調用了另一個同步方法 public synchronized boolean removeElement(Object obj),是以該方法依然是同步的。
♦ public synchronized void removeElementAt(int index)：删除指定位置的元素。
查找元素
♦ public synchronized E elementAt(int index)：查找指定位置的元素。
其他方法
♦ public synchronized E get(int index)：擷取指定位置index的元素。
♦ public synchronized E set(int index,E element)：用指定的元素element 替代 Vector 中指定位置index上的元素。
對比Vector 和 ArrayList 的主要方法，可以發現：Vector的方法與ArrayList 的方法的主要差異是增加了 synchronized 關鍵字，這樣保證了執行的線程安全，但也勢必會影響Vector的性能。
是以在不要求線程安全的場景中，推薦使用性能更好的 ArrayList。
LinkedList
LinkedList 也是List 的一個重要實作類。它的内部資料結構由連結清單結構實作，并且是非線程安全的，适合資料的動态插入和删除，插入和删除元素時不需要對資料進行移動、是以插入、删除效率較高，但随機通路速度較慢。
Set 集合
HashSet 和 TreeSet 是Set接口的兩個最重要的實作類，在Set容器類中得到廣泛使用。其中 TreeSet是 Set的子接口 SortedSet的實作類。
HashSet
HashSet 是java.util包中的類，實作了Set接口，封裝了HashMap,元素是通過HashMap來儲存的。
關于 HashSet 有以下幾點需要說明：
① HashSet 中的元素可以是null,但隻能有一個null(因為實作了Set接口，是以不允許有重複的值）。
② HashSet 是非線程安全的。
③ 插入HashSet 中的對象不保證與插入的順序一緻，元素的排列順序可能改變。
④ 向HashSet 中添加新的對象時，HashSet類會進行重複對象元素判斷：判斷添加對象和容器内已有對象是否重複，如果重複則不添加，如果不重複則添加。
HashSet 是怎麼區分重複元素的？
在上面已經說過，HashSet實作了Set接口，是以不能存儲重複元素。在向 HashSet 中添加元素時會調用 HashSet的boolean add(E e)方法，在該方法中，HashSet 會首先判斷所要添加的元素是否與容器内已存在的元素有重複，如果沒有重複則添該元索并傳回true,否則不添加元素并傳回 false。
那麼如何判斷所要添加的元素是否與容器内已存在的元素有重複呢？在 HashSet 内部，HashSet 封裝了 HashMap,在調用add()方法時，實際上是調用了HashMap 的 put()方法添加元素，源碼如下：
public boolean add(E e){
return map.put(e,PRESENT)==null;
} 我們來看上面的代碼，其中添加的元素e就是HashMap的key(put方法的第一個參數）。HashMap 的 put()方法首先會調用元素e的hashCode()得到其在 HashMap 中的索引，如果在該索引位置上已存在其他元素（即兩個元素的hashCode()傳回值相等），則再調用e的equals()方法判斷該索引位置上的元素是否與要添加的元素e相等。隻有上述兩個條件都滿足，才能确認該HashMap 中已經包含元素e.
總結一下，要準确判斷HashSet 中兩個對象重複與否，需要hashCode()和 equals()這兩個方法共同來确定，即如果 hashCode()傳回值相等并且 equals()傳回true,則判定兩個對象重複，隻要任一條件不滿足，則判定兩個對象不重複。
如果大家還對此過程有疑惑，我們可以進一步了解HashSet 中的 HashMap.put()方法，看看它是如何實作添加元素功能的，源代碼如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} 進一步來看putVal 方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 如果存儲元素的table為空，則進行必要字段的初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 擷取長度（預設初始容量：16）
n = (tab = resize()).length;
// 如果根據hash值擷取的結點為空，則建立一個結點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果該節點不為空，則進行進一步判斷
else {
Node<K,V> e;
K k;
// 1.找到與插入節點相映射的節點，如果沒有則建立
// 這裡的p結點是根據hash值算出來對應在數組中的元素
// 如果新插入的結點和table中p結點的hash值，key值相同的話，将節點p指派給節點e
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是紅黑樹結點的話，進行紅黑樹插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果是單連結清單的話，周遊連結清單，查找對應節點
else {
for (int binCount = 0; ; ++binCount) {
// 如果周遊完了單連結清單，直接新增節點到連結清單末尾，并退出循環
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 連結清單長度大于8時，将連結清單轉紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果需要插入的結點和table中p結點的hash值，key值相同的話，直接退出循環
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// 周遊下一個節點
p = e;
}
}
// 2.如果存在這個映射就覆寫
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判斷是否允許覆寫，并且value是否為空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回調以允許LinkedHashMap後置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更改操作次數
++modCount;
// 如果長度大于臨界值
if (++size > threshold)
// 将數組大小設定為原來的2倍，并将原先的數組中的元素放到新數組中
// 因為有連結清單，紅黑樹之類，是以還要調整他們
resize();
// 回調以允許LinkedHashMap後置操作
afterNodeInsertion(evict);
return null;
} 通過代碼的描述能夠看出，這裡向HashSet中添加的元素實際上就是HashMap 中的key,而不是value。代碼中首先擷取對象key的hash值，然後以此hash值得到key 在HashMap 中的索引。因為HashMap 本質上是一個數組＋連結清單＋紅黑樹的資料結構，是以在同一個索引i下可能存在多個元素，是以這裡通過一個循環周遊該索引i下的每一個元素。如果發現要添加到HashMap 中的元素key與該索引上的某個元素重複（hash值相等并且equals 傳回值為true),則用新的value覆寫掉舊的value,并傳回oldValue,這樣調用它的HashSet.add()方法則傳回false,表示添加元素不成功；如果發現要添加到HashMap 中的元素key與該索引上的任何元素都不重複，則把（key,value)鍵值對插入該索引下，然後傳回null,這樣調用它的HashSet.add()方法則傳回true,表示添加元素成功。
類型轉換問題
我們來看一段代碼：
public static void main(String[] args) {
Set<Short> set = new HashSet<Short>();
for (short i = 0; i < 10; i++) {
set.add(i);
set.remove(i - 1);
}
System.out.println(set.size());
} 大家可以看一下上面的代碼，然後算一下輸出的結果應該是多少？下面我們來一一分析：
HashSet 的常用方法總結如下：
① add(Ee):傳回boolean型值，其功能是在HashSet 中添加指定元素e.
說明：添加元素e時HashSet類先進行重複元素判斷：如果要添加的元素和已有元素重複，則添加不成功，傳回false;否則添加元素e,傳回true.
② remove(Object o):傳回boolean 型值，其功能是從HashSet 中移除指定元素o.
說明：如果元素o不包含在HashSet中，則未删除任何元素，傳回false;否則，删除元素o,傳回true.
下面我們來分析代碼的執行情況：
先建立了一個 Short類型的 HashSet 對象。然後調用add()方法向HashSet中插入元素。因為這裡插入的是short類型的值，而add()方法的參數是引用類型Short,是以 short類型的參數會自動裝箱成其包裝類Short類型。調用remove(i-1),i為short型，1為int類型，因為short、byte 型在進行數字運算時，會自動轉換為int,是以i-1傳回一個int類型值。
執行 set.remove(i-1)時，i-1會自動裝箱為Integer對象。雖然一個Short類型對象和一個Integer類型對象的值可能相等，但是它們的類型不同，是以比較時認為對象不相等，是以這裡的remove操作其實都不成功，因為set中不存在元素i-1,是以沒有删除任何對象，同時編譯器不報錯。
綜上所述，該段代碼的實質是，set中加入了10個元素，每一個都成功添加沒有被删除，是以輸出大小結果為10。
特别提示：
對于泛型集合HashSet<E>的add和remove方法，add()方法傳遞的參數類型一定要和Set中定義的類型一緻，否則會報編譯錯誤；但是remove()方法的參數類型是Objeet，是以可以接受任何類型，不會報編譯錯誤。
TreeSet
TreeSet 是java.util 包中的類，也實作了Set接口，是以TreeSet中同樣不能有重複元素。TreeSet 封裝了TreeMap,是以是一個有序的容器，容器内的元素是排好序的。
關于TreeSet,有以下幾點需要說明：
① TreeSet 中的元素是一個有序的集合（在插入元素時會進行排序），不允許放入null值。
② TreeSet 是非線程安全的。
③ 向TreeSet 中添加新的對象時，TreeSet 會将添加對象和已有對象進行比較，存在重複對象則不進行添加，不存在重複對象的情況下，新插入對象和已有對象根據比較結果排序再進行存儲。
TreeSet 是如何保證元素有序的？
TreeSet 底層資料結構是一種自平衡的二叉搜尋樹，即紅黑樹。紅黑樹保證了元素的有序性，TreeSet 是按照紅黑樹的結點進行存儲和取出資料的。
注意：
HashSet中元素的無序和LinkedHashSet中元素按照插入的順序有序是指向容器中插入元素的順序是否與周遊順序一緻。例如，向一個HashSet中順序插入元素a、b、c,而周遊 HashSet時通路元素的順序就不一定是a、b、c了，這叫作不保證周遊順序和插入順序一緻。而TreeSet 中元素的有序是指元素按照CompareTo(Object obj)方法來比較元素之間大小關系後的順序進行的排序，它與按照插入的順序有序不是一個概念。
LinkedHashSet
LinkedHashSet 類是HashSet 的子類，它的元素也是唯一的，LinkedHashSet 是基于 HashMap和雙向連結清單的實作類。LinkedHashSet 與HashSet 相比，它底層是用雙向連結清單實作，用連結清單記錄資料，實作了按照插入的順序有序，也就是說，周遊順序和插人順序是一緻的。LinkedHashSet在疊代通路Set 中全部元素時性能會比HashSet好，但插人元素時性能不如 HashSet.
Map 集合
HashMap 和 Hashtable 是Map接口的主要實作類。
HashMap
HashMap 又稱為哈希表，它是根據鍵key的 hashCode值來存儲資料的它存儲的是鍵值對（key-value)映射，具有快速定位的特點。HashMap 繼承于 AbstractMap,實作了Map等接口。它的實作是不同步的，是以不是線程安全的。它的key、value 都可以為null,而key最多隻能出現一個 null。同時 HashMap 中的映射不是有序的（存儲序不等于插入序）。
HashMap 的主要方法總結：
添加元素
♦ public V put(K key,V value)：向 HashMap 中插入結點＜key,value>,若key已經存在，則覆寫相同key的結點。
♦ public void putAll(Map<?extends K,?extends V>m)：将指定的map m中的＜key,value>插入HashMap 中。
删除元素
♦ public V remove(Object key)：移除key指定的鍵值對＜key,value>。
查找元素
♦ public V get(Object key)：傳回鍵key對應的值 value。
♦ final Entry<K,V> getEntry(Object key)：根據鍵key查找鍵值對。
♦ public boolean containsKey(Object key)：判斷是否包含鍵key指定的鍵值對。
♦ public boolean contains Value(Object value)：判斷是否包含 value 對應的鍵值對。
其他方法
♦ public int size()：傳回哈希表中鍵值對個數。
♦ public Set<Map.Entry<K,V>>entrySet()：傳回一個鍵值對集合。
HashMap 的資料結構：
HashMap 的資料結構是由數組＋連結清單＋紅黑樹來實作的。HashMap 底層是一個數組Entry[] table,數組中的每個元素Entry都是一個單項連結清單的引用，從JDK1.8開始，當連結清單長度大于8時，連結清單會調整為紅黑樹結構。
從JDK1.8開始，HashMap 為什麼要引入紅黑樹結構？
HashMap 采用數組和連結清單相結合的資料結構，底層是一個數組，每個數組元素都是一個連結清單結構，連結清單的每個結點就是HashMap 中的每個元素（鍵值對）。當要向 HashMap 中添加一個鍵值對時，會先調用該鍵值對的key的 hashCode()方法計算出 hashCode值，進而得到該元素在數組中的下标。如果數組在該位置上已儲存有元素（已存在一個連結清單），則說明發生了沖突（不同的key值對應了同一個hash值，是以映射的數組下标也相同），接下來就要按照HashMap 沖突管理算法進行處理。
HashMap 采用鍊位址法，即用單連結清單将所有沖突的元素連結起來，通過這種方法來進行沖突管理。但是這個連結清單并不會無限地增長，當連結清單中元素個數大于8時，這個連結清單會自動轉為紅黑樹結構。之是以引入紅黑樹結構是因為在連結清單中查找每個元素的時間複雜度都是O(n),而在紅黑樹中查找元素的時間複雜度為O(logn),這樣當HashMap 中元素量較多并産生了大量Hash 沖突時，紅黑樹的快速增删改查的特點能提高 HashMap 的性能。
紅黑樹（Red Black Tree)是一種自平衡二叉查找樹，它是在1972年由 Rudolf Bayer 發明的。紅黑樹用紅色和黑色來标記結點，并且有以下三個特點：
① 根和葉子結點都是黑色的。
② 從每個葉子到根的所有路徑上不能有兩個連續的紅色結點。
③ 從任一結點到它所能到達的葉子結點的所有簡單路徑都包含相同數目的黑色結點。
以上三個特性保證了紅黑樹比其他的二叉查找樹有更好的結點查找穩定性、查找效率和增删結點時的效率。鑒于以上原因，引入了紅黑樹來解決HashMap 的哈希沖突效率等問題。
紅黑樹結構這麼好，為什麼在元素個數小于8時還要用連結清單，而不直接使用紅黑樹？
當元素數目較少時，連結清單的效率更高，而紅黑樹的實作和調整都更複雜，反而會影響整體性能。
HashMap 對象的兩個重要屬性和擴容：
HashMap 對象的兩個重要屬性：初始容量和加載因子。初始容量是指 HashMap 在建立時的容量，加載因子是 HashMap 在其容量自動增加之前可以達到多滿的一種尺度。HashMap的初始容量預設值為16,預設加載因子是0.75,當 HashMap 中的元素數目超出加載因子與目前容量的乘積時，則要對該 HashMap 進行擴容操作，擴容後數組大小為目前的2倍。
HashMap 的沖突管理：
HashMap 采用“hash 算法”來決定每個元素的存儲位置，當添加新的元素時，系統會調用 hashCode()方法得到一個 hashCode值，再根據這個hashCode值決定這個元素在 HashMap 中的存儲位置。當不同的對象的hashCode值相同時，就出現了沖突，HashMap 采用鍊位址法，即用單連結清單将所有沖突的元素連結起來，通過這種方法來進行沖突管理。當連結清單的元素個數大于8時，會自動轉為紅黑樹結構，這樣會提升查詢性能，把順序搜尋連結清單記錄的時間複雜度從O(n)提高到O(logn)。
HashTable
Hashtable 類與 HashMap 類似，不同的是Hashtable是線程安全的，而且屬于遺留類。需要注意的是，如果對同步性和遺留代碼的相容性沒有特殊要求，建議使用HashMap類，這是因為 Hashtable 雖然有線程安全的優點，但是效率較低。Hashtable 的方法類似于HashMap。在實際應用中如果需要線程安全的場景，推薦使用 ConcurrentHashMap 代替 Hashtable。
ConcurrentHashMap
ConcurrentHashMap 和 HashMap 的定義類似，但它是線程安全的，和Hashtable相比更加細化，而且性能優勢更大。學習時需要掌握ConcurrentHashMap 的加鎖原理。
HashMap 和 Hashtable 的主要差別：
① HashMap 和Hashtable 是Map 接口的兩個重要實作類，HashMap是Hashtable的輕量級實作。
② HashMap 是非線程安全的，Hashtable是線程安全的。
③ HashMap的鍵（key)和值（value)都支援null，Hashtable 鍵（key)和值（value)都不支援null。
④ 關于 fail-fast(快速失敗）機制，HashMap 使用 Iterator 進行周遊，Iterator 疊代器支援fail-fast(快速失敗）機制；而 Hashtable 用Iterator 周遊時支援 fail-fast,但是用 Enumerationr 周遊時不支援 fail-fast。
注意：
快速失效機制（fail-fast):快速失效機制fail-fast是Java容器中的一種錯誤檢測機制。當使用疊代器疊代容器類的過程中，如果同時該容器在結構上發生改變，就有可能觸發fail-fast,抛出 ConcurrentModificationException 異常。這種機制一般僅用于檢測bug。
例如：當使用Iterator疊代容器類 ArrayList 時，在循環送代過程中每次調用 ArrayList的remove()方法删除元素，讓容器結構發生了改變，就可能引起快速失效機制，進而抛出 ConcurrentModificationException 異常。