java集合筆記
- 集合概述
  - 什么是集合
  - 集合的特點
  - 集合和陣列的區別
  - 使用集合框架的好處
  - 常用的集合類有哪些？
  - List，Set，Map三者的區別？List、Set、Map 是否繼承自 Collection 介面？List、Map、Set 三個介面存取元素時，各有什么特點？
  - 集合框架底層資料結構
  - 哪些集合類是執行緒安全的？
  - Java集合的快速失敗機制 “fail-fast”？
  - 怎么確保一個集合不能被修改？
- Collection介面
  - List介面
    - 迭代器 Iterator 是什么？
    - Iterator 怎么使用？有什么特點？
    - 如何邊遍歷邊移除 Collection 中的元素？
    - Iterator 和 ListIterator 有什么區別？
    - 遍歷一個 List 有哪些不同的方式？每種方法的實作原理是什么？Java 中 List 遍歷的最佳實踐是什么？
    - 說一下 ArrayList 的優缺點
    - 如何實作陣列和 List 之間的轉換？
    - ArrayList 和 LinkedList 的區別是什么？
    - ArrayList 和 Vector 的區別是什么？
    - 插入資料時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存盤性能和特性？
    - 多執行緒場景下如何使用 ArrayList？
    - 為什么 ArrayList 的 elementData 加上 transient 修飾？
    - List 和 Set 的區別
  - Set介面
    - 說一下 HashSet 的實作原理？
    - HashSet如何檢查重復？HashSet是如何保證資料不可重復的？
  - Queue
    - BlockingQueue是什么？
    - 在 Queue 中 poll()和 remove()有什么區別？
- Map介面
  - 說一下 HashMap 的實作原理？
  - HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實作
  - HashMap的put方法的具體流程？
  - HashMap的擴容操作是怎么實作的？
  - HashMap是怎么解決哈希沖突的？
  - 能否使用任何類作為 Map 的 key？
  - 為什么HashMap中String、Integer這樣的包裝類適合作為Key？
  - 如果使用Object作為HashMap的Key，應該怎么辦呢？
  - HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？
  - HashMap 的長度為什么是2的冪次方
  - HashMap 與 HashTable 有什么區別？
  - 如何決定使用 HashMap 還是 TreeMap？
  - HashMap 和 ConcurrentHashMap 的區別
  - ConcurrentHashMap 和 Hashtable 的區別？
  - ConcurrentHashMap 底層具體實作知道嗎？實作原理是什么？
  - Array 和 ArrayList 有何區別？
  - 如何實作 Array 和 List 之間的轉換？
  - comparable 和 comparator的區別？
  - Collection 和 Collections 有什么區別？
  - TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？

java集合筆記

集合概述

什么是集合

集合框架：用于存盤資料的容器，

集合框架是為表示和操作集合而規定的一種統一的標準的體系結構，
任何集合框架都包含三大塊內容：對外的介面、介面的實作和對集合運算的演算法，

介面：表示集合的抽象資料型別，介面允許我們操作集合時不必關注具體實作，從而達到“多型”，在面向物件編程語言中，介面通常用來形成規范，

實作：集合介面的具體實作，是重用性很高的資料結構，

演算法：在一個實作了某個集合框架中的介面的物件身上完成某種有用的計算的方法，例如查找、排序等，這些演算法通常是多型的，因為相同的方法可以在同一個介面被多個類實作時有不同的表現，事實上，演算法是可復用的函式，
它減少了程式設計的辛勞，

集合框架通過提供有用的資料結構和演算法使你能集中注意力于你的程式的重要部分上，而不是為了讓程式能正常運轉而將注意力于低層設計上，
通過這些在無關API之間的簡易的互用性，使你免除了為改編物件或轉換代碼以便聯合這些API而去寫大量的代碼，它提高了程式速度和質量，

集合的特點

集合的特點主要有如下兩點：

物件封裝資料，物件多了也需要存盤，集合用于存盤物件，
物件的個數確定可以使用陣列，物件的個數不確定的可以用集合，因為集合是可變長度的，

集合和陣列的區別

陣列是固定長度的；集合可變長度的，
陣列可以存盤基本資料型別，也可以存盤參考資料型別；集合只能存盤參考資料型別，
陣列存盤的元素必須是同一個資料型別；集合存盤的物件可以是不同資料型別，

使用集合框架的好處

容量自增長；
提供了高性能的資料結構和演算法，使編碼更輕松，提高了程式速度和質量；
允許不同 API 之間的互操作，API之間可以來回傳遞集合；
可以方便地擴展或改寫集合，提高代碼復用性和可操作性，
通過使用JDK自帶的集合類，可以降低代碼維護和學習新API成本，

常用的集合類有哪些？

Map介面和Collection介面是所有集合框架的父介面：

Collection介面的子介面包括：Set介面和List介面
Map介面的實作類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
Set介面的實作類主要有：HashSet、TreeSet、LinkedHashSet等
List介面的實作類主要有：ArrayList、LinkedList、Stack以及Vector等

List，Set，Map三者的區別？List、Set、Map 是否繼承自 Collection 介面？List、Map、Set 三個介面存取元素時，各有什么特點？

集合框架底層資料結構

Collection

List

Arraylist： Object陣列
Vector： Object陣列
LinkedList：雙向回圈鏈表

HashSet（無序，唯一）：底層采用 HashMap 來保存元素
LinkedHashSet： LinkedHashSet 繼承于HashSet，并且其內部是通過 LinkedHashMap 來實作的，
TreeSet（有序，唯一）：紅黑樹(自平衡的排序二叉樹，)

Map

HashMap： JDK1.8之前HashMap由陣列+鏈表組成的；JDK1.8以后鏈表+紅黑樹；
LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由陣列和鏈表或紅黑樹組成，另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序，同時通過對鏈表進行相應的操作，實作了訪問順序相關邏輯，
HashTable：陣列+鏈表組成的，陣列是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在
TreeMap：紅黑樹（自平衡的排序二叉樹）

哪些集合類是執行緒安全的？

vector：就比arraylist多了個同步化機制（執行緒安全），因為效率較低，現在已經不太建議使用，在web應用中，特別是前臺頁面，往往效率（頁面回應速度）是優先考慮的，
statck：堆疊類，先進后出，
hashtable：就比hashmap多了個執行緒安全，
enumeration：列舉，相當于迭代器，

Java集合的快速失敗機制 “fail-fast”？

是java集合的一種錯誤檢測機制，當多個執行緒對集合進行結構上的改變的操作時，有可能會產生 fail-fast 機制，

例如：假設存在兩個執行緒（執行緒1、執行緒2），執行緒1通過Iterator在遍歷集合A中的元素，在某個時候執行緒2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這個時候程式就會拋出 ConcurrentModificationException 例外，從而產生fail-fast機制，

原因：迭代器在遍歷時直接訪問集合中的內容，并且在遍歷程序中使用一個 modCount 變數，集合在被遍歷期間如果內容發生變化，就會改變modCount的值，每當迭代器使用hashNext()/next()遍歷下一個元素之前，都會檢測modCount變數是否為expectedmodCount值，是的話就回傳遍歷；否則拋出例外，終止遍歷，

解決辦法：

在遍歷程序中，所有涉及到改變modCount值得地方全部加上synchronized，

使用CopyOnWriteArrayList來替換ArrayList

怎么確保一個集合不能被修改？

可以使用 Collections. unmodifiableCollection(Collection c) 方法來創建一個只讀集合，這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 例外，

Collection介面

List介面

迭代器 Iterator 是什么？

Iterator 介面提供遍歷任何 Collection 的介面，迭代器取代了 Java 集合框架中的 Enumeration，迭代器允許呼叫者在迭代程序中移除元素，

Iterator 怎么使用？有什么特點？

Iterator 的特點是只能單向遍歷，但是更加安全，因為它可以確保，在當前遍歷的集合元素被更改的時候，就會拋出 ConcurrentModificationException 例外，

如何邊遍歷邊移除 Collection 中的元素？

邊遍歷邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法

Iterator 和 ListIterator 有什么區別？

Iterator 可以遍歷 Set 和 List 集合，而 ListIterator 只能遍歷 List，
Iterator 只能單向遍歷，而 ListIterator 可以雙向遍歷（向前/后遍歷），
ListIterator 實作 Iterator 介面，然后添加了一些額外的功能，比如添加一個元素、替換一個元素、獲取前面或后面元素的索引位置，

遍歷一個 List 有哪些不同的方式？每種方法的實作原理是什么？Java 中 List 遍歷的最佳實踐是什么？

for 回圈遍歷，基于計數器，在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后停止，
迭代器遍歷，Iterator，Iterator 是面向物件的一個設計模式，目的是屏蔽不同資料集合的特點，統一遍歷集合的介面，Java 在 Collections 中支持了 Iterator 模式，
foreach 回圈遍歷，foreach 內部也是采用了 Iterator 的方式實作，使用時不需要顯式宣告 Iterator 或計數器，優點是代碼簡潔，不易出錯；缺點是只能做簡單的遍歷，不能在遍歷程序中操作資料集合，例如洗掉、替換，

推薦的做法就是，支持 Random Access 的串列可用 for 回圈遍歷，否則建議用 Iterator 或 foreach 遍歷，

說一下 ArrayList 的優缺點

優點：隨機訪問快

缺點：插入洗掉需復制，耗費性能

如何實作陣列和 List 之間的轉換？

陣列轉 List：使用 Arrays. asList(array) 進行轉換，
List 轉陣列：使用 List 自帶的 toArray() 方法，

ArrayList 和 LinkedList 的區別是什么？

資料結構實作：ArrayList 動態陣列，而 LinkedList 雙向鏈表
隨機訪問效率：ArrayList 更好
增加和洗掉效率：LinkedList 更好
記憶體空間占用：LinkedList 比 ArrayList 更占記憶體，因為 LinkedList 的節點除了存盤資料，還存盤了兩個參考
執行緒安全：都不保證執行緒安全；
綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和洗掉操作較多時，更推薦使用 LinkedList，

ArrayList 和 Vector 的區別是什么？

執行緒安全：Vector 使用了 Synchronized 來實作執行緒同步，是執行緒安全的，而 ArrayList 是非執行緒安全的，
性能：ArrayList 在性能方面要優于 Vector，
擴容：ArrayList 和 Vector 都會根據實際的需要動態的調整容量，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%，

插入資料時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存盤性能和特性？

ArrayList、Vector 底層陣列方式存盤資料，

LinkedList 雙向鏈表，LinkedList 插入速度較快，

多執行緒場景下如何使用 ArrayList？

ArrayList 不是執行緒安全的，如果遇到多執行緒場景，可以通過 Collections 的 synchronizedList 方法將其轉換成執行緒安全的容器后再使用

為什么 ArrayList 的 elementData 加上 transient 修飾？

每次序列化時，先呼叫 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍歷 elementData，只序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之后的檔案大小，

List 和 Set 的區別

list: 有序元素可重復多個null 有索引 for和iterator 檢索低效插入洗掉高效

set: 無序不可重復一個null iterator 查找高效插入洗掉低效

Set介面

說一下 HashSet 的實作原理？

HashSet: 底層HashMap hashmap的value統一為PRESENT 底層呼叫hashmap的方法 hashset不允許重復

HashSet如何檢查重復？HashSet是如何保證資料不可重復的？

檢查重復，不僅比較hash值，還要結合equals方法

值作為hashmap的key，所以不會重復

Queue

BlockingQueue是什么？

阻塞佇列在進行檢索或移除一個元素的時候，它會等待佇列變為非空；當在添加一個元素時，它會等待佇列中的可用空間

在 Queue 中 poll()和 remove()有什么區別？

相同點：回傳第一元素，并洗掉

不同點：沒有元素，poll回傳null remove拋出例外NoSuchElementException

Map介面

說一下 HashMap 的實作原理？

概述： HashMap是基于哈希表的Map介面的非同步實作

陣列和鏈表的結合體

1.用key的hashcode作hash計算下標

2.(1)key相同，覆寫原始值；(2)key不同（出現沖突），key-value放入鏈表

Jdk 1.8中對HashMap的實作做了優化，當鏈表中的節點資料超過八個之后，該鏈表會轉為紅黑樹來提高查詢效率，從原來的O(n)到O(logn)

HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實作

JDK1.8之前: 資料+鏈表；之后：鏈表長度大于閾值（默認為8），鏈表轉為紅黑樹

HashMap的put方法的具體流程？

①.判斷鍵值對陣列table是否為慷訓為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的陣列索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這里的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；

⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷程序中若發現key已經存在直接覆寫value即可；

⑥.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容，

HashMap的擴容操作是怎么實作的？

①.在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就呼叫resize方法進行擴容；

②.每次擴展的時候，都是擴展2倍；

③.擴展后Node物件的位置要么在原位置，要么移動到原偏移量兩倍的位置，

HashMap是怎么解決哈希沖突的？

什么是哈希：就是把任意長度的輸入通過散列演算法，變換成固定長度的輸出，該輸出就是散列值（哈希值）

基本特性：根據同一散列函式計算出的散列值如果不同，那么輸入值肯定也不同，但是，根據同一散列函式計算出的散列值如果相同，輸入值不一定相同

什么是哈希沖突：當兩個不同的輸入值，根據同一散列函式計算出相同的散列值的現象，我們就把它叫做碰撞（哈希碰撞）

HashMap的資料結構：陣列的特點是：尋址容易，插入和洗掉困難；鏈表的特點是：尋址困難，但插入和洗掉容易

hash()函式：與自己右移16位進行異或運算（高低位異或）

能否使用任何類作為 Map 的 key？

可以，考慮一下幾點：

1.重寫了 equals() 方法，也應該重寫 hashCode() 方法，

2.遵循與 equals() 和 hashCode() 相關的規則，

3.用戶自定義 Key 類最佳實踐是使之為不可變的

為什么HashMap中String、Integer這樣的包裝類適合作為Key？

1.都是final型別，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況

2.內部已重寫了equals()、hashCode()等方法，遵守了HashMap內部的規范

如果使用Object作為HashMap的Key，應該怎么辦呢？

重寫hashCode()和equals()方法

HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？

hashCode()方法回傳的是int整數型別，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間；哈希值可能不在陣列大小范圍內，進而無法匹配存盤位置

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

hash%length==hash&(length-1)的前提是 length 是2的 n 次方；

HashMap 與 HashTable 有什么區別？

1.執行緒安全 hashtable用synchronized修飾

2.效率 hashmap效率高

3.對null key的支持 hashmap可以 hashtable報錯

4.Hashtable 默認大小11，之后擴充，容量為原來2n+1，HashMap 默認大小16，擴充，原來的2倍

如何決定使用 HashMap 還是 TreeMap？

對于在Map中插入、洗掉和定位元素，HashMap最好，然而，對一個有序的key集合進行遍歷，TreeMap更好

HashMap 和 ConcurrentHashMap 的區別

1.JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實作,利用CAS演算法，

2.hashmap允許null

ConcurrentHashMap 和 Hashtable 的區別？

1.底層資料結構，ConcurrentHashMap：陣列+鏈表/紅黑二叉樹；Hashtable：陣列+鏈表

2.實作執行緒安全的方式（重要）：① 在JDK1.7的時候，ConcurrentHashMap（分段鎖）對整個桶陣列進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分資料，多執行緒訪問容器里不同資料段的資料，就不會存在鎖競爭，提高并發訪問率，（默認分配16個Segment，比Hashtable效率提高16倍，）到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 陣列+鏈表+紅黑樹的資料結構來實作，并發控制使用 synchronized 和 CAS 來操作，（JDK1.6以后對 synchronized鎖做了很多優化）整個看起來就像是優化過且執行緒安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的資料結構，但是已經簡化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證執行緒安全，效率非常低下，當一個執行緒訪問同步方法時，其他執行緒也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個執行緒不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低，

ConcurrentHashMap 底層具體實作知道嗎？實作原理是什么？

JDK1.7: ConcurrentHashMap采用Segment + HashEntry的方式進行實作

JDK1.8: synchronized只鎖定當前鏈表或紅黑二叉樹的首節點

Array 和 ArrayList 有何區別？

Array 存盤基本資料型別和物件，ArrayList 只能存盤物件，
Array 是指定固定大小的，而 ArrayList 大小是自動擴展的，
Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有，

如何實作 Array 和 List 之間的轉換？

Array 轉 List： Arrays. asList(array) ；
List 轉 Array：List 的 toArray() 方法，

comparable 和 comparator的區別？

comparable介面實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序
comparator介面實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序

Collection 和 Collections 有什么區別？

java.util.Collection 是一個集合介面（集合類的一個頂級介面），它提供了對集合物件進行基本操作的通用介面方法，Collection介面在Java 類別庫中有很多具體的實作，Collection介面的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承介面有List與Set，
Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及執行緒安全等各種操作，

TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？

TreeSet 要求存放的物件所屬的類必須實作 Comparable 介面，該介面提供了比較元素的 compareTo()方法，當插入元素時會回呼該方法比較元素的大小，TreeMap 要求存放的鍵值對映射的鍵必須實作 Comparable 介面從而根據鍵對元素進行排序，
Collections 工具類的 sort 方法有兩種多載的形式，

第一種要求傳入的待排序容器中存放的物件比較實作 Comparable 介面以實作元素的比較；

第二種不強制性的要求容器中的元素必須可比較，但是要求傳入第二個引數，引數是Comparator 介面的子型別（需要重寫 compare 方法實作元素的比較），相當于一個臨時定義的排序規則，其實就是通過介面注入比較元素大小的演算法，也是對回呼模式的應用（Java 中對函式式編程的支持），

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/160511.html

標籤：Java

上一篇：一文告訴你 Java RMI 和 RPC 的區別！

下一篇：Redis入門實戰(4)-Jedis操作redis