一、集合的類型
? 1炊邦、集合分為單列集合和雙列集合
? ?1.1單列集合
Collection為單列集合的根馁害。它常用的子接口有List碘菜、Set
List忍啸，為有序集合计雌，它提供了方便的訪問凿滤、插入翁脆、刪除等操作。
ArrayList沙热、Vector校读、LinkedList為List的常用實現(xiàn)類
Set祖能，Set 是不允許重復(fù)元素的雁芙，這是和 List 最明顯的區(qū)別
HashSet、TreeSet為Set常用的實現(xiàn)類
HashSet由哈希表(實際上是一個HashMap實例)支持兔甘，不保證set的迭代順序洞焙，并允許使用null元素
了解：Queue/Deque澡匪，則是 Java 提供的標準隊列結(jié)構(gòu)的實現(xiàn)唁情，除了集合的基本功能甸鸟，它還
支持類似先入先出或者后入先出抢韭。
Stack是棧后雷。是繼承于Vector(矢量隊列)的，由于Vector是通過數(shù)組實現(xiàn)的臀突，這就意味著贾漏，Stack也是通過數(shù)組實現(xiàn)的候学，而非鏈表它的特性是：先進后出
1.2雙列集合
Map為雙列集合的根。它常用的實現(xiàn)類有HashMap纵散、TreeMap
? ? ? ? HashMap類：
基于哈希表的Map接口實現(xiàn)梳码，非線程同步，提供所有可選的映射操作伍掀，允許null鍵值掰茶，不保證映射順序。
TreeMap：
基于紅黑樹的SortedMap接口實現(xiàn)蜜笤，保證映射按照升序排列關(guān)鍵字濒蒋，根據(jù)使用的構(gòu)造方法不同，可能會按不同的方法排序把兔。
二沪伙、集合底層的實現(xiàn)
1：數(shù)據(jù)結(jié)構(gòu)
? ? ? ? ?ArrayList：
? ? ?1：是List接口的可變數(shù)組非同步實現(xiàn)围橡，并允許包括null在內(nèi)的所有元素。
? ? ?2：底層使用數(shù)組實現(xiàn)
? ? ? ?LinkedList：
? ? 1：是List接口的雙向鏈表非同步實現(xiàn)，并允許包括null在內(nèi)的所有元素牧嫉。
? ? 2：底層的數(shù)據(jù)結(jié)構(gòu)是基于雙向鏈表的鳍置，該數(shù)據(jù)結(jié)構(gòu)我們稱為節(jié)點
? ? ? ? HashSet：
? ?1：由哈希表(實際上是一個HashMap實例)支持偷崩，不保證set的迭代順序，并允許使用null元素。
? ?2：基于HashMap實現(xiàn)
? ? ? ? HashMap
? ?1：是基于哈希表的Map接口的非同步實現(xiàn)，允許使用null值和null鍵，但不保證映射的順序。
? ?2：底層使用數(shù)組實現(xiàn)，數(shù)組中每一項是個單向鏈表祟绊，即數(shù)組和鏈表的結(jié)合體；當鏈表長度大于一定閾值時讲坎，鏈表轉(zhuǎn)換為紅黑樹，這樣減少鏈表查詢時間。?
? ?注意：? 在jdk1.8版本之前HashMap的底層數(shù)據(jù)結(jié)構(gòu)使用數(shù)組和鏈表實現(xiàn)。紅黑樹 在? jdk1.8版本開始使用
2：擴容機制
Vector：擴容成原來 2 倍
ArrayList：擴容成原來的 1.5 倍
如果實例化 list 的時候秆撮，沒有指定初始容量舒裤，JDK1.8 中 默認容量是 0伴鳖，但是 JDK6
和 7 默認是 10须肆。我們可以肯定的是擴容的時機是 add 調(diào)度的時候
當集合中通過 add 方法踢入第一個元素的時候拒贱，容量為 10
LinkedList
??? 鏈表結(jié)構(gòu)，且是是雙向鏈表缰揪， 不涉及擴容的問題定硝。
HashMap
? ?在增加第一個元素之前容量為16镀虐，加載因子是0.75
3：源碼分析
HashMap底層實現(xiàn)原理
HashMap 繼承于 AbstractMap 類辈毯，實現(xiàn)了 Map 接口。Map 是"key-value 鍵?
值對"接口铆隘，AbstractMap 實現(xiàn)了"鍵值對"的通用函數(shù)接口融击。
HashMap 基于 Hash 算法實現(xiàn)的尊浪，我們通過 put(key,value)存儲券躁，get(key)
來獲取也拜。當傳入 key 時岸军，HashMap 會根據(jù) key. hashCode() 計算出 hash
值方妖，根據(jù) hash 值將 value 保存在 bucket 里。當計算出的 hash 值相同
時讶请，我們稱之為 hash 沖突剿牺，HashMap 的做法是用鏈表和紅黑樹存儲相同
hash 值的 value。當 hash 沖突的個數(shù)比較少時环壤，使用鏈表否則使用紅黑
樹晒来。
三、集合在特定場景下的應(yīng)用方案
? ? ? ? ? ? ? ? ? ?最近瀏覽可以選取 LinkedList
? ? ? ? ? ? ? ? ? 先進先出可以考慮 Queue 隊列
? ? ? ? ? ? ? ? ? 先進后出可以考慮 Stack
四郑现、Iterator 迭代器
迭代器是 Iterator 接口：該接口中有三個核心方法 湃崩，維護指針可以向下移動
（next），移動到指定位置后接箫，取出當前位置的元素(next)攒读，以及重置指針操作
remove。
所有的數(shù)組和單列集合都實現(xiàn)了 Iterable 接口
五辛友、集合的 fail-fast 機制（了解）
ail-fast 機制是java集合(Collection)中的一種錯誤機制薄扁。當多個線程對同一個集合的內(nèi)容進行操作時，就可能會產(chǎn)生fail-fast事件废累。
例如：當某一個線程A通過iterator去遍歷某集合的過程中邓梅，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問集合時邑滨，就會拋出ConcurrentModificationException異常日缨，產(chǎn)生fail-fast事件。
