淺談 Java集合

• 2020 年 10 月 10 日
• 筆記
• Java基礎

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 接口中的方法

Collection 接口常用方法

　　這兒只列出來了一些常用的方法，這些方法被Collection 下屬的三個集合接口List、Set、Queue所繼承，它們又繼承給自己打下屬接口。注意，此時並沒有實現這些方法，因為Java集合類庫是將接口和實現分離的，後續我們會講到方法的實現。

Map 接口

　　Map集合用於保存具有映射關係的數據，存儲鍵(key)值(value)對，一對一對往裡存，保證鍵(key)的唯一性。

Map 接口中的方法

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 異常。