介紹
JDK提供了一組主要的數據結構實現,如List、Map、Set等常用數據結構。這些數據都繼承自 java.util.Collection 接口,並位於 java.util 包內。
1、List接口
最重要的三種List接口實現:ArrayList、Vector、LinkedList。它們的類圖如下:
可以看到,3種List均來自 AbstratList 的實現。而 AbstratList 直接實現了List接口,並擴展自 AbstratCollection。
ArrayList 和 Vector 使用了數組實現,可以認為,ArrayList 封裝了對內部數組的操作。比如向數組中添加、刪除、插入新的元素或數組的擴展和重定義。對ArrayList或者Vector的操作,等價於對內部對象數組的操作。
ArrayList 和 Vector 幾乎使用了相同的算法,它們的唯一區別可以認為是對多線程的支持。ArrayList 沒有對一個方法做線程同步,因此不是線程安全的。Vector 中絕大多數方法都做了線程同步,是一種線程安全的實現。因此ArrayList 和 Vector 的性能特性相差無幾。
LinkedList 使用了循環雙向鏈表數據結構。LinkedList 由一系列表項連接而成。一個表項總是包含3個部分:元素內容、前驅表項和後驅表項。如圖所示:
LinkedList的表項源碼:
private static class Node{
E item;
Nodenext;
Nodeprev;
Node(Nodeprev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
無論LinkedList是否為空,鏈表都有一個header表項,它既是鏈表的開始,也表示鏈表的結尾。它的後驅表項便是鏈表的第一個元素,前驅表項便是鏈表的最後一個元素。如圖所示:
下面比較下ArrayList 和 LinkedList的不同。
1.增加元素到列表尾端
對於ArrayList來說,只要當前容量足夠大,add()操作的效率是非常高的。
只有當ArrayList對容量的需求超過當前數組的大小時,才需要進行擴容。擴容會進行大量的數組複製操作。而複製時最終調用的是System.arraycopy()方法,因此,add()效率還是相當高的。
LinkedList由於使用了鏈表的結構,因此不需要維護容量的大小。這點比ArrayList有優勢,不過,由於每次元素增加都需要新建Node對象,並進行更多的賦值操作。在頻繁的系統調用中,對性能會產生一定影響。
2.插入元素到列表任意位置
ArrayList是基於數組實現的,而數組是一塊連續的內存空間,每次插入操作,都會進行一次數組複製。大量的數組複製會導致系統性能低下。
LinkedList是基於鏈表實現的,在任意位置插入和在尾端增加是一樣的。所以,如果系統應用需要對List對象在任意位置進行頻繁的插入操作,可以考慮用LinkedList替代ArrayList。
3.刪除任意位置元素
對ArrayList來說,每次remove()移除元素都需要進行數組重組。並且元素位置越靠前開銷越大,要刪除的元素越靠後,開銷越小。
在LinkedList的實現中,首先需要通過循環找到要刪除的元素。如果要刪除的元素位置處於List的前半段,則從前往後找;若處於後半段,則從後往前找。如果要移除中間位置的元素,則需要遍歷完半個List,效率很低。
4.容量參數
容量參數是ArrayList 和 Vector等基於數組的List的特有性能參數,它表示初始數組的大小。
合理的設置容量參數,可以減少數組擴容,提升系統性能。
默認ArrayList的數組初始大小為10。
private static final int DEFAULT_CAPACITY = 10;
5.遍歷列表
常用的三種列表遍歷方式:ForEach操作、迭代器 和 for循環。
對於ForEach操作,反編譯可知實際上是將ForEach循環體作為迭代器處理。不過ForEach比自定義的迭代器多了一步賦值操作,性能不如直接使用迭代器的方式。
使用For循環通過隨機訪問遍歷列表,ArrayList表現很好,速度最快;但是LinkedList的表現非常差,應避免使用,這是因為對LinkedList的隨機訪問時,總會進行一次列表的遍歷操作。
2、Map接口
Map是一種非常常用的數據結構。圍繞著Map接口,最主要的實現類有Hashtable, HashMap, LinkedHashMap 和 TreeMap,在Hashtable中,還有Properties 類的實現。
Hashtable和hashMap的區別在於Hashtable的大部分方法都做了線程同步,而HashMap沒有,因此,Hashtable是線程安全的,HashMap不是。其次,Hashtable 不允許key 或 value使用null值,而HashMap可以。第三,它們在內部對key的hash算法和hash值到內存索引的映射算法不同。
由於HashMap使用廣泛,本文以HashMap為例,闡述它的實現原理。
1.HashMap的實現原理
簡單來說,HashMap就是將key做hash算法,然後將hash值映射到內存地址,直接取得key所對應的數據。在HashMap中,底層數據結構使用的是數組。所謂的內存地址,就是數組的下標索引。
用代碼簡單表示如下:
object[key_hash] = value;
2.Hash衝突
當需要存放的兩個元素1和2經hash計算後,發現對應在內存中的同一個地址。此時HashMap又會如何處理以保證數據的完整存放?
在HashMap的底層使用數組,但數組內的元素不是簡單的值,而是一個Entity類的對象。每一個Entity表項包括key,value,next,hash幾項。注意這裡的next部分,它指向另外一個Entity。當put()操作有衝突時,新的Entity會替換原有的值,為了保證舊值不丟失,會將next指向舊值。這便實現了在一個數組空間內存放多個值項。因此,HashMap實際上是一個鏈表的數組。而在進行get()操作時,如果定位到的數組元素不含鏈表(當前entry的next指向null),則直接返回;如果定位到的數組元素包含鏈表,則需要遍歷鏈表,通過key對象的equals方法逐一比對查找。
3.容量參數
和ArrayList一樣,基於數組的結構,不可避免的需要在數組空間不足時,進行擴展。而數組的重組比較耗時,因此對其做一定的優化很有必要了。
HashMap提供了兩個可以指定初始化大小的構造函數:
HashMap(int initialCapacity)
構造一個帶指定初始容量和默認負載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)
構造一個帶指定初始容量和負載因子的空 HashMap。
其中,HashMap會使用大於等於initialCapacity並且是2的指數次冪的最小的整數作為內置數組的大小。
負載因子又叫做填充比,它是介於0和1之間的浮點數。
負載因子 = 實際元素個數 / 內部數組總大小
負載因子的作用就是決定HashMap的閾值(threshold)。
閾值 = 數組總容量 × 負載因子
當HashMap的實際容量超過閾值便會進行擴容,每次擴容將新的數組大小設置為原大小的1.5倍。
默認情況下,HashMap的初始大小是16,負載因子為0.75。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
4.LinkedHashMap
LinkedHashMap繼承自HashMap,因此,它具備了HashMap的優良特性,並在此基礎上,LinkedHashMap又在內部增加了一個鏈表,用以存放元素的順序。因此,LinkedHashMap 可以簡單理解為一個維護了元素次序表的HashMap.
LinkedHashMap 提供兩種類型的順序:一是元素插入時的順序;二是最近訪問的順序。
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
構造一個帶指定初始容量、負載因子和排序模式的空 LinkedHashMap 實例
其中 accessOrder 為 true 時,按照元素最後訪問時間排序;當 accessOrder 為 false 時,按照插入順序排序。默認為 false 。
在內部實現中,LinkedHashMap 通過繼承 HashMap.Entity 類,實現 LinkedHashMap.Entity,為 HashMap.Entity 增加了 before 和 after屬性用以記錄某一表項的前驅和後繼,並構成循環鏈表。
5.TreeMap
TreeMap可以簡單理解為一種可以進行排序的Map實現。與 LinkedHashMap 不同,LinkedHashMap 是根據元素增加或者訪問的先後順序進行排序,而TreeMap則根據元素的Key進行排序。為了確定Key的排序算法,可以使用兩種方式指定:
(1)在TreeMap的構造函數中注入一個Comparator:
TreeMap(Comparator super K> comparator)
(2)使用一個實現了 Comparable 接口的 Key。
TreeMap的內部實現是基於紅黑樹的。紅黑樹是一種平衡查找樹,這裡不做過多介紹。
TreeMap 其它排序接口如下:
subMap(K fromKey, K toKey)
返回此映射的部分視圖,其鍵值的範圍從 fromKey(包括)到 toKey(不包括)。
tailMap(K fromKey)
返回此映射的部分視圖,其鍵大於等於 fromKey。
firstKey()
返回此映射中當前第一個(最低)鍵。
headMap(K toKey)
返回此映射的部分視圖,其鍵值嚴格小於 toKey。
一個簡單示例如下:
public class MyKey implements Comparable<mykey> {
private int id;
public MyKey(int id) {
this.id = id;
}
@Override
public int compareTo(MyKey o) {
if (o.id < this.id){
return 1;
}else if (o.id > this.id){
return -1;
}
return 0;
}
public static void main(String[] args) {
MyKey myKey1 = new MyKey(1);
MyKey myKey2 = new MyKey(2);
MyKey myKey3 = new MyKey(3);
Map<mykey> map = new TreeMap<>();
map.put(myKey1,"一號");
map.put(myKey3,"三號");
map.put(myKey2,"二號");
Iterator<mykey> iterator = map.keySet().iterator();
while (iterator.hasNext()){
System.out.println(map.get(iterator.next()));
}
}
}
/<mykey>/<mykey>/<mykey>
3、Set接口
Set並沒有在Collection接口之上增加額外的操作,Set集合中的元素是不能重複的。
其中最為重要的是HashSet、LinkedHashSet、TreeSet 的實現。這裡不再一一贅述,因為所有的這些Set實現都只是對應的Map的一種封裝而已。
4、優化集合訪問代碼
1.分離循環中被重複調用的代碼
舉個例子,當我們要使用for循環遍歷集合時
for (int i =0;i<collection.size> //.....
}
/<collection.size>
很明顯,每次循環都會調用size()方法,並且每次都會返回相同的數值。分離所有類似的代碼對提升循環性能有著積極地意義。因此,可以將上段代碼改造成
int size= collection.size();
for (int i =0;i<size> //.....
}
/<size>
當元素的數量越多時,這樣的處理就越有意義。
2.省略相同的操作
假設我們有一段類似的操作如下
int size= collection.size();
for (int i =0;i<size> if (list.get(i)==1||list.get(i)==2||list.get(i)==3){
//...
}
}
/<size>
雖然每次循環調用get(i)的返回值不同,但在同一次調用中,結果是相同的,因此可以提取這些相同的操作。
int size= collection.size();
int k=0;
for (int i =0;i<size> if ((k = list.get(i))==1||k==2||k==3){
//...
}
}
/<size>
3.減少方法調用
方法調用是需要消耗系統堆棧的,如果可以,則儘量訪問內部元素,而不要調用對應的接口,函數調用是需要消耗系統資源的,直接訪問元素會更高效。
假設上面的代碼是Vector.class的子類的部分代碼,那麼可以這麼改寫
int size = this.elementCount;
Object k=null;
for (int i =0;i<size> if ((k = elementData[i])=="1"||k=="2"||k=="3"){
//...
}
}
/<size>
可以看到,原本的 size() 和 get() 方法被直接替代為訪問原始變量,這對系統性能的提升是非常有用的。
5、RandomAccess接口
RandomAccess接口是一個標誌接口,本身並沒有提供任何方法,任何實現RandomAccess接口的對象都可以認為是支持快速隨機訪問的對象。此接口的主要目的是標識那些可以支持快速隨機訪問的List實現。
在JDK中,任何一個基於數組的List實現都實現了 RandomAccess接口,而基於鏈表的實現則沒有。這很好理解,只有數組能夠快速隨機訪問,(比如:通過 object[5],object[6]可以直接查找並返回對象),而對鏈表的隨機訪問需要進行鏈表的遍歷。
在實際操作中,可以根據list instanceof RandomAccess來判斷對象是否實現 RandomAccess 接口,從而選擇是使用隨機訪問還是iterator迭代器進行訪問。
在應用程序中,如果需要通過索引下標對 List 做隨機訪問,儘量不要使用 LinkedList,ArrayList和Vector都是不錯的選擇。
閱讀更多 Java識堂 的文章