1. 首頁 > 生活 > >

java集合詳解和集合面試題目 java 集合面試總結

小知識



文章插圖
java集合詳解和集合面試題目 java 集合面試總結

文章插圖
本章節主要分享一些Java中的集合在面試中常問的高頻問題 ， 這里給出的是相對比較簡略的答案 ， 不過針對面試的回答 ， 這些就足夠了 ， 另外就是一定要加入自己的個人理解 ， 不要背書形式的回答 。
1.Java中的集合框架有哪些？
回答：Java 集合框架主要包括兩種類型的容器 ， 一種是集合（Collection） ， 存儲一個元素集合 ， 另一種是圖（Map） ， 存儲鍵/值對映射 。
Collection 接口又有 3 種子類型 ， List、Set 和 Queue ， 再下面是一些抽象類 ， 最后是具體實現類 ， 常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、TreeMap、LinkedHashMap 等等 。
2.ArrayList和LinkedList的底層實現和區別？
【java集合詳解和集合面試題目 java 集合面試總結】回答：ArrayList底層使用的是 Object數組；LinkedList底層使用的是 雙向鏈表 數據結構 。
ArrayList:增刪慢、查詢快 ， 線程不安全 ， 對元素必須連續存儲 。
LinkedList:增刪快 ， 查詢慢 ， 線程不安全 。
追問：說說ArrayList的擴容機制？
回答：通過閱讀ArrayList的源碼我們可以發現當以無參數構造方法創建 ArrayList 時 ， 實際上初始化賦值的是一個空數組 。當真正對數組進行添加元素操作時 ， 才真正分配容量 。即向數組中添加第一個元素時 ， 數組容量擴為 10 。當插入的元素個數大于當前容量時 ， 就需要進行擴容了 ，  ArrayList 每次擴容之后容量都會變為原來的 1.5 倍左右 。
3.HashMap的底層實現？擴容？是否線程安全？
回答：在jdk1.7之前HashMap是基于數組和鏈表實現的 ， 而且采用頭插法 。
而jdk1.8 之后在解決哈希沖突時有了較大的變化 ， 當鏈表長度大于閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷 ， 如果當前數組的長度小于 64 ， 那么會選擇先進行數組擴容 ， 而不是轉換為紅黑樹）時 ， 將鏈表轉化為紅黑樹 ， 以減少搜索時間 。采用尾插法 。
HashMap默認的初始化大小為 16 。當HashMap中的元素個數之和大于負載因子*當前容量的時候就要進行擴充 ， 容量變為原來的 2 倍 。（這里注意不是數組中的個數 ， 而且數組中和鏈/樹中的所有元素個數之和！）
注意：我們還可以在預知存儲數據量的情況下 ， 提前設置初始容量（初始容量 = 預知數據量 / 加載因子） 。這樣做的好處是可以減少 resize() 操作 ， 提高 HashMap 的效率
美團面試的時候問到這個問題 ， 還給出具體的值 ， 讓我算出初始值設置為多少合適？
HashMap是線程不安全的 ， 其主要體現：
1.在jdk1.7中 ， 在多線程環境下 ， 擴容時會造成環形鏈或數據丟失 。
2.在jdk1.8中 ， 在多線程環境下 ， 會發生數據覆蓋的情況 。
追問：HashMap擴容的時候為什么是2的n次冪？
回答：數組下標的計算方法是（n-1）& hash ， 取余(%)操作中如果除數是2的冪次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；） 。并且采用二進制位操作 & ， 相對于%能夠提高運算效率 ， 這就解釋了 HashMap 的長度為什么是2的冪次方 。
追問：HashMap的put方法說一下 。
回答：通過閱讀源碼 ， 可以從jdk1.7和1.8兩個方面來回答
1.根據key通過哈希算法與與運算得出數組下標
2.如果數組下標元素為空 ， 則將key和value封裝為Entry對象（JDK1.7是Entry對象 ， JDK1.8是Node對象）并放入該位置 。
3.如果數組下標位置元素不為空 ， 則要分情況
(i)如果是在JDK1.7 ， 則首先會判斷是否需要擴容 ， 如果要擴容就進行擴容 ， 如果不需要擴容就生成Entry對象 ， 并使用頭插法添加到當前鏈表中 。
(ii)如果是在JDK1.8中 ， 則會先判斷當前位置上的TreeNode類型 ， 看是紅黑樹還是鏈表Node
? (a)如果是紅黑樹TreeNode ， 則將key和value封裝為一個紅黑樹節點并添加到紅黑樹中去 ， 在這個過程中會判斷紅黑樹中是否存在當前key ， 如果存在則更新value 。
? (b)如果此位置上的Node對象是鏈表節點 ， 則將key和value封裝為一個Node并通過尾插法插入到鏈表的最后位置去 ， 因為是尾插法 ， 所以需要遍歷鏈表 ， 在遍歷過程中會判斷是否存在當前key ， 如果存在則更新其value ， 當遍歷完鏈表后 ， 將新的Node插入到鏈表中 ， 插入到鏈表后 ， 會看當前鏈表的節點個數 ， 如果大于8 ， 則會將鏈表轉為紅黑樹
? (c)將key和value封裝為Node插入到鏈表或紅黑樹后 ， 在判斷是否需要擴容 ， 如果需要擴容 ， 就結束put方法 。
追問：HashMap源碼中在計算hash值的時候為什么要右移16位？
回答：我的理解是讓元素在HashMap中更加均勻的分布 ， 具體的可以看下圖 ， 下圖是《阿里調優手冊》里說的 。
4.Java中線程安全的集合有哪些？
Vector：就比Arraylist多了個同步化機制（線程安全） 。
Hashtable：就比Hashmap多了個線程安全 。
ConcurrentHashMap:是一種高效但是線程安全的集合 。
Stack：棧 ， 也是線程安全的 ， 繼承于Vector 。
追問：說一下ConcurrentHashMap的底層實現 ， 它為什么是線程安全的？
回答：在jdk1.7是 分段的數組+鏈表  ， jdk1.8的時候跟HashMap1.8的時候一樣都是基于數組+鏈表/紅黑樹 。
ConcurrentHashMap是線程安全的
（1）在jdk1.7的時候是使用分段所segment ， 每一把鎖只鎖容器其中一部分數據 ， 多線程訪問容器里不同數據段的數據 ， 就不會存在鎖競爭 ， 提高并發訪問率 。
（2）在jdk1.8的時候摒棄了 Segment的概念 ， 而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現 ， 并發控制使用 synchronized 和 CAS 來操作 。synchronized只鎖定當前鏈表或紅黑二叉樹的首節點 。
5.HashMap和Hashtable的區別
回答：
（1）線程是否安全： HashMap 是非線程安全的 ， HashTable 是線程安全的,因為 HashTable 內部的方法基本都經過synchronized 修飾 。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?；
（2）對 Null key 和 Null value 的支持： HashMap 可以存儲 null 的 key 和 value ， 但 null 作為鍵只能有一個 ， null 作為值可以有多個；HashTable 不允許有 null 鍵和 null 值 ， 否則會拋出 NullPointerException 。
（3）初始容量大小和每次擴充容量大小的不同 ： ① 創建時如果不指定容量初始值 ， Hashtable 默認的初始大小為 11 ， 之后每次擴充 ， 容量變為原來的 2n+1 。HashMap 默認的初始化大小為 16 。之后每次擴充 ， 容量變為原來的 2 倍 。② 創建時如果給定了容量初始值 ， 那么 Hashtable 會直接使用你給定的大小 ， 而 HashMap 會將其擴充為 2 的冪次方大?。℉ashMap 中的tableSizeFor()方法保證 ， 下面給出了源代碼） 。也就是說 HashMap 總是使用 2 的冪作為哈希表的大小,后面會介紹到為什么是 2 的冪次方 。
（4）底層數據結構： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化 ， 當鏈表長度大于閾值（默認為 8）（將鏈表轉換成紅黑樹前會判斷 ， 如果當前數組的長度小于 64 ， 那么會選擇先進行數組擴容 ， 而不是轉換為紅黑樹）時 ， 將鏈表轉化為紅黑樹 ， 以減少搜索時間 。Hashtable 沒有這樣的機制 。
（5）效率： 因為線程安全的問題 ， HashMap 要比 HashTable 效率高一點 。另外 ， HashTable 基本被淘汰 ， 不要在代碼中使用它；
6.HashMap和TreeMap的區別？
回答：
1、HashMap是通過hash值進行快速查找的；HashMap中的元素是沒有順序的；TreeMap中所有的元素都是有某一固定順序的 ， 如果需要得到一個有序的結果 ， 就應該使用TreeMap；
2、HashMap和TreeMap都是線程不安全的；
3、HashMap繼承AbstractMap類；覆蓋了hashcode() 和equals() 方法 ， 以確保兩個相等的映射返回相同的哈希值；
TreeMap繼承SortedMap類；它保持鍵的有序順序；
4、HashMap：基于hash表實現的；使用HashMap要求添加的鍵類明確定義了hashcode() 和equals() （可以重寫該方法）；為了優化HashMap的空間使用 ， 可以調優初始容量和負載因子；
TreeMap：基于紅黑樹實現的；TreeMap就沒有調優選項 ， 因為紅黑樹總是處于平衡的狀態；
5、HashMap：適用于Map插入 ， 刪除 ， 定位元素；
TreeMap：適用于按自然順序或自定義順序遍歷鍵（key）