hashmap實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組、桶等。

image.png

如圖所示 JDK 1.7，是以數(shù)組+鏈表組成的，鏈表為相同hash的鍵值對，表頭儲存在數(shù)組中，形成以拉鏈的結(jié)構(gòu)，這就是他的數(shù)據(jù)結(jié)構(gòu)，當有新的鍵值對插入的時候， hash函數(shù)得到數(shù)組的位置，如果根據(jù)位置找到放入鍵值對，如果該位置存在鍵值對，就遍歷到表尾，進行放入。
桶就是上述的鏈表的，數(shù)組被叫做桶數(shù)組。
在JDK1.8后，鏈表長度大于8后，會樹化變?yōu)榧t黑樹。相當于數(shù)組+鏈表+紅黑樹組成。

hashmap是空的情況下，map.get(a) 得到的是啥

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位鍵值對所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 類型，則調(diào)用黑紅樹查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
            // 2. 對鏈表進行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

來自JDK 1.8 get方法，內(nèi)部會調(diào)用getNode，因為未被初始化，（初始化時在put操作時候進行的），table==null，return null。

HashMap怎么手寫實現(xiàn)？

理解到就是數(shù)組+鏈表的實現(xiàn)
https://blog.csdn.net/it_lihongmin/article/details/76377229

hashmap如何put數(shù)據(jù)（從hashmap源碼角度講解）？

環(huán)境JDK1.8
插入操作的入口方法是 put(K,V)，

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;
    // 初始化桶數(shù)組 table，table 被延遲到插入新數(shù)據(jù)時再進行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果桶中不包含鍵值對節(jié)點引用，則將新鍵值對節(jié)點的引用存入桶中即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時，則將 e 指向該鍵值對
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            
        // 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹的插入方法
        else if (p instanceof TreeNode)  
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 對鏈表進行遍歷，并統(tǒng)計鏈表長度
            for (int binCount = 0; ; ++binCount) {
                // 鏈表中不包含要插入的鍵值對節(jié)點時，則將該節(jié)點接在鏈表的最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果鏈表長度大于或等于樹化閾值，則進行樹化操作
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 條件為 true，表示當前鏈表包含要插入的鍵值對，終止遍歷
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 判斷要插入的鍵值對是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 鍵值對數(shù)量超過閾值時，則進行擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
  }

• 當桶數(shù)組 table 為空時，通過擴容的方式初始化 table
• 查找要插入的鍵值對是否已經(jīng)存在，存在的話根據(jù)條件判斷是否用新值替換舊值
• 如果不存在，則將鍵值對鏈入鏈表中，并根據(jù)鏈表長度決定是否將鏈表轉(zhuǎn)為紅黑樹
• 判斷鍵值對數(shù)量是否大于閾值，大于的話則進行擴容操作

Resize操作的過程。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不為空，表明已經(jīng)初始化過了
    if (oldCap > 0) {
        // 當 table 容量超過容量最大值，則不再擴容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } 
        // 按舊容量和閾值的2倍計算新容量和閾值的大小
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化時，將 threshold 的值賦值給 newCap，
         * HashMap 使用 threshold 變量暫時保存 initialCapacity 參數(shù)的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        /*
         * 調(diào)用無參構(gòu)造方法時，桶數(shù)組容量為默認容量，
         * 閾值為默認容量與默認負載因子乘積
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // newThr 為 0 時，按閾值計算公式進行計算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 創(chuàng)建新的桶數(shù)組，桶數(shù)組的初始化也是在這里完成的
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 如果舊的桶數(shù)組不為空，則遍歷桶數(shù)組，并將鍵值對映射到新的桶數(shù)組中
        for (int j = 0; j < oldCap; ++j) {
            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 TreeNode)
                    // 重新映射時，需要對紅黑樹進行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍歷鏈表，并將鏈表節(jié)點按原順序進行分組
                    do {
                        next = e.next;
                        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;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

• 計算新桶數(shù)組的容量 newCap 和新閾值 newThr
• 根據(jù)計算出的 newCap 創(chuàng)建新的桶數(shù)組，桶數(shù)組 table 也是在這里進行初始化的
• 將鍵值對節(jié)點重新映射到新的桶數(shù)組里。如果節(jié)點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節(jié)點，則節(jié)點按原順序進行分組。

- 簡單說說 JDK1.7 中 HashMap 什么情況下會發(fā)生擴容？如何擴容？

JDK1.7中HashMap擴容比較簡單，鍵值對的數(shù)量 >=threshold = capacity * loadFactor就達到擴容的條件，
1.先模運算定位我們要插入這個桶的位置
2.判斷插入的桶子是否為空，為空就將鍵值對存入即可，不為空則遍歷到表的最后一個存入，或者更新Node.

- 簡單說說 JDK1.7 中 HashMap 什么情況下會發(fā)生擴容？如何擴容？

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//當size超過臨界閾值threshold，并且即將發(fā)生哈希沖突時進行擴容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

通過以上代碼能夠得知，當發(fā)生哈希沖突并且size大于閾值的時候，需要進行數(shù)組擴容.擴容時，需要新建一個長度為之前數(shù)組2倍的新的數(shù)組，然后將當前的Entry數(shù)組中的元素全部傳輸過去，擴容后的新數(shù)組長度為之前的2倍.

擴容操作發(fā)生在resize（int newCapacity）

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    
    
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
　　　　　//for循環(huán)中的代碼，逐個遍歷鏈表，重新計算索引位置，將老數(shù)組數(shù)據(jù)復制到新數(shù)組中去（數(shù)組不存儲實際數(shù)據(jù)，所以僅僅是拷貝引用而已）
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
　　　　　　　　　 //將當前entry的next鏈指向新的索引位置,newTable[i]有可能為空，有可能也是個entry鏈，如果是entry鏈，直接在鏈表頭部插入。
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

這個方法就是將每個Node遍歷出來，通過key值進行hash擾亂運算后，與length-1取余得到新的下標，放入的流程和put一樣。
http://www.cnblogs.com/chengxiao/p/6059914.html

hashmap容量為2次冪的原因。

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

每一個鍵值對必須調(diào)用這個上面的方法得到位置索引的過程，。length-1 ，比如length=16，得到就是15，為11111，這樣的低位和高位的或運算得到得到的可能會更多，所以分布就更為均勻，從而減少了碰撞的幾率。
https://blog.csdn.net/qq_36523667/article/details/79657400
http://www.cnblogs.com/chengxiao/p/6059914.html

HashMap的實現(xiàn)，與HashSet的區(qū)別

HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調(diào)用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。

當兩個不同的鍵對象的hashcode相同時會發(fā)生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。

https://www.cnblogs.com/beatIteWeNerverGiveUp/p/5709841.html
https://www.cnblogs.com/beatIteWeNerverGiveUp/p/5709841.html

HashSet與HashMap怎么判斷集合元素重復

發(fā)現(xiàn)HashSet是借助HashMap來實現(xiàn)的，存入的元素作為key，利用HashMap中Key的唯一性，來保證HashSet中不出現(xiàn)重復值，所以最終得看HashMap源碼如何判斷元素重復的。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //?。。。。?        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
        }
    }
}

在put可以看見先的得到下標，然后遍歷每一個元素比較hashcode（）和equal（）來判斷是否唯一。
注意：為了保證對象不會出現(xiàn)重復值，被存方的元素必須重寫equal（）。
https://blog.csdn.net/ning109314/article/details/17354839

簡單說說 HashMap 和 LinkedHashMap 的區(qū)別

LinkedHashMap 實現(xiàn)與 HashMap 的不同之處在于，LinkedHashMap 維護著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。該迭代順序通常就是將鍵插入到映射中的順序，如果在映射中重新插入鍵，則插入的順序?qū)⒉皇苡绊?。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數(shù)據(jù)較少時，遍歷起來可能會比 LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關，和容量無關，而HashMap的遍歷速度和他的容量有關。

https://www.cnblogs.com/hubingxu/archive/2012/02/21/2361281.html
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
https://blog.csdn.net/xiyuan1999/article/details/6198394
https://blog.csdn.net/qq_33535433/article/details/80035383
https://blog.csdn.net/lzm1340458776/article/details/37816073

說說你對 LinkedHashSet 的理解及其與 HashSet 的關系？

LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序。這樣使得元素看起 來像是以插入順序保存的，也就是說，當遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。

關系LinkedHashSet繼承與HashSet,但只是在構(gòu)造函數(shù)里調(diào)用父類的構(gòu)造函數(shù)并且傳入LinkedHashMap，而LinkedHashMap內(nèi)部維護的雙向鏈表，這讓LinkedHashSet具有保存迭代順序順序的功能，LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。
https://www.cnblogs.com/Terry-greener/archive/2011/12/02/2271707.html

HashMap是如何解決hash碰撞的？拉鏈法的優(yōu)缺點

利用（JDK1.7以下）拉鏈法，解決hash沖突

hash:散列，是把任意長度的輸入，通過散列算法，變成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種 壓縮映射，也就是說，散列值的空間通常遠小于輸入的空間。不同的輸入可能會散列成相同的輸出，從而不可能從散列值來唯一的確定輸入值。簡單的說，就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。
hash沖突： 就是根據(jù)key即經(jīng)過一個哈希函數(shù)f(key)運算得到的結(jié)果i的作為地址去存放當前的key value鍵值對(這個是hashmap的存值方式)，但是卻發(fā)現(xiàn)算出來的地址上存在另外的鍵值對（不為空），這就成為hash沖突。
鏈地址法（拉鏈法）：JDK1.7 hashmap用的拉鏈法，將哈希值相同的元素以鏈表形式排列，并且表頭的地址為hash表的第i個元素
，在JDK1.8之后 則是一個混合模式，如果單鏈表的節(jié)點大于8，單鏈表會樹化為紅黑樹儲存具有相同hash的元素。
[圖片上傳失敗...(image-50d3cd-1535258600772)]

優(yōu)點：
解決了線性探測所導致的太多的哈希沖突。
刪除結(jié)點相比于開放定址法更容易實現(xiàn)（在線性探測中如果刪除結(jié)點，后面的結(jié)點無法訪問）。
由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應的結(jié)點即可。而對開放地址法構(gòu)造的散列表，刪除結(jié)點不能簡單地將被刪結(jié) 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點上做刪除標記，而不能真正刪除結(jié)點

缺陷：如果相同元素過多，元素在一個桶內(nèi)部鏈接過長，反而導致時間復雜度上升。解決思路是桶中元素不再指向鏈表，而指向一個紅黑樹
指針需要額外的空間，故當結(jié)點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

Hash怎么防止碰撞

防止還是難以防止，但是可以減少Hash碰撞

• 構(gòu)造hash時 增大initialCapacity，減少loadFactor
• 重寫hashCode方法，增加得到hash的復雜度
• 傳入類的時候按照規(guī)則重寫自定義類equal方法

hashmap的參數(shù)及影響性能的關鍵參數(shù)：加載因子和初始容量。

簡單說說你對 HashMap 構(gòu)造方法中 initialCapacity（初始容量）、loadFactor（加載因子）的理解

initialCapacity：初始化hashTable的長度，是影響擴容閥值因素之一，默認16，擴容時候數(shù)組長度會變成2倍，不管如何內(nèi)部會調(diào)用tableSizeFor（）使用位運算 找到大于或等于該值的最小2的冪，作為Capacity儲存，而initialCapacity將會被棄用。
loadFactor：
在節(jié)點均勻分布在桶數(shù)組中的條件下，可以調(diào)節(jié)負載因子。
節(jié)負載因子低時，HashMap容納的鍵值對變少了，擴容時候，重寫將鍵值對儲存新的通數(shù)組里，這樣hash碰撞就降低了，鏈表變短了，增刪查改的操作效率就會變高。
節(jié)負載因子高的時候，HashMap容納的鍵值對變高，空間利用率變高，鏈表邊長，效率變低，時間和空間的互換

HashSet 和 TreeSet

HashSet、LinkedHashSet與TreeSet有什么區(qū)別，應用場景是什么？

https://www.cnblogs.com/Terry-greener/archive/2011/12/02/2271707.html
https://blog.csdn.net/StemQ/article/details/66477615
http://m.itdecent.cn/p/14bd5d9654fe
http://www.coolblog.xyz/2018/01/11/TreeMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

HashSet使用哈希表實現(xiàn)的，元素是無序的。添加、刪除操作時間復雜度都是O(1)。
TreeSet內(nèi)部結(jié)構(gòu)是一個樹結(jié)構(gòu)(紅黑樹)，元素是有序的，添加、刪除操作時間復雜度為O(log(n))，并且提供了first(), last(), headSet(), tailSet()等方法來處理有序集合。?
TreeSet不允許重復，不允許null值（如果有基于null的比較器，就可以允許為null），默認按升序排列。
LinkedHashSet是HashSet的子類，是介于HashSet 和 TreeSet之間，內(nèi)部是一個雙向鏈表結(jié)構(gòu)，時間復雜度是O(1)。允許null值，保留插入順序，非線程安全。

簡而言之,如何你需要的是一個快速的集合，建議你使用HashSet，如果你需要的是一個排序集合，請選擇TreeSet，如果你需要一套能夠存儲插入順序的集合,請使用LinkedHashSet。

請使用 Java 集合實現(xiàn)一個簡約優(yōu)雅的 LRU 容器

由于 LinkedHashMap 天生支持插入順序或者訪問順序的 key-value 對，而 LRU 算法的核心恰巧用到它的訪問順序特性，即對一個鍵執(zhí)行 get、put 操作后其對應的鍵值對會移到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒被訪問的。LinkedHashMap 有一個 boolean 類型的 accessOrder 參數(shù)，當該參數(shù)為 true 時則按照元素最后訪問時間在雙向鏈表中排序，為 false 則按照插入順序排序，默認為 false，所以這里需要的操作就是 accessOrder 為 true 的情況。
。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
            private int maxEntries;//maxEntries 最大緩存?zhèn)€數(shù)

            public LRUCache(int maxEntries) {
                super(16, 0.75f, true);
                this.maxEntries = maxEntries;
            }

            //在添加元素到LinkedHashMap后會調(diào)用這個方法，傳遞的參數(shù)是最久沒被訪問的鍵值對，
            // 如果這個方法返回true則這個最久的鍵值對就會被刪除，LinkedHashMap的實現(xiàn)總是返回false，
            // 所以容量沒有限制。
            @Override
            protected boolean removeEldestEntry(Entry<K, V> eldest) {
                return size() > maxEntries;
            }
        }

可以看見實現(xiàn)的簡約 LRU 容器核心優(yōu)雅點就是充分利用了 LinkedHashMap 的有序性特性和容量限制特性。

- List/Set/Map三者的區(qū)別.

簡單說說你理解的 List 、Map、Set、Queue 的區(qū)別和關系

List 和 Map 的實現(xiàn)方式以及存儲方式

List,Set,Map的區(qū)別，實現(xiàn)方式以及存儲方式。

集合的接口和具體實現(xiàn)類，介紹

容器類介紹以及之間的區(qū)別

集合類相關over

https://blog.csdn.net/u013825231/article/details/52027323
https://blog.csdn.net/lipeng88888888/article/details/78456047
https://blog.csdn.net/chuntiandejiaobu10/article/details/52350338
https://blog.csdn.net/ice197983/article/details/1546848
http://www.cnblogs.com/goody9807/p/6431501.html

Collection

一組"對立"的元素，通常這些元素都服從某種規(guī)則

• List必須保持元素特定的順序
• Set不能有重復元素
• Queue保持一個隊列(先進先出)的順序

2) Map

一組成對的"鍵值對"對象

Collection和Map的區(qū)別在于容器中每個位置保存的元素個數(shù):

• Collection 每個位置只能保存一個元素(對象)
• Map保存的是"鍵值對"，就像一個小型數(shù)據(jù)庫。我們可以通過"鍵"找到該鍵對應的"值"

List

共性：有序 可以重復
List集合特征：

• 允許重復元素添加
• 有序：放入的順序和取出的順序是一樣的
• 一個List可以生成ListIterator,使用它可以從兩個方向遍歷List,也可以從List中間插入和移除元素。

List接口主要實現(xiàn)類包括：

• ArrayList() 代表長度可以改變得數(shù)組。可以對元素進行隨機的訪問，向ArrayList()中插入與刪除元素的速度慢。沒有線程安全，性能高
• LinkedList()雙向鏈表式算法: 在實現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)。每次操作插入刪除，只需要修改元素的后置節(jié)點引用，不需要后面元素移動位置，插入和刪除速度快，每次都要從開始往后依次查找，訪問速度慢。

List接口對Collection進行了簡單的擴充，它的具體實現(xiàn)類常用的有ArrayList和LinkedList。你可以將任何東西放到一個List容器中，并在需要時從中取出。ArrayList從其命名中可以看出它是一種類似數(shù)組的形式進行存儲，因此它的隨機訪問速度極快，而LinkedList的內(nèi)部實現(xiàn)是鏈表，它適合于在鏈表中間需要頻繁進行插入和刪除操作。在具體應用時可以根據(jù)需要自由選擇。前面說的Iterator只能對容器進行向前遍歷，而ListIterator則繼承了Iterator的思想，并提供了對List進行雙向遍歷的方法。

Set集合

對象元素不能重復，Set的元素必須定義equals()方法以確保對象的唯一性。
可排序
也是Collection的一種擴展加入 ，Set與Collection有完全一樣的接口

set接口主要實現(xiàn)類包括：

• HashSet：能快速定位一個元素，但是你放到HashSet中的對象需要實現(xiàn)hashCode()方法，它使用了前面說過的哈希碼的算法。該也是線程不安全的，它不允許出現(xiàn)重復元素；允許包含值為null的元素，但最多只能有一個null元素。不能保證元素的插入順序，添加也是通過add進行添加的，而輸出則是通過迭代Iteratori=hash.iterator();來實現(xiàn)的。

• 而TreeSet則將放入其中的元素按序存放，這就要求你放入其中的對象是可排序的，這就用到了集合框架提供的另外兩個實用類Comparable和Comparator。一個類是可排序的，它就應該實現(xiàn)Comparable接口。有時多個類具有相同的排序算法，那就不需要在每分別重復定義相同的排序算法，只要實現(xiàn)Comparator接口即可。

map接口：

是一種把鍵對象和值對象進行關聯(lián)的容器，而一個值對象又可以是一個Map，依次類推，這樣就可形成一個多級映射。一個Map容器中的鍵對象不允許重復。當然在使用過程中，某個鍵所對應的值對象可能會發(fā)生變化，這時會按照最后一次修改的值對象與鍵對應。對于值對象則沒有唯一性的要求。你可以將任意多個鍵都映射到一個值對象上，這不會發(fā)生任何問題（不過對你的使用卻可能會造成不便，你不知道你得到的到底是那一個鍵所對應的值對象）。
Map有兩種比較常用的實現(xiàn)：

• HashMap HashMap也用到了哈希碼的算法，以便快速查找一個鍵，無序
• TreeMap。TreeMap則是對鍵按序存放，因此它便有一些擴展的方法，比如firstKey(),lastKey()等，你還可以從TreeMap中指定一個范圍以取得其子Map。鍵和值的關聯(lián)很簡單，用pub(Object key,Object value)方法即可將一個鍵與一個值對象相關聯(lián)。用get(Object key)可得到與此key對象所對應的值對象。

Queue

用于模擬"隊列"這種數(shù)據(jù)結(jié)構(gòu)(先進先出 FIFO)。隊列的頭部保存著隊列中存放時間最長的元素，隊列的尾部保存著隊列中存放時間最短的元素。新元素插入(offer)到隊列的尾部，訪問元素(poll)操作會返回隊列頭部的元素，隊列不允許隨機訪問隊列中的元素。結(jié)合生活中常見的排隊就會很好理解這個概念。

• PriorityQueue
  PriorityQueue并不是一個比較標準的隊列實現(xiàn)，PriorityQueue保存隊列元素的順序并不是按照加入隊列的順序，而是按照隊列元素的大小進行重新排序，這點從它的類名也可以看出來

• Deque
  Deque接口代表一個"雙端隊列"，雙端隊列可以同時從兩端來添加、刪除元素，因此Deque的實現(xiàn)類既可以當成隊列使用、也可以當成棧使用

• ArrayDeque
  是一個基于數(shù)組的雙端隊列，和ArrayList類似，它們的底層都采用一個動態(tài)的、可重分配的Object[]數(shù)組來存儲集合元素，當集合元素超出該數(shù)組的容量時，系統(tǒng)會在底層重新分配一個Object[]數(shù)組來存儲集合元素

這篇文章贊 ：https://blog.csdn.net/KingCat666/article/details/75579632

List, Set, Map是否繼承自Collection接口?

• List, Set繼承Collection接口 ，List接口對Collection進行了簡單的擴充，而Set也是Collection的一種擴展加入 ，Set與Collection有完全一樣的接口，Collection 每個位置只能保存一個元素(對象)。
• Map 是一種把鍵對象和值對象進行關聯(lián)的容器，沒有繼承于Collection接口，Map就像一個小型數(shù)據(jù)庫。我們可以通過"鍵"找到該鍵對應的"值"。

Collection 和 Collections的區(qū)別

• java.util.Collection 是一個集合接口。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現(xiàn)。Collection接口的意義是為各種具體的集合提供了最大化的統(tǒng)一操作方式。
• java.util.Collections 是一個包裝類。它包含有各種有關集合操作的靜態(tài)多態(tài)方法。此類不能實例化，就像一個工具類，服務于Java的Collection框架。
  http://pengcqu.iteye.com/blog/492196

hashtable和hashmap異同。

• HashTable 基于 Dictionary 類，而 HashMap 是基于 AbstractMap。Dictionary 是任何可將鍵映射到相應值的類- 的抽象父類，而 AbstractMap 是基于 Map 接口的實現(xiàn)，它以最大限度地減少實現(xiàn)此接口所需的工作。
• HashMap 的 key 和 value 都允許為 null，而 Hashtable 的 key 和 value 都不允許為 null。HashMap 遇到 key 為 null 的時候，調(diào)用 putForNullKey 方法進行處理，而對 value 沒有處理；Hashtable遇到 null，直接返回 NullPointerException。
• Hashtable 方法是同步，而HashMap則不是。我們可以看一下源碼，Hashtable 中的幾乎所有的 public 的方法都是 synchronized 的，而有些方法也是在內(nèi)部通過 synchronized 代碼塊來實現(xiàn)。所以有人一般都建議如果是涉及到多線程同步時采用 HashTable，沒有涉及就采用 HashMap，但是在 Collections 類中存在一個靜態(tài)方法：synchronizedMap()，該方法創(chuàng)建了一個線程安全的 Map 對象，并把它作為一個封裝的對象來返回。HashTable是線程安全的.

為什么hashtable被棄用？

hashtable的線程安全的策略實現(xiàn)代價太大，而且簡單粗暴，get/put的方法操作都是synchronized，這相當于給整個hash表加了一個大大的鎖，多線程訪問時候所有操作都得串行，在激烈的并發(fā)場景的性能會變得相當?shù)牟睢?/p>

hashtable線程安全、synchronized加鎖

1. hashtable線程是安全，他和hashmap類似內(nèi)部也是實現(xiàn)了拉鏈法的hash表，但是像put/get操作方法加上去synchronized關鍵詞，使得多線程操作該容器時串行，保證了線程安全。

concurrenthashmap的插入操作是直接操作數(shù)組中的鏈表嗎？

JDK1.7 版本 第一步定位Segment并且確定Segemnt已經(jīng)初始化、 2，調(diào)用segment這個加鎖的put的方法3.重新定位hash在數(shù)組的位置，如果在Buket位置上已存在鏈表就得操作鏈表進行遍歷插入到表尾
JDK1.8 版本

• 第一步根據(jù)hash定位索引位置，并且獲取對應的索引位置（用Usafe.getObjectVolatile直接獲得指定內(nèi)存的數(shù)據(jù)保證拿到最新的數(shù)據(jù)）
• 如果 f ==null 用CAS直接插入Node
  • 如果CAS成功，說明已經(jīng)插入，然后判斷是不是要擴容
  • 如果失敗，自旋嘗試在插入
• 如果f的hash是-1 ，則說明其他線程正在擴容，
• 其余情況把新的Node節(jié)點按鏈表或紅黑樹的方式插入到合適的位置，這個過程采用同步內(nèi)置鎖實現(xiàn)并發(fā)。

說明1.7版本是先確定sgement的位置然后上鎖調(diào)用其put方法插入鏈表，而1.8版本則是直接插入，不過如果是鏈表插入上的是同步鎖

https://www.cnblogs.com/chengxiao/p/6842045.html
http://m.itdecent.cn/p/c0642afe03e0

concurrenthashmap相比于hashtable做的優(yōu)化、segment的概念、concurrenthashmap高效的原因

• HashTable的線程安全使用的是一個單獨的全部Map范圍的鎖，ConcurrentHashMap拋棄了HashTable的單鎖機制，使用了鎖分離技術，使得多個修改操作能夠并發(fā)進行,只有進行SIZE()操作時ConcurrentHashMap會鎖住整張表。

• HashTable的put和get方法都是同步方法， 而ConcurrentHashMap的get方法多數(shù)情況都不用鎖，put方法需要鎖。

但是ConcurrentHashMap不能替代HashTable,因為兩者的迭代器的一致性不同的，hash table的迭代器是強一致性的，而concurrenthashmap是弱一致的。 ConcurrentHashMap的get，clear，iterator 都是弱一致性的。
hashtable是全局采用一個大鎖，使用synchronized來保證線程安全，但是在競爭激烈的情況下HashTable的效率非常低下，但是在concurrenthashmap中則是把桶數(shù)組分為多個sgement，并給每個segment上重入鎖ReentrantLock鎖的分段鎖形式

Segment繼承了ReentrantLock，所以它就是一種可重入鎖（ReentrantLock)。在ConcurrentHashMap，一個Segment就是一個子哈希表，Segment里維護了一個HashEntry數(shù)組，并發(fā)環(huán)境下，對于不同Segment的數(shù)據(jù)進行操作是不用考慮鎖競爭的。（就按默認的ConcurrentLeve為16來講，理論上就允許16個線程并發(fā)執(zhí)行，有木有很酷）

ConcurrentHashMap之所以高效是因為它，把map表劃分為了多個Segemnt，并且每個Segment繼承了ReentrantLock，這樣更好的降低了鎖的粒度，
http://www.cnblogs.com/ynyhl/p/9317688.html
https://blog.csdn.net/MBuger/article/details/62418754
https://blog.csdn.net/hitxueliang/article/details/24734861

SpareArray做了哪些優(yōu)化？

• 使用int[]數(shù)組存放key，避免了HashMap中基本數(shù)據(jù)類型需要裝箱的步驟
• 不需要額外的結(jié)構(gòu)體，單個元素的存儲成本更低
• 數(shù)據(jù)量小的情況下，隨機訪問的效率更高

簡單說一說SpareArray的插入流程？

public void put(int key, E value) {
    // 首先通過二分查找去 key 數(shù)組中查找要插入的 key，返回索引
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
    if (i >= 0) {
      // 如果 i>=0 說明數(shù)組中已經(jīng)有了該key，則直接覆蓋原來的值
        mValues[i] = value;
    } else {
      // 取反，這里得到的i應該是最適合該key的插入位置，具體怎么得到的，后面會說
        i = ~i;
        // 如果索引小于當前已經(jīng)存放的長度，并且這個位置上的值為DELETED(即被標記為刪除的值)
        if (i < mSize && mValues[i] == DELETED) {
          // 直接賦值并返回，注意 size 不需要增加
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }
        // 到這一步說明直接賦值失敗，檢查當前是否被標記待回收且當前存放的長度已經(jīng)大于或等于了數(shù)組長度
        if (mGarbage && mSize >= mKeys.length) {
            // 回收數(shù)組中應該被干掉的值
            gc();
            // 重新再獲取一下索引，因為數(shù)組發(fā)生了變化
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }
        // 最終在 i 位置上插入鍵與值，并且size ＋1
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

http://extremej.itscoder.com/sparsearray_source_analyse/

為什么 ArrayList 的增加或刪除操作相對來說效率比較低？能簡單解釋下為什么嗎？

只有刪除，或者是添加插入指定的位置時候才會出現(xiàn)效率變低的問題，因為不管添加刪除，都得移動添加刪除位置后面得元素導致時間復雜度急劇上升。

image

image

ArrayList和Vector的區(qū)別 ，ArrayList與LinkedList有什么區(qū)別

- 簡單說說 ArrayList 和 Vector 的區(qū)別

ArrayList和Vector的區(qū)別

• ArrayList和Vector都實現(xiàn)了List接口，底層都是基于Java數(shù)組來存儲集合元素

• ArrayList使用transient修飾了elementData數(shù)組，而Vector則沒有

• Vector是ArrayList的線程安全版本，用synchronized上同步鎖實現(xiàn)的，一個個大大的鎖了解一下

• 容量擴充 ArrayList為0.5倍+1，而Vector若指定了增長系數(shù)，則新的容量=”原始容量+增長系數(shù)”, 否則增長為原來的1倍
  https://www.cnblogs.com/skywang12345/p/3308833.html#a4
  https://blog.csdn.net/itmyhome1990/article/details/76033175

ArrayList與LinkedList有什么區(qū)別

1. ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，而LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)；
2. 對于隨機訪問get和set，ArrayList要優(yōu)于LinkedList，因為LinkedList要移動指針；
3. 對于添加和刪除操作add和remove，一般大家都會說LinkedList要比ArrayList快，因為ArrayList要移動數(shù)據(jù)。但是實際情況并非這樣，對于添加或刪除，LinkedList和ArrayList并不能明確說明誰快誰慢。

• 添加刪除情況 ：從源碼可以看出來linkedhashmap耗時的地方主要是鏈表的遍歷（盡管以及判斷是否從左右邊開始了）
  而arrayList耗時的地方就是System.arraycopy，讓index后面的元素的所有元素都移動。
• 所以當插入的數(shù)據(jù)量很小時，兩者區(qū)別不太大，當插入的數(shù)據(jù)量大時，大約在容量的1/10之前，LinkedList會優(yōu)于ArrayList，在其后就劣與ArrayList，且越靠近后面越差。

https://blog.csdn.net/eson_15/article/details/51145788

ArrayList 與 LinkedList 使用普通 for 循環(huán)遍歷誰快誰慢？為什么？

https://blog.csdn.net/zhzzhz123456/article/details/53323093

Arraylist 的動態(tài)擴容機制是如何自動增加的？簡單說說你理解的流程

在add方法里面判斷是不是需要擴容（size+1），如果是需要就開始擴容，擴容計算出最小的容量，一般是初始化的開始，算出當然容量的下限，如果當前容量減去數(shù)組的長度大于0就開始擴容，擴容采用位運算得到擴容后的容量大小，然后進行邊界檢查，最后把老數(shù)組的元素copy到新的數(shù)組中，這樣擴容就完成了，因為ArrayList的底部容器本身是數(shù)組，所以位置完全相同，就不存在計算擴容后還需要重新計算位置的問題。
http://www.coolblog.xyz/2018/01/28/ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
https://blog.csdn.net/u010176014/article/details/52073339

簡單說說 Array 和 ArrayList 的區(qū)別？

應該是完美的答案：
http://blog.qianlicao.cn/translate/2016/03/09/array-vs-arraylist/

http://www.coolblog.xyz/2018/01/18/HashMap-%E6%BA%90%E7%A0%81%E8%AF%A6%E7%BB%86%E5%88%86%E6%9E%90-JDK1-8/
https://blog.csdn.net/caisini_vc/article/details/52452498

為什么現(xiàn)在都不提倡使用 Vector 了

答：因為 Vector 實現(xiàn)并發(fā)安全的原理是在每個操作方法上加鎖，這些鎖并不是必須要的，在實際開發(fā)中一般都是通過鎖一系列的操作來實現(xiàn)線程安全，也就是說將需要同步的資源放一起加鎖來保證線程安全，如果多個 Thread 并發(fā)執(zhí)行一個已經(jīng)加鎖的方法，但是在該方法中又有 Vector 的存在，Vector 本身實現(xiàn)中已經(jīng)加鎖了，雙重鎖會造成額外的開銷，即 Vector 同 ArrayList 一樣有 fail-fast 問題（即無法保證遍歷安全），所以在遍歷 Vector 操作時又得額外加鎖保證安全，還不如直接用 ArrayList 加鎖性能好，所以在 JDK 1.5 之后推薦使用 java.util.concurrent 包下的并發(fā)類。此外 Vector 是一個從 JDK1.0 就有的古老集合，那時候 Java 還沒有提供系統(tǒng)的集合框架，所以在 Vector 里提供了一些方法名很長的方法（如 addElement(Object obj)，實際上這個方法和 add(Object obj) 沒什么區(qū)別），從 JDK1.2 以后 Java 提供了集合框架，然后就將 Vector 改為實現(xiàn) List 接口，從而導致 Vector 里有一些重復的方法。

- 為什么使用 for-each 時調(diào)用 List 的 remove 方法元素會拋出ConcurrentModificationException 異常？

 int expectedModCount = modCount;
 
  final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    
  public E remove(int index) {
    rangeCheck(index);

    modCount++;
    // 返回被刪除的元素值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 將 index + 1 及之后的元素向前移動一位，覆蓋被刪除值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 將最后一個元素置空，并將 size 值減1                
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

問題出在迭代器，其實for-each循環(huán)會在編譯的時候轉(zhuǎn)換為迭代器，在迭代的過程中remove會調(diào)用使得modcount增加，而在代碼中expectedModCount的值還是原來那個modcount的值，導致拋出異常。
這篇文章的結(jié)尾做了具體的闡述：
http://www.coolblog.xyz/2018/01/28/ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/

什么是 Vector 和 Stack，各有什么特點？

Vector 是線程安全的動態(tài)數(shù)組，同 ArrayList 一樣繼承自 AbstractList 且實現(xiàn)了 List、RandomAccess、Cloneable、Serializable 接口，內(nèi)部實現(xiàn)依然基于數(shù)組，Vector 與 ArrayList 基本是一致的，唯一不同的是 Vector 是線程安全的，會在可能出現(xiàn)線程安全的方法前面加上 synchronized 關鍵字，其和 ArrayList 類似，隨機訪問速度快，插入和移除性能較差（數(shù)組原因），支持 null 元素，有順序，元素可以重復，線程安全。

Stack 是繼承自 Vector 基于動態(tài)數(shù)組實現(xiàn)的線程安全棧，不過現(xiàn)在已經(jīng)不推薦使用了，Stack 是并發(fā)安全的后進先出，實現(xiàn)了一些?；静僮鞯姆椒ǎㄆ鋵嵅⒉皇侵荒芎筮M先出，因為繼承自 Vector，所以可以有很多操作，嚴格說不是一個棧）。其共同點都是使用了方法鎖（即 synchronized）來保證并發(fā)安全的。

Collections.emptyList() 與 new ArrayList() 有什么區(qū)別

在這篇文章中提到如果你想返回一個空的List最好的方式就是返回Collections.emptyList（），且支持泛型，但是如果是return new ArrayList（）的話，ArrayList()在初始化時會占用一定的資源增加開銷，這不是一個好的選擇。
https://blog.csdn.net/liyuming0000/article/details/49474659

容器類中fastfail的概念

fail-fast 機制是java集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的內(nèi)容進行操作時，就可能會產(chǎn)生fail-fast事件。

例如：當某一個線程A通過iterator去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。
解決方法:改換成線程安全的類。
若 “modCount 不等于 expectedModCount”，則拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。

https://blog.csdn.net/coslay/article/details/44891035

CopyOnWriteArrayList的了解。

CopyOnWriteArrayList這是一個ArrayList的線程安全的變體，其原理大概可以通俗的理解為:初始化的時候只有一個容器，很常一段時間，這個容器數(shù)據(jù)、數(shù)量等沒有發(fā)生變化的時候，大家(多個線程)，都是讀取(假設這段時間里只發(fā)生讀取的操作)同一個容器中的數(shù)據(jù)，所以這樣大家讀到的數(shù)據(jù)都是唯一、一致、安全的，但是后來有人往里面增加了一個數(shù)據(jù)，這個時候CopyOnWriteArrayList 底層實現(xiàn)添加的原理是先copy出一個容器(可以簡稱副本)，再往新的容器里添加這個新的數(shù)據(jù)，最后把新的容器的引用地址賦值給了之前那個舊的的容器地址，但是在添加這個數(shù)據(jù)的期間，其他線程如果要去讀取數(shù)據(jù)，仍然是讀取到舊的容器里的數(shù)據(jù)。
https://blog.csdn.net/likailonghaha/article/details/53405895
https://blog.csdn.net/hua631150873/article/details/51306021

請使用 LinkedList 模擬一個堆?；蜿犃械臄?shù)據(jù)結(jié)構(gòu)

https://blog.csdn.net/shineflowers/article/details/41746777

簡單說說 Iterator 和 ListIterator 的區(qū)別？

https://blog.csdn.net/yueying521314/article/details/80919095
https://www.nowcoder.com/questionTerminal/9dbbd35ff35e4e008fdd792c2b539940

為什么說集合的不同列表應該選擇不同的遍歷方式，舉例談談你的認識？

https://blog.csdn.net/zhzzhz123456/article/details/53323093
https://blog.csdn.net/u012552052/article/details/45008237

并發(fā)集合了解哪些

之前聊到的hashtable concurrentHashmap CopyOnWriteArrayList Vector ..都可以聊
http://youyu4.iteye.com/blog/2352846

簡單說說 Comparable 和 Comparator 的區(qū)別和場景？

區(qū)別

Comparable可以認為是一個內(nèi)比較器，實現(xiàn)了Comparable接口的類有一個特點，就是這些類是可以和自己比較的，至于具體和另一個實現(xiàn)了Comparable接口的類如何比較，則依賴compareTo方法的實現(xiàn)，compareTo方法也被稱為自然比較方法。如果開發(fā)者add進入一個Collection的對象想要Collections的sort方法幫你自動進行排序的話，那么這個對象必須實現(xiàn)Comparable接口。
Comparator可以認為是是一個外比較器，個人認為有兩種情況可以使用實現(xiàn)Comparator接口的方式：
1、一個對象不支持自己和自己比較（沒有實現(xiàn)Comparable接口），但是又想對兩個對象進行比較
2、一個對象實現(xiàn)了Comparable接口，但是開發(fā)者認為compareTo方法中的比較方式并不是自己想要的那種比較方式

場景

1. 如果實現(xiàn)類沒有實現(xiàn)Comparable接口，又想對兩個類進行比較（或者實現(xiàn)類實現(xiàn)了Comparable接口，但是對compareTo方法內(nèi)的比較算法不滿意），那么可以實現(xiàn)Comparator接口，自定義一個比較器，寫比較算法
2. 如果比較的方法只要用在一個類中，用該類實現(xiàn)Comparable接口就可以。
3. 如果比較的方法在很多類中需要用到，就自己寫個類實現(xiàn)Comparator接口，這樣當要比較的時候把實現(xiàn)了Comparator接口的類傳過去就可以，省得重復造輪子。這也是為什么Comparator會在java.util包下的原因。

https://blog.csdn.net/u011240877/article/details/53399019
https://www.cnblogs.com/linbingdong/p/5300720.html

簡單說說 EnumMap 的實現(xiàn)原理

簡單談談你對 EnumMap 的理解及其特點與應用場景？

簡單談談你對 EnumMap 的理解及其特點與應用場景？

簡單說說 EnumMap 的實現(xiàn)原理

http://m.itdecent.cn/p/d842893c4cb2
https://mp.weixin.qq.com/s?__biz=MzIxOTI1NTk5Nw==&mid=2650047360&idx=1&sn=129ffbc5b963b5d6a692aae595e2b402&chksm=8fde2652b8a9af446be044953353fc89ea69627e472969fc7b4e9f32d10565c80b584d785ff5&scene=21#wechat_redirect

說說 EnumSet 怎么用，其基本原理是什么

https://www.cnblogs.com/swiftma/p/6044718.html
https://blog.csdn.net/bolink5/article/details/4201384

簡單說說什么是 Deque 以及 ArrayDeque 與 LinkedList 的區(qū)別及特點

Deque 是一個雙端隊列接口，Deque 擴展了 Queue，有隊列的所有方法，還可以看做棧，有棧的基本方法 push/pop/peek，還有明確的操作兩端的方法 addFirst/removeLast 等，主要如下：

//將指定元素插入雙向隊列開頭
        void addFirst (Object e );
        // 將指定元素插入雙向隊列末尾
        void addLast (Object e );
        // 返回對應的迭代器，以逆向順序來迭代隊列中的元素
        Iterator descendingIterator ();
        // 獲取但不刪除雙向隊列的第一個元素
        Object getFirst ();
        // 獲取但不刪除雙向隊列的最后一個元素 
        Object getLast ();
        // 將指定元素插入雙向隊列開頭 
        boolean offerFirst (Object e );
        // 將指定元素插入雙向隊列結(jié)尾 
        boolean offerLast (Object e );
        // 獲取但不刪除雙向隊列的第一個元素，如果雙端隊列為空則返回 null 
        Object peekFirst ();
        // 獲取但不刪除雙向隊列的最后一個元素，如果此雙端隊列為空則返回 null 
        Object peekLast ();
        // 獲取并刪除雙向隊列的第一個元素，如果此雙端隊列為空則返回 null
        Object pollFirst ();
        // 獲取并刪除雙向隊列的最后一個元素，如果此雙端隊列為空則返 null 
        Object pollLast ();
        // 退棧出該雙向隊列中的第一個元素 
        Object pop ();
        // 將元素入棧進雙向隊列棧中
        void push (Object e );
        // 獲取并刪除該雙向隊列的第一個元素 
        Object removeFirst ();
        // 刪除雙向隊列第一次出現(xiàn)的元素 e 
        Object removeFirstOccurrence (Object e );
        // 獲取并刪除雙向隊列的最后一個元素 
        removeLast();
        // 刪除雙向隊列最后一次出現(xiàn)的元素 e 
        removeLastOccurrence(Object e);

LinkedList 是一個比較奇怪的類，其即實現(xiàn)了 List 接口又實現(xiàn)了 Deque 接口（Deque 是 Queue 的子接口），而 LinkedList 的實現(xiàn)是基于雙向鏈表結(jié)構(gòu)的，其容量沒有限制，是非并發(fā)安全的隊列，所以不僅可以當成列表使用，還可以當做雙向隊列使用，同時也可以當成棧使用（因為還實現(xiàn)了 pop 和 push 方法）。此外 LinkedList 的元素可以為 null 值。

ArrayDeque 是一個用數(shù)組實現(xiàn)的雙端隊列 Deque，為滿足可以同時在數(shù)組兩端插入或刪除元素的需求，該數(shù)組還必須是循環(huán)的，即循環(huán)數(shù)組（circular array），也就是說數(shù)組的任何一點都可能被看作起點或者終點，ArrayDeque 是非線程安全的，當多個線程同時使用的時候需要手動同步，此外該容器不允許放 null 元素，同時與 ArrayList 和 LinkedList 不同的是沒有索引位置的概念，不能根據(jù)索引位置進行操作。
http://m.itdecent.cn/p/d842893c4cb2

簡單說說 ArrayDeque 與 LinkedList 的適用場景？

ArrayDeque 和 LinkedList 都實現(xiàn)了 Deque 接口，如果只需要 Deque 接口且從兩端進行操作則一般來說 ArrayDeque 效率更高一些，如果同時需要根據(jù)索引位置進行操作或經(jīng)常需要在中間進行插入和刪除操作則應該優(yōu)先選 LinkedList 效率高些，因為 ArrayDeque 實現(xiàn)是循環(huán)數(shù)組結(jié)構(gòu)（即一個動態(tài)擴容數(shù)組，默認容量 16，然后通過一個 head 和 tail 索引記錄首尾相連），而 LinkedList 是基于雙向鏈表結(jié)構(gòu)的。

http://m.itdecent.cn/p/d842893c4cb2

簡單說說什么是 Queue 以及 PriorityQueue 與 LinkedList 的區(qū)別及特點？

首先 Queue 是一種模擬 FIFO 隊列的數(shù)據(jù)結(jié)構(gòu)，新元素插入（offer）到隊列的尾部，訪問元素（poll）返回隊列頭部，一般隊列不允許隨機訪問隊列中的元素。Queue 接口主要定義了如下幾個方法：

//將指定元素加入隊列尾部 
        void add (Object e );
// 獲取隊列頭部元素，但是不刪除該元素，如果隊列為空拋出 NoSuchElementException 異常
        Object element ();
// 將指定元素加入隊列尾部（當使用有容量限制的隊列時此方法比 add(Object e) 更好）
        boolean offer (Object e );
// 獲取隊列頭部元素，但是不刪除該元素，如果隊列為空返回 null 
        Object peek ();
// 獲取隊列頭部元素并刪除該元素，如果隊列為空則返回 null 
        Object poll ();
// 獲取隊列頭部元素并刪除該元素，如果隊列為空拋出 NoSuchElementException 異常 
        Object remove ();

LinkedList 是一個比較奇怪的類，其即實現(xiàn)了 List 接口又實現(xiàn)了 Deque 接口（Deque 是 Queue 的子接口），而 LinkedList 的實現(xiàn)是基于雙向鏈表結(jié)構(gòu)的，其容量沒有限制，是非并發(fā)安全的隊列，所以不僅可以當成列表使用，還可以當做雙向隊列使用，同時也可以當成棧使用（因為還實現(xiàn)了 pop 和 push 方法）。此外 LinkedList 的元素可以為 null 值。

PriorityQueue 是一個優(yōu)先級列表隊列，因為 PriorityQueue 保存隊列元素的順序并不是按加入隊列的順序，而是按隊列元素的大小進行重新排序，所以當調(diào)用 peek 或者 pull 方法從隊列頭取元素時并不是取出最先進入隊列的元素，而是取出隊列中最小的元素（默認順序），所以說 PriorityQueue 實質(zhì)違反了 FIFO 隊列的基本原則，從而成了優(yōu)先級列表實現(xiàn)，同時 PriorityQueue 的實現(xiàn)是基于動態(tài)擴容數(shù)組的二叉樹堆結(jié)構(gòu)，其最大容量長度為 Int 大小，是非并發(fā)安全的隊列。此外 PriorityQueue 的元素不可為 null 值。

PriorityQueue 是怎么確定哪一個元素的優(yōu)先級最高的？

PriorityQueue 確定最高優(yōu)先級元素使用的是堆數(shù)據(jù)結(jié)構(gòu)，因為堆是一棵完全樹，堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點值的，常見的堆有二叉堆、斐波那契堆等，二叉堆是完全二叉樹或者是近似完全二叉樹的一種特殊堆，其分為最大堆和最小堆，最大堆中父結(jié)點值總是大于或等于任何一個子節(jié)點值，最小堆中父結(jié)點值總是小于或等于任何一個子節(jié)點值，由于二叉堆一直是自左向右自上向下一層層填充的，所以其可以用數(shù)組來表示而不是用鏈表，PriorityQueue 就是采用了基于動態(tài)數(shù)組的二叉堆來確定優(yōu)先級。

談談你對二叉堆數(shù)據(jù)結(jié)構(gòu)的理解及在 PriorityQueue 中的實現(xiàn)？

http://m.itdecent.cn/p/b308d23f3775

談你對 ArrayDeque 主要方法實現(xiàn)原理的認識？

http://m.itdecent.cn/p/5763d9c1c321

http://www.cnblogs.com/chengxiao/p/6059914.html
https://blog.csdn.net/qq_27093465/article/details/52269862
https://blog.csdn.net/justloveyou_/article/details/52464440
http://m.itdecent.cn/p/4d3cb99d7580
http://m.itdecent.cn/p/550cea8c25ef

nextTable 是新的兩倍數(shù)組
ForwardingNode