首先要說一下,本文對這些Java集合框架的面試題只做了一個總結式的回答,對每一道題目,都值得深入去了解一下(什麼是紮實基本功,這些就是基本功~~),後續可能對每一道題目拆開獨立篇章來深入講解一下。
大家看到這些總結,有疑惑的,就趕緊去查一查深入瞭解一下,當然也歡迎指出文中錯誤之處。
以下是大綱:
HashMap和HashTable的區別?
說一下 HashMap 的底層結構?
為什麼HashMap是線程不安全的
ArrayList 和 LinkedList 的區別是什麼?
ArrayList 和 Vector 的區別是什麼?
Array 和 ArrayList 有何區別?
說一下 HashSet 的實現原理?
如何決定使用 HashMap 還是 TreeMap?
List、Set、Map 之間的區別是什麼?
HashMap怎樣解決hash衝突
1.HashMap和HashTable的區別?
HashMap 不是線程安全的
HashMap 是 map 接口的實現類,是將鍵映射到值的對象,其中鍵和值都是對象,並且不能包含重複鍵,但可以包含重複值。HashMap 允許 null key 和 null value,而 HashTable 不允許。
HashTable 是線程安全 Collection。
HashMap 是 HashTable 的輕量級實現,他們都完成了Map 接口,主要區別在於 HashMap 允許 null key 和 null value,由於非線程安全,效率上可能高於 Hashtable。
區別:
- HashMap允許將 null 作為一個 entry 的 key 或者 value,而 Hashtable 不允許。
- HashMap 把 Hashtable 的 contains 方法去掉了,改成 containsValue 和 containsKey。因為 contains 方法容易讓人引起誤解。
- HashTable 繼承自 Dictionary 類,而 HashMap 是 Java1.2 引進的 Map interface 的一個實現。
- HashTable 的方法是 Synchronize 的,而 HashMap 不是,在多個線程訪問 Hashtable 時,不需要自己為它的方法實現同步,而 HashMap 就必須為之提供外同步。
2.說一下 HashMap 的底層結構?
HashMap的主幹是一個Entry數組。Entry是HashMap的基本組成單元,每一個Entry包含一個key-value鍵值對。整體結構圖:
HashMap由數組+鏈表組成的。
數組是HashMap的主體,鏈表則是主要為了解決哈希衝突而存在的,如果定位到的數組位置不含鏈表(當前entry的next指向null),那麼對於查找,添加等操作很快,僅需一次尋址即可;如果定位到的數組包含鏈表,對於添加操作,其時間複雜度為O(n),首先遍歷鏈表,存在即覆蓋,否則新增;對於查找操作來講,仍需遍歷鏈表,然後通過key對象的equals方法逐一比對查找。所以,性能考慮,HashMap中的鏈表出現越少,性能才會越好。
3.為什麼HashMap是線程不安全的
見20期:【20期】你知道為什麼HashMap是線程不安全的嗎?
4.ArrayList 和 LinkedList 的區別是什麼?
- ArrayList是實現了基於動態數組的數據結構,LinkedList基於鏈表的數據結構。
- 對於隨機訪問get和set,ArrayList覺得優於LinkedList,因為LinkedList要移動指針。
- 對於新增和刪除操作add和remove,LinedList比較佔優勢,因為ArrayList要移動數據。
5.ArrayList 和 Vector 的區別是什麼?
1.同步性:
Vector是線程安全的,也就是說是它的方法之間是線程同步的,而ArrayList是線程序不安全的,它的方法之間是線程不同步的。如果只有一個線程會訪問到集合,那最好是使用ArrayList,因為它不考慮線程安全,效率會高些;如果有多個線程會訪問到集合,那最好是使用Vector,因為不需要我們自己再去考慮和編寫線程安全的代碼。
PS:對於Vector&ArrayList、Hashtable&HashMap,要記住線程安全的問題,記住Vector與Hashtable是舊的,是java一誕生就提供了的,它們是線程安全的,ArrayList與HashMap是java2時才提供的,它們是線程不安全的。所以,我們講課時先講老的。
2.數據增長:
ArrayList與Vector都有一個初始的容量大小,當存儲進它們裡面的元素的個數超過了容量時,就需要增加ArrayList與Vector的存儲空間,每次要增加存儲空間時,不是隻增加一個存儲單元,而是增加多個存儲單元,每次增加的存儲單元的個數在內存空間利用與程序效率之間要取得一定的平衡。
Vector默認增長為原來兩倍,而ArrayList的增長策略在文檔中沒有明確規定(從源代碼看到的是增長為原來的1.5倍)。ArrayList與Vector都可以設置初始的空間大小,Vector還可以設置增長的空間大小,而ArrayList沒有提供設置增長空間的方法。
即Vector增長原來的一倍,ArrayList增加原來的0.5倍。
6.Array 和 ArrayList 有何區別?
- Array 可以包含基本數據類型和引用類型,ArrayList只能包含引用類型。
- ArrayList是基於數組實現的,Array大小不可以調整大小,但ArrayList可以通過內部方法自動調整容量。
- ArrayList是List接口的實現類,相比Array支持更多的方法和特性。
7.說一下 HashSet 的實現原理?
1.HashSet是基於HashMap實現的,默認構造函數是構建一個初始容量為16,負載因子為0.75 的HashMap。封裝了一個 HashMap 對象來存儲所有的集合元素,所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存,而 HashMap 的 value 則存儲了一個 PRESENT,它是一個靜態的 Object 對象。
2.當我們試圖把某個類的對象當成 HashMap的 key,或試圖將這個類的對象放入 HashSet 中保存時,重寫該類的equals(Object obj)方法和 hashCode() 方法很重要,而且這兩個方法的返回值必須保持一致:當該類的兩個的 hashCode() 返回值相同時,它們通過 equals() 方法比較也應該返回 true。通常來說,所有參與計算 hashCode() 返回值的關鍵屬性,都應該用於作為 equals() 比較的標準。
3.HashSet的其他操作都是基於HashMap的。
8.如何決定使用 HashMap 還是 TreeMap?
見03期:【03期】如何決定使用 HashMap 還是 TreeMap?
9.List、Set、Map 之間的區別是什麼?
List(列表)
List的元素以線性方式存儲,可以存放重複對象,List主要有以下兩個實現類:
1.ArrayList: 長度可變的數組,可以對元素進行隨機的訪問,向ArrayList中插入與刪除元素的速度慢。JDK8中ArrayList擴容的實現是通過grow()方法裡使用語句newCapacity = oldCapacity + (oldCapacity >> 1)(即1.5倍擴容)計算容量,然後調用Arrays.copyof()方法進行對原數組進行復制。
LinkedList: 採用鏈表數據結構,插入和刪除速度快,但訪問速度慢。
Set(集合)
Set中的對象不按特定(HashCode)的方式排序,並且沒有重複對象,Set主要有以下兩個實現類:
1.HashSet:HashSet按照哈希算法來存取集合中的對象,存取速度比較快。當HashSet中的元素個數超過數組大小*loadFactor(默認值為0.75)時,就會進行近似兩倍擴容(newCapacity = (oldCapacity << 1) + 1)。
2.TreeSet:TreeSet實現了SortedSet接口,能夠對集合中的對象進行排序。
Map(映射)
Map是一種把鍵對象和值對象映射的集合,它的每一個元素都包含一個鍵對象和值對象。Map主要有以下實現類:
HashMap:HashMap基於散列表實現,其插入和查詢的開銷是固定的,可以通過構造器設置容量和負載因子來調整容器的性能。
LinkedHashMap:類似於HashMap,但是迭代遍歷它時,取得的順序是其插入次序,或者是最近最少使用(LRU)的次序。
TreeMap:TreeMap基於紅黑樹實現。查看時,它們會被排序。TreeMap是唯一的帶有subMap()方法的Map,subMap()可以返回一個子樹。
10.HashMap怎樣解決hash衝突
見16期:【16期】你能談談HashMap怎樣解決hash衝突嗎