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

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ù)組存儲闸衫，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響涛贯。比如執(zhí)行add(E e)方法的時候，ArrayList會默認在將指定的元素追加到此列表的末尾蔚出，這種情況時間復(fù)雜度就是O(1)弟翘。但是如果要在指定位置i插入和刪除元素的話（add(int index,E element)）時間負責(zé)度就為O(n-i)含懊。因為在進行上述操作的時候集合中第i和 第i個元素之后的（n-i）個元素都是要執(zhí)行向后位/向前移一位的操作。ListedList采用鏈表存儲衅胀，所以插入岔乔，刪除元素時間復(fù)雜度不受元素位置的影響。都是近似O(1)而數(shù)組為近似O(n)滚躯。
  • 4.是否支持快速隨機訪問：LiskedList不支持高效的隨機元素訪問雏门，而ArrayList支持〉停快速隨機訪問就就是通過元素的序號快速獲取元素對象（對應(yīng)于get(int index)方法）茁影。
  • 內(nèi)存空間占用： ArrayList的 空間浪費主要體現(xiàn)在List列表的結(jié)尾會預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的 空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）丧凤。

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

public interface RandomAccess {
}

查看源碼我們發(fā)現(xiàn)實際上 RandomAccess 接口中什么都沒有定義募闲。所以，在我看來 RandomAccess 接口不過是一個標(biāo)識罷了愿待。標(biāo)識什么浩螺？ 標(biāo)識實現(xiàn)這個接口的類具有隨機訪問功能。

在binarySearch（）方法中仍侥，它要判斷傳入的list 是否RamdomAccess的實例要出，如果是，調(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 實現(xiàn)了 RandomAccess 接口， 而 LinkedList 沒有實現(xiàn)砸紊。為什么呢传于？我覺得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)！ArraysList 底層是數(shù)組醉顽，而 LinkedList 底層是鏈表沼溜。數(shù)組天然支持隨機訪問，時間復(fù)雜度為 O（1）徽鼎，所以稱為快速隨機訪問盛末。鏈表需要遍歷到特定位置才能訪問特定位置的元素，時間復(fù)雜度為 O（n）否淤，所以不支持快速隨機訪問悄但。，ArraysList 實現(xiàn)了 RandomAccess 接口石抡，就表明了他具有快速隨機訪問功能檐嚣。 RandomAccess 接口只是標(biāo)識，并不是說 ArraysList 實現(xiàn) RandomAccess 接口才具有快速隨機訪問功能的！

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

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

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

① JDK1.8之前

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

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

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化其弊，但是原理不變癞己。

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

對比一下 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 方法的性能會稍差一點點，因為畢竟擾動了 4 次籽御。

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

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

② JDK1.8之后

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

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

TreeMap龄毡、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹吠卷。紅黑樹就是為了解決二叉查找樹的缺陷，因為二叉查找樹在某些情況下會退化成一個線性結(jié)構(gòu)沦零。

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

3.3 既然談到了紅黑樹路操，你給我手繪一個出來吧疾渴，然后簡單講一下自己對于紅黑樹的理解

紅黑樹

紅黑樹特點:

  1. 每個節(jié)點非紅即黑千贯；
  2. 根節(jié)點總是黑色的；
  3. 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）搞坝；
  4. 如果節(jié)點是紅色的搔谴，則它的子節(jié)點必須是黑色的（反之不一定）；
  5. 從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑桩撮，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）

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

TreeMap敦第、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹。

為什么要用紅黑樹

簡單來說紅黑樹就是為了解決二叉查找樹的缺陷距境，因為二叉查找樹在某些情況下會退化成一個線性結(jié)構(gòu)申尼。

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

說一下自己對于這個問題的看法：我們知道紅黑樹屬于（自）平衡二叉樹师幕，但是為了保持“平衡”是需要付出代價的，紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋诬滩，右旋霹粥、變色這些操作來保持平衡，這費事啊疼鸟。你說說我們引入紅黑樹就是為了查找數(shù)據(jù)快后控，如果鏈表長度很短的話，根本不需要引入紅黑樹的空镜，你引入之后還要付出代價維持它的平衡浩淘。但是鏈表過長就不一樣了。至于為什么選 8 這個值呢吴攒？通過概率統(tǒng)計所得张抄，這個值是綜合查詢成本和新增元素成本得出的最好的一個值。

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

HashMap 和 Hashtable 的區(qū)別

  1. 線程是否安全： HashMap 是非線程安全的洼怔，HashTable 是線程安全的署惯；HashTable 內(nèi)部的方法基本都經(jīng)過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧Ａ土ァ）极谊；
  2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點安岂。另外轻猖，HashTable 基本被淘汰嗜闻，不要在代碼中使用它蜕依；
  3. 對Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個样眠，可以有一個或多個鍵所對應(yīng)的值為 null友瘤。。但是在 HashTable 中 put 進的鍵值只要有一個 null檐束，直接拋出 NullPointerException辫秧。
  4. 初始容量大小和每次擴充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值，Hashtable 默認的初始大小為11被丧，之后每次擴充盟戏，容量變?yōu)樵瓉淼?n+1。HashMap 默認的初始化大小為16甥桂。之后每次擴充柿究，容量變?yōu)樵瓉淼?倍。②創(chuàng)建時如果給定了容量初始值黄选，那么 Hashtable 會直接使用你給定的大小蝇摸，而 HashMap 會將其擴充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證办陷，下面給出了源代碼）貌夕。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方。
  5. 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化民镜，當(dāng)鏈表長度大于閾值（默認為8）時啡专，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間制圈。Hashtable 沒有這樣的機制们童。

HashSet 和 HashMap 區(qū)別

如果你看過 HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實現(xiàn)的。（HashSet 的源碼非常非常少鲸鹦，因為除了 clone() 方法病附、writeObject()方法、readObject()方法是 HashSet 自己不得不實現(xiàn)之外亥鬓，其他方法都是直接調(diào)用 HashMap 中的方法。）

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap和Map和HashTable區(qū)別

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

image

JDK1.7的ConcurrentHashMap：


image

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


image

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

JDK1.7（上面有示意圖）

首先將數(shù)據(jù)分為一段一段的存儲炕婶，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)時莱预，其他段的數(shù)據(jù)也能被其他線程訪問柠掂。

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

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

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

一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組危喉。Segment 的結(jié)構(gòu)和HashMap類似宋渔，是一種數(shù)組和鏈表結(jié)構(gòu)，一個 Segment 包含一個 HashEntry 數(shù)組辜限，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素皇拣，每個 Segment 守護著一個HashEntry數(shù)組里的元素，當(dāng)對 HashEntry 數(shù)組的數(shù)據(jù)進行修改時薄嫡，必須首先獲得對應(yīng)的 Segment的鎖氧急。

JDK1.8 （上面有示意圖）

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

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

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

① 兩者都是可重入鎖

兩者都是可重入鎖嵌纲》悖“可重入鎖”概念是：自己可以再次獲取自己的內(nèi)部鎖。比如一個線程獲得了某個對象的鎖疹瘦，此時這個對象鎖還沒有釋放苦掘，當(dāng)其再次想要獲取這個對象的鎖的時候還是可以獲取的氛魁，如果不可鎖重入的話壁酬，就會造成死鎖伤锚。同一個線程每次獲取鎖，鎖的計數(shù)器都自增1险胰，所以要等到鎖的計數(shù)器下降為0時才能釋放鎖汹押。

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

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

③ ReenTrantLock 比 synchronized 增加了一些高級功能

相比synchronized怯伊，ReenTrantLock增加了一些高級功能。主要來說主要有三點：①等待可中斷判沟；②可實現(xiàn)公平鎖耿芹；③可實現(xiàn)選擇性通知（鎖可以綁定多個條件）

  • ReenTrantLock提供了一種能夠中斷等待鎖的線程的機制，通過lock.lockInterruptibly()來實現(xiàn)這個機制挪哄。也就是說正在等待的線程可以選擇放棄等待吧秕，改為處理其他事情。
  • ReenTrantLock可以指定是公平鎖還是非公平鎖迹炼。而synchronized只能是非公平鎖砸彬。所謂的公平鎖就是先等待的線程先獲得鎖。 ReenTrantLock默認情況是非公平的斯入，可以通過 ReenTrantLock類的ReentrantLock(boolean fair)構(gòu)造方法來制定是否是公平的拿霉。
  • synchronized關(guān)鍵字與wait()和notify/notifyAll()方法相結(jié)合可以實現(xiàn)等待/通知機制，ReentrantLock類當(dāng)然也可以實現(xiàn)咱扣，但是需要借助于Condition接口與newCondition() 方法。Condition是JDK1.5之后才有的涵防，它具有很好的靈活性闹伪，比如可以實現(xiàn)多路通知功能也就是在一個Lock對象中可以創(chuàng)建多個Condition實例（即對象監(jiān)視器）沪铭，線程對象可以注冊在指定的Condition中，從而可以有選擇性的進行線程通知偏瓤，在調(diào)度線程上更加靈活杀怠。 在使用notify/notifyAll()方法進行通知時，被通知的線程是由 JVM 選擇的厅克，用ReentrantLock類結(jié)合Condition實例可以實現(xiàn)“選擇性通知” 赔退，這個功能非常重要，而且是Condition接口默認提供的证舟。而synchronized關(guān)鍵字就相當(dāng)于整個Lock對象中只有一個Condition實例硕旗，所有的線程都注冊在它一個身上。如果執(zhí)行notifyAll()方法的話就會通知所有處于等待狀態(tài)的線程這樣會造成很大的效率問題女责，而Condition實例的signalAll()方法 只會喚醒注冊在該Condition實例中的所有等待線程漆枚。

如果你想使用上述功能，那么選擇ReenTrantLock是一個不錯的選擇抵知。

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

在JDK1.6之前墙基，synchronized 的性能是比 ReenTrantLock 差很多。具體表示為：synchronized 關(guān)鍵字吞吐量歲線程數(shù)的增加刷喜，下降得非常嚴重残制。而ReenTrantLock 基本保持一個比較穩(wěn)定的水平。我覺得這也側(cè)面反映了掖疮， synchronized 關(guān)鍵字還有非常大的優(yōu)化余地初茶。后續(xù)的技術(shù)發(fā)展也證明了這一點，我們上面也講了在 JDK1.6 之后 JVM 團隊對 synchronized 關(guān)鍵字做了很多優(yōu)化氮墨。JDK1.6 之后纺蛆，synchronized 和 ReenTrantLock 的性能基本是持平了。所以網(wǎng)上那些說因為性能才選擇 ReenTrantLock 的文章都是錯的规揪！JDK1.6之后桥氏，性能已經(jīng)不是選擇synchronized和ReenTrantLock的影響因素了！而且虛擬機在未來的性能改進中會更偏向于原生的synchronized猛铅，所以還是提倡在synchronized能滿足你的需求的情況下字支，優(yōu)先考慮使用synchronized關(guān)鍵字來進行同步！優(yōu)化后的synchronized和ReenTrantLock一樣奸忽，在很多地方都是用到了CAS操作堕伪。

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ū)別：）富俄； 詳細可閱讀JDK1.7-LinkedList循環(huán)鏈表優(yōu)化
  • 3. 插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲禁炒，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時候霍比， ArrayList 會默認在將指定的元素追加到此列表的末尾幕袱，這種情況時間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復(fù)雜度就為 O(n-i)悠瞬。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作们豌。 ② LinkedList 采用鏈表存儲，所以插入浅妆，刪除元素時間復(fù)雜度不受元素位置的影響望迎，都是近似 O（1）而數(shù)組為近似 O（n）。
  • 4. 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問狂打，而 ArrayList 支持擂煞。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)趴乡。
  • 5. 內(nèi)存空間占用： ArrayList的空 間浪費主要體現(xiàn)在在list列表的結(jié)尾會預(yù)留一定的容量空間对省，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）。
    -**6. 發(fā)
    補充內(nèi)容:RandomAccess接口 
public interface RandomAccess {
}

查看源碼我們發(fā)現(xiàn)實際上 RandomAccess 接口中什么都沒有定義晾捏。所以蒿涎，在我看來 RandomAccess 接口不過是一個標(biāo)識罷了。標(biāo)識什么惦辛？ 標(biāo)識實現(xiàn)這個接口的類具有隨機訪問功能劳秋。

在binarySearch（）方法中，它要判斷傳入的list 是否RamdomAccess的實例胖齐，如果是玻淑，調(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);
    }

ArrayList 實現(xiàn)了 RandomAccess 接口补履， 而 LinkedList 沒有實現(xiàn)。為什么呢剿另？我覺得還是和底層數(shù)據(jù)結(jié)構(gòu)有關(guān)箫锤！ArrayList 底層是數(shù)組，而 LinkedList 底層是鏈表雨女。數(shù)組天然支持隨機訪問谚攒，時間復(fù)雜度為 O（1），所以稱為快速隨機訪問氛堕。鏈表需要遍歷到特定位置才能訪問特定位置的元素馏臭，時間復(fù)雜度為 O（n），所以不支持快速隨機訪問讼稚。位喂，ArrayList 實現(xiàn)了 RandomAccess 接口浪耘，就表明了他具有快速隨機訪問功能。 RandomAccess 接口只是標(biāo)識塑崖，并不是說 ArrayList 實現(xiàn) RandomAccess 接口才具有快速隨機訪問功能的！

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

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

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

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

image

ArrayList 與 Vector 區(qū)別

Vector類的所有方法都是同步的吻贿〈幔可以由兩個線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間舅列。

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

HashMap的底層實現(xiàn)

JDK1.8之前

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

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

JDK 1.8 HashMap 的 hash 方法源碼:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化剂邮，但是原理不變。

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

對比一下 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 方法的性能會稍差一點點，因為畢竟擾動了 4 次引瀑。

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

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

JDK1.8之后

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

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

TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹唧瘾。紅黑樹就是為了解決二叉查找樹的缺陷措译，因為二叉查找樹在某些情況下會退化成一個線性結(jié)構(gòu)。

推薦閱讀：

HashMap 和 Hashtable 的區(qū)別

  1. 線程是否安全： HashMap 是非線程安全的劈愚，HashTable 是線程安全的瞳遍；HashTable 內(nèi)部的方法基本都經(jīng)過 synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧＞稹）掠械；
  2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點注祖。另外猾蒂，HashTable 基本被淘汰，不要在代碼中使用它是晨；
  3. 對Null key 和Null value的支持： HashMap 中肚菠，null 可以作為鍵，這樣的鍵只有一個罩缴，可以有一個或多個鍵所對應(yīng)的值為 null蚊逢。。但是在 HashTable 中 put 進的鍵值只要有一個 null箫章，直接拋出 NullPointerException烙荷。
  4. 初始容量大小和每次擴充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值，Hashtable 默認的初始大小為11檬寂，之后每次擴充终抽，容量變?yōu)樵瓉淼?n+1。HashMap 默認的初始化大小為16。之后每次擴充昼伴，容量變?yōu)樵瓉淼?倍匾旭。②創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小圃郊，而 HashMap 會將其擴充為2的冪次方大屑劾浴（HashMap 中的tableSizeFor()方法保證，下面給出了源代碼）持舆。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方飒泻。
  5. 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當(dāng)鏈表長度大于閾值（默認為8）時吏廉，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間惰许。Hashtable 沒有這樣的機制席覆。

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);
    }

下面這個方法保證了 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 的長度為什么是2的冪次方

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

這個算法應(yīng)該如何設(shè)計呢幌蚊？

我們首先可能會想到采用%取余的操作來實現(xiàn)。但是溃卡，重點來了：“取余(%)操作中如果除數(shù)是2的冪次則等價于與其除數(shù)減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方溢豆；）∷芗澹” 并且 采用二進制位操作 &沫换，相對于%能夠提高運算效率，這就解釋了 HashMap 的長度為什么是2的冪次方。

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

在多線程下讯赏，進行 put 操作會導(dǎo)致 HashMap 死循環(huán)垮兑，原因在于 HashMap 的擴容 resize()方法。由于擴容是新建一個數(shù)組漱挎，復(fù)制原數(shù)據(jù)到數(shù)組系枪。由于數(shù)組下標(biāo)掛有鏈表，所以需要復(fù)制鏈表磕谅，但是多線程操作有可能導(dǎo)致環(huán)形鏈表私爷。復(fù)制鏈表過程如下:
以下模擬2個線程同時擴容。假設(shè)膊夹，當(dāng)前 HashMap 的空間為2（臨界值為1）衬浑，hashcode 分別為 0 和 1，在散列地址 0 處有元素 A 和 B放刨，這時候要添加元素 C工秩，C 經(jīng)過 hash 運算，得到散列地址為 1进统，這時候由于超過了臨界值助币，空間不夠，需要調(diào)用 resize 方法進行擴容螟碎，那么在多線程條件下眉菱，會出現(xiàn)條件競爭，模擬過程如下：

線程一：讀取到當(dāng)前的 HashMap 情況掉分，在準(zhǔn)備擴容時俭缓，線程二介入

image

線程二：讀取 HashMap，進行擴容

image

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

image

這個過程為叉抡，先將 A 復(fù)制到新的 hash 表中尔崔，然后接著復(fù)制 B 到鏈頭（A 的前邊：B.next=A），本來 B.next=null褥民，到此也就結(jié)束了（跟線程二一樣的過程）季春，但是，由于線程二擴容的原因消返，將 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)的問題倡勇。

HashSet 和 HashMap 區(qū)別

如果你看過 HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實現(xiàn)的逞刷。（HashSet 的源碼非常非常少，因為除了 clone() 方法、writeObject()方法夸浅、readObject()方法是 HashSet 自己不得不實現(xiàn)之外仑最，其他方法都是直接調(diào)用 HashMap 中的方法。）

HashSet 和 HashMap 區(qū)別

ConcurrentHashMap 和 Hashtable 的區(qū)別

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

  • 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實現(xiàn)警医，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹坯钦。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式预皇，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的婉刀；
  • 實現(xiàn)線程安全的方式（重要）： ① 在JDK1.7的時候吟温，ConcurrentHashMap（分段鎖） 對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數(shù)據(jù)突颊，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)溯街，就不會存在鎖競爭，提高并發(fā)訪問率洋丐。 到了 JDK1.8 的時候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)挥等，并發(fā)控制使用 synchronized 和 CAS 來操作友绝。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)肝劲，但是已經(jīng)簡化了屬性迁客，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全辞槐，效率非常低下掷漱。當(dāng)一個線程訪問同步方法時，其他線程也訪問同步方法榄檬，可能會進入阻塞或輪詢狀態(tài)卜范，如使用 put 添加元素，另一個線程不能使用 put 添加元素鹿榜，也不能使用 get海雪，競爭會越來越激烈效率越低。

兩者的對比圖：

圖片來源：http://www.cnblogs.com/chengxiao/p/6842045.html

HashTable:


image

JDK1.7的ConcurrentHashMap：


image

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


image

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

JDK1.7（上面有示意圖）

首先將數(shù)據(jù)分為一段一段的存儲舱殿，然后給每一段數(shù)據(jù)配一把鎖奥裸，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)時，其他段的數(shù)據(jù)也能被其他線程訪問沪袭。

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

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

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

一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組埠啃。Segment 的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)畦攘，一個 Segment 包含一個 HashEntry 數(shù)組霸妹，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素，每個 Segment 守護著一個HashEntry數(shù)組里的元素知押，當(dāng)對 HashEntry 數(shù)組的數(shù)據(jù)進行修改時叹螟，必須首先獲得對應(yīng)的 Segment的鎖。

JDK1.8 （上面有示意圖）

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

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

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

Collection

1. List

2. Set

  • HashSet（無序市咽，唯一）: 基于 HashMap 實現(xiàn)的痊银，底層采用 HashMap 來保存元素
  • LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內(nèi)部是通過 LinkedHashMap 來實現(xiàn)的施绎。有點類似于我們之前說的LinkedHashMap 其內(nèi)部是基于 Hashmap 實現(xiàn)一樣溯革，不過還是有一點點區(qū)別的。
  • TreeSet（有序谷醉，唯一）： 紅黑樹(自平衡的排序二叉樹致稀。)

Map

  • HashMap： JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體俱尼，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化抖单，當(dāng)鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹遇八，以減少搜索時間
  • LinkedHashMap: LinkedHashMap 繼承自 HashMap臭猜，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外押蚤，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上蔑歌，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對的插入順序揽碘。同時通過對鏈表進行相應(yīng)的操作次屠，實現(xiàn)了訪問順序相關(guān)邏輯园匹。詳細可以查看：《LinkedHashMap 源碼詳細分析（JDK1.8）》
  • HashTable: 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體劫灶，鏈表則是主要為了解決哈希沖突而存在的
  • TreeMap: 紅黑樹（自平衡的排序二叉樹）

推薦閱讀：

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末供汛，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子涌穆，更是在濱河造成了極大的恐慌怔昨，老刑警劉巖，帶你破解...
    沈念sama閱讀 206,482評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件宿稀，死亡現(xiàn)場離奇詭異趁舀，居然都是意外死亡，警方通過查閱死者的電腦和手機祝沸，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,377評論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門矮烹，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人罩锐，你說我怎么就攤上這事奉狈。” “怎么了涩惑？”我有些...
    開封第一講書人閱讀 152,762評論 0贊 342
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵嘹吨，是天一觀的道長。 經(jīng)常有香客問我境氢，道長，這世上最難降的妖魔是什么碰纬？ 我笑而不...
    開封第一講書人閱讀 55,273評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任萍聊，我火速辦了婚禮，結(jié)果婚禮上悦析，老公的妹妹穿的比我還像新娘寿桨。我一直安慰自己，他們只是感情好强戴，可當(dāng)我...
    茶點故事閱讀 64,289評論 5贊 373
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布亭螟。 她就那樣靜靜地躺著，像睡著了一般骑歹。 火紅的嫁衣襯著肌膚如雪预烙。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 49,046評論 1贊 285
  • 城市分裂傳說
    那天道媚，我揣著相機與錄音扁掸，去河邊找鬼翘县。 笑死，一個胖子當(dāng)著我的面吹牛谴分，可吹牛的內(nèi)容都是我干的锈麸。 我是一名探鬼主播，決...
    沈念sama閱讀 38,351評論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼牺蹄，長吁一口氣：“原來是場噩夢啊……” “哼忘伞！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起沙兰，我...
    開封第一講書人閱讀 36,988評論 0贊 259
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤氓奈，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后僧凰，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體探颈，經(jīng)...
    沈念sama閱讀 43,476評論 1贊 300
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 35,948評論 2贊 324
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年训措，在試婚紗的時候發(fā)現(xiàn)自己被綠了伪节。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,064評論 1贊 333
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡绩鸣，死狀恐怖怀大，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情呀闻，我是刑警寧澤化借，帶...
    沈念sama閱讀 33,712評論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站捡多，受9級特大地震影響蓖康，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜垒手，卻給世界環(huán)境...
    茶點故事閱讀 39,261評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一蒜焊、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧科贬，春花似錦泳梆、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,264評論 0贊 19
  • 一樁弒父案优妙，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至憎账，卻和暖如春套硼，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背胞皱。 一陣腳步聲響...
    開封第一講書人閱讀 31,486評論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人带膜。 一個月前我還...
    沈念sama閱讀 45,511評論 2贊 354
  • 代替公主和親
    正文 我出身青樓和敬，卻偏偏與公主長得像，于是被迫代替她去往敵國和親做入。 傳聞我的和親對象是個殘疾皇子竟块，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 42,802評論 2贊 345