Java容器總結
- 2019 年 10 月 16 日
- 筆記
容器總結
Java容器工具包框架圖
List,Set,Map三者的區別
- List(對付順序的好幫手)： List介面存儲一組不唯一（可以有多個元素引用相同的對象），有序的對象
- Set(注重獨一無二的性質): 不允許重複的集合。不會有多個元素引用相同的對象。
- Map(用Key來搜索的專家): 使用鍵值對存儲。Map會維護與Key有關聯的值。兩個Key可以引用相同的對象，但Key不能重複，典型的Key是String類型，但也可以是任何對象。
Arraylist 與 LinkedList 區別
- 是否保證執行緒安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證執行緒安全；
- 底層數據結構： Arraylist 底層使用的是 Object 數組；LinkedList 底層使用的是 雙向鏈表 數據結構（JDK1.6之前為循環鏈表，JDK1.7取消了循環。注意雙向鏈表和雙向循環鏈表的區別，下面有介紹到！）
- 插入和刪除是否受元素位置的影響： ① ArrayList 採用數組存儲，所以插入和刪除元素的時間複雜度受元素位置的影響。 比如：執行add(E e) 方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間複雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element) ）時間複雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之後的(n-i)個元素都要執行向後位/向前移一位的操作。 ② LinkedList 採用鏈表存儲，所以插入，刪除元素時間複雜度不受元素位置的影響，都是近似 O（1）而數組為近似 O（n）。
- 是否支援快速隨機訪問： LinkedList 不支援高效的隨機元素訪問，而 ArrayList 支援。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應於get(int index) 方法)。
- 記憶體空間佔用： ArrayList的空 間浪費主要體現在在list列表的結尾會預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接後繼和直接前驅以及數據）。
HashMap 和 Hashtable 的區別
- 執行緒是否安全： HashMap 是非執行緒安全的，HashTable 是執行緒安全的；HashTable 內部的方法基本都經過synchronized 修飾。（如果你要保證執行緒安全的話就使用 ConcurrentHashMap 吧！）；
- 效率： 因為執行緒安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在程式碼中使用它；
- 對Null key 和Null value的支援： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException。
- 初始容量大小和每次擴充容量大小的不同 ： ①創建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之後每次擴充，容量變為原來的2n+1。HashMap 默認的初始化大小為16。之後每次擴充，容量變為原來的2倍。②創建時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證，下面給出了源程式碼）。也就是說 HashMap 總是使用2的冪作為哈希表的大小,後面會介紹到為什麼是2的冪次方。
- 底層數據結構： JDK1.8 以後的 HashMap 在解決哈希衝突時有了較大的變化，當鏈表長度大於閾值（默認為8）時，將鏈錶轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。
