數(shù)據(jù)容器關(guān)系圖

導(dǎo)讀：Map竟然不屬于Java集合框架的子集？隊(duì)列也和List一樣屬于集合的三大子集之一？更有隊(duì)列的正確使用姿勢，一起來看吧！

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

本文的重點(diǎn)將會(huì)圍繞： 集合的使用、性能、線程安全、差異性、源碼解讀等幾個(gè)方面進(jìn)行介紹。

本文涉及的知識點(diǎn)，分為兩部分：

第一部分，Collection所有子集：

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

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

一、List

我們先來看List、Vector、ArrayList、LinkedList，它們之間的繼承關(guān)系圖，如下圖：

關(guān)系圖

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

來看它們的主要方法，如下圖：

List方法

常用方法：

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

1.1 Vector

Vector是Java早期提供的 線程安全的動(dòng)態(tài)數(shù)組， 如果不需要線程安全，并不建議選擇，畢竟同步是有額外開銷的。Vector 內(nèi)部是使用對象數(shù)組來保存數(shù)據(jù)，可以根據(jù)需要自動(dòng)的增加容量，當(dāng)數(shù)組已滿時(shí)，會(huì)創(chuàng)建新的數(shù)組，并拷貝原有數(shù)組數(shù)據(jù)。

看源代碼可以知道，我們Vector是通過 synchronized 實(shí)現(xiàn)線程安全的：

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

Vector動(dòng)態(tài)增加容量，源碼查看：

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動(dòng)態(tài)增加容量總結(jié)： 由上面的源碼可知，如果初始化Vector的時(shí)候指定了動(dòng)態(tài)容量擴(kuò)展大小，就增加指定的動(dòng)態(tài)大小，如果未指定，則擴(kuò)展一倍的容量。

1.2 ArrayList

ArrayList 是應(yīng)用更加廣泛的動(dòng)態(tài)數(shù)組，它本身不是線程安全的，所以性能要好很多。

ArrayList的使用與Vector類似，但有著不同的動(dòng)態(tài)擴(kuò)容機(jī)制，如下源碼：

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”是位運(yùn)算相當(dāng)于除2，所有ArrayList擴(kuò)容是動(dòng)態(tài)擴(kuò)展50%.

1.3 LinkedList

LinkedList 顧名思義是 Java 提供的雙向鏈表，所以它不需要像上面兩種那樣調(diào)整容量，它也不是線程安全的，它包含一個(gè)非常重要的內(nèi)部類：Entry。Entry是雙向鏈表節(jié)點(diǎn)所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)，它包括的屬性有：當(dāng)前節(jié)點(diǎn)所包含的值，上一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)。

1.4 Vector、ArrayList、LinkedList區(qū)別

Vector、ArrayList、LinkedList的區(qū)別，可以從以下幾個(gè)維度進(jìn)行對比：

1.4.1 底層實(shí)現(xiàn)的區(qū)別

Vector、ArrayList 內(nèi)部使用數(shù)組進(jìn)行實(shí)現(xiàn)，LinkedList 內(nèi)部使用雙向鏈表實(shí)現(xiàn)。

1.4.2 讀寫性能方面的區(qū)別

ArrayList 對元素 非末位 的增加和刪除都會(huì)引起內(nèi)存分配空間的動(dòng)態(tài)變化，因此非末位的操作速度較慢，但檢索速度很快。

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

1.4.3 線程安全方面的區(qū)別

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

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

二、Map

Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實(shí)現(xiàn)，是以鍵值對的形式存儲(chǔ)和操作數(shù)據(jù)的容器類型。

它們之間的關(guān)系，如下圖：

map

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

HashMap 的性能表現(xiàn)非常依賴于哈希碼的有效性，請務(wù)必掌握 hashCode 和 equals 的一些基本約定，比如：

equals 相等，hashCode 一定要相等；
重寫了 equals 也要重寫 hashCode；
hashCode 需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致；
equals 的對稱、反射、傳遞等特性；

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

三、Set

Set有兩個(gè)比較常用的子集：HashSet、TreeSet.

HashSet內(nèi)部使用的是HashMap實(shí)現(xiàn)的，看源代碼可知：

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

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

HashSet可以去除重復(fù)的值，如下代碼：

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);
}

編譯器不會(huì)報(bào)錯(cuò)，執(zhí)行的結(jié)果為：[orange, banana, apple, grape]，去掉了重復(fù)的“banana”選項(xiàng)。但排序是無序的，如果要實(shí)現(xiàn)有序的存儲(chǔ)就要使用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);
}

輸出的結(jié)果是：[apple, banana, grape, orange]

同樣，我們查看源碼發(fā)現(xiàn)，TreeSet的底層實(shí)現(xiàn)是TreeMap，源碼如下：

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

TreeSet也是非線程安全的。

四、Queue

Queue（隊(duì)列）與棧是相對的一種數(shù)據(jù)結(jié)構(gòu)。只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。棧的特點(diǎn)是后進(jìn)先出，而隊(duì)列的特點(diǎn)是先進(jìn)先出。隊(duì)列的用處很大，但大多都是在其他的數(shù)據(jù)結(jié)構(gòu)中，比如，樹的按層遍歷，圖的廣度優(yōu)先搜索等都需要使用隊(duì)列做為輔助數(shù)據(jù)結(jié)構(gòu)。

Queue的直接子集，如下圖：

queue

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

4.1 Queue方法

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

注意：

避免add()和remove()方法，而是要使用offer()和poll()添加和移除元素。后者操作失敗不會(huì)報(bào)錯(cuò)，前者會(huì)拋出異常；
element() / peek() 都為查詢第一個(gè)元素，不會(huì)刪除集合，但element()查詢失敗會(huì)拋出異常，peek()不會(huì)。

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 查詢失敗會(huì)拋出異常
System.out.println(queue);

4.3 其他隊(duì)列

ArrayBlockingQueue 底層是數(shù)組，有界隊(duì)列，如果我們要使用生產(chǎn)者-消費(fèi)者模式，這是非常好的選擇。

LinkedBlockingQueue 底層是鏈表，可以當(dāng)做無界和有界隊(duì)列來使用，所以大家不要以為它就是無界隊(duì)列。

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

PriorityBlockingQueue 是無界隊(duì)列，基于數(shù)組，數(shù)據(jù)結(jié)構(gòu)為二叉堆，數(shù)組第一個(gè)也是樹的根節(jié)點(diǎn)總是最小值。

ArrayBlockingQueue ：一個(gè)由數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列。

LinkedBlockingQueue ：一個(gè)由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列。

PriorityBlockingQueue ：一個(gè)支持優(yōu)先級排序的無界阻塞隊(duì)列。

DelayQueue：一個(gè)使用優(yōu)先級隊(duì)列實(shí)現(xiàn)的無界阻塞隊(duì)列。

SynchronousQueue：一個(gè)不存儲(chǔ)元素的阻塞隊(duì)列。

LinkedTransferQueue：一個(gè)由鏈表結(jié)構(gòu)組成的無界阻塞隊(duì)列。

LinkedBlockingDeque：一個(gè)由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列

五、擴(kuò)展：String的線程安全

關(guān)于String、StringBuffer、StringBuilder的線程安全

String是典型的Immutable（不可變）類，被聲明為final所有屬性也都是final，所有它是不可變的，所有拼加、截取等動(dòng)作等會(huì)產(chǎn)生新的String對象。

StringBuffer是為了解決上面的問題，而誕生的，提供了append方法實(shí)現(xiàn)了對字符串的拼加，append方法使用了synchronized實(shí)現(xiàn)了線程安全。

StringBuilder是JDK 1.5 新出的特性，作為StringBuffer的性能補(bǔ)充，StringBuffer的append方法使用了synchronized實(shí)現(xiàn)了線程的安全，但同時(shí)也帶來了性能開銷，在沒有線程安全的情況下可以優(yōu)先使用StringBuilder。

六、總結(jié)

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

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

Queue/Deque 則是 Java 提供的標(biāo)準(zhǔn)隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)，除了集合的基本功能，它還支持類似先入先出（FIFO， First-in-First-Out）或者后入先出（LIFO，Last-In-First-Out）等特定行為。這里不包括 BlockingQueue，因?yàn)橥ǔＪ遣l(fā)編程場合，所以被放置在并發(fā)包里。

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

七、參考資料

《碼出高效：Java開發(fā)手冊》

Java核心技術(shù)36講：http://t.cn/EwUJvWA

Oracle docs：https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Java核心（四）你不知道的數(shù)據(jù)集合

Java核心（四）你不知道的數(shù)據(jù)集合

一、List

1.1 Vector

1.2 ArrayList

1.3 LinkedList

1.4 Vector、ArrayList、LinkedList區(qū)別

1.4.1 底層實(shí)現(xiàn)的區(qū)別

1.4.2 讀寫性能方面的區(qū)別

1.4.3 線程安全方面的區(qū)別

二、Map

三、Set

四、Queue

4.1 Queue方法

4.2 Queue使用

4.3 其他隊(duì)列

五、擴(kuò)展：String的線程安全

六、總結(jié)

七、參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Java核心（四）你不知道的數(shù)據(jù)集合

一、List

1.1 Vector

1.2 ArrayList

1.3 LinkedList

1.4 Vector、ArrayList、LinkedList區(qū)別

1.4.1 底層實(shí)現(xiàn)的區(qū)別

1.4.2 讀寫性能方面的區(qū)別

1.4.3 線程安全方面的區(qū)別

二、Map

三、Set

四、Queue

4.1 Queue方法

4.2 Queue使用

4.3 其他隊(duì)列

五、擴(kuò)展：String的線程安全

六、總結(jié)

七、參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、List

1.4 Vector、ArrayList、LinkedList區(qū)別

三、Set

四、Queue