為了賬號安全,請及時綁定郵箱和手機立即綁定

Java核心(四)你不知道的數據集合

2018.11.28 09:47 2102瀏覽

數據容器關系圖

導讀:Map竟然不屬于Java集合框架的子集?隊列也和List一樣屬于集合的三大子集之一?更有隊列的正確使用姿勢,一起來看吧!

Java中的集合通常指的是Collection下的三個集合框架List、Set、Queue和Map集合,Map并不屬于Collection的子集,而是和它平行的頂級接口。Collection下的子集的關系如文章開頭圖片所示。

本文的重點將會圍繞: 集合的使用、性能、線程安全、差異性、源碼解讀等幾個方面進行介紹。

本文涉及的知識點,分為兩部分:

第一部分,Collection所有子集:

  • List => Vector、ArrayList、LinkedList
  • Set => HashSet、TreeSet
  • Queue

第二部分,Map => Hashtable、HashMap、TreeMap、ConcurrentHashMap。

一、List

我們先來看List、Vector、ArrayList、LinkedList,它們之間的繼承關系圖,如下圖:

關系圖

可以看出Vector、ArrayList、LinkedList,這三者都是實現集合框架中的List,也就是所謂的有序集合,因此具體功能也比較近似,比如都提供按照位置進行定位、添加或者刪除的操作,都提供迭代器以遍歷其內容等。但因為具體的設計區別,在行為、性能、線程安全等方面,表現又有很大不同。

來看它們的主要方法,如下圖:

List方法

常用方法:

  • size 集合個數
  • add()/add(int, E) 添加末尾/添加指定位置
  • get(int) 獲取
  • remove 刪除
  • clear 清空

1.1 Vector

Vector是Java早期提供的 線程安全的動態數組, 如果不需要線程安全,并不建議選擇,畢竟同步是有額外開銷的。Vector 內部是使用對象數組來保存數據,可以根據需要自動的增加容量,當數組已滿時,會創建新的數組,并拷貝原有數組數據。

看源代碼可以知道,我們Vector是通過 synchronized 實現線程安全的:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

Vector動態增加容量,源碼查看:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

capacityIncrement變量是what?答案如下:

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

Vector動態增加容量總結: 由上面的源碼可知,如果初始化Vector的時候指定了動態容量擴展大小,就增加指定的動態大小,如果未指定,則擴展一倍的容量。

1.2 ArrayList

ArrayList 是應用更加廣泛的動態數組,它本身不是線程安全的,所以性能要好很多。

ArrayList的使用與Vector類似,但有著不同的動態擴容機制,如下源碼:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

其中“>> 1”是位運算相當于除2,所有ArrayList擴容是動態擴展50%.

1.3 LinkedList

LinkedList 顧名思義是 Java 提供的雙向鏈表,所以它不需要像上面兩種那樣調整容量,它也不是線程安全的,它包含一個非常重要的內部類:Entry。Entry是雙向鏈表節點所對應的數據結構,它包括的屬性有:當前節點所包含的值,上一個節點,下一個節點。

1.4 Vector、ArrayList、LinkedList區別

Vector、ArrayList、LinkedList的區別,可以從以下幾個維度進行對比:

1.4.1 底層實現的區別

Vector、ArrayList 內部使用數組進行實現,LinkedList 內部使用雙向鏈表實現。

1.4.2 讀寫性能方面的區別

ArrayList 對元素 非末位 的增加和刪除都會引起內存分配空間的動態變化,因此非末位的操作速度較慢,但檢索速度很快。

LinkedList 基于鏈表方式存放數據,增加和刪除元素的速度較快,但是檢索速度較慢。

1.4.3 線程安全方面的區別

Vector 使用了synchronized 修飾了操作方法是線程安全的,而 ArrayList、LinkedList 是非線程安全的。

如果需要使用線程安全的List可以使用CopyOnWriteArrayList類。

二、Map

Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實現,是以鍵值對的形式存儲和操作數據的容器類型。

它們之間的關系,如下圖:

map

  • Hashtable 是早期 Java 類庫提供的一個哈希表實現,本身是同步的,不支持 null 鍵和值,由于同步導致的性能開銷,所以已經很少被推薦使用。
  • HashMap 是應用更加廣泛的哈希表實現,行為上大致上與 HashTable 一致,主要區別在于 HashMap 不是同步的,支持 null 鍵和值等。通常情況下,HashMap 進行 put 或者 get 操作,可以達到常數時間的性能,所以它是絕大部分利用鍵值對存取場景的首選,比如,實現一個用戶 ID 和用戶信息對應的運行時存儲結構。
  • TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map,和 HashMap 不同,它的 get、put、remove 之類操作都是 O(log(n))的時間復雜度,具體順序可以由指定的 Comparator 來決定,或者根據鍵的自然順序來判斷。

HashMap 的性能表現非常依賴于哈希碼的有效性,請務必掌握 hashCode 和 equals 的一些基本約定,比如:

  • equals 相等,hashCode 一定要相等;
  • 重寫了 equals 也要重寫 hashCode;
  • hashCode 需要保持一致性,狀態改變返回的哈希值仍然要一致;
  • equals 的對稱、反射、傳遞等特性;

線程安全: Hashtable是線程安全的,HashMap和TreeMap是非線程安全的。HashMap可以使用ConcurrentHashMap來保證線程安全。

三、Set

Set有兩個比較常用的子集:HashSet、TreeSet.

HashSet內部使用的是HashMap實現的,看源代碼可知:

public HashSet() {
    map = new HashMap<>();
}

HashSet也并不是線程安全的,HashSet用于存儲無序(存入和取出的順序不一定相同)元素,值也不能重復。

HashSet可以去除重復的值,如下代碼:

public static void main(String[] args) {
        Set set = new HashSet();
        set.add("orange");
        set.add("apple");
        set.add("banana");
        set.add("grape");
        set.add("banana");
        System.out.println(set);
}

編譯器不會報錯,執行的結果為:[orange, banana, apple, grape],去掉了重復的“banana”選項。但排序是無序的,如果要實現有序的存儲就要使用TreeSet了。

public static void main(String[] args) {
    Set set = new TreeSet();
    set.add("orange");
    set.add("apple");
    set.add("banana");
    set.add("grape");
    set.add("banana");
    System.out.println(set);
}

輸出的結果是:[apple, banana, grape, orange]

同樣,我們查看源碼發現,TreeSet的底層實現是TreeMap,源碼如下:

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet也是非線程安全的。

四、Queue

Queue(隊列)與棧是相對的一種數據結構。只允許在一端進行插入操作,而在另一端進行刪除操作的線性表。棧的特點是后進先出,而隊列的特點是先進先出。隊列的用處很大,但大多都是在其他的數據結構中,比如,樹的按層遍歷,圖的廣度優先搜索等都需要使用隊列做為輔助數據結構。

Queue的直接子集,如下圖:

queue

其中最常用的就是線程安全類:BlockingQueue.

4.1 Queue方法

  • 添加:add(e) / offer(e)
  • 移除:remove() / poll()
  • 查找:element() / peek()

注意:

  1. 避免add()和remove()方法,而是要使用offer()和poll()添加和移除元素。后者操作失敗不會報錯,前者會拋出異常;
  2. element() / peek() 都為查詢第一個元素,不會刪除集合,但element()查詢失敗會拋出異常,peek()不會。

4.2 Queue使用

Queue<String> queue =  new LinkedList<String>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
System.out.println(queue);
queue.poll();
System.out.println(queue);
queue.poll();
queue.poll();
queue.poll();
System.out.println(queue.peek());
// System.out.println(queue.element()); // element 查詢失敗會拋出異常
System.out.println(queue);

4.3 其他隊列

ArrayBlockingQueue 底層是數組,有界隊列,如果我們要使用生產者-消費者模式,這是非常好的選擇。

LinkedBlockingQueue 底層是鏈表,可以當做無界和有界隊列來使用,所以大家不要以為它就是無界隊列。

SynchronousQueue 本身不帶有空間來存儲任何元素,使用上可以選擇公平模式和非公平模式。

PriorityBlockingQueue 是無界隊列,基于數組,數據結構為二叉堆,數組第一個也是樹的根節點總是最小值。

ArrayBlockingQueue :一個由數組結構組成的有界阻塞隊列。

LinkedBlockingQueue :一個由鏈表結構組成的有界阻塞隊列。

PriorityBlockingQueue :一個支持優先級排序的無界阻塞隊列。

DelayQueue:一個使用優先級隊列實現的無界阻塞隊列。

SynchronousQueue:一個不存儲元素的阻塞隊列。

LinkedTransferQueue:一個由鏈表結構組成的無界阻塞隊列。

LinkedBlockingDeque:一個由鏈表結構組成的雙向阻塞隊列

五、擴展:String的線程安全

關于String、StringBuffer、StringBuilder的線程安全

String是典型的Immutable(不可變)類,被聲明為final所有屬性也都是final,所有它是不可變的,所有拼加、截取等動作等會產生新的String對象。

StringBuffer是為了解決上面的問題,而誕生的,提供了append方法實現了對字符串的拼加,append方法使用了synchronized實現了線程安全。

StringBuilder是JDK 1.5 新出的特性,作為StringBuffer的性能補充,StringBuffer的append方法使用了synchronized實現了線程的安全,但同時也帶來了性能開銷,在沒有線程安全的情況下可以優先使用StringBuilder。

六、總結

List 也就是我們前面介紹最多的有序集合,它提供了方便的訪問、插入、刪除等操作。

Set 是不允許重復元素的,這是和 List 最明顯的區別,也就是不存在兩個對象 equals 返回 true。我們在日常開發中有很多需要保證元素唯一性的場合。

Queue/Deque 則是 Java 提供的標準隊列結構的實現,除了集合的基本功能,它還支持類似先入先出(FIFO, First-in-First-Out)或者后入先出(LIFO,Last-In-First-Out)等特定行為。這里不包括 BlockingQueue,因為通常是并發編程場合,所以被放置在并發包里。

Map 是廣義 Java 集合框架中的另外一部分,Map 接口存儲一組鍵值對象,提供key(鍵)到value(值)的映射。

七、參考資料

《碼出高效:Java開發手冊》

Java核心技術36講:http://t.cn/EwUJvWA

點擊查看更多內容

本文原創發布于慕課網 ,轉載請注明出處,謝謝合作

4人點贊

若覺得本文不錯,就分享一下吧!

評論

相關文章推薦

正在加載中
意見反饋 幫助中心 APP下載
官方微信

舉報

0/150
提交
取消
开奖号码