Adslv ·1. 前言
通過前面的學習，我們其實對 ArrayList 和 LinkedList 已經(jīng)很熟悉了，他們雖然都是繼承自 List，但是前者是基于數(shù)組實現(xiàn)的，后者是基于鏈表實現(xiàn)的，結合各自的特點我們會在前半節(jié)對比總結他們的特點和用法。
HashMap 和 HashSet 分別實現(xiàn)了 Map 接口和 Set 接口，HashSet 是一個值不重復的集合，HashMap 對鍵值對進行映射，是一個鍵不重復的集合。我們會在后半部分對比介紹各自的特點和用法。
2. Vector和ArrayList
結合 JAVA 源碼，我們可以看到 Vector 和 ArrayList 都是基于數(shù)組實現(xiàn)的，都繼承自 List 接口。因此他們隨機查詢的效率是非常高的，但是他們在數(shù)據(jù)插入或刪除，以及需要擴容的時候效率都比較低下，需要在原有數(shù)組之外進行復制、移動。還有一點細節(jié)的區(qū)別在于擴容的默認值，ArrayList 在內(nèi)存不足時默認擴容至 1.5 倍再加 1 個，Vector 默認擴容為原來的 2 倍。
他們最重要的區(qū)別在于 Vector 中大量使用了 synchronized 來修飾方法，所以它是線程安全的，相應的，效率也是比 ArrayList 更低的。所以我們生成今天的第一條結論：
- 需要線程安全的場景使用Vector。
3. ArrayList和LinkeList
經(jīng)過前面的學習我們已經(jīng)知道了 ArrayList 是基于數(shù)組的，查詢快插入慢，LinkedList 是基于鏈表的，插入快遍歷慢。我們來做個實驗看一下是不是真的如此：
Integer index = 10000000;
List<Integer> arrayList = new ArrayList<Integer>();
List<Integer> linkedList = new LinkedList<Integer>();
Long arrayStart = new Date().getTime();
for (int i = 0; i < index; i++){
arrayList.add(i);
}
Long arrayEnd = new Date().getTime();
Long linkedStart = new Date().getTime();
for (int j = 0; j < index; j++) {
linkedList.add(j);
}
Long linkedEnd = new Date().getTime();
System.out.println("插入"+index+"條記錄：");
System.out.println("ArrayList耗時:"+(arrayEnd-arrayStart)+"毫秒");
System.out.println("LinkedList耗時:"+(linkedEnd-linkedStart)+"毫秒");
結果：
插入 10000000 條記錄：
ArrayList 耗時：359 毫秒
LinkedList 耗時：2891 毫秒
我們會發(fā)現(xiàn)兩者相差并不大，而且當我們把數(shù)據(jù)量上升到 10000000 的時候還會發(fā)現(xiàn) ArrayList 的效率反而更快，這是什么原因呢。
原來我們使用的 add (E e) 方法有這樣的注釋：
Appends the specified element to the end of this list (optional operation).
所以當把元素追加在最后的時候，數(shù)組中的其他元素不需要移動，此時 ArrayList 的處理效率也很不錯。那么我們換個思路再試：
//元素個數(shù)減少到10萬即可看出效果
Integer index = 100000;
List<Integer> arrayList = new ArrayList<Integer>();
List<Integer> linkedList = new LinkedList<Integer>();
Long arrayStart = new Date().getTime();
for (int i = 0; i < index; i++){
//其他代碼不變，我們將每次遍歷時添加新元素的位置固定為第一個
arrayList.add(0,i);
}
Long arrayEnd = new Date().getTime();
Long linkedStart = new Date().getTime();
for (int j = 0; j < index; j++) {
//其他代碼不變，我們將每次遍歷時添加新元素的位置固定為第一個
linkedList.add(0,j);
}
Long linkedEnd = new Date().getTime();
System.out.println("插入"+index+"條記錄：");
System.out.println("ArrayList耗時:"+(arrayEnd-arrayStart)+"毫秒");
System.out.println("LinkedList耗時:"+(linkedEnd-linkedStart)+"毫秒");
結果：
插入 100000 條記錄
ArrayList 耗時：828 毫秒
LinkedList 耗時：16 毫秒
這個測試結果跟理論就匹配上了，ArrayList 把大量的時間都用在了移動元素上，而 LinkedList 不需要做這樣的操作，所以此時它的效率優(yōu)勢體現(xiàn)的非常明顯。所以我們在日常使用中一定要區(qū)分，在使用 add 方法的時候是否需要指定新添加元素的位置，另外，由于 ArrayList 是基于無序數(shù)組的，因此遍歷的時候可能輸出順序和插入順序是不一致的，而 LinkedList 由于有嚴格的指針相連，順序一定是固定的。
所以我們生成第二組結論：
- 需要頻繁在指定位置添加、刪除元素，而查詢指定位置數(shù)據(jù)較少的場景優(yōu)先使用 LinkedList；
- 隨機查詢較多、在指定位置添加、刪除元素較少，或者干脆不關心插入或刪除元素的位置及遍歷順序時，優(yōu)先使用 ArrayList；
- 需要元素按順序排列時，使用 LinkedList；
4. Map家族
java.util.Map 接口常用的實現(xiàn)類有 HashMap、HashTable、ConcurrentHashMap、LinkedHashMap 和 TreeMap。他們都是用來儲存 key-value 鍵值對的，可以通過鍵快速的讀取值，也因此，他們的鍵都是不可以重復的。那么他們各自又有什么特點，彼此又有什么區(qū)別呢？
4.1 HashMap
HashMap 是我們最常用的 Map 類，它的底層是由數(shù)組和鏈表來實現(xiàn)的，允許鍵或值為 null，并且順序是不固定的，默認容量是 16，當元素超過 Entry 數(shù)組的加載因子（默認值是 75%）時觸發(fā)擴容，擴容時原來數(shù)組中的元素要依次重新插入到新的數(shù)組中。它是非線程安全的。
4.2 HashTable
HashTable 初始容量為 11，并且鍵和值都不允許為 null，其他特性與 HashMap 沒有太大區(qū)別。雖然它是線程安全的，但是我個人更推薦大家使用 ConcurrentHashMap。
4.3 ConcurrentHashMap
我們可以在 java.util.concurrent.ConcurrentHashMap 下通過注釋了解到，這個類在 HashMap 和 HashTable 的基礎上做了優(yōu)化。它實現(xiàn)了線程安全，通過把 Map 分段成若干個段，在需要鎖定的時候只鎖定其中的一段，而在讀取的時候不做任何鎖定操作，另外用 volatile 修飾 HashEntry 的 value 來實現(xiàn)數(shù)據(jù)的實時更新，在 HashTable 的基礎上大大提升了效率。
4.4 LinkedHashMap
LinkedHashMap 記錄了元素保存的順序，因此在遍歷的時候可以按照當時的順序讀取，一般用于我們需要保留元素順序的場景。
Map<String, String> hashMap = new HashMap<String, String>();
hashMap.put("水果", "蘋果");
hashMap.put("蔬菜", "白菜");
hashMap.put("堅果", "核桃");
Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
對于無序的 HashMap，依次輸出
key: 蔬菜，value: 白菜
key: 水果，value: 蘋果
key: 堅果，value: 核桃
Map<String, String> linkedHashMap = new LinkedHashMap<String,String>();
linkedHashMap.put("水果", "蘋果");
linkedHashMap.put("蔬菜", "白菜");
linkedHashMap.put("堅果", "核桃");
Iterator<Map.Entry<String, String>> iterator = linkedHashMap.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
對于有序的 LinkedHashMap，依次輸出
key: 水果，value: 蘋果
key: 蔬菜，value: 白菜
key: 堅果，value: 核桃
4.5 TreeMap
TreeMap 的底層實現(xiàn)了紅黑樹的結構，是一個可以比較元素大小的 Map 集合，默認會根據(jù)元素的 key 值進行自然排序（前提是 key 值實現(xiàn)了 Comparable 接口），我們也可以自己定義比較器來進行排序。
總結一下：
- 日常使用 HashMap;
- 需要線程安全時用 ConcurrentHashMap;
- 需要記錄元素保存順序時使用 LinkedHashMap;
- 需要排序時使用 TreeMap。
5. 小結
本節(jié)我們學習了數(shù)據(jù)結構在 Java 中的應用，對于不同數(shù)據(jù)結構的封裝類的使用場景做了一些總結：List 接口下需要線程安全的場景使用 Vector，增、刪較多或需要元素有序時使用 LinkedList，查詢較多時使用 ArrayList；Map 接口下需要線程安全的場景使用 ConcurrentHashMap，需要記錄元素順序時使用 LinkedHashMap，需要排序時使用 TreeMap，日常使用 HashMap。
2025 imooc.com All Rights Reserved |