一精置、集合基礎(chǔ)

1.01 集合的類繼承關(guān)系仁锯？

• java集合主要由Collection和Map兩大接口派生出來：
  • Collection用于存放單一元素：
    • List
    • Set
    • Queue
  • Map用于存放鍵值對

1.02 說說 List, Set, Queue, Map 四者的區(qū)別？

• List：有序的此洲、可重復(fù)
  • Arraylist： Object[] 數(shù)組
  • Vector：Object[] 數(shù)組
  • LinkedList： 雙向鏈表(JDK1.6 之前為循環(huán)鏈表厂汗，JDK1.7 取消了循環(huán))
• Set：無序不可重復(fù)
  • HashSet(無序，唯一): 基于 HashMap 實現(xiàn)的呜师，底層采用
  • LinkedHashSet: LinkedHashSet 是 HashSet 的子類娶桦，構(gòu)造函數(shù)是用LinkedHashMap來構(gòu)造的，LinkedHashMap又是在HashMap的基礎(chǔ)上汁汗，重寫了三個保留方法 afterNodeAccess衷畦、afterNodeInsertion、afterNodeRemoval來維護雙向鏈表的知牌。
  • TreeSet(有序祈争，唯一): 紅黑樹(自平衡的排序二叉樹)
• Queue：先進先出、有序角寸、可重復(fù)
  • ArrayBlockingQueue：數(shù)組 + 雙指針
  • PriorityQueue：Object[] 數(shù)組來實現(xiàn)二叉堆
• Map：鍵值對存儲菩混，key不可重復(fù)忿墅，value可以重復(fù)
  • HashMap：JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的，之后換成了數(shù)組+鏈表+紅黑樹的方式沮峡，當(dāng)鏈表長度達到8時球匕，看看數(shù)組長度，數(shù)組長度小于64帖烘，進行擴容亮曹，大于64，轉(zhuǎn)成紅黑樹
  • Hashtable： 數(shù)組+鏈表組成的秘症，數(shù)組是 Hashtable 的主體照卦，鏈表則是主要為了解決哈希沖突而存在的
  • TreeMap： 紅黑樹（自平衡的排序二叉樹）

1.03 如何選用集合？

• 當(dāng)存放鍵值對時乡摹，選用Map接口下集合役耕，需要對key排序時，選用TreeMap聪廉，需要保證線程安全瞬痘，就用ConcurrentHashMap。
• 當(dāng)我們只需要存放元素值時板熊，就選擇實現(xiàn)Collection 接口的集合框全，需要保證元素唯一時選擇實現(xiàn) Set 接口的集合比如 TreeSet 或 HashSet，不需要就選擇實現(xiàn) List 接口的比如 ArrayList 或 LinkedList干签，然后再根據(jù)實現(xiàn)這些接口的集合的特點來選用津辩。

1.04 為什么要使用集合？

• 為了存儲一組類型相同的數(shù)據(jù)容劳。

1.05 Arraylist 和 Vector 的區(qū)別?

• ArrayList 是 List 的主要實現(xiàn)類喘沿，底層使用 Object[ ]存儲，適用于頻繁的查找工作竭贩，線程不安全蚜印。
• Vector 是 List 的古老實現(xiàn)類，底層使用Object[ ] 存儲留量，線程安全的（方法上加synchronized關(guān)鍵字）窄赋。

1.06 Arraylist 與 LinkedList 區(qū)別?

• 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全肪获。
• 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是 Object 數(shù)組寝凌；LinkedList 底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)柒傻。
• 插入和刪除是否受元素位置的影響：
  • ArrayList插入O(1)孝赫，刪除O(n)要移動元素，按照index插入O(n)
  • LinkedList：插入O(1)红符，按照index插入O(n)指針移動到刪除位置青柄，刪除O(1)
• 是否支持快速隨機訪問：
  • LinkedList 不支持高效的隨機元素訪問
  • ArrayList 支持伐债。快速隨機訪問就是通過元素的序號快速獲取元素對象
• 內(nèi)存空間占用：
  • ArrayList 的空 間浪費主要體現(xiàn)在在 list 列表的結(jié)尾會預(yù)留一定的容量空間
  • LinkedList 的空間花費則體現(xiàn)在它的每一個元素都需要消耗比 ArrayList 更多的空間（要存放指針）

1.07 comparable 和 Comparator 的區(qū)別致开？

• comparable：接口來自java.lang包峰锁，內(nèi)部比較器，一個類如果想要使用 Collections.sort(list) 方法進行排序双戳，則需要實現(xiàn)該接口虹蒋，重寫compareTo(Object obj)方法。
• Comparator：接口來自Java.util包飒货，外部比較器魄衅，用于對那些沒有實現(xiàn)Comparable接口或者對已經(jīng)實現(xiàn)的Comparable接口中的排序規(guī)則不滿意進行排序。無需改變類的結(jié)構(gòu)塘辅，更加靈活晃虫。重寫compare(Object obj1, Object obj2)方法，（策略模式）扣墩。

1.08 無序性和不可重復(fù)性的含義是什么哲银？

• 無序性是指不按照數(shù)組的索引順序添加，而是根據(jù)數(shù)據(jù)的hash值決定呻惕。
• 不可重復(fù)性是指荆责，添加的元素按照equals方法比較時，返回false亚脆。要求重寫equals和hashCode方法草巡。

1.09 HashSet、LinkedHashSet 和 TreeSet 三者的異同型酥？

• 相同：都是 Set 接口的實現(xiàn)類山憨，都能保證元素唯一，并且都不是線程安全的弥喉。
• 底層數(shù)據(jù)結(jié)構(gòu)不同：
  • HashSet 的底層數(shù)據(jù)結(jié)構(gòu)是哈希表（基于 HashMap 實現(xiàn)）
  • LinkedHashSet 繼承自HashSet（基于LinkedHashMap實現(xiàn)）郁竟，在構(gòu)造函數(shù)中，調(diào)用了HashSet的提供LinkedHashMap的構(gòu)造函數(shù)由境，由LinkedHashMap來保證FIFO棚亩，其他api都是共用HashSet的。
  • TreeSet 底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹（基于TreeMap實現(xiàn)虏杰，TreeMap是用紅黑樹實現(xiàn)的）讥蟆，元素是有序的，排序的方式有自然排序和定制排序纺阔。
• 應(yīng)用場景不同：
  • HashSet 用于不需要保證元素插入和取出順序的場景
  • LinkedHashSet 用于保證元素的插入和取出順序滿足 FIFO 的場景
  • TreeSet 用于支持對元素自定義排序規(guī)則的場景

1.20 Queue 與 Deque 的區(qū)別瘸彤？

• Queue：

  • Queue 是單端隊列，只能從一端插入元素笛钝，另一端刪除元素质况，實現(xiàn)上一般遵循 先進先出（FIFO） 規(guī)則愕宋。

  • 根據(jù) 因為容量問題而導(dǎo)致操作失敗后處理方式的不同 可以分為兩類方法: 一種在操作失敗后會拋出異常，另一種則會返回特殊值结榄。

    Queue接口	拋出異常	返回特殊值
    插入隊尾	add(E e)	offer(E e)
    刪除隊首	remove()	poll()
    查詢隊首元素	element()	peek()

    類似基于列表的方法拋異常中贝，add、remove臼朗、element

• Deque:

  • Deque 是雙端隊列邻寿，在隊列的兩端均可以插入或刪除元素。

  • Deque 擴展了 Queue 的接口, 增加了在隊首和隊尾進行插入和刪除的方法视哑，同樣根據(jù)失敗后處理方式的不同分為兩類老厌。

    Deque接口	拋出異常	返回特殊值
    插入隊首	addFirst(E e)	offerFirst(E e)
    插入隊尾	addLast(E e)	offerLast(E e)
    刪除隊首	removeFirst()	pollFirst()
    刪除隊尾	removeLast()	pollLast()
    查詢對首元素	getFirst()	peekFirst()
    查詢隊尾元素	getLast()	peekLast()

    類似基于列表的方法拋異常，add黎炉、remove枝秤、get

  • Deque 還提供有 push() 和 pop() 等其他方法，可用于模擬棧慷嗜。

1.21 ArrayDeque 與 LinkedList 的區(qū)別淀弹？

• ArrayDeque 和 LinkedList 都實現(xiàn)了 Deque 接口，兩者都具有隊列的功能庆械。
• ArrayDeque 是基于可變長的數(shù)組和雙指針來實現(xiàn)薇溃，而 LinkedList 則通過鏈表來實現(xiàn)。
• ArrayDeque 不支持存儲 NULL 數(shù)據(jù)缭乘，但 LinkedList 支持沐序。
• ArrayDeque 插入時可能存在擴容過程, 不過均攤后的插入操作依然為 O(1)。雖然 LinkedList 不需要擴容堕绩，但是每次插入數(shù)據(jù)時均需要申請新的堆空間策幼，均攤性能相比更慢。
• 從性能的角度上奴紧，選用 ArrayDeque 來實現(xiàn)隊列要比 LinkedList 更好特姐。此外，ArrayDeque 也可以用于實現(xiàn)棧黍氮。

1.22 談一談 PriorityQueue唐含？

• PriorityQueue 與 Queue 的區(qū)別在于元素出隊順序是與優(yōu)先級相關(guān)的，即總是優(yōu)先級最高的元素先出隊沫浆。
• 利用了二叉堆的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的捷枯，底層使用可變長的數(shù)組來存儲數(shù)據(jù)。
• 通過堆元素的上浮和下沉专执，實現(xiàn)了在 O(logn) 的時間復(fù)雜度內(nèi)插入元素和刪除堆頂元素淮捆。
• 是非線程安全的，且不支持存儲 NULL 和 non-comparable 的對象。
• 默認是小頂堆争剿，但可以接收一個 Comparator 作為構(gòu)造參數(shù)已艰，從而來自定義元素優(yōu)先級的先后痊末。

1.23 HashMap 和 Hashtable 的區(qū)別蚕苇？

• 線程是否安全： HashMap 是非線程安全的，Hashtable 是線程安全的,因為 Hashtable 內(nèi)部的方法基本都經(jīng)過synchronized 修飾凿叠。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧Ｉ浴）
• 效率： 因為線程安全的問題，HashMap 要比 Hashtable 效率高一點盒件。另外蹬碧，Hashtable 基本被淘汰，不要在代碼中使用它炒刁。
• 對 Null key 和 Null value 的支持： HashMap 可以存儲 null 的 key 和 value恩沽，但 null 作為鍵只能有一個，null 作為值可以有多個翔始；Hashtable 不允許有 null 鍵和 null 值罗心，否則會拋出 NullPointerException。
• 初始容量大小和每次擴充容量大小的不同 ：
  • ① 創(chuàng)建時如果不指定容量初始值城瞎，Hashtable 默認的初始大小為 11渤闷，之后每次擴充，容量變?yōu)樵瓉淼?2n+1脖镀。HashMap 默認的初始化大小為 16飒箭。之后每次擴充，容量變?yōu)樵瓉淼?2 倍蜒灰。
  • ② 創(chuàng)建時如果給定了容量初始值弦蹂，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為 2 的冪次方大星拷选（HashMap 中的tableSizeFor()方法保證盈匾，下面給出了源代碼）。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小毕骡。

• 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化削饵，當(dāng)鏈表長度大于閾值（默認為 8）（將鏈表轉(zhuǎn)換成紅黑樹前會判斷，如果當(dāng)前數(shù)組的長度小于 64未巫，那么會選擇先進行數(shù)組擴容窿撬，而不是轉(zhuǎn)換為紅黑樹）時，將鏈表轉(zhuǎn)化為紅黑樹叙凡，以減少搜索時間劈伴。Hashtable 沒有這樣的機制。

1.24 HashMap 和 HashSet 區(qū)別?

• HashSet 底層就是基于 HashMap 實現(xiàn)的，HashSet 持有一個HashMap跛璧。
• HashMap實現(xiàn)了Map接口严里，HashSet實現(xiàn)了Set接口。
• HashMap存鍵值對追城，HashSet存對象刹碾，（值存的一個Object假值）。
• HashMap添加元素用put方法座柱，HashSet添加元素用add方法迷帜。
• HashMap計算hashCode用鍵計算，HashSet用存儲的對象計算色洞。

1.25 HashMap 和 TreeMap 區(qū)別戏锹？

• TreeMap 和HashMap 都繼承自AbstractMap ，但是需要注意的是TreeMap它還實現(xiàn)了NavigableMap接口和SortedMap 接口火诸。
• NavigableMap 接口讓 TreeMap 有了對集合內(nèi)元素的搜索的能力锦针。
• SortedMap接口讓 TreeMap 有了對集合中的元素根據(jù)鍵排序的能力。默認是按 key 的升序排序置蜀，不過我們也可以指定排序的比較器奈搜，比如在創(chuàng)建TreeMap時，實現(xiàn)Comparator接口盾碗。

1.26 HashSet 如何檢查重復(fù)媚污？

• 當(dāng)你把對象加入HashSet時，HashSet 會先計算對象的hashcode值來判斷對象加入的位置廷雅，同時也會與其他加入的對象的 hashcode 值作比較耗美，如果沒有相等的 hashcode，HashSet 會假設(shè)對象沒有重復(fù)出現(xiàn)航缀。但是如果發(fā)現(xiàn)有相同 hashcode 值的對象商架，這時會調(diào)用equals()方法來檢查 hashcode 相等的對象是否真的相同。如果兩者相同芥玉，HashSet 就不會讓加入操作成功蛇摸。

1.27 HashMap 的長度為什么是 2 的冪次方？

• 為了讓計算槽位的算法能從 hashCode%n 轉(zhuǎn)換成位移&運算灿巧，提高運算速度赶袄。
• 為了讓數(shù)據(jù)分布更加均勻

1.28 HashMap 有哪幾種常見的遍歷方式?

• 迭代器 EntrySet
• 迭代器 KeySet
• ForEach EntrySet
• ForEach KeySet
• Lambda forEach
• EntrySet/KeySet Streams

1.29 ConcurrentHashMap 和 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 的底層數(shù)據(jù)結(jié)構(gòu)采用 數(shù)組+鏈表 的形式盾似。
• 實現(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 來操作， 整個看起來就像是優(yōu)化過且線程安全的 HashMap乾吻。
  • Hashtable(同一把鎖) :使用 synchronized 來保證線程安全髓梅，效率非常低下拟蜻。當(dāng)一個線程訪問同步方法時绎签，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態(tài)酝锅，如使用 put 添加元素诡必，另一個線程不能使用 put 添加元素，也不能使用 get搔扁，競爭會越來越激烈效率越低爸舒。

1.30 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 是一種可重入鎖。
  • .一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組设哗。一個 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ù)組+鏈表/紅黑二叉樹烦感。
  • Java 8 在鏈表長度超過一定閾值（8）時將鏈表（尋址時間復(fù)雜度為 O(N)）轉(zhuǎn)換為紅黑樹（尋址時間復(fù)雜度為 O(log(N))巡社。
  • synchronized 只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點，這樣只要 hash 不沖突啸盏，就不會產(chǎn)生并發(fā)重贺，效率又提升 N 倍。

1.31 Collections 工具類常用方法？

• 排序：

  // 反轉(zhuǎn)
  void reverse(List list)
  // 隨機排序
  void shuffle(List list)
  // 按自然排序的升序排序
  void sort(List list)
  // 定制排序气笙，由Comparator控制排序邏輯
  void sort(List list, Comparator c)
  // 交換兩個索引位置的元素
  void swap(List list, int i , int j)
  // 旋轉(zhuǎn)次企。當(dāng)distance為正數(shù)時，將list后distance個元素整體移到前面潜圃。
  // 當(dāng)distance為負數(shù)時缸棵，將 list的前distance個元素整體移到后面
  void rotate(List list, int distance)
  

• 查找,替換操作：

  // 對List進行二分查找，返回索引谭期，注意List必須是有序的
  int binarySearch(List list, Object key)
  // 根據(jù)元素的自然順序堵第，返回最大的元素。 類比int min(Collection coll)
  int max(Collection coll)
  // 根據(jù)定制排序隧出，返回最大元素踏志，排序規(guī)則由Comparatator類控制。
  // 類比int min(Collection coll, Comparator c)
  int max(Collection coll, Comparator c)
  // 用指定的元素代替指定list中的所有元素
  void fill(List list, Object obj)
  // 統(tǒng)計元素出現(xiàn)次數(shù)
  int frequency(Collection c, Object o)
  // 統(tǒng)計target在list中第一次出現(xiàn)的索引胀瞪，找不到則返回-1针余，
  // 類比int lastIndexOfSubList(List source, list target)
  int indexOfSubList(List list, List target) 
  // 用新元素替換舊元素
  boolean replaceAll(List list, Object oldVal, Object newVal)
  

• **同步控制 **(不推薦，需要線程安全的集合類型時請考慮使用 JUC 包下的并發(fā)集合)

二凄诞、集合使用問題

2.01 判斷所有集合內(nèi)部的元素是否為空?

• 判斷所有集合內(nèi)部的元素是否為空圆雁，使用 isEmpty() 方法，而不是 size()==0 的方式帆谍。
• 因為 isEmpty() 方法的可讀性更好伪朽，并且時間復(fù)雜度為 O(1)。
• 絕大部分我們使用的集合的 size() 方法的時間復(fù)雜度也是 O(1)汛蝙，不過烈涮，也有很多復(fù)雜度不是 O(1) 的，ConcurrentHashMap的size()時間復(fù)雜度為O(n)患雇，動態(tài)去統(tǒng)計hash槽里的數(shù)據(jù)跃脊。

2.02 集合轉(zhuǎn) Map？

• 在使用 java.util.stream.Collectors 類的 toMap() 方法轉(zhuǎn)為 Map 集合時苛吱，一定要注意當(dāng) value 為 null 時會拋 NPE 異常酪术。

2.03 集合遍歷？

• 不要在 foreach 循環(huán)里進行元素的 remove/add 操作翠储。remove 元素請使用 Iterator 方式绘雁，如果并發(fā)操作，需要對 Iterator 對象加鎖援所。
• Java8 開始庐舟，可以使用 list.removeIf()方法刪除滿足特定條件的元素。

2.04 集合去重住拭？

• 可以利用 Set 元素唯一的特性挪略，可以快速對一個集合進行去重操作历帚，避免使用 List 的 contains() 進行遍歷去重或者判斷包含操作。
• HashSet 的 contains() 方法底部依賴的 HashMap 的 containsKey() 方法杠娱，時間復(fù)雜度接近于 O（1）（沒有出現(xiàn)哈希沖突的時候為 O（1））挽牢。
• ArrayList 的 contains() 方法是通過遍歷所有元素的方法來做的，時間復(fù)雜度接近是 O(n)摊求。

2.05 集合轉(zhuǎn)數(shù)組禽拔？

• 使用集合轉(zhuǎn)數(shù)組的方法，必須使用集合的 toArray(T[] array)室叉，傳入的是類型完全一致睹栖、長度為 0 的空數(shù)組。

2.06 數(shù)組轉(zhuǎn)集合茧痕？

• 使用工具類 Arrays.asList() 把數(shù)組轉(zhuǎn)換成集合時野来，不能使用其修改集合相關(guān)的方法， 它的 add/remove/clear 方法會拋出 UnsupportedOperationException 異常凿渊。

2.07 數(shù)組轉(zhuǎn)換為 ArrayList的方式?

• 手動實現(xiàn)工具類梁只，for循環(huán)挨個添加缚柳。
• 最簡便的方法埃脏，利用ArrayList的構(gòu)造方法，接收一個數(shù)組創(chuàng)建秋忙。
• java8的Stream彩掐；List myList = Arrays.stream(myArray).collect(Collectors.toList());
• 使用 Guava
• 使用 Apache Commons Collections
• 使用 Java9 的 List.of()方法

三、源碼分析

3.1 ArrayList源碼&擴容機制分析

3.1.1 ArrayList 簡介灰追？

• ArrayList繼承于 AbstractList 堵幽，實現(xiàn)了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口
• RandomAccess 是一個標(biāo)志接口，表明實現(xiàn)這個這個接口的 List 集合是支持快速隨機訪問的弹澎。在 ArrayList 中朴下，我們即可以通過元素的序號快速獲取元素對象评疗，這就是快速隨機訪問棍矛。
• ArrayList 實現(xiàn)了 Cloneable 接口 匀奏，即覆蓋了函數(shù)clone()冶忱，能被克隆纵东。
• ArrayList 實現(xiàn)了 java.io.Serializable接口酬诀，這意味著ArrayList支持序列化颓影，能通過序列化去傳輸枫虏。

3.1.2 Arraylist 和 Vector 的區(qū)別?

• ArrayList 是 List 的主要實現(xiàn)類报强，底層使用 Object[ ]存儲灸姊，適用于頻繁的查找工作，線程不安全 .
• Vector 是 List 的古老實現(xiàn)類秉溉，底層使用 Object[ ]存儲力惯，線程安全的碗誉，整個方法添加synchronized關(guān)鍵字，即鎖住當(dāng)前對象.

3.1.3 Arraylist 與 LinkedList 區(qū)別?

• 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的父晶，也就是不保證線程安全诗充。
• 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)诱建。
• 插入和刪除是否受元素位置的影響：
  • ArrayList 采用數(shù)組存儲蝴蜓，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響。
  • LinkedList 采用鏈表存儲俺猿，所以對于add(E e)方法的插入茎匠，刪除元素時間復(fù)雜度不受元素位置的影響，近似 O(1)押袍，如果是要在指定位置i插入和刪除元素的話（(add(int index, E element)） 時間復(fù)雜度近似為o(n))因為需要先移動到指定位置再插入诵冒。
• 是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持谊惭∑觯快速隨機訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)。
• 內(nèi)存空間占用： ArrayList 的空 間浪費主要體現(xiàn)在在 list 列表的結(jié)尾會可能會浪費一定的容量空間圈盔，而 LinkedList 的空間花費則體現(xiàn)在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）豹芯。

3.1.4 Arraylist源碼分析？

• 默認初始容量大小10驱敲。
• 無參構(gòu)造默認返回一個空數(shù)組铁蹈，第一次添加元素時擴容到默認初始容量10。
• 用Object數(shù)組保存數(shù)據(jù)众眨。
• 帶初始容量參數(shù)的構(gòu)造函數(shù)握牧，會返回一個初始容量大小的Arraylist。
• 帶集合參數(shù)的構(gòu)造函數(shù)娩梨，構(gòu)造一個包含指定集合的元素的列表沿腰。

3.1.5 Arraylist擴容機制？

• add添加元素之前狈定，先擴容颂龙。
• 首先計算每次add前，需要的最小數(shù)組長度掸冤，為元素個數(shù)+1厘托。當(dāng)元素個數(shù)為0時，最小需要長度會賦默認值10稿湿。當(dāng)最小需要值大于數(shù)組的長度铅匹，需要進行擴容。
• 擴容大小為饺藤，oldCapacity + (oldCapacity >> 1)包斑，即1.5倍原長度流礁。
• 因為不是線程安全的，不會加鎖罗丰。

3.1.6 System.arraycopy() 和 Arrays.copyOf()方法神帅？

• System.arraycopy()是本地方法
• Arrays.copyOf()是基于System.arraycopy()封裝的方法

3.1.7 ensureCapacity(int minCapacity)方法？

• ensureCapacity方法在源碼中沒有調(diào)用萌抵，這個方法是留給使用者調(diào)用找御，作用是大量add元素時，減少擴容次數(shù)绍填，提高效率霎桅。

3.2 HashMap源碼&底層數(shù)據(jù)結(jié)構(gòu)分析

3.2.01 HashMap源碼&底層數(shù)據(jù)結(jié)構(gòu)分析？

• JDK1.8 之前 HashMap 由 數(shù)組+鏈表 組成的讨永，JDK1.8 之后由 數(shù)組 + 鏈表/紅黑樹 組成滔驶。當(dāng)鏈表長度大于閾值（默認為 8）（數(shù)組的長度大于等于 64，那么會選擇先進行數(shù)組擴容卿闹，而不是轉(zhuǎn)換為紅黑樹）時揭糕，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間锻霎。
• 默認的初始化大小為 16著角。之后每次擴充，容量變?yōu)樵瓉淼?2 倍量窘。并且雇寇， HashMap 總是使用 2 的冪作為哈希表的大小。
• 哈希表大小總是2的冪次蚌铜，是為了將求余計算轉(zhuǎn)為邏輯與運算，提高運算效率嫩海，同時為了讓鍵值分布更均勻冬殃。

3.2.02 HashMap類成員變量？

• 默認的初始容量是16叁怪。
• 默認的填充因子0.75f审葬，除了默認的填充因子，還可以自己指定填充因子奕谭。
  • 填充因子是控制數(shù)據(jù)疏密的程度的涣觉，填充因子越接近1，填充密度越大血柳，查找越慢（越容易出現(xiàn)沖突）官册。填充因子越接近0，填充密度約心寻啤（浪費空間）膝宁，越容易查找鸦难。官方給出的默認值是0.75f.
• 鏈表轉(zhuǎn)成紅黑樹閾值是8。
• 紅黑樹退化成鏈表閾值是6员淫。
• 鏈表轉(zhuǎn)紅黑樹數(shù)組的最小長度是64合蔽。
• Node<k,v>[]數(shù)組存儲鍵值對，數(shù)組長度是2的冪次介返。
• 修改計數(shù)器拴事。
• 存儲的元素個數(shù)。
• 臨界值 = 容量*填充因子圣蝎， 當(dāng)實際存入個數(shù)大于臨界值時挤聘，會觸發(fā)擴容。
  • threshold = capacity * loadFactor（臨界值 = 容量*填充因子）捅彻，當(dāng) Size>=threshold的時候组去，那么就要考慮對數(shù)組的擴增了，也就是說步淹，這個的意思就是 衡量數(shù)組是否需要擴增的一個標(biāo)準(zhǔn)从隆。

3.2.03 HashMap 三個構(gòu)造函數(shù)？

• 無參構(gòu)造函數(shù)缭裆，創(chuàng)建一個數(shù)組大小默認16的HashMap键闺。
• 包含另一個“Map”的構(gòu)造函數(shù)。
• 指定“容量大小”的構(gòu)造函數(shù)澈驼。
• 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)辛燥。

3.2.04 HashMap put方法分析?

• 判斷table數(shù)組是否為空，如果為空進行擴容缝其。
• 計算哈希值挎塌，看看在table中是否存在，不存在直接插入數(shù)據(jù)内边，存在進行對比值榴都，值相同直接覆蓋返回，值不同判斷節(jié)點類型漠其。
• 如果節(jié)點為樹節(jié)點嘴高，直接插入，如果節(jié)點為鏈表和屎，插入后判斷長度是否大于8拴驮，table長度是否大于64，是的話轉(zhuǎn)換成樹柴信，否則++size后套啤，判斷是否需要擴容。

3.2.05 HashMap get方法颠印？

• 計算hash取余（轉(zhuǎn)移位運算）纲岭，計算出在table中的位置抹竹。

• 取第一個節(jié)點key的進行相等判斷，如果key相等止潮，直接返回窃判，如果key不相等繼續(xù)判斷節(jié)點類型。

• 如果節(jié)點為樹喇闸，遍歷樹袄琳，如果節(jié)點為鏈表遍歷鏈表。

3.2.06 resize 擴容方法燃乍？

• 首先判斷原始容量是不是已經(jīng)達到最大值（Integer的最大值21億唆樊，-2^31 —— 2^31-1），如果達到最大值刻蟹，不再擴容逗旁，只能隨便碰撞了。
• 如果沒有達到最大值舆瘪，擴大到原值的2倍片效。
• 重新計算臨界值（閾值）。
• 新創(chuàng)建一個原來容量2倍容量的table英古，遍歷舊table淀衣，將舊table的數(shù)據(jù)重新hash插入到新table中，重新插入會分三種情況：
  • 如果舊節(jié)點的next為空召调，直接插入新的節(jié)點
  • 如果舊節(jié)點的類型是樹
  • 如果舊節(jié)點是鏈表
• 擴容會伴隨重新hash（hash存放在Node節(jié)點里）膨桥，非常耗時。所以應(yīng)該盡量避免觸發(fā)擴容唠叛。

3.3 ConcurrentHashMap源碼&底層數(shù)據(jù)結(jié)構(gòu)分析

3.3.1 JDK1.7:

3.3.1.1 ConcurrentHashMap源碼&底層數(shù)據(jù)結(jié)構(gòu)分析只嚣？

• 不可變的Segment數(shù)組內(nèi)嵌套可擴容的HashEntry<K,V>[]數(shù)組組成，當(dāng)出現(xiàn)沖突時玻墅，HashEntry<K,V>會轉(zhuǎn)成鏈表解決沖突介牙，Segment數(shù)組默認長度為16（不可變），可以理解為支持最大16個并發(fā)澳厢。

3.3.1.2 put方法分析？

• 計算要 put 的 key 的位置囚似，獲取指定位置的 Segment
• 如果指定位置的 Segment 為空剩拢。則初始化這個 Segment：
  • 檢查計算得到的位置的 Segment 是否為null
  • 為 null 繼續(xù)初始化，使用 Segment[0] 的容量和負載因子創(chuàng)建一個 HashEntry 數(shù)組饶唤。
  • 再次檢查計算得到的指定位置的 Segment 是否為null徐伐。
  • 使用創(chuàng)建的 HashEntry 數(shù)組初始化這個 Segment。
  • 自旋判斷計算得到的指定位置的 Segment 是否為null募狂，使用 CAS 在這個位置賦值為 Segment办素。
• Segment.put 插入 key,value 值：
  • tryLock() 獲取鎖角雷，獲取不到使用 scanAndLockForPut 方法繼續(xù)獲取。
  • 計算 put 的數(shù)據(jù)要放入的index 位置性穿，然后獲取這個位置上的 HashEntry 勺三。
  • 遍歷 put 新元素。為什么要遍歷需曾？因為這里獲取的 HashEntry 可能是一個空元素吗坚，也可能是鏈表已存在，所以要區(qū)別對待：
    • 如果這個位置上的 HashEntry 不存在：
      • 如果當(dāng)前容量大于擴容閥值呆万，小于最大容量商源，進行擴容
      • 直接頭插法插入。
    • 如果這個位置上的 HashEntry 存在：
      • 判斷鏈表當(dāng)前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致谋减。一致則替換值牡彻。
      • 不一致，獲取鏈表下一個節(jié)點出爹，直到發(fā)現(xiàn)相同進行值替換庄吼，或者鏈表表里完畢沒有相同的。
      • 如果當(dāng)前容量大于擴容閥值以政，小于最大容量霸褒，進行擴容。
      • 直接鏈表頭插法插入
  • 如果要插入的位置之前已經(jīng)存在盈蛮，替換后返回舊值废菱，否則返回 null

3.3.1.3 scanAndLockForPut方法分析？

• 自旋獲取鎖抖誉，如果自旋超過最大自旋次數(shù)殊轴，使用lock() 阻塞獲取鎖。

3.3.1.4 rehash方法擴容袒炉？

• ConcurrentHashMap 的擴容只會擴容到原來的2倍旁理。老數(shù)組里的數(shù)據(jù)移動到新的數(shù)組時，位置要么不變我磁，要么變?yōu)?index+ oldSize孽文，參數(shù)里的 node 會在擴容之后使用鏈表頭插法插入到指定位置。

3.3.1.5 get方法查找夺艰？

• 計算得到 key 的存放位置芋哭。
• 遍歷指定位置查找相同 key 的 value 值。

JDK1.8:

3.3.2.1 JDK1.8 ConcurrentHashMap源碼&底層數(shù)據(jù)結(jié)構(gòu)分析郁副？

• 數(shù)據(jù)結(jié)構(gòu)：Node 數(shù)組 + 鏈表 / 紅黑樹减牺，與HashMap類似。

initTable 方法初始化？

• ConcurrentHashMap 的初始化是通過自旋和 CAS 操作完成的拔疚。里面需要注意的是變量 sizeCtl 肥隆，它的值決定著當(dāng)前的初始化狀態(tài)。
• -1 說明正在初始化
• -N 說明有N-1個線程正在進行擴容

put 方法稚失？

• key栋艳、value不允許為null。
• 進入自旋處理墩虹，首先判斷table是不是存在嘱巾，不存在需要初始化，然后自旋一次诫钓。
• 判斷計算出來的位置是不是為null旬昭，為null就cas嘗試寫入，寫入成功就跳出自旋菌湃，否則進入下一次自旋问拘。
• 判斷hashcode == MOVED == -1，如果是惧所，就需要擴容骤坐。
• 如果都不滿足，則利用synchronized加鎖寫入數(shù)據(jù)下愈，寫入數(shù)據(jù)要分成鏈表和紅黑樹處理纽绍。
• 節(jié)點加入成功后，判斷是否達到樹化閾值8势似，如果達到拌夏，需要進行樹化。樹化時也要判斷數(shù)組長度是否達到64了履因，如果沒有達到障簿，只是擴容。

get 方法栅迄？

• 根據(jù) hash 值計算位置站故。

• 查找到指定位置，如果頭節(jié)點就是要找的毅舆，直接返回它的 value西篓。

• 如果頭節(jié)點 hash 值小于 0 ，說明正在擴容或者是紅黑樹憋活，查找之污淋。

• 如果是鏈表，遍歷查找之余掖。