ArrayList和LinkedList區(qū)別？

1.是否保證線程安全： ArrayList和LinkedList都是不同步的，也就是不保證線程安全。
2.底層數(shù)據(jù)結(jié)構(gòu)： ArrayList底層使用的是Object數(shù)組；LinkedList底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)（注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別）；
插入和刪除是否受元素位置的影響： ArrayList采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。比如執(zhí)行add(E e)方法的時(shí)候，ArrayList會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是O(1)。但是如果要在指定位置i插入和刪除元素的話（add(int index,E element)）時(shí)間負(fù)責(zé)度就為O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的（n-i）個(gè)元素都是要執(zhí)行向后位/向前移一位的操作。ListedList采用鏈表存儲(chǔ)，所以插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響。都是近似O(1)而數(shù)組為近似O(n)。
4.是否支持快速隨機(jī)訪問(wèn)：LiskedList不支持高效的隨機(jī)元素訪問(wèn)，而ArrayList支持?？焖匐S機(jī)訪問(wèn)就就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象（對(duì)應(yīng)于get(int index)方法）。
內(nèi)存空間占用： ArrayList的空間浪費(fèi)主要體現(xiàn)在List列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。

補(bǔ)充內(nèi)容:RandomAccess接口

public interface RandomAccess {
}

查看源碼我們發(fā)現(xiàn)實(shí)際上 RandomAccess 接口中什么都沒(méi)有定義。所以，在我看來(lái) RandomAccess 接口不過(guò)是一個(gè)標(biāo)識(shí)罷了。標(biāo)識(shí)什么？標(biāo)識(shí)實(shí)現(xiàn)這個(gè)接口的類(lèi)具有隨機(jī)訪問(wèn)功能。

在binarySearch（）方法中，它要判斷傳入的list 是否RamdomAccess的實(shí)例，如果是，調(diào)用indexedBinarySearch（）方法，如果不是，那么調(diào)用iteratorBinarySearch（）方法

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArraysList 實(shí)現(xiàn)了 RandomAccess 接口，而 LinkedList 沒(méi)有實(shí)現(xiàn)。為什么呢？我覺(jué)得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)！ArraysList 底層是數(shù)組，而 LinkedList 底層是鏈表。數(shù)組天然支持隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為 O（1），所以稱(chēng)為快速隨機(jī)訪問(wèn)。鏈表需要遍歷到特定位置才能訪問(wèn)特定位置的元素，時(shí)間復(fù)雜度為 O（n），所以不支持快速隨機(jī)訪問(wèn)。，ArraysList 實(shí)現(xiàn)了 RandomAccess 接口，就表明了他具有快速隨機(jī)訪問(wèn)功能。 RandomAccess 接口只是標(biāo)識(shí)，并不是說(shuō) ArraysList 實(shí)現(xiàn) RandomAccess 接口才具有快速隨機(jī)訪問(wèn)功能的！

下面再總結(jié)一下 list 的遍歷方式選擇：

實(shí)現(xiàn)了RandomAccess接口的list，優(yōu)先選擇普通for循環(huán) ，其次foreach,
未實(shí)現(xiàn)RandomAccess接口的ist，優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過(guò)iterator實(shí)現(xiàn)的），大size的數(shù)據(jù)，千萬(wàn)不要使用普通for循環(huán)

3.2 HashMap的底層實(shí)現(xiàn)

① JDK1.8之前

JDK1.8 之前 HashMap 底層是 數(shù)組和鏈表 結(jié)合在一起使用也就是 鏈表散列。HashMap 通過(guò) key 的 hashCode 經(jīng)過(guò)擾動(dòng)函數(shù)處理過(guò)后得到 hash 值，然后通過(guò) (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的時(shí)數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過(guò)拉鏈法解決沖突。

所謂擾動(dòng)函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的 hashCode() 方法換句話說(shuō)使用擾動(dòng)函數(shù)之后可以減少碰撞。

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法相比于 JDK 1.7 hash 方法更加簡(jiǎn)化，但是原理不變。

      static final int hash(Object key) {
        int h;
        // key.hashCode()：返回散列值也就是hashcode
        // ^ ：按位異或
        // >>>:無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

對(duì)比一下 JDK1.7的 HashMap 的 hash 方法源碼.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次。

所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

jdk1.8之前的內(nèi)部結(jié)構(gòu)

② JDK1.8之后

相比于之前的版本， JDK1.8之后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。

JDK1.8之后的HashMap底層數(shù)據(jù)結(jié)構(gòu)

TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹(shù)。紅黑樹(shù)就是為了解決二叉查找樹(shù)的缺陷，因?yàn)槎娌檎覙?shù)在某些情況下會(huì)退化成一個(gè)線性結(jié)構(gòu)。

問(wèn)完 HashMap 的底層原理之后，面試官可能就會(huì)緊接著問(wèn)你 HashMap 底層數(shù)據(jù)結(jié)構(gòu)相關(guān)的問(wèn)題！

3.3 既然談到了紅黑樹(shù)，你給我手繪一個(gè)出來(lái)吧，然后簡(jiǎn)單講一下自己對(duì)于紅黑樹(shù)的理解

紅黑樹(shù)

紅黑樹(shù)特點(diǎn):

每個(gè)節(jié)點(diǎn)非紅即黑；
根節(jié)點(diǎn)總是黑色的；
每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）；
如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）；
從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）

紅黑樹(shù)的應(yīng)用：

TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹(shù)。

為什么要用紅黑樹(shù)

簡(jiǎn)單來(lái)說(shuō)紅黑樹(shù)就是為了解決二叉查找樹(shù)的缺陷，因?yàn)槎娌檎覙?shù)在某些情況下會(huì)退化成一個(gè)線性結(jié)構(gòu)。

3.4 紅黑樹(shù)這么優(yōu)秀，為何不直接使用紅黑樹(shù)得了？

說(shuō)一下自己對(duì)于這個(gè)問(wèn)題的看法：我們知道紅黑樹(shù)屬于（自）平衡二叉樹(shù)，但是為了保持“平衡”是需要付出代價(jià)的，紅黑樹(shù)在插入新數(shù)據(jù)后可能需要通過(guò)左旋，右旋、變色這些操作來(lái)保持平衡，這費(fèi)事啊。你說(shuō)說(shuō)我們引入紅黑樹(shù)就是為了查找數(shù)據(jù)快，如果鏈表長(zhǎng)度很短的話，根本不需要引入紅黑樹(shù)的，你引入之后還要付出代價(jià)維持它的平衡。但是鏈表過(guò)長(zhǎng)就不一樣了。至于為什么選 8 這個(gè)值呢？通過(guò)概率統(tǒng)計(jì)所得，這個(gè)值是綜合查詢成本和新增元素成本得出的最好的一個(gè)值。

3.5 HashMap 和 Hashtable 的區(qū)別/HashSet 和 HashMap 區(qū)別

HashMap 和 Hashtable 的區(qū)別

線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過(guò) synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?；
效率： 因?yàn)榫€程安全的問(wèn)題，HashMap 要比 HashTable 效率高一點(diǎn)。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對(duì)Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null。。但是在 HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null，直接拋出 NullPointerException。
初始容量大小和每次擴(kuò)充容量大小的不同： ①創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2n+1。HashMap 默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2倍。②創(chuàng)建時(shí)如果給定了容量初始值，那么 Hashtable 會(huì)直接使用你給定的大小，而 HashMap 會(huì)將其擴(kuò)充為2的冪次方大?。℉ashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說(shuō) HashMap 總是使用2的冪作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方。
底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。Hashtable 沒(méi)有這樣的機(jī)制。

HashSet 和 HashMap 區(qū)別

如果你看過(guò) HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的。（HashSet 的源碼非常非常少，因?yàn)槌?clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實(shí)現(xiàn)之外，其他方法都是直接調(diào)用 HashMap 中的方法。）

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap和Map和HashTable區(qū)別

底層數(shù)據(jù)結(jié)構(gòu)：JDK1.7的ConcurrentHashMap底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，JDK1.8采用的數(shù)據(jù)結(jié)構(gòu)和HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹(shù)。Hashtable和JDK1.8之前的HashMap的底層數(shù)據(jù)結(jié)構(gòu)類(lèi)似都是采用數(shù)組+鏈表的形式，數(shù)據(jù)是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的；
實(shí)現(xiàn)線程安全的方式（重要）在JDK1.7的時(shí)候，ConcurrentHashMap（分段鎖）對(duì)真?zhèn)€桶數(shù)組進(jìn)行了分割分段（Segment），每一把鎖只鎖其中一部分?jǐn)?shù)據(jù)，多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問(wèn)率。（默認(rèn)分配16個(gè)Segment，比HashTable效率提高16倍）到了JDK1.8的時(shí)候已經(jīng)摒棄了Segment的概念，而是直接Node數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用synchronized和CAS來(lái)操作（JDK1.6以后對(duì)synchronized鎖做了很多優(yōu)化）整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的HashMap，雖然在JDK1.8中還能看到Segment的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本；HashTable（同一把鎖）使用synchronized來(lái)保證線程安全，效率非常低下，當(dāng)一個(gè)線程訪問(wèn)同步方法時(shí)，其他線程也訪問(wèn)同步方法，可能會(huì)加入阻塞或者輪訓(xùn)淘汰，如使用put添加元素，也不能使用get競(jìng)爭(zhēng)會(huì)越來(lái)越競(jìng)爭(zhēng)激烈效果低下。
兩者的對(duì)比圖：
圖片來(lái)源：http://www.cnblogs.com/chengxiao/p/6842045.html
HashTable:

image

JDK1.7的ConcurrentHashMap：

image

JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹(shù)節(jié)點(diǎn)
Node: 鏈表節(jié)點(diǎn)）：

image

2.2 ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

首先將數(shù)據(jù)分為一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)。

ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成。

Segment 實(shí)現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色。HashEntry 用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組。Segment 的結(jié)構(gòu)和HashMap類(lèi)似，是一種數(shù)組和鏈表結(jié)構(gòu)，一個(gè) Segment 包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè) Segment 守護(hù)著一個(gè)HashEntry數(shù)組里的元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的 Segment的鎖。

JDK1.8 （上面有示意圖）

ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來(lái)保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類(lèi)似，數(shù)組+鏈表/紅黑二叉樹(shù)。

synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹(shù)的首節(jié)點(diǎn)，這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)，效率又提升N倍。

三談?wù)?synchronized 和 ReenTrantLock 的區(qū)別

① 兩者都是可重入鎖

兩者都是可重入鎖?！翱芍厝腈i”概念是：自己可以再次獲取自己的內(nèi)部鎖。比如一個(gè)線程獲得了某個(gè)對(duì)象的鎖，此時(shí)這個(gè)對(duì)象鎖還沒(méi)有釋放，當(dāng)其再次想要獲取這個(gè)對(duì)象的鎖的時(shí)候還是可以獲取的，如果不可鎖重入的話，就會(huì)造成死鎖。同一個(gè)線程每次獲取鎖，鎖的計(jì)數(shù)器都自增1，所以要等到鎖的計(jì)數(shù)器下降為0時(shí)才能釋放鎖。

② synchronized 依賴于 JVM 而 ReenTrantLock 依賴于 API

synchronized 是依賴于 JVM 實(shí)現(xiàn)的，前面我們也講到了虛擬機(jī)團(tuán)隊(duì)在 JDK1.6 為 synchronized 關(guān)鍵字進(jìn)行了很多優(yōu)化，但是這些優(yōu)化都是在虛擬機(jī)層面實(shí)現(xiàn)的，并沒(méi)有直接暴露給我們。ReenTrantLock 是 JDK 層面實(shí)現(xiàn)的（也就是 API 層面，需要 lock() 和 unlock 方法配合 try/finally 語(yǔ)句塊來(lái)完成），所以我們可以通過(guò)查看它的源代碼，來(lái)看它是如何實(shí)現(xiàn)的。

③ ReenTrantLock 比 synchronized 增加了一些高級(jí)功能

相比synchronized，ReenTrantLock增加了一些高級(jí)功能。主要來(lái)說(shuō)主要有三點(diǎn)：①等待可中斷；②可實(shí)現(xiàn)公平鎖；③可實(shí)現(xiàn)選擇性通知（鎖可以綁定多個(gè)條件）

ReenTrantLock提供了一種能夠中斷等待鎖的線程的機(jī)制，通過(guò)lock.lockInterruptibly()來(lái)實(shí)現(xiàn)這個(gè)機(jī)制。也就是說(shuō)正在等待的線程可以選擇放棄等待，改為處理其他事情。
ReenTrantLock可以指定是公平鎖還是非公平鎖。而synchronized只能是非公平鎖。所謂的公平鎖就是先等待的線程先獲得鎖。 ReenTrantLock默認(rèn)情況是非公平的，可以通過(guò) ReenTrantLock類(lèi)的ReentrantLock(boolean fair)構(gòu)造方法來(lái)制定是否是公平的。
synchronized關(guān)鍵字與wait()和notify/notifyAll()方法相結(jié)合可以實(shí)現(xiàn)等待/通知機(jī)制，ReentrantLock類(lèi)當(dāng)然也可以實(shí)現(xiàn)，但是需要借助于Condition接口與newCondition() 方法。Condition是JDK1.5之后才有的，它具有很好的靈活性，比如可以實(shí)現(xiàn)多路通知功能也就是在一個(gè)Lock對(duì)象中可以創(chuàng)建多個(gè)Condition實(shí)例（即對(duì)象監(jiān)視器），線程對(duì)象可以注冊(cè)在指定的Condition中，從而可以有選擇性的進(jìn)行線程通知，在調(diào)度線程上更加靈活。在使用notify/notifyAll()方法進(jìn)行通知時(shí)，被通知的線程是由 JVM 選擇的，用ReentrantLock類(lèi)結(jié)合Condition實(shí)例可以實(shí)現(xiàn)“選擇性通知” ，這個(gè)功能非常重要，而且是Condition接口默認(rèn)提供的。而synchronized關(guān)鍵字就相當(dāng)于整個(gè)Lock對(duì)象中只有一個(gè)Condition實(shí)例，所有的線程都注冊(cè)在它一個(gè)身上。如果執(zhí)行notifyAll()方法的話就會(huì)通知所有處于等待狀態(tài)的線程這樣會(huì)造成很大的效率問(wèn)題，而Condition實(shí)例的signalAll()方法只會(huì)喚醒注冊(cè)在該Condition實(shí)例中的所有等待線程。

如果你想使用上述功能，那么選擇ReenTrantLock是一個(gè)不錯(cuò)的選擇。

④ 兩者的性能已經(jīng)相差無(wú)幾

在JDK1.6之前，synchronized 的性能是比 ReenTrantLock 差很多。具體表示為：synchronized 關(guān)鍵字吞吐量歲線程數(shù)的增加，下降得非常嚴(yán)重。而ReenTrantLock 基本保持一個(gè)比較穩(wěn)定的水平。我覺(jué)得這也側(cè)面反映了， synchronized 關(guān)鍵字還有非常大的優(yōu)化余地。后續(xù)的技術(shù)發(fā)展也證明了這一點(diǎn)，我們上面也講了在 JDK1.6 之后 JVM 團(tuán)隊(duì)對(duì) synchronized 關(guān)鍵字做了很多優(yōu)化。JDK1.6 之后，synchronized 和 ReenTrantLock 的性能基本是持平了。所以網(wǎng)上那些說(shuō)因?yàn)樾阅懿胚x擇 ReenTrantLock 的文章都是錯(cuò)的！JDK1.6之后，性能已經(jīng)不是選擇synchronized和ReenTrantLock的影響因素了！而且虛擬機(jī)在未來(lái)的性能改進(jìn)中會(huì)更偏向于原生的synchronized，所以還是提倡在synchronized能滿足你的需求的情況下，優(yōu)先考慮使用synchronized關(guān)鍵字來(lái)進(jìn)行同步！優(yōu)化后的synchronized和ReenTrantLock一樣，在很多地方都是用到了CAS操作。

Arraylist 與 LinkedList 異同
- 補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表
ArrayList 與 Vector 區(qū)別
HashMap的底層實(shí)現(xiàn)
- JDK1.8之前
- JDK1.8之后
HashMap 和 Hashtable 的區(qū)別
HashMap 的長(zhǎng)度為什么是2的冪次方
HashMap 多線程操作導(dǎo)致死循環(huán)問(wèn)題
HashSet 和 HashMap 區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別
ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)
- JDK1.7（上面有示意圖）
- JDK1.8 （上面有示意圖）
集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)
- Collection
  - 1. List
  - 2. Set
- Map
- 推薦閱讀：

Arraylist 與 LinkedList 異同

1. 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
2. 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是Object數(shù)組；LinkedList 底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別：）；詳細(xì)可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化
3. 插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時(shí)候， ArrayList 會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。 ② LinkedList 采用鏈表存儲(chǔ)，所以插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，都是近似 O（1）而數(shù)組為近似 O（n）。
4. 是否支持快速隨機(jī)訪問(wèn)： LinkedList 不支持高效的隨機(jī)元素訪問(wèn)，而 ArrayList 支持。快速隨機(jī)訪問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于get(int index)方法)。
5. 內(nèi)存空間占用： ArrayList的空間浪費(fèi)主要體現(xiàn)在在list列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。
-**6. 發(fā)
補(bǔ)充內(nèi)容:RandomAccess接口

public interface RandomAccess {
}

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 實(shí)現(xiàn)了 RandomAccess 接口，而 LinkedList 沒(méi)有實(shí)現(xiàn)。為什么呢？我覺(jué)得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)！ArrayList 底層是數(shù)組，而 LinkedList 底層是鏈表。數(shù)組天然支持隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為 O（1），所以稱(chēng)為快速隨機(jī)訪問(wèn)。鏈表需要遍歷到特定位置才能訪問(wèn)特定位置的元素，時(shí)間復(fù)雜度為 O（n），所以不支持快速隨機(jī)訪問(wèn)。，ArrayList 實(shí)現(xiàn)了 RandomAccess 接口，就表明了他具有快速隨機(jī)訪問(wèn)功能。 RandomAccess 接口只是標(biāo)識(shí)，并不是說(shuō) ArrayList 實(shí)現(xiàn) RandomAccess 接口才具有快速隨機(jī)訪問(wèn)功能的！

下面再總結(jié)一下 list 的遍歷方式選擇：

實(shí)現(xiàn)了RandomAccess接口的list，優(yōu)先選擇普通for循環(huán) ，其次foreach,
未實(shí)現(xiàn)RandomAccess接口的ist，優(yōu)先選擇iterator遍歷（foreach遍歷底層也是通過(guò)iterator實(shí)現(xiàn)的），大size的數(shù)據(jù)，千萬(wàn)不要使用普通for循環(huán)

補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表，如下圖所示，同時(shí)下圖也是LinkedList 底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)。

image

ArrayList 與 Vector 區(qū)別

Vector類(lèi)的所有方法都是同步的?？梢杂蓛蓚€(gè)線程安全地訪問(wèn)一個(gè)Vector對(duì)象、但是一個(gè)線程訪問(wèn)Vector的話代碼要在同步操作上耗費(fèi)大量的時(shí)間。

Arraylist不是同步的，所以在不需要保證線程安全時(shí)時(shí)建議使用Arraylist。

HashMap的底層實(shí)現(xiàn)

JDK1.8之前

JDK1.8 之前 HashMap 底層是 數(shù)組和鏈表 結(jié)合在一起使用也就是 鏈表散列。HashMap 通過(guò) key 的 hashCode 經(jīng)過(guò)擾動(dòng)函數(shù)處理過(guò)后得到 hash 值，然后通過(guò) (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過(guò)拉鏈法解決沖突。

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法相比于 JDK 1.7 hash 方法更加簡(jiǎn)化，但是原理不變。

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位異或
      // >>>:無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

對(duì)比一下 JDK1.7的 HashMap 的 hash 方法源碼.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次。

jdk1.8之前的內(nèi)部結(jié)構(gòu)

JDK1.8之后

JDK1.8之后的HashMap底層數(shù)據(jù)結(jié)構(gòu)

TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹(shù)。紅黑樹(shù)就是為了解決二叉查找樹(shù)的缺陷，因?yàn)槎娌檎覙?shù)在某些情況下會(huì)退化成一個(gè)線性結(jié)構(gòu)。

推薦閱讀：

《Java 8系列之重新認(rèn)識(shí)HashMap》：https://zhuanlan.zhihu.com/p/21673805

HashMap 和 Hashtable 的區(qū)別

線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過(guò) synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?/li>
效率： 因?yàn)榫€程安全的問(wèn)題，HashMap 要比 HashTable 效率高一點(diǎn)。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對(duì)Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null。。但是在 HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null，直接拋出 NullPointerException。
初始容量大小和每次擴(kuò)充容量大小的不同： ①創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2n+1。HashMap 默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2倍。②創(chuàng)建時(shí)如果給定了容量初始值，那么 Hashtable 會(huì)直接使用你給定的大小，而 HashMap 會(huì)將其擴(kuò)充為2的冪次方大?。℉ashMap 中的tableSizeFor()方法保證，下面給出了源代碼）。也就是說(shuō) HashMap 總是使用2的冪作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方。
底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。Hashtable 沒(méi)有這樣的機(jī)制。

HasMap 中帶有初始容量的構(gòu)造函數(shù)：

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面這個(gè)方法保證了 HashMap 總是使用2的冪作為哈希表的大小。

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap 的長(zhǎng)度為什么是2的冪次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻。我們上面也講到了過(guò)了，Hash 值的范圍值-2147483648到2147483647，前后加起來(lái)大概40億的映射空間，只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。所以這個(gè)散列值是不能直接拿來(lái)用的。用之前還要先做對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來(lái)要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是“ (n - 1) & hash ”。（n代表數(shù)組長(zhǎng)度）。這也就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方。

這個(gè)算法應(yīng)該如何設(shè)計(jì)呢？

我們首先可能會(huì)想到采用%取余的操作來(lái)實(shí)現(xiàn)。但是，重點(diǎn)來(lái)了：“取余(%)操作中如果除數(shù)是2的冪次則等價(jià)于與其除數(shù)減一的與(&)操作（也就是說(shuō) hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）?！?/strong> 并且 采用二進(jìn)制位操作 &，相對(duì)于%能夠提高運(yùn)算效率，這就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方。

HashMap 多線程操作導(dǎo)致死循環(huán)問(wèn)題

在多線程下，進(jìn)行 put 操作會(huì)導(dǎo)致 HashMap 死循環(huán)，原因在于 HashMap 的擴(kuò)容 resize()方法。由于擴(kuò)容是新建一個(gè)數(shù)組，復(fù)制原數(shù)據(jù)到數(shù)組。由于數(shù)組下標(biāo)掛有鏈表，所以需要復(fù)制鏈表，但是多線程操作有可能導(dǎo)致環(huán)形鏈表。復(fù)制鏈表過(guò)程如下:
以下模擬2個(gè)線程同時(shí)擴(kuò)容。假設(shè)，當(dāng)前 HashMap 的空間為2（臨界值為1），hashcode 分別為 0 和 1，在散列地址 0 處有元素 A 和 B，這時(shí)候要添加元素 C，C 經(jīng)過(guò) hash 運(yùn)算，得到散列地址為 1，這時(shí)候由于超過(guò)了臨界值，空間不夠，需要調(diào)用 resize 方法進(jìn)行擴(kuò)容，那么在多線程條件下，會(huì)出現(xiàn)條件競(jìng)爭(zhēng)，模擬過(guò)程如下：

線程一：讀取到當(dāng)前的 HashMap 情況，在準(zhǔn)備擴(kuò)容時(shí)，線程二介入

image

線程二：讀取 HashMap，進(jìn)行擴(kuò)容

image

線程一：繼續(xù)執(zhí)行

image

這個(gè)過(guò)程為，先將 A 復(fù)制到新的 hash 表中，然后接著復(fù)制 B 到鏈頭（A 的前邊：B.next=A），本來(lái) B.next=null，到此也就結(jié)束了（跟線程二一樣的過(guò)程），但是，由于線程二擴(kuò)容的原因，將 B.next=A，所以，這里繼續(xù)復(fù)制A，讓 A.next=B，由此，環(huán)形鏈表出現(xiàn)：B.next=A; A.next=B

注意：jdk1.8已經(jīng)解決了死循環(huán)的問(wèn)題。

HashSet 和 HashMap 區(qū)別

如果你看過(guò) HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的。（HashSet 的源碼非常非常少，因?yàn)槌?clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不實(shí)現(xiàn)之外，其他方法都是直接調(diào)用 HashMap 中的方法。）

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線程安全的方式上不同。

底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實(shí)現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹(shù)。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類(lèi)似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；

實(shí)現(xiàn)線程安全的方式（重要）： ① 在JDK1.7的時(shí)候，ConcurrentHashMap（分段鎖） 對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問(wèn)率。到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用 synchronized 和 CAS 來(lái)操作。（JDK1.6以后對(duì) synchronized鎖做了很多優(yōu)化）整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來(lái)保證線程安全，效率非常低下。當(dāng)一個(gè)線程訪問(wèn)同步方法時(shí)，其他線程也訪問(wèn)同步方法，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)，如使用 put 添加元素，另一個(gè)線程不能使用 put 添加元素，也不能使用 get，競(jìng)爭(zhēng)會(huì)越來(lái)越激烈效率越低。

兩者的對(duì)比圖：

圖片來(lái)源：http://www.cnblogs.com/chengxiao/p/6842045.html

HashTable:

image

JDK1.7的ConcurrentHashMap：

image

JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹(shù)節(jié)點(diǎn)
Node: 鏈表節(jié)點(diǎn)）：

image

ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

首先將數(shù)據(jù)分為一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)。

ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成。

Segment 實(shí)現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色。HashEntry 用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)。

static class Segment<K,V> extends ReentrantLock implements Serializable { }

一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組。Segment 的結(jié)構(gòu)和HashMap類(lèi)似，是一種數(shù)組和鏈表結(jié)構(gòu)，一個(gè) Segment 包含一個(gè) HashEntry 數(shù)組，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè) Segment 守護(hù)著一個(gè)HashEntry數(shù)組里的元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的 Segment的鎖。

JDK1.8 （上面有示意圖）

ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來(lái)保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)類(lèi)似，數(shù)組+鏈表/紅黑二叉樹(shù)。

synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹(shù)的首節(jié)點(diǎn)，這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)，效率又提升N倍。

集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

Collection

1. List

Arraylist： Object數(shù)組

Vector： Object數(shù)組

LinkedList： 雙向鏈表(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán))
詳細(xì)可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化

2. Set

HashSet（無(wú)序，唯一）: 基于 HashMap 實(shí)現(xiàn)的，底層采用 HashMap 來(lái)保存元素

LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內(nèi)部是通過(guò) LinkedHashMap 來(lái)實(shí)現(xiàn)的。有點(diǎn)類(lèi)似于我們之前說(shuō)的LinkedHashMap 其內(nèi)部是基于 Hashmap 實(shí)現(xiàn)一樣，不過(guò)還是有一點(diǎn)點(diǎn)區(qū)別的。

TreeSet（有序，唯一）： 紅黑樹(shù)(自平衡的排序二叉樹(shù)。)

Map

HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間

LinkedHashMap: LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹(shù)組成。另外，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對(duì)的插入順序。同時(shí)通過(guò)對(duì)鏈表進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)了訪問(wèn)順序相關(guān)邏輯。詳細(xì)可以查看：《LinkedHashMap 源碼詳細(xì)分析（JDK1.8）》

HashTable: 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的

TreeMap: 紅黑樹(shù)（自平衡的排序二叉樹(shù)）

推薦閱讀：

jdk1.8中ConcurrentHashMap的實(shí)現(xiàn)原理

HashMap? ConcurrentHashMap? 相信看完這篇沒(méi)人能難住你！

HASHMAP、HASHTABLE、CONCURRENTHASHMAP的原理與區(qū)別

ConcurrentHashMap實(shí)現(xiàn)原理及源碼分析

java-并發(fā)-ConcurrentHashMap高并發(fā)機(jī)制-jdk1.8

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Java集合相關(guān)面試

Java集合相關(guān)面試

ArrayList和LinkedList區(qū)別？

3.2 HashMap的底層實(shí)現(xiàn)

① JDK1.8之前

② JDK1.8之后

3.3 既然談到了紅黑樹(shù)，你給我手繪一個(gè)出來(lái)吧，然后簡(jiǎn)單講一下自己對(duì)于紅黑樹(shù)的理解

3.4 紅黑樹(shù)這么優(yōu)秀，為何不直接使用紅黑樹(shù)得了？

3.5 HashMap 和 Hashtable 的區(qū)別/HashSet 和 HashMap 區(qū)別

ConcurrentHashMap和Map和HashTable區(qū)別

2.2 ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

JDK1.8 （上面有示意圖）

三談?wù)?synchronized 和 ReenTrantLock 的區(qū)別

Arraylist 與 LinkedList 異同

補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表

ArrayList 與 Vector 區(qū)別

HashMap的底層實(shí)現(xiàn)

JDK1.8之前

JDK1.8之后

HashMap 和 Hashtable 的區(qū)別

HashMap 的長(zhǎng)度為什么是2的冪次方

HashMap 多線程操作導(dǎo)致死循環(huán)問(wèn)題

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

JDK1.8 （上面有示意圖）

集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

Collection

1. List

2. Set

Map

推薦閱讀：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Java集合相關(guān)面試

ArrayList和LinkedList區(qū)別？

3.2 HashMap的底層實(shí)現(xiàn)

① JDK1.8之前

② JDK1.8之后

3.3 既然談到了紅黑樹(shù)，你給我手繪一個(gè)出來(lái)吧，然后簡(jiǎn)單講一下自己對(duì)于紅黑樹(shù)的理解

3.4 紅黑樹(shù)這么優(yōu)秀，為何不直接使用紅黑樹(shù)得了？

3.5 HashMap 和 Hashtable 的區(qū)別/HashSet 和 HashMap 區(qū)別

ConcurrentHashMap和Map和HashTable區(qū)別

2.2 ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

JDK1.8 （上面有示意圖）

三 談?wù)?synchronized 和 ReenTrantLock 的區(qū)別

Arraylist 與 LinkedList 異同

補(bǔ)充：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙向鏈表

ArrayList 與 Vector 區(qū)別

HashMap的底層實(shí)現(xiàn)

JDK1.8之前

JDK1.8之后

HashMap 和 Hashtable 的區(qū)別

HashMap 的長(zhǎng)度為什么是2的冪次方

HashMap 多線程操作導(dǎo)致死循環(huán)問(wèn)題

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)

JDK1.7（上面有示意圖）

JDK1.8 （上面有示意圖）

集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

Collection

1. List

2. Set

Map

推薦閱讀：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

ArrayList和LinkedList區(qū)別？

3.3 既然談到了紅黑樹(shù)，你給我手繪一個(gè)出來(lái)吧，然后簡(jiǎn)單講一下自己對(duì)于紅黑樹(shù)的理解

3.4 紅黑樹(shù)這么優(yōu)秀，為何不直接使用紅黑樹(shù)得了？

三談?wù)?synchronized 和 ReenTrantLock 的區(qū)別