簡(jiǎn)介

1、集合類存放于java.util包中魔种。
2滔金、集合類型主要有3種：set(集）、list(列表）和map(映射)惫周。
3、集合存放的都是對(duì)象的引用康栈，而非對(duì)象本身递递。所以我們稱集合中的對(duì)象就是集合中對(duì)象的引用。
簡(jiǎn)單來(lái)講：集合就是一個(gè)放數(shù)據(jù)的容器啥么，準(zhǔn)確的說(shuō)是放數(shù)據(jù)對(duì)象引用的容器登舞。

一、集合框架圖

集合與數(shù)組的區(qū)別

常用的集合

Collection
├——-List ：有序集合氯迂，元素按進(jìn)入先后有序保存稽煤，可重復(fù)
│—————-├ LinkedList 基于鏈表， 遍歷效率低囚戚，插入刪除效率高， 非同步轧简， 線程不安全
│—————-├ ArrayList 驰坊， 基于數(shù)組， 實(shí)現(xiàn)了動(dòng)態(tài)大小的數(shù)組哮独，遍歷效率高拳芙， 非同步， 線程不安全
│—————-└ Vector ： 基于數(shù)組皮璧， 同步舟扎， 線程安全，效率低
│ ———————-└ Stack 是Vector類的實(shí)現(xiàn)類
└——-Set 接口： 無(wú)序集合悴务，不允許相同元素睹限，最多有一個(gè)null元素
├—————-└HashSet 使用hash表（數(shù)組）存儲(chǔ)元素
│————————└ LinkedHashSet 鏈表維護(hù)元素的插入次序
└ —————-TreeSet 底層實(shí)現(xiàn)為二叉樹(shù)譬猫，元素排好序

Map 接口 鍵值對(duì)的集合 （雙列集合）
├———Hashtable 接口實(shí)現(xiàn)類， 同步羡疗， 線程安全
├———HashMap 接口實(shí)現(xiàn)類 染服，沒(méi)有同步， 線程不安全-
│—————–├ LinkedHashMap 雙向鏈表和哈希表實(shí)現(xiàn)
│—————–└ WeakHashMap
├ ——–TreeMap 紅黑樹(shù)對(duì)所有的key進(jìn)行排序
└———IdentifyHashMap

三叨恨、List集合

List是有序的Collection柳刮，使用此接口能夠精確的控制每個(gè)元素插入的位置。用戶能夠使用索引（元素在List中的位置痒钝，類似于數(shù)組下標(biāo)）來(lái)訪問(wèn)List中的元素秉颗，這類似于Java的數(shù)組。List允許有相同的元素送矩。

3.1蚕甥、ArrayList

3.1.1、ArrayList擴(kuò)容機(jī)制：

1益愈、我們對(duì)ArrayList的源碼進(jìn)行解讀梢灭，發(fā)現(xiàn)如下幾個(gè)重要屬性：

    // 默認(rèn)初始容量
    private static final int DEFAULT_CAPACITY = 10;

     // 默認(rèn)共享的空對(duì)象數(shù)組：
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // ArrayList 實(shí)際數(shù)據(jù)存儲(chǔ)的一個(gè)數(shù)組：
    transient Object[] elementData; // non-private to simplify nested class access

    // elementData 的大小：
    private int size;

2蒸其、新增數(shù)據(jù)的add 方法

    /**
     * 將指定元素追加到列表的末尾敏释。
     */
    public boolean add(E e) {
        // 確保容量夠用
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果新增數(shù)據(jù)已沒(méi)有位置存放，則進(jìn)行擴(kuò)容摸袁。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

2钥顽、具體擴(kuò)容方法：

    private void grow(int minCapacity) {
        // 原來(lái)的容量
        int oldCapacity = elementData.length;
        // 新的容量是原來(lái)的1.5倍，準(zhǔn)確的說(shuō)是新容量=原容量+原容量右移1位
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // 最終利用Arrays.coppy 進(jìn)行擴(kuò)容靠汁，生成一個(gè)1.5倍元素的數(shù)組蜂大。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

總結(jié)：ArrayList 的內(nèi)部實(shí)現(xiàn)，其實(shí)是用一個(gè)對(duì)象數(shù)組進(jìn)行存放具體的值蝶怔，然后用一種擴(kuò)容的機(jī)制奶浦，進(jìn)行數(shù)組的動(dòng)態(tài)增長(zhǎng)。
其擴(kuò)容機(jī)制可以理解為踢星，當(dāng)元素的個(gè)數(shù)大于其容量時(shí)澳叉，則把其容量擴(kuò)展為原來(lái)容量的1.5倍，準(zhǔn)確的說(shuō)是【新容量=原容量+原容量右移1位】沐悦。

3.1.2成洗、remove方法源碼解讀：

public E remove(int index) {
        // 檢查索引是否在范圍內(nèi)
        rangeCheck(index);

        modCount++;
        // 返回刪除元素
        E oldValue = elementData(index);
        //  需要移動(dòng)的數(shù)組長(zhǎng)度
        int numMoved = size - index - 1;
        if (numMoved > 0)
            /**
             *Object src : 原數(shù)組
             *int srcPos : 從元數(shù)據(jù)的起始位置開(kāi)始
　　         * Object dest : 目標(biāo)數(shù)組
　　         *  int destPos : 目標(biāo)數(shù)組的開(kāi)始起始位置
　　          *  int length  : 要copy的數(shù)組的長(zhǎng)度
             **/
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 設(shè)置最后一位為null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

3.2、LinkedList

1藏否、LinkedList是一個(gè)繼承于AbstractSequentialList的雙向鏈表瓶殃。它也可以被當(dāng)做堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行使用副签。
2遥椿、LinkedList實(shí)現(xiàn)List接口基矮，能讓它進(jìn)行隊(duì)列操作。
3修壕、LinkedList實(shí)現(xiàn)Deque接口愈捅，即能將LinkedList當(dāng)做雙端隊(duì)列使用。
4慈鸠、LinkedList實(shí)現(xiàn)Cloneable蓝谨，即覆蓋了函數(shù)clone()，能被克隆青团。
5譬巫、LinkedList實(shí)現(xiàn)了java.io.Serializable接口，這意味著LinkedList支持序列化督笆，能通過(guò)序列化去傳輸芦昔。
6、LinkedList中的操作不是線程安全的娃肿。

源碼解讀：

3.2.1咕缎、幾個(gè)重要屬性

//鏈表節(jié)點(diǎn)的個(gè)數(shù)
transient int size = 0;
//鏈表首節(jié)點(diǎn)
transient Node<E> first;
//鏈表尾節(jié)點(diǎn)
transient Node<E> last;

3.2.2、Node結(jié)構(gòu)

數(shù)據(jù)存儲(chǔ)與Node中料扰，Node結(jié)構(gòu)如下：

private static class Node<E> {
        E item;     //當(dāng)前節(jié)點(diǎn)元素值
        Node<E> next;  //下一個(gè)節(jié)點(diǎn)元素
        Node<E> prev; // 上一個(gè)節(jié)點(diǎn)元素

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

3.2.3凭豪、添加元素

public boolean add(E e) {
        // 在鏈表尾部添加元素
        linkLast(e);
        // 因?yàn)槭菬o(wú)界的，所以添加元素總是會(huì)成功
        return true;
    }
  
   // 在鏈表尾部添加元素
  void linkLast(E e) {
        //將內(nèi)部保存的尾節(jié)點(diǎn)賦值給l
        final Node<E> l = last;
        //創(chuàng)建新節(jié)點(diǎn)晒杈，新節(jié)點(diǎn)的prev節(jié)點(diǎn)是當(dāng)前的尾節(jié)點(diǎn)
        final Node<E> newNode = new Node<>(l, e, null);
        //把新節(jié)點(diǎn)作為新的尾節(jié)點(diǎn)
        last = newNode;
        //判斷是否是第一個(gè)添加的元素
        if (l == null)
            //如果是將新節(jié)點(diǎn)賦值給first
            first = newNode;
        else
            //如果不是把原首節(jié)點(diǎn)的next設(shè)置為新節(jié)點(diǎn)
            l.next = newNode;
        //更新鏈表節(jié)點(diǎn)個(gè)數(shù)
        size++;
        //將集合修改次數(shù)加1
        modCount++;
    }

    /**
     * 在鏈表首部添加元素原理相同嫂伞，不做解讀
     */

3.2.4、獲取元素

使用二分法查找元素拯钻，提供搜索效率帖努。

Node<E> node(int index) {
        //如果index小于size的一半，就從首節(jié)點(diǎn)開(kāi)始遍歷粪般，一直獲取x的下一個(gè)節(jié)點(diǎn)
        //如果index大于或等于size的一半拼余，就從尾節(jié)點(diǎn)開(kāi)始遍歷，一直獲取x的上一個(gè)節(jié)點(diǎn)
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

3.2.5亩歹、刪除元素

public boolean remove(Object o) {
        //因?yàn)長(zhǎng)inkedList允許存在null姿搜，所以需要進(jìn)行null判斷
        if (o == null) {
            //從首節(jié)點(diǎn)開(kāi)始遍歷
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    //調(diào)用unlink方法刪除指定節(jié)點(diǎn)，指定節(jié)點(diǎn)是null
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    //調(diào)用unlink方法刪除指定節(jié)點(diǎn)捆憎，指定節(jié)點(diǎn)不是null
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    //刪除指定節(jié)點(diǎn)
    E unlink(Node<E> x) {
        //獲取x節(jié)點(diǎn)的元素，以及它上一個(gè)節(jié)點(diǎn)梭纹，和下一個(gè)節(jié)點(diǎn)
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //如果x的上一個(gè)節(jié)點(diǎn)為null躲惰，說(shuō)明是首節(jié)點(diǎn)，將x的下一個(gè)節(jié)點(diǎn)設(shè)置為新的首節(jié)點(diǎn)
        //否則將x的上一節(jié)點(diǎn)設(shè)置為next变抽，將x的上一節(jié)點(diǎn)設(shè)為null
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        //如果x的下一節(jié)點(diǎn)為null础拨，說(shuō)明是尾節(jié)點(diǎn)氮块，將x的上一節(jié)點(diǎn)設(shè)置新的尾節(jié)點(diǎn)
        //否則將x的上一節(jié)點(diǎn)設(shè)置x的上一節(jié)點(diǎn)，將x的下一節(jié)點(diǎn)設(shè)為null
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //將x節(jié)點(diǎn)的元素值設(shè)為null诡宗，等待垃圾收集器收集
        x.item = null;
        //鏈表節(jié)點(diǎn)個(gè)數(shù)減1
        size--;
        //將集合修改次數(shù)加1
        modCount++;
        //返回刪除節(jié)點(diǎn)的元素值
        return element;
    }

3.3滔蝉、Vector

3.3.1 Vector的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：和數(shù)組類似開(kāi)辟一段連續(xù)的空間，并且支持隨機(jī)訪問(wèn)塔沃，所以它的查找效率高其時(shí)間復(fù)雜度O(1)蝠引。
缺點(diǎn)：由于開(kāi)辟一段連續(xù)的空間，所以插入刪除會(huì)需要對(duì)數(shù)據(jù)進(jìn)行移動(dòng)比較麻煩蛀柴，時(shí)間復(fù)雜度O（n）螃概，另外當(dāng)空間不足時(shí)還需要進(jìn)行擴(kuò)容。

3.3.2 Vector與ArrayList的區(qū)別

閱讀Vector源碼分容易發(fā)現(xiàn)鸽疾，Vector的方法都是同步的吊洼，這是Vector與ArrayList最大的不同。ArrayList是線程非安全的制肮，在并發(fā)下一定會(huì)出現(xiàn)線程安全問(wèn)題冒窍。另一個(gè)方法就是Vector，它是ArrayList的線程安全版本豺鼻，其實(shí)現(xiàn)90%和ArrayList都完全一樣综液，區(qū)別在于：

1、Vector是線程安全的拘领，ArrayList是線程非安全的
2意乓、在默認(rèn)情況下，當(dāng)用來(lái)存放元素的數(shù)組超過(guò)了內(nèi)部分配的長(zhǎng)度的時(shí)候约素。ArrayList會(huì)按照原長(zhǎng)度的50%來(lái)續(xù)加長(zhǎng)度届良。
Vector會(huì)按照原長(zhǎng)度的一倍來(lái)增加長(zhǎng)度。（Vector也可以指定增長(zhǎng)因子圣猎，如果該增長(zhǎng)因子指定了士葫，那么擴(kuò)容的時(shí)候會(huì)每次新的數(shù)組大小會(huì)在原數(shù)組的大小基礎(chǔ)上加上增長(zhǎng)因子；如果不指定增長(zhǎng)因子送悔，那么就給原數(shù)組大小*2慢显。）

3.4、Stack

棧是Vector的一個(gè)子類欠啤，它實(shí)現(xiàn)了一個(gè)標(biāo)準(zhǔn)的后進(jìn)先出的棧荚藻。

堆棧只定義了默認(rèn)構(gòu)造函數(shù)，用來(lái)創(chuàng)建一個(gè)空棧洁段。 堆棧除了包括由Vector定義的所有方法应狱，也定義了自己的一些方法。

4祠丝、Set集合

Set是一種無(wú)序的并且不包含重復(fù)的元素的Collection疾呻，即任意的兩個(gè)元素e1和e2都有e1.equals(e2)=false除嘹，Set最多有一個(gè)null元素。

4.1岸蜗、HashSet

HashSet是基于HashMap實(shí)現(xiàn)的尉咕，底層采用HashMap來(lái)保存元素，在準(zhǔn)確的說(shuō)使用HashMap的key來(lái)保存元素璃岳，value中統(tǒng)一存放private static final Object PRESENT = new Object();
HashSet 按 Hash 算法來(lái)存儲(chǔ)集合中的元素年缎，因此具有很好的存取和查找性能。
HashSet 的方法都是非同步的矾睦，不是線程非安全的晦款。

源碼解讀

    // 底層是由HashMap實(shí)現(xiàn)的
    private transient HashMap<E,Object> map;
    // value中統(tǒng)一存放PRESENT 
    private static final Object PRESENT = new Object();

    /**
     * 默認(rèn)初始容量（16）和負(fù)載系數(shù)（0.75）
     */
    public HashSet() {
        // 底層是由HashMap實(shí)現(xiàn)的
        map = new HashMap<>();
    }

4.2、LinkedHashSet

LinkedHashSet繼承自HashSet枚冗，但是LinkedHashSet內(nèi)部使用的是LinkHashMap來(lái)存儲(chǔ)數(shù)據(jù)缓溅。這樣做的意義或者好處就是LinkedHashSet中的元素順序是可以保證的，也就是說(shuō)遍歷序和插入序是一致的赁温。

// 繼承HashSet
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

  
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
     // 調(diào)用HashSet中的方法創(chuàng)建對(duì)象
    public LinkedHashSet() {
        super(16, .75f, true);
    }

// HashSet類
// 底層由LinkedHashMap存儲(chǔ)
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

總結(jié)：
LinkedHashSet 是 Set 的一個(gè)具體實(shí)現(xiàn)坛怪，其維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序股囊，該迭代順序可為插入順序或是訪問(wèn)順序袜匿。
如果需要迭代的順序?yàn)椴迦腠樞蚧蛘咴L問(wèn)順序，那么 LinkedHashSet 是需要你首先考慮的稚疹。

4.3居灯、TreeSet

TreeSet是一個(gè)有序的集合，它的作用是提供有序的Set集合内狗。TreeSet是基于TreeMap實(shí)現(xiàn)的怪嫌，TreeSet的元素支持2種排序方式：自然排序或者根據(jù)提供的Comparator進(jìn)行排序。

總結(jié)：
1柳沙、不能有重復(fù)的元素岩灭；
2、具有排序功能赂鲤；
3噪径、TreeSet中的元素必須實(shí)現(xiàn)Comparable接口并重寫(xiě)compareTo()方法，TreeSet判斷元素是否重復(fù) 数初、以及確定元素的順序 靠的都是這個(gè)方法找爱；
①對(duì)于Java類庫(kù)中定義的類，TreeSet可以直接對(duì)其進(jìn)行存儲(chǔ)泡孩，如String缴允，Integer等,因?yàn)檫@些類已經(jīng)實(shí)現(xiàn)了Comparable接口);
②對(duì)于自定義類，如果不做適當(dāng)?shù)奶幚恚琓reeSet中只能存儲(chǔ)一個(gè)該類型的對(duì)象實(shí)例练般，否則無(wú)法判斷是否重復(fù)。
4锈候、依賴TreeMap薄料。
5、相對(duì)HashSet,TreeSet的優(yōu)勢(shì)是有序泵琳，劣勢(shì)是相對(duì)讀取慢摄职。根據(jù)不同的場(chǎng)景選擇不同的集合。

5获列、Map集合

Map沒(méi)有繼承Collection接口谷市，Map提供key到value的映射。一個(gè)Map中不能包含相同的key击孩，每個(gè)key只能映射一個(gè)value迫悠。Map接口提供3種集合的視圖，Map的內(nèi)容可以被當(dāng)作一組key集合巩梢，一組value集合创泄，或者一組key-value映射。

5.1括蝠、HashMap

基于哈希表的 Map 接口的實(shí)現(xiàn)鞠抑。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵忌警。（除了非同步和允許使用 null 之外搁拙，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序法绵，特別是它不保證該順序恒久不變箕速。 此實(shí)現(xiàn)假定哈希函數(shù)將元素適當(dāng)?shù)胤植荚诟魍爸g，可為基本操作（get 和 put）提供穩(wěn)定的性能礼烈。迭代 collection 視圖所需的時(shí)間與 HashMap 實(shí)例的“容量”（桶的數(shù)量）及其大谢÷（鍵-值映射關(guān)系數(shù)）成比例。所以此熬，如果迭代性能很重要庭呜，則不要將初始容量設(shè)置得太高（或?qū)⒓虞d因子設(shè)置得太低）。

HashMap存儲(chǔ)結(jié)構(gòu)圖

源碼解讀-屬性

    // 默認(rèn)的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默認(rèn)的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹(shù)
    static final int TREEIFY_THRESHOLD = 8; 
    // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹(shù)轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹(shù)對(duì)應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲(chǔ)元素的數(shù)組犀忱，總是2的冪次倍
    transient Node<k,v>[] table; 
    // 存放具體元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的個(gè)數(shù)募谎，注意這個(gè)不等于數(shù)組的長(zhǎng)度。
    transient int size;
    // 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器
    transient int modCount;   
    // 臨界值 當(dāng)實(shí)際大小(容量*填充因子)超過(guò)臨界值時(shí)阴汇，會(huì)進(jìn)行擴(kuò)容
    int threshold;
    // 填充因子数冬，默認(rèn)值是0.75f
    final float loadFactor;

put新增數(shù)據(jù)

//根據(jù)key值計(jì)算出hashcode，
 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

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數(shù)組未初始化或者長(zhǎng)度為0，進(jìn)行擴(kuò)容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 確定元素存放在哪個(gè)桶中拐纱，桶為空铜异，新生成結(jié)點(diǎn)放入桶中(此時(shí)，這個(gè)結(jié)點(diǎn)是放在數(shù)組中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已經(jīng)存在元素
    else {
        Node<K,V> e; K k;
        // 比較桶中第一個(gè)元素(數(shù)組中的結(jié)點(diǎn))的hash值相等秸架，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 將第一個(gè)元素賦值給e揍庄，用e來(lái)記錄
                e = p;
        // hash值不相等，即key不相等东抹；為紅黑樹(shù)結(jié)點(diǎn)
        else if (p instanceof TreeNode)
            // 放入樹(shù)中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 為鏈表結(jié)點(diǎn)
        else {
            // 在鏈表最末插入結(jié)點(diǎn)
            for (int binCount = 0; ; ++binCount) {
                // 到達(dá)鏈表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新結(jié)點(diǎn)
                    p.next = newNode(hash, key, value, null);
                    // 結(jié)點(diǎn)數(shù)量達(dá)到閾值蚂子，轉(zhuǎn)化為紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循環(huán)
                    break;
                }
                // 判斷鏈表中結(jié)點(diǎn)的key值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循環(huán)
                    break;
                // 用于遍歷桶中的鏈表缭黔，與前面的e = p.next組合食茎，可以遍歷鏈表
                p = e;
            }
        }
        // 表示找到key值、hash值與插入元素相等的結(jié)點(diǎn)
        if (e != null) { 
            // 記錄e的value
            V oldValue = e.value;
            // onlyIfAbsent為false或者舊值為null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替換舊值
                e.value = value;
            // 訪問(wèn)后回調(diào)
            afterNodeAccess(e);
            // 返回舊值
            return oldValue;
        }
    }
    // 結(jié)構(gòu)性修改
    ++modCount;
    // 實(shí)際大小大于閾值則擴(kuò)容
    if (++size > threshold)
        resize();
    // 插入后回調(diào)
    afterNodeInsertion(evict);
    return null;
}

加入過(guò)程用腦圖進(jìn)行表示：

小疑問(wèn)：為什么使用 (n - 1) & hash 確定元素存放在哪個(gè)桶中?
其中就利用了按位與操作的一個(gè)特點(diǎn),必須兩個(gè)位都為1,才是1,那么也就是說(shuō),如果數(shù)組最大下標(biāo)為15,那么不管Hash(key)是多少都不會(huì)大于15馏谨，也就不會(huì)數(shù)組越界的問(wèn)題别渔。

resize擴(kuò)容

什么時(shí)候擴(kuò)容：當(dāng)向容器添加元素的時(shí)候，會(huì)判斷當(dāng)前容器的元素個(gè)數(shù)田巴，如果大于等于閾---即當(dāng)前數(shù)組的長(zhǎng)度乘以加載因子的值的時(shí)候钠糊，就要自動(dòng)擴(kuò)容啦。
擴(kuò)容(resize)就是重新計(jì)算容量壹哺，向HashMap對(duì)象里不停的添加元素抄伍，而HashMap對(duì)象內(nèi)部的數(shù)組無(wú)法裝載更多的元素時(shí)，對(duì)象就需要擴(kuò)大數(shù)組的長(zhǎng)度管宵，以便能裝入更多的元素截珍。當(dāng)然Java里的數(shù)組是無(wú)法自動(dòng)擴(kuò)容的，方法是使用一個(gè)新的數(shù)組代替已有的容量小的數(shù)組箩朴，就像我們用一個(gè)小桶裝水岗喉，如果想裝更多的水，就得換大水桶炸庞。

/**
     * 初始化或者翻倍表大小钱床。
     * 如果表為null，則根據(jù)存放在threshold變量中的初始化capacity的值來(lái)分配table內(nèi)存
     * （這個(gè)注釋說(shuō)的很清楚埠居，在實(shí)例化HashMap時(shí)查牌，capacity其實(shí)是存放在了成員變量threshold中，
     * 注意滥壕，HashMap中沒(méi)有capacity這個(gè)成員變量）
     * 纸颜。如果表不為null，由于我們使用2的冪來(lái)擴(kuò)容(指長(zhǎng)度擴(kuò)為原來(lái)2倍)绎橘，所以胁孙，經(jīng)過(guò)rehash之后
     * 則每個(gè)bin元素要么還是在原來(lái)的bucket(桶)中，，要么是在原位置再移動(dòng)2次冪的位置
     * 此方法功能：初始化或擴(kuò)容
     */
    final HashMap.Node<K,V>[] resize() {
        // 把擴(kuò)容前的table數(shù)組  賦值給  oldTab
        HashMap.Node<K,V>[] oldTab = table;
        // oldCap： 原容量值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // oldThr：原擴(kuò)容閥界值
        int oldThr = threshold;
        //新的容量值涮较，新的擴(kuò)容閥界值
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 超過(guò)最大值就不再擴(kuò)充了稠鼻，就只好隨你碰撞去吧
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 閾值設(shè)置為整數(shù)的最大值 Integer.MAX_VALUE
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // newCap： 新長(zhǎng)度設(shè)置為原長(zhǎng)度的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果能進(jìn)來(lái)證明此map是擴(kuò)容而不是初始化
                //操作：將原擴(kuò)容閥界值<<1(相當(dāng)于*2)賦值給 newThr
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
        /**
         * 進(jìn)入此if證明創(chuàng)建map時(shí)用的帶參構(gòu)造：public HashMap(int initialCapacity)
         *  或 public HashMap(int initialCapacity, float loadFactor)
         * 注：帶參的構(gòu)造中initialCapacity（初始容量值）不管是輸入幾都會(huì)通過(guò)
         * “this.threshold = tableSizeFor(initialCapacity);”來(lái)作為初始化容量（初始化容量==oldThr）
         * tableSizeFor方法:返回一個(gè)比給定值大的最小的2的次冪（大于initialCapacity參數(shù)的最小的2^n的數(shù)值）
         * tableSizeFor(initialCapacity)方法說(shuō)明：例如輸入100會(huì)返回128
         */
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //進(jìn)入此if證明創(chuàng)建map時(shí)用的無(wú)參構(gòu)造：
            // 新長(zhǎng)度設(shè)置為默認(rèn)容量：16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 新閾值設(shè)置為 默認(rèn)加載因子（0.75f）*16 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            //進(jìn)入此if有兩種可能
            // 第一種：進(jìn)入此“if (oldCap > 0)”中且不滿足該if中的兩個(gè)if
            // 第二種：進(jìn)入這個(gè)“else if (oldThr > 0)”

            //分析：進(jìn)入此if證明該map在創(chuàng)建時(shí)用的帶參構(gòu)造，如果是第一種情況就說(shuō)明是進(jìn)行擴(kuò)容且oldCap（舊容量）小于16狂票，
            // 如果是第二種說(shuō)明是第一次put
            float ft = (float)newCap * loadFactor;
            //計(jì)算擴(kuò)容閥界值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
        table = newTab;
        //如果“oldTab != null”說(shuō)明是擴(kuò)容枷餐，否則直接返回newTab
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof HashMap.TreeNode)
                        ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //此對(duì)象接收會(huì)放在原來(lái)位置
                        HashMap.Node<K,V> loHead = null, loTail = null;
                        //此對(duì)象接收會(huì)放在“j + oldCap”（當(dāng)前位置索引+原容量的值）
                        HashMap.Node<K,V> hiHead = null, hiTail = null;
                        HashMap.Node<K,V> next;
                        do {
                            next = e.next;
                            // e.hash & oldCap判斷是否需要移位
                            if ((e.hash & oldCap) == 0) {
                                // 不需要移位
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                // 需要移位
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            // 放在原位置
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            // 移動(dòng)到當(dāng)前hash槽位 + oldCap的位置
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1、 如果table == null, 則為HashMap的初始化, 生成空table返回即可;
2苫亦、 如果table不為空, 需要重新計(jì)算table的長(zhǎng)度, newLength = oldLength << 1(注, 如果原oldLength已經(jīng)到了上限, 則newLength = oldLength);
3、 遍歷oldTable:
4怨咪、 首節(jié)點(diǎn)為空, 本次循環(huán)結(jié)束;
5屋剑、 無(wú)后續(xù)節(jié)點(diǎn), 重新計(jì)算hash位, 本次循環(huán)結(jié)束;
6、 當(dāng)前是紅黑樹(shù), 走紅黑樹(shù)的重定位;
7诗眨、 當(dāng)前是鏈表, JAVA7時(shí)還需要重新計(jì)算hash位, 但是JAVA8做了優(yōu)化, 通過(guò)(e.hash & oldCap) == 0來(lái)判斷是否需要移位; 如果為真則在原位不動(dòng), 否則則需要移動(dòng)到當(dāng)前hash槽位 + oldCap的位置;

HashMap::resize的核心就是上圖, 鏈表與紅黑樹(shù)的resize過(guò)程大同小異: 紅黑樹(shù)是把構(gòu)建新鏈表的過(guò)程變?yōu)闃?gòu)建兩顆新的紅黑樹(shù), 定位table中的index都是用的 e.hash & oldCap == 0 來(lái)判斷;
再來(lái)看下 e.hash & oldCap == 0為什么可以判斷當(dāng)前節(jié)點(diǎn)是否需要移位, 而不是再次計(jì)算hash;

只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了（紅線標(biāo)注）唉匾，是0的話索引沒(méi)變，是1的話索引變成“原索引+oldCap”匠楚。
這個(gè)設(shè)計(jì)確實(shí)非常的巧妙巍膘，既省去了重新計(jì)算hash值的時(shí)間，而且同時(shí)芋簿，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的峡懈，因此resize的過(guò)程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了与斤。這一塊就是JDK1.8新增的優(yōu)化點(diǎn)肪康。

5.2、HashTable

Hashtable與HashMap的區(qū)別
1撩穿、HashMap是非同步的磷支，沒(méi)有對(duì)讀寫(xiě)等操作進(jìn)行鎖保護(hù)，所以是線程不安全的食寡，在多線程場(chǎng)景下會(huì)出現(xiàn)數(shù)據(jù)不一致的問(wèn)題雾狈。而HashTable是同步的，所有的讀寫(xiě)等操作都進(jìn)行了鎖（synchronized）保護(hù)抵皱，在多線程環(huán)境下沒(méi)有安全問(wèn)題善榛。但是鎖保護(hù)也是有代價(jià)的，會(huì)對(duì)讀寫(xiě)的效率產(chǎn)生較大影響叨叙。
2锭弊、HashMap結(jié)構(gòu)中，是允許保存null的擂错，Entry.key和Entry.value均可以為null味滞。但是HashTable中是不允許保存null的。
3、兩個(gè)遍歷方式的內(nèi)部實(shí)現(xiàn)上不同剑鞍。Hashtable昨凡、HashMap都使用了 Iterator。而由于歷史原因蚁署，Hashtable還使用了Enumeration的方式 便脊。
4、哈希值的使用不同光戈，HashTable直接使用對(duì)象的hashCode哪痰。而HashMap重新計(jì)算hash值。代碼是這樣的：
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
而HashMap重新計(jì)算hash值久妆，而且用與代替求模：
int hash = hash(k);
int i = indexFor(hash, table.length);
5晌杰、Hashtable和HashMap它們兩個(gè)內(nèi)部實(shí)現(xiàn)方式的數(shù)組的初始大小和擴(kuò)容的方式。HashTable中hash數(shù)組默認(rèn)大小是11筷弦，增加的方式是 old*2+1肋演。HashMap中hash數(shù)組的默認(rèn)大小是16，而且一定是2的指數(shù)烂琴。

5.3爹殊、TreeMap

TreeMap使用的存儲(chǔ)結(jié)構(gòu)是平衡二叉樹(shù)，也稱為紅黑樹(shù)奸绷。它首先是一棵二叉樹(shù)梗夸，具有二叉樹(shù)所有的特性，即樹(shù)中的任何節(jié)點(diǎn)的值大于它的左子節(jié)點(diǎn)健盒，且小于它的右子節(jié)點(diǎn)绒瘦，如果是一棵左右完全均衡的二叉樹(shù)，元素的查找效率將獲得極大提高扣癣。最壞的情況就是一邊倒惰帽，只有左子樹(shù)或只有右子樹(shù)，這樣勢(shì)必會(huì)導(dǎo)致二叉樹(shù)的檢索效率大大降低父虑。為了維持二叉樹(shù)的平衡该酗，程序員們提出了各種實(shí)現(xiàn)的算法，其中平衡二叉樹(shù)就是其中的一種算法士嚎。平衡二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)如下圖所示：

TreeMap存儲(chǔ)結(jié)構(gòu)

5.4呜魄、LinkHashMap

LinkHashMap存儲(chǔ)結(jié)構(gòu)

應(yīng)用場(chǎng)景

HashMap是無(wú)序的，當(dāng)我們希望有順序地去存儲(chǔ)key-value時(shí)莱衩，就需要使用LinkedHashMap了爵嗅。

        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("name1", "josan1");
        hashMap.put("name2", "josan2");
        hashMap.put("name3", "josan3");
        Set<Entry<String, String>> set = hashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

image

我們是按照xxx1、xxx2笨蚁、xxx3的順序插入的睹晒，但是輸出結(jié)果并不是按照順序的趟庄。

同樣的數(shù)據(jù)，我們?cè)僭囋嘗inkedHashMap

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name1", "josan1");
        linkedHashMap.put("name2", "josan2");
        linkedHashMap.put("name3", "josan3");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

image

結(jié)果可知伪很，LinkedHashMap是有序的戚啥，且默認(rèn)為插入順序