java面試常問資料結構

本文主要總結面試中常問的java集合資料結構

java面試常問資料結構_OldWeiR的部落格-CSDN部落格

一、List

ArrayList

底層是

陣列佇列

，相當於動態陣列。與 Java 中的陣列相比，它的

容量能動態增長

。

資料結構-線性表的順序儲存，在指定位置插入/刪除元素的時間複雜度為O（n），求表長以及在陣列末尾增加元素，取第 i 元素的時間複雜度為O（1），因為陣列的記憶體是連續的，想要訪問那個元素，直接從陣列的首地址處向後偏移就可以訪問到了

ArrayList 繼承了AbstractList，實現了List。它是一個數組佇列，提供了相關的新增、刪除、修改、遍歷等功能。

ArrayList 實現了RandomAccess 介面， RandomAccess 是一個標誌介面，表明實現這個這個介面的 List 集合是支援快速隨機訪問的。在 ArrayList 中，我們即可以透過元素的序號快速獲取元素物件，這就是快速訪問-隨機存取。

ArrayList 實現了Cloneable 介面，即覆蓋了函式 clone（），能被克隆。

ArrayList 實現java。io。Serializable 介面，這意味著ArrayList支援序列化，能透過序列化去傳輸。

ArrayList 中的操作不是執行緒安全的！所以，建議在單執行緒中才使用 ArrayList，而在多執行緒中可以選擇 Vector 或者 CopyOnWriteArrayList。

LinkedList

LinkedList底層是

雙向連結串列

（JDK1。6之前為迴圈連結串列，JDK1。7取消了迴圈）

LinkedList是一個實現了List介面和Deque介面的雙端連結串列。

inkedList底層的連結串列結構使它支援高效的插入和刪除操作，另外它實現了Deque介面，使得LinkedList類也具有佇列的特性；

LinkedList不是執行緒安全的，如果想使LinkedList變成執行緒安全的，可以呼叫靜態類Collections類中的synchronizedList方法；

ArrayList和LinkedList的底層分別對應陣列和連結串列，這兩種結構在記憶體儲存上的表現不一樣，所以也有各自的特點

陣列

陣列的特點

- 在記憶體中，陣列是一塊連續的區域

- 陣列需要預留空間。在使用前需要提前申請所佔記憶體的大小，由於預先可能不知道需要多大的空間，若多申請了會浪費記憶體空間，空間利用率低；

- 在陣列起始位置處，插入資料和刪除資料效率低。插入資料時，待插入位置的的元素和它後面的所有元素都需要向後搬移；刪除資料時，待刪除位置後面的所有元素都需要向前搬移

- 隨機訪問效率很高，時間複雜度可以達到O（1）

- 陣列開闢的空間，在不夠使用的時候需要擴容，擴容的話，就會涉及到需要把舊陣列中的所有元素向新陣列中搬移

- 陣列的空間是從棧分配的

2。 陣列的優點

隨機訪問性強，查詢速度快，時間複雜度為O（1）

3。 陣列的缺點

- 頭插和頭刪的效率低，時間複雜度為O（N）

- 空間利用率不高

- 記憶體空間要求高，必須有足夠的連續的記憶體空間

- 陣列空間的大小固定，不能動態拓展

連結串列

連結串列的特點

- 在記憶體中，元素的空間可以在任意地方，空間是分散的，不需要連續

- 連結串列中的元素都會兩個屬性，一個是元素的值，另一個是指標，此指標標記了下一個元素的地址

- 查詢資料時效率低，時間複雜度為O（N）。由於連結串列的空間是分散的特點，不具有隨機訪問性，要訪問某個位置的資料，需要從第一個資料開始找起，利用next指標依次往後遍歷，直到找到待查詢的位置，時間複雜度達到O（N）

- 空間不需要提前指定大小，是動態申請的，根據需求動態的申請和刪除記憶體空間，擴充套件方便，故空間的利用率較高

- 任意位置插入元素和刪除元素效率較高，時間複雜度為O（1）

- 連結串列的空間是從堆中分配的

2。 連結串列的優點

- 任意位置插入元素和刪除元素的速度快，時間複雜度為O（1）

- 記憶體利用率高，不會浪費記憶體

- 連結串列的空間大小不固定，可以動態拓展

3。 連結串列的缺點

隨機訪問效率低，時間複雜度為0（N）

Vector

Vector 類實現了一個

動態陣列

。和 ArrayList 很相似，都是封裝了一個Object［］，但是兩者是不同的：

Vector 是同步訪問的。

Vector 包含了許多傳統的方法，這些方法不屬於集合框架。

Vector是執行緒安全的，ArrayList是非執行緒安全的，但效能上Vector比ArrayList低

Vector 主要用在事先不知道陣列的大小，或者只是需要一個可以改變大小的陣列的情況

二、Map

HashMap

JDK1。8 之前 HashMap 由

陣列+連結串列

組成的，陣列是 HashMap 的主體，連結串列則是主要為了解決雜湊衝突而存在的（“拉鍊法”解決衝突）。JDK1。8 以後在解決雜湊衝突時有了較大的變化，當連結串列長度大於閾值（預設為 8）時，將連結串列轉化為

紅黑樹

。

為什麼要這樣設計呢？

好處就是避免在最極端的情況下連結串列變得很長很長，在查詢的時候，效率會非常慢

紅黑樹查詢：其訪問效能近似於折半查詢，時間複雜度 O（logn）；

連結串列查詢：在極端情況下，需要遍歷全部元素才行，時間複雜度 O（n）；

HashMap中的put（）和get（）的實現原理：

map。put（k，v）實現原理

（1）首先將k，v封裝到Node物件當中（節點）。

（2）然後它的底層會呼叫K的hashCode（）方法得出hash值。

（3）透過雜湊表函式/雜湊演算法，將hash值轉換成陣列的下標，下標位置上如果沒有任何元素，就把Node新增到這個位置上。如果說下標對應的位置上有連結串列。此時，就會拿著k和連結串列上每個節點的k進行equal。如果所有的equals方法返回都是false，那麼這個新的節點將被新增到連結串列的末尾。如其中有一個equals返回了true，那麼這個節點的value將會被覆蓋。

map。get（k）實現原理

（1） 先呼叫k的hashCode（）方法得出雜湊值，並透過雜湊演算法轉換成陣列的下標。

（2） 透過上一步雜湊演算法轉換成陣列的下標之後，在透過陣列下標快速定位到某個位置上。如果這個位置上什麼都沒有，則返回null。如果這個位置上有單向連結串列，那麼它就會拿著K和單向連結串列上的每一個節點的K進行equals，如果所有equals方法都返回false，則get方法返回null。如果其中一個節點的K和引數K進行equals返回true，那麼此時該節點的value就是我們要找的value了，get方法最終返回這個要找的value。

HashMap在多執行緒下的執行緒不安全問題

HashMap在多執行緒情況下，在put的時候，插入的元素超過了容量（由負載因子決定）的範圍就會觸發擴容操作，就是rehash，這個會重新將原陣列的內容重新hash到新的擴容陣列中，在多執行緒的環境下，存在同時其他的元素也在進行put操作，如果hash值相同，可能出現同時在同一陣列下用連結串列表示，造成閉環，導致在get時會出現死迴圈，所以HashMap是執行緒不安全的。

另一個鍵值儲存集合**HashTable，它是執行緒安全的，它在所有涉及到多執行緒操作的都加上了synchronized**關鍵字來鎖住整個table，這就意味著所有的執行緒都在競爭一把鎖，在多執行緒的環境下，它是安全的，但是無疑是效率低下的。

其實HashTable有很多的最佳化空間，鎖住整個table這麼粗暴的方法可以變相的柔和點，比如在多執行緒的環境下，對不同的資料集進行操作時其實根本就不需要去競爭一個鎖，因為他們不同hash值，不會因為rehash造成執行緒不安全，所以互不影響，這就是鎖分離技術，將鎖的粒度降低，利用多個鎖來控制多個小的table，而這就**ConcurrentHashMap**，併發環境下推薦使用 ConcurrentHashMap 。

LinkedHashMap

LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基於拉鍊式雜湊結構即由

陣列+連結串列+紅黑樹

組成。

LinkedHashMap 在上面結構的基礎上，增加了一條雙向連結串列，使得上面的結構可以保持鍵值對的插入順序。同時透過對連結串列進行相應的操作，實現了訪問順序相關邏輯，解決了 HashMap 不能隨時保持遍歷順序和插入順序一致的問題。

- 連結串列的建立過程是在插入鍵值對節點時開始的，初始情況下，讓 LinkedHashMap 的 head 和 tail 引用同時指向新節點，連結串列就算建立起來了。隨後不斷有新節點插入，透過將新節點接在 tail 引用指向節點的後面，即可實現連結串列的更新

- 連結串列結點的刪除過程刪除的過程並不複雜，其實就做了三件事：

（1）根據 hash 定位到桶位置

（2）遍歷連結串列或呼叫紅黑樹相關的刪除方法

（3）從 LinkedHashMap 維護的雙鏈表中移除要刪除的節點

- LinkedHashMap 允許使用null值和null鍵， 執行緒是不安全的，雖然底層使用了雙線連結串列，但是增刪相快了。因為他底層的Entity 保留了hashMap node 的next 屬性。

HashTable

HashTable類中，儲存實際資料的，依然是Entry物件。其資料結構與HashMap是相同的。

HashTable類繼承自Dictionary類，實現了三個介面，分別是Map，Cloneable和java。io。Serializable

HashTable的主要方法的原始碼實現邏輯，與HashMap中非常相似，有一點重大區別就是所有的操作都是透過synchronized鎖保護的。只有獲得了對應的鎖，才能進行後續的讀寫等操作。

put方法

（1） 先獲取synchronized鎖

put方法不允許null值，如果發現是null，則直接丟擲異常。

（2） 計算key的雜湊值和index

（3） 更新value或新增節點

- 遍歷對應位置的連結串列，如果發現已經存在相同的hash和key，則更新value，並返回舊值。

- 如果不存在相同的key的Entry節點，則呼叫addEntry方法增加節點。

- addEntry方法中，如果需要則進行擴容，之後新增新節點到連結串列頭部。

get方法

（1） 先獲取synchronized鎖。

（2） 計算key的雜湊值和index。

（3） 返回值

- 在對應位置的連結串列中尋找具有相同hash和key的節點，返回節點的value。

- 如果遍歷結束都沒有找到節點，則返回null。

HashMap和HashTable的區別

- HashMap 不是執行緒安全的，HashTable 是執行緒安全 Collection。

- HashMap允許將 null 作為一個 entry 的 key 或者 value，而 Hashtable 不允許。

- HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。

- HashTable 繼承自 Dictionary 類，而 HashMap 是 Map介面的一個實現。

- HashTable 的方法是 Synchronize 的，而 HashMap 不是，也就是說在多個執行緒訪問中，不用專門的操作就安全地可以使用Hashtable 了；而對於HashMap，則需要額外的同步機制。

TreeMap

TreeMap實現了SotredMap介面，它是有序的集合。而且是一個紅黑樹結構，每個key-value都作為一個紅黑樹的節點。如果在呼叫TreeMap的建構函式時沒有指定比較器，則根據key執行自然排序，如果指定了比較器則按照比較器來進行排序。

在插入K，V時他會根據紅黑樹的特性，根據compare方法返回的值在left，right中遍歷找到對應的位置插入Entry或替換V。

TreeMap 底層結構為

紅黑樹

紅黑樹的Node排序是根據Key進行比較

每次新增刪除節點，都可能導致紅黑樹的重排

紅黑樹中不支援兩個or已上的Node節點對應紅黑值相等

三、Set

HashSet

HashSet內部

基於HashMap來實現的

，底層採用

HashMap來儲存元素

。Set集合無序並不可重複。HashSet中的元素都存放在HashMap的key上面，而value中的值都是統一的一個private static final Object PRESENT = new Object（）；。HashSet跟HashMap一樣，都是一個

存放連結串列的陣列

。

- 實現了 Serializable 介面，表明它支援序列化。

- 實現了 Cloneable 介面，表明它支援克隆，可以呼叫超類的 clone（）方法進行淺複製。

- 繼承了 AbstractSet 抽象類，和 ArrayList 和 LinkedList 一樣，在他們的抽象父類中，都提供了 equals（） 方 法和 hashCode（） 方法。它們自身並不實現這兩個方法

- 實現了 Set 介面，由雜湊表（實際上是一個 HashMap 例項）支援，不能保證元素的順序。

HashSet 特性

不能保證元素的順序，元素是無序的

HashSet 不是同步的，需要外部保持執行緒之間的同步問題

集合元素值允許為 null

時間複雜度

add（） 複雜度為 O（1）

remove（） 複雜度為 O（1）

contains（） 複雜度為 O（1）

LinkedHashSet

LinkedHashSet 繼承於 HashSet，底層是一個LinkedHashMap， 維護了一個

陣列 + 雙向連結串列

。 hashSet的存取是隨機的，但是LinkedHashSet的

存取是有序的

。在保證元素唯一性的情況下還可以保證

遍歷順序是插入順序

。

LinkedHashSet根據元素的hashCode值來決定元素的儲存位置，同時使用連結串列維護元素的次序，這使得元素看起來是以插入順序儲存的，同時LinkedHashSet不允許新增重複元素。

元素新增

1。 在LInkedHashSet中維護了一個hash表和雙向連結串列，LinkedHashSet中有head和tail，分別指向連結串列的頭和尾

2。 每一個節點有before和after屬性，這樣可以形成雙向連結串列

3。 在新增一個元素時，先求hash值，再求索引，確定該元素在table表中的位置，然後將新增的元素加入到雙向連結串列（如果該元素已經存在，則不新增）

tail。next

= newElement

newElement。pre = tail

4。 這樣在遍歷LinkedHashSet時也能確保插入順序和遍歷順序一致

TreeSet

TreeSet的底層是TreeMap，所以它的資料結構是紅黑樹新增的資料存入了map的key的位置，而value則固定是PRESENT。TreeSet中的元素是有序且不重複的，因為TreeMap中的key是有序且不重複的。

TreeSet有序、不可重複、非執行緒安全。

TreeMap底層使用紅黑樹的結構進行資料的增刪改查，紅黑樹是一種自平衡的二叉查詢樹，二叉查詢樹是一種有序樹，即進行中序遍歷可以得到一組有序序列，所以TreeMap也是有序的Map集合。

在紅黑樹的加持下，TreeMap的眾多方法，如：containsKey、get、put和reomve，都能保證log（n）的時間複雜度，這個效率可以說是相當高了。

有序性如何保證

TreeMap使用兩種方法來保證有序性：Comparator和Comparable。

1。 Comparator

你可以把它看做一個比較器，它的compare方法可以比較兩個傳入型別的物件，至於比較的規則是你實現這個介面後自己重寫。從上面的程式碼看到，TreeMap中有一個全域性comparator屬性，你可以在構造其中傳入自己的實現類。後面再put、get時就會呼叫

comparator的compare方法來比較你的key和已存在的key

，以此來決定存或取的位置。

public interface Comparator

{

int compare

（

T o1， T o2

）

；

……

}

2。 Comparable

TreeMap規定，

put、get和remove等方法傳入的引數key必須是實現了Comparable介面的

，否則在呼叫這些方法的時候會丟擲型別轉換的異常，因為要呼叫compareTo方法就必須把key強制轉換成Comparable型別，即：（Comparable<？ super K>）key。

所以這種比較方式就是：key1。compareTo（key2）。

public interface Comparable {

public int compareTo（T o）；

……

}

時間複雜度

List

ArrayList

get（） 直接讀取下標，複雜度 O（1）

add（E） 直接在隊尾新增，複雜度 O（1）

add（index， E） 在第n個元素後插入，n後面的元素需要向後移動，複雜度 O（n）

remove（） 刪除元素後面的元素需要逐個前移，複雜度 O（n）

LinkedList

addFirst（） 新增佇列頭部，複雜度 O（1）

removeFirst（） 刪除佇列頭部，複雜度 O（1）

addLast（） 新增佇列尾部，複雜度 O（1）

removeLast（） 刪除佇列尾部，複雜度 O（1）

getFirst（） 獲取佇列頭部，複雜度 O（1）

getLast（） 獲取佇列尾部，複雜度 O（1）

get（） 獲取第n個元素，依次遍歷，複雜度O（n）

add（E） 新增到佇列尾部，複雜度O（1）

add（index， E） 新增到第n個元素後，需要先查詢到第n個元素，複雜度O（n）

remove（） 刪除元素，修改前後元素節點指標，複雜度O（1）

Set

HashSet

add（） 複雜度為 O（1）

remove（） 複雜度為 O（1）

contains（） 複雜度為 O（1）

TreeSet(基於紅黑樹)

add（） 複雜度為 O（log （n））

remove（） 複雜度為 O（log （n））

contains（） 複雜度為 O（log （n））

Map

TreeMap(基於紅黑樹)

平均時間複雜度 O（log n）

HashMap

正常時間複雜度 O（1）~O（n）

紅黑樹後 O（log n）

LinkedHashMap

能以時間複雜度 O（1） 查詢元素，又能夠保證key的有序性