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