前言：Collection是最基本的集合接口弧呐，在JDK 1.2版本被引入到Java的世界中來赚爵。Collection的出現(xiàn)瓢湃，使得Java擁有了前所未有的強(qiáng)大能力矢炼。本文就將介紹Collection體系下常用的類的實(shí)現(xiàn)以及它們背后的數(shù)據(jù)結(jié)構(gòu)。
Collection體系簡(jiǎn)介
Java集合框架(Java collections framework)是一個(gè)包含一系列實(shí)作可重復(fù)使用集合的數(shù)據(jù)結(jié)構(gòu)的類別 "類別 (計(jì)算機(jī)科學(xué))")和界面"界面 (程式設(shè)計(jì))")集合慷垮。 雖然稱為“框架”揖闸，其使用方式卻像個(gè)函式庫(kù)。集合框架提供了定義各式各樣集合的界面和實(shí)作上述集合的類別料身。
我們可以在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繼承體系中的根接口。一個(gè)Collection代表一組對(duì)象芹血，被稱為它的元素贮泞。有一些集合允許重復(fù)的元素（如List），而另一些則不允許重復(fù)（如Set）祟牲。一些是有序的（如ArrayList），而有些則是無序的（如HashSet）抖部。 JDK不提供對(duì)Collection這個(gè)接口的任何直接實(shí)現(xiàn)：它提供了很多對(duì)它子接口（如Set和List）的實(shí)現(xiàn)说贝。該接口通常用于在非常通用的地方把Collection當(dāng)作參數(shù)傳來傳去，同時(shí)對(duì)它們進(jìn)行操作慎颗。
與數(shù)組的不同處
集合和數(shù)組在可被視作為一個(gè)團(tuán)體上有著功能上的相似處乡恕。集合和數(shù)組其中一點(diǎn)不同的是，集合在聲明時(shí)不需要指定固定的容量俯萎。集合可以在新增或移除內(nèi)容時(shí)自動(dòng)地增加或縮減其容量傲宜。 另外，集合無法收納基本數(shù)據(jù)類型夫啊，像是整數(shù)（int)函卒、長(zhǎng)整數(shù)（long）或者雙精度浮點(diǎn)數(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.
有序集合（也稱為序列）锚国。該界面的用戶可以精確控制列表中每個(gè)元素的插入位置腕巡。用戶可以通過其整數(shù)索引（列表中的位置）訪問元素，并在列表中搜索元素血筑。
List接口是一個(gè)有序的 Collection绘沉，使用此接口能夠精確的控制每個(gè)元素插入的位置，能夠通過索引(元素在List中位置豺总，類似于數(shù)組的下標(biāo))來訪問List中的元素车伞，第一個(gè)元素的索引為 0，而且允許有相同的元素园欣。List 接口存儲(chǔ)一組不唯一帖世，有序（插入順序）的對(duì)象。
常用的List的實(shí)現(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.
一個(gè)不包含重復(fù)元素的集合日矫。更正式地說，集合不包含元素對(duì)e1和e2绑榴，使得e1.equals(e2)最多包含一個(gè)空元素哪轿。顧名思義，此接口對(duì)數(shù)學(xué)集合抽象進(jìn)行建模翔怎。
Set 具有與 Collection 完全一樣的接口窃诉，只是行為上不同，Set 不保存重復(fù)的元素赤套。Set 接口存儲(chǔ)一組唯一飘痛，無序的對(duì)象。
常用的Set的實(shí)現(xiàn)類：HashSet
需要注意的是：Set判斷重復(fù)是通過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.
將鍵映射到值的對(duì)象宣脉。映射不能包含重復(fù)的鍵；每個(gè)鍵最多可以映射到一個(gè)值剔氏。該接口代替了Dictionary類塑猖，后者是一個(gè)完全抽象的類，而不是一個(gè)接口谈跛。
Map 接口存儲(chǔ)一組鍵值對(duì)象羊苟，提供key（鍵）到value（值）的映射。
常用的Map實(shí)現(xiàn)類：HashMap
Collection體系常用實(shí)現(xiàn)類詳解
List
ArrayList（線性結(jié)構(gòu)感憾，基于動(dòng)態(tài)數(shù)組）
- 本質(zhì)上蜡励，
ArrayList就是一個(gè)數(shù)組。 - 動(dòng)態(tài)擴(kuò)容的實(shí)現(xiàn)：
- 創(chuàng)建一個(gè)更大的空間彭则。然后把原先的所有元素拷貝過去
線性結(jié)構(gòu)
簡(jiǎn)單地說占遥，線性結(jié)構(gòu)就是表中各個(gè)結(jié)點(diǎn)具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語言來描述瓦胎，線性結(jié)構(gòu)應(yīng)該包括如下幾點(diǎn)：
1、線性結(jié)構(gòu)是非空集搔啊。
2、線性結(jié)構(gòu)有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)漫蛔。
3旧蛾、線性結(jié)構(gòu)所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)锨天。
線性表就是典型的線性結(jié)構(gòu)病袄，還有棧、隊(duì)列和串等都屬于線性結(jié)構(gòu)脑奠。
LinkedList（鏈表）
鏈表
鏈表是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)宋欺，這種存儲(chǔ)結(jié)構(gòu)具有在物理上存在非連續(xù)的特點(diǎn)迄靠。鏈表由一系列數(shù)據(jù)結(jié)點(diǎn)構(gòu)成，每個(gè)數(shù)據(jù)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分菩咨。其中，指針域保存了數(shù)據(jù)結(jié)構(gòu)中下一個(gè)元素存放的地址特占。鏈表結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序來實(shí)現(xiàn)的是目。
ArrayList和LinkedList比較
由于二者是基于不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的懊纳，基于鏈表和線性結(jié)構(gòu)的不同嗤疯，二者主要的不同用法：
- ArrayList 對(duì)于【查】茂缚、【改】操作性能更高
- LinkedList 對(duì)與【增】屋谭、【刪】操作性能更高
Set
HashSet
最常用戴而，最高效的Set實(shí)現(xiàn)
-
List可以使用Set來去重Set去重
注意：HashSet是無序的淮逊，如果需要有序的HashSet可以使用LinkedHashSet扶踊。
散列表（Hash）
散列表源自于散列函數(shù)(Hash function)秧耗，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄分井，那么必定在F(T)的存儲(chǔ)位置可以找到該記錄尺锚，這樣就可以不用進(jìn)行比較操作而直接取得所查記錄瘫辩。
TreeSet
TreeSet是有序的，因?yàn)镃omparable的默認(rèn)順序是從小到大裸影，所以TreeSet的默認(rèn)順序是從小到大军熏，即自然順序荡澎。
因此：TreeSet最大的用途就是用來排序的衔瓮。TreeSet內(nèi)部的數(shù)據(jù)結(jié)構(gòu)是紅黑樹热鞍。
樹
樹是典型的非線性結(jié)構(gòu)薇宠，它是包括，2個(gè)結(jié)點(diǎn)的有窮集合K椒涯。在樹結(jié)構(gòu)中废岂，有且僅有一個(gè)根結(jié)點(diǎn)湖苞，該結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)财骨。在樹結(jié)構(gòu)中的其他結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)隆箩，而且可以有兩個(gè)后繼結(jié)點(diǎn)捌臊，m≥0问畅。
LinkedHashSet（有順序的HashSet）
保證內(nèi)部順序和插入的順序一樣护姆。
Map
HashMap
HashMap的線程不安全性
注意：HashMap是線程不安全的卵皂，在jdk的官方注釋中也提到了【Note that this implementation is not synchronized.】灯变。即：請(qǐng)注意添祸，HashMap的實(shí)現(xiàn)沒有被同步刃泌。
在多線程中耙替，HashMap的死循環(huán)問題：在多線程中俗扇，擴(kuò)容的時(shí)候，即resize的時(shí)候滞谢，有可能變成一個(gè)死循環(huán)的鏈表爹凹。感興趣的可以移步：疫苗：JAVA HASHMAP的死循環(huán)禾酱。因此在多線程中颤陶，應(yīng)該使用ConcurrentHashMap滓走，即并發(fā)的HashMap搅方。
HashMap在jdk1.7后的改變：同一個(gè)哈希桶中存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)由鏈表改為紅黑樹
如果恰好一個(gè)Map的所有的key的hashCode都是一樣的姨涡，那么他們就會(huì)放到同一個(gè)哈希桶中涛漂，那么這個(gè)HashMap就會(huì)變成一個(gè)效率極低的鏈表匈仗，導(dǎo)致程序運(yùn)行變慢悠轩，喪失了使用Hash算法的好處火架。JDK7以后距潘，發(fā)生哈希碰撞，存在同一個(gè)哈希桶中的數(shù)據(jù)不再是一個(gè)鏈表俭尖，而是變成了一個(gè)紅黑樹稽犁，從而提高了性能已亥。
TreeMap
內(nèi)部數(shù)據(jù)結(jié)構(gòu)同TreeSet虑椎，此處不再贅述捆姜。
HashMap和HashSet本質(zhì)上是?種東?：
- HashMap的key的set就是一個(gè)HashSet
- HashSet的實(shí)現(xiàn)中就包含了一個(gè)HashMap
哈希算法簡(jiǎn)介
Java世界里第二重要的約定（hashCode）
（第一重要的約定是equals約定）
- 同于一個(gè)對(duì)象必須始終返回相同的hashCode
- 兩個(gè)對(duì)象的equals返回true泥技，則必須返回相同的hashCode
- 因此珊豹，當(dāng)我們重寫equals方法時(shí)店茶，必須重寫hashCode方法
- 兩個(gè)對(duì)象不等忽妒，也可能返回相同的hashCode
哈希就是一個(gè)單項(xiàng)的映射段直，舉例來說就像百家姓：先把所有人按照姓來分類鸯檬，然后再查找：人名怎么取hashCode呢喧务，通過取他的姓功茴；那對(duì)象Object就會(huì)通過hashCode算法坎穿，映射成一個(gè)int玲昧。
在內(nèi)存中孵延，上面百家姓的例子尘应，姓就是內(nèi)存中的哈希桶菩收，通過hashCode方法算出一個(gè)哈希值娜饵，然后放到哈希桶中箱舞。如果我們有10萬條數(shù)據(jù)晴股，通過哈希算法分散到10萬個(gè)哈希桶中电湘，那么我們查找某一條數(shù)據(jù)寂呛，只需要查找一次贷痪，因此通過哈希算法劫拢，查找的時(shí)間復(fù)雜度是呈指數(shù)下降的舱沧。
Collection的其他實(shí)現(xiàn)
Queue（隊(duì)列）
有優(yōu)先級(jí)的集合简烤，LILO（Last In Last Out）
隊(duì)列
隊(duì)列和棧類似，也是一種特殊的線性表肾筐。和棧不同的是吗铐，隊(duì)列只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作镊逝。一般來說撑蒜，進(jìn)行插入操作的一端稱為隊(duì)尾座菠，進(jìn)行刪除操作的一端稱為隊(duì)頭浴滴。隊(duì)列中沒有元素時(shí)升略，稱為空隊(duì)列品嚣。
Deque（雙端隊(duì)列）
允許在兩端進(jìn)行增刪元素腰根。
Veetor
Vector是ArrayList的前身额嘿，已棄用
Stack（棧）
LIFO（Last In First Out）册养，如果需要”椙蚶梗“這種數(shù)據(jù)結(jié)構(gòu)坎炼，推薦使用Deque
棧
棧是一種特殊的線性表谣光，它只能在一個(gè)表的一個(gè)固定端進(jìn)行數(shù)據(jù)結(jié)點(diǎn)的插入和刪除操作萄金。棧按照后進(jìn)先出的原則來存儲(chǔ)數(shù)據(jù)，也就是說孙乖，先插入的數(shù)據(jù)將被壓入棧底的圆，最后插入的數(shù)據(jù)在棧頂越妈，讀出數(shù)據(jù)時(shí)梅掠，從棧頂開始逐個(gè)讀出阎抒。棧在匯編語言程序中且叁，經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場(chǎng)保護(hù)逞带。棧中沒有數(shù)據(jù)時(shí)展氓，稱為空棧遇汞。
ConcurrentHashMap
線程安全的HashMap
PriorityQueue（使用”堆“來實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列）
堆
堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)络它，一般討論的堆都是二叉堆化戳。堆的特點(diǎn)是根結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中最小的或者最大的迂烁，并且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆結(jié)構(gòu)
