數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。

JDK中常使用的數(shù)據(jù)結(jié)構(gòu)如下：

List

ArrayList：基于數(shù)組實(shí)現(xiàn)，非線程安全，訪問(wèn)速度快，插入和移除性能較差，可以放null元素；

LinkedList：基于鏈表實(shí)現(xiàn)，非線程安全，插入和刪除操作更加高效，訪問(wèn)速度較ArrayList慢。

CopyOnWriteArrayList：基于數(shù)組實(shí)現(xiàn)，每次對(duì)該對(duì)象操作時(shí)，都會(huì)復(fù)制之前數(shù)組創(chuàng)建一個(gè)新的數(shù)組，性能開(kāi)銷較大。適合使用在讀操作遠(yuǎn)遠(yuǎn)大于寫(xiě)操作的場(chǎng)景里，比如緩存。

Vector：Vector與ArrayList基本是一致的，不同的是Vector是線程安全的，會(huì)在可能出現(xiàn)線程安全的方法前面加上synchronized關(guān)鍵字。隨機(jī)訪問(wèn)速度快，插入和移除性能較差。該類可以使用Collections.synchronizedList替換掉。

Stack：繼承Vector，后進(jìn)先出，實(shí)現(xiàn)了一些棧基本操作的方法，線程安全。

Map

HashMap：非線程安全，讀寫(xiě)效率較高?；跀?shù)組、鏈表、紅黑樹(shù)實(shí)現(xiàn)，內(nèi)部維護(hù)著一個(gè)數(shù)組table，該數(shù)組保存著每個(gè)頭結(jié)點(diǎn)； 在鏈表長(zhǎng)度大于8的時(shí)候，將后面的數(shù)據(jù)存在紅黑樹(shù)中，以加快檢索速度。

Hashtable：線程安全類，基于數(shù)組和鏈表實(shí)現(xiàn)，內(nèi)部維護(hù)著一個(gè)數(shù)組table，該數(shù)組保存著每個(gè)鏈表的頭結(jié)點(diǎn)。對(duì)hashtable操作是用synchronized保障線程安全。

TreeMap：非線程安全，是一個(gè)有序Map，會(huì)將Key按照自然順序進(jìn)行排序或者根據(jù)創(chuàng)建映射時(shí)提供的Comparator接口進(jìn)行排序?；诩t黑樹(shù)實(shí)現(xiàn)。

LinkedHashMap：非線程安全，繼承HashMap，維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問(wèn)順序。

ConcurrentHashMap：線程安全，基于數(shù)組、鏈表、紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用Synchronized和CAS，每次操作只鎖首節(jié)點(diǎn)。

ConcurrentSkipListMap：線程安全, 是一個(gè)有序Map,是基于跳表實(shí)現(xiàn)的，原理是先大步查找確定范圍，再逐漸縮小。并發(fā)控制使用CAS

跳躍表具有以下幾個(gè)特點(diǎn)：

最底層包含所有節(jié)點(diǎn)的一個(gè)有序的鏈表

每一層都是一個(gè)有序的鏈表

每個(gè)節(jié)點(diǎn)都有兩個(gè)指針，一個(gè)指向右側(cè)節(jié)點(diǎn)（沒(méi)有則為空），一個(gè)指向下層節(jié)點(diǎn)（沒(méi)有則為空）

一個(gè)頭節(jié)點(diǎn)指向最高層的第一個(gè)節(jié)點(diǎn)，通過(guò)它可以遍歷整張表

WeakHashMap：非線程安全, 基于Entry數(shù)組和鏈表實(shí)現(xiàn)，內(nèi)部是通過(guò)弱引用來(lái)管理entry的，可以被GC自動(dòng)回收，適用于緩存的場(chǎng)景。當(dāng)使用 WeakHashMap 時(shí)，即使沒(méi)有顯示的添加或刪除任何元素，也可能發(fā)生如下情況：

?????? (1)調(diào)用兩次size()方法返回不同的值；

?????? (2)兩次調(diào)用isEmpty()方法，第一次返回false，第二次返回true；

?????? (3)兩次調(diào)用containsKey()方法，第一次返回true，第二次返回false，盡管兩次使用的是同一個(gè)key；

?????? (4)兩次調(diào)用get()方法，第一次返回一個(gè)value，第二次返回null，盡管兩次使用的是同一個(gè)對(duì)象。

IdentityHashMap：非線程安全, 基于數(shù)組實(shí)現(xiàn)，在判斷Map中的兩個(gè)key是否相等時(shí)，只通過(guò)==來(lái)判斷，而不通過(guò)equals，也就是說(shuō)，如果兩個(gè)key相同，那么這兩個(gè)key必須是同一個(gè)對(duì)象。key和value的值實(shí)際上都是存儲(chǔ)在數(shù)組中的，而且val是挨著key存儲(chǔ)的。

Set

HashSet：基于HashMap實(shí)現(xiàn)，值不能重復(fù)，無(wú)序集合，性能較好，非線程安全；

TreeSet：基于TreeMap實(shí)現(xiàn)，值不能重復(fù)，按照compareTo方法對(duì)對(duì)象排序，有序集合，非線程安全；

LinkedHashSet：繼承HashSet，基于LinkedHashMap實(shí)現(xiàn)，是一個(gè)保存了插入順序的Set，非線程安全；

Queue

ArrayBlockingQueue：線程安全，由數(shù)組構(gòu)成的一個(gè)有界隊(duì)列，按照FIFO（先進(jìn)先出）原則，不支持?jǐn)U容，一旦創(chuàng)建，就不能在增加其容量；

LinkedBlockingQueue：線程安全，基于鏈表實(shí)現(xiàn)，如果不指定容量，默認(rèn)為Integer.MAX_VALUE，也就是無(wú)界隊(duì)列，如果指定容量是個(gè)有界隊(duì)列。按照FIFO（先進(jìn)先出）原則

PriorityBlockingQueue：線程安全，一個(gè)支持線程優(yōu)先級(jí)排序的無(wú)界隊(duì)列，默認(rèn)自然序進(jìn)行排序，也可以自定義實(shí)現(xiàn)compareTo()方法來(lái)指定元素排序規(guī)則，不能保證同優(yōu)先級(jí)元素的順序。。

SynchronousQueue：線程安全，此隊(duì)列設(shè)計(jì)的理念類似于"單工模式",對(duì)于每個(gè)put/offer操作,必須等待一個(gè)take/poll操作。

DelayQueue：線程安全，一個(gè)實(shí)現(xiàn)PriorityBlockingQueue實(shí)現(xiàn)延遲獲取的無(wú)界隊(duì)列，在創(chuàng)建元素時(shí)，可以指定多久才能從隊(duì)列中獲取當(dāng)前元素。只有延時(shí)期滿后才能從隊(duì)列中獲取元素。可適用于緩存系統(tǒng)、定時(shí)任務(wù)調(diào)度等

LinkedTransferQueue：線程安全，采用一種預(yù)占模式。意思就是消費(fèi)者線程取元素時(shí)，如果隊(duì)列為空，那就生成一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)元素為null）入隊(duì)，然后消費(fèi)者線程被等待在這個(gè)節(jié)點(diǎn)上，后面生產(chǎn)者線程入隊(duì)時(shí)發(fā)現(xiàn)有一個(gè)元素為null的節(jié)點(diǎn)，生產(chǎn)者線程就不入隊(duì)了，直接就將元素填充到該節(jié)點(diǎn)，并喚醒該節(jié)點(diǎn)等待的線程，被喚醒的消費(fèi)者線程取走元素，從調(diào)用的方法返回。我們稱這種節(jié)點(diǎn)操作為“匹配”方式。