前言：Collection是最基本的集合接口，在JDK 1.2版本被引入到Java的世界中來。Collection的出現(xiàn)，使得Java擁有了前所未有的強大能力。本文就將介紹Collection體系下常用的類的實現(xiàn)以及它們背后的數(shù)據(jù)結(jié)構(gòu)。
Collection體系簡介
Java集合框架(Java collections framework)是一個包含一系列實作可重復使用集合的數(shù)據(jù)結(jié)構(gòu)的類別 "類別 (計算機科學)")和界面"界面 (程式設計)")集合。 雖然稱為“框架”，其使用方式卻像個函式庫。集合框架提供了定義各式各樣集合的界面和實作上述集合的類別。
我們可以在IDEA中搜到Collection.java，然后發(fā)現(xiàn)在注釋中介紹Collection的第一段話是這么說的：
The root interface in the collection hierarchy. A collection
represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces likeSetandList. This interface is typically used to pass collections around and manipulate them where maximum generality is desired.
翻譯過來是這樣的：
Collection是Java Collection繼承體系中的根接口。一個Collection代表一組對象，被稱為它的元素。有一些集合允許重復的元素（如List），而另一些則不允許重復（如Set）。一些是有序的（如ArrayList），而有些則是無序的（如HashSet）。 JDK不提供對Collection這個接口的任何直接實現(xiàn)：它提供了很多對它子接口（如Set和List）的實現(xiàn)。該接口通常用于在非常通用的地方把Collection當作參數(shù)傳來傳去，同時對它們進行操作。
與數(shù)組的不同處
集合和數(shù)組在可被視作為一個團體上有著功能上的相似處。集合和數(shù)組其中一點不同的是，集合在聲明時不需要指定固定的容量。集合可以在新增或移除內(nèi)容時自動地增加或縮減其容量。 另外，集合無法收納基本數(shù)據(jù)類型，像是整數(shù)（int)、長整數(shù)（long）或者雙精度浮點數(shù)（double）。取而代之的是，集合可以收納上述基本數(shù)據(jù)類型的封裝類型（Integer、Long、Double）
Collection體系下的三種結(jié)構(gòu)
（本節(jié)的引用摘自jdk官方注釋。）
List（有序列表）
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
有序集合（也稱為序列）。該界面的用戶可以精確控制列表中每個元素的插入位置。用戶可以通過其整數(shù)索引（列表中的位置）訪問元素，并在列表中搜索元素。
List接口是一個有序的 Collection，使用此接口能夠精確的控制每個元素插入的位置，能夠通過索引(元素在List中位置，類似于數(shù)組的下標)來訪問List中的元素，第一個元素的索引為 0，而且允許有相同的元素。List 接口存儲一組不唯一，有序（插入順序）的對象。
常用的List的實現(xiàn)類：ArrayList。
Set （集合）
A collection that contains no duplicate elements. More formally, sets contain no pair of elements
e1ande2such thate1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
一個不包含重復元素的集合。更正式地說，集合不包含元素對e1和e2，使得e1.equals(e2)最多包含一個空元素。顧名思義，此接口對數(shù)學集合抽象進行建模。
Set 具有與 Collection 完全一樣的接口，只是行為上不同，Set 不保存重復的元素。Set 接口存儲一組唯一，無序的對象。
常用的Set的實現(xiàn)類：HashSet
需要注意的是：Set判斷重復是通過equals方法，
Map（映射表）
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.
將鍵映射到值的對象。映射不能包含重復的鍵；每個鍵最多可以映射到一個值。該接口代替了Dictionary類，后者是一個完全抽象的類，而不是一個接口。
Map 接口存儲一組鍵值對象，提供key（鍵）到value（值）的映射。
常用的Map實現(xiàn)類：HashMap
Collection體系常用實現(xiàn)類詳解
List
ArrayList（線性結(jié)構(gòu)，基于動態(tài)數(shù)組）
- 本質(zhì)上，
ArrayList就是一個數(shù)組。 - 動態(tài)擴容的實現(xiàn)：
- 創(chuàng)建一個更大的空間。然后把原先的所有元素拷貝過去
線性結(jié)構(gòu)
簡單地說，線性結(jié)構(gòu)就是表中各個結(jié)點具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述，線性結(jié)構(gòu)應該包括如下幾點：
1、線性結(jié)構(gòu)是非空集。
2、線性結(jié)構(gòu)有且僅有一個開始結(jié)點和一個終端結(jié)點。
3、線性結(jié)構(gòu)所有結(jié)點都最多只有一個直接前趨結(jié)點和一個直接后繼結(jié)點。
線性表就是典型的線性結(jié)構(gòu)，還有棧、隊列和串等都屬于線性結(jié)構(gòu)。
LinkedList（鏈表）
鏈表
鏈表是一種數(shù)據(jù)元素按照鏈式存儲結(jié)構(gòu)進行存儲的數(shù)據(jù)結(jié)構(gòu)，這種存儲結(jié)構(gòu)具有在物理上存在非連續(xù)的特點。鏈表由一系列數(shù)據(jù)結(jié)點構(gòu)成，每個數(shù)據(jù)結(jié)點包括數(shù)據(jù)域和指針域兩部分。其中，指針域保存了數(shù)據(jù)結(jié)構(gòu)中下一個元素存放的地址。鏈表結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序來實現(xiàn)的。
ArrayList和LinkedList比較
由于二者是基于不同的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，基于鏈表和線性結(jié)構(gòu)的不同，二者主要的不同用法：
- ArrayList 對于【查】、【改】操作性能更高
- LinkedList 對與【增】、【刪】操作性能更高
Set
HashSet
最常用，最高效的Set實現(xiàn)
-
List可以使用Set來去重Set去重
注意：HashSet是無序的，如果需要有序的HashSet可以使用LinkedHashSet。
散列表（Hash）
散列表源自于散列函數(shù)(Hash function)，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄，那么必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進行比較操作而直接取得所查記錄。
TreeSet
TreeSet是有序的，因為Comparable的默認順序是從小到大，所以TreeSet的默認順序是從小到大，即自然順序。
因此：TreeSet最大的用途就是用來排序的。TreeSet內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是紅黑樹。
樹
樹是典型的非線性結(jié)構(gòu)，它是包括，2個結(jié)點的有窮集合K。在樹結(jié)構(gòu)中，有且僅有一個根結(jié)點，該結(jié)點沒有前驅(qū)結(jié)點。在樹結(jié)構(gòu)中的其他結(jié)點都有且僅有一個前驅(qū)結(jié)點，而且可以有兩個后繼結(jié)點，m≥0。
LinkedHashSet（有順序的HashSet）
保證內(nèi)部順序和插入的順序一樣。
Map
HashMap
HashMap的線程不安全性
注意：HashMap是線程不安全的，在jdk的官方注釋中也提到了【Note that this implementation is not synchronized.】。即：請注意，HashMap的實現(xiàn)沒有被同步。
在多線程中，HashMap的死循環(huán)問題：在多線程中，擴容的時候，即resize的時候，有可能變成一個死循環(huán)的鏈表。感興趣的可以移步：疫苗：JAVA HASHMAP的死循環(huán)。因此在多線程中，應該使用ConcurrentHashMap，即并發(fā)的HashMap。
HashMap在jdk1.7后的改變：同一個哈希桶中存儲的數(shù)據(jù)結(jié)構(gòu)由鏈表改為紅黑樹
如果恰好一個Map的所有的key的hashCode都是一樣的，那么他們就會放到同一個哈希桶中，那么這個HashMap就會變成一個效率極低的鏈表，導致程序運行變慢，喪失了使用Hash算法的好處。JDK7以后，發(fā)生哈希碰撞，存在同一個哈希桶中的數(shù)據(jù)不再是一個鏈表，而是變成了一個紅黑樹，從而提高了性能。
TreeMap
內(nèi)部數(shù)據(jù)結(jié)構(gòu)同TreeSet，此處不再贅述。
HashMap和HashSet本質(zhì)上是?種東?：
- HashMap的key的set就是一個HashSet
- HashSet的實現(xiàn)中就包含了一個HashMap
哈希算法簡介
Java世界里第二重要的約定（hashCode）
（第一重要的約定是equals約定）
- 同于一個對象必須始終返回相同的hashCode
- 兩個對象的equals返回true，則必須返回相同的hashCode
- 因此，當我們重寫equals方法時，必須重寫hashCode方法
- 兩個對象不等，也可能返回相同的hashCode
哈希就是一個單項的映射，舉例來說就像百家姓：先把所有人按照姓來分類，然后再查找：人名怎么取hashCode呢，通過取他的姓；那對象Object就會通過hashCode算法，映射成一個int。
在內(nèi)存中，上面百家姓的例子，姓就是內(nèi)存中的哈希桶，通過hashCode方法算出一個哈希值，然后放到哈希桶中。如果我們有10萬條數(shù)據(jù)，通過哈希算法分散到10萬個哈希桶中，那么我們查找某一條數(shù)據(jù)，只需要查找一次，因此通過哈希算法，查找的時間復雜度是呈指數(shù)下降的。
Collection的其他實現(xiàn)
Queue（隊列）
有優(yōu)先級的集合，LILO（Last In Last Out）
隊列
隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來說，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。
Deque（雙端隊列）
允許在兩端進行增刪元素。
Veetor
Vector是ArrayList的前身，已棄用
Stack（棧）
LIFO（Last In First Out），如果需要”棧“這種數(shù)據(jù)結(jié)構(gòu)，推薦使用Deque
棧
棧是一種特殊的線性表，它只能在一個表的一個固定端進行數(shù)據(jù)結(jié)點的插入和刪除操作。棧按照后進先出的原則來存儲數(shù)據(jù)，也就是說，先插入的數(shù)據(jù)將被壓入棧底，最后插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)時，從棧頂開始逐個讀出。棧在匯編語言程序中，經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場保護。棧中沒有數(shù)據(jù)時，稱為空棧。
ConcurrentHashMap
線程安全的HashMap
PriorityQueue（使用”堆“來實現(xiàn)的優(yōu)先級隊列）
堆
堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，一般討論的堆都是二叉堆。堆的特點是根結(jié)點的值是所有結(jié)點中最小的或者最大的，并且根結(jié)點的兩個子樹也是一個堆結(jié)構(gòu)
