目錄

Collection、List、Set、Map概述
Collection
Map
HashMap的實現(xiàn)原理
TreeMap的紅黑樹
Collections和Arrays輔助類
Iterator、ListIterator和Foreach三種遍歷
Concurrent包

Collection、List、Set、Map概述

Collection
........|--------List
........|..........|----------ArrayList
........|..........|----------Vector
........|..........|.............|-----Stack
........|..........|----------LinkedList
........|--------Set
...................|----------HashSet .
...................|.............|-----LinkedHashSet
...................|----------SortedSet
.................................|-----TreeSet
　
Iterator
.....|-------ListIterator
　
Map
.....|------Hashtable
.....|..........|------Properties
.....|------HashMap
.....|..........|------LinkedHashMap
.....|------WeakHashMap
.....|------SortedMap
................|------TreeMap

Collection .
●..實現(xiàn)該接口及其子接口的所有類都可應(yīng)用clone()方法，并是序列化類.

.....List.
.....●..可隨機訪問包含的元素
.....●..元素是有序的
.....●..可在任意位置增、刪元素
.....●..不管訪問多少次，元素位置不變
.....●..允許重復元素
.....●..用Iterator實現(xiàn)單向遍歷，也可用ListIterator實現(xiàn)雙向遍歷

..........ArrayList
..........●..用數(shù)組作為根本的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)List
..........●..元素順序存儲
..........●..新增元素改變List大小時，內(nèi)部會新建一個數(shù)組，在將添加元素前將所有數(shù)據(jù)拷貝到新數(shù)組中
..........●..隨機訪問很快，刪除非頭尾元素慢，新增元素慢而且費資源
..........●..較適用于無頻繁增刪的情況
..........●..比數(shù)組效率低，如果不是需要可變數(shù)組，可考慮使用數(shù)組
..........●..非線程安全
.
..........Vector .
..........●..另一種ArrayList，具備ArrayList的特性
..........●..所有方法都是線程安全的（雙刃劍，和ArrayList的主要區(qū)別）
..........●..比ArrayList效率低

...............Stack
...............●..LIFO的數(shù)據(jù)結(jié)構(gòu)

..........LinkedList.
..........●..鏈接對象數(shù)據(jù)結(jié)構(gòu)（類似鏈表）
..........●..隨機訪問很慢，增刪操作很快，不耗費多余資源
..........●..非線程安全

.....Set .
.....●..不允許重復元素，可以有一個空元素
.....●..不可隨機訪問包含的元素
.....●..只能用Iterator實現(xiàn)單向遍歷

..........HashSet
..........●..用HashMap作為根本數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)Set
..........●..元素是無序的
..........●..迭代訪問元素的順序和加入的順序不同
..........●..多次迭代訪問，元素的順序可能不同
..........●..非線程安全

...............LinkedHashSet
...............●..基于HashMap和鏈表的Set實現(xiàn)
...............●..迭代訪問元素的順序和加入的順序相同
...............●..多次迭代訪問，元素的順序不便
...............●..因此可說這是一種有序的數(shù)據(jù)結(jié)構(gòu)
...............●..性能比HashSet差
...............●..非線程安全

..........SortedSet
..........●..加入SortedSet的所有元素必須實現(xiàn)Comparable接口
..........●..元素是有序的

...............TreeSet .
...............●..基于TreeMap實現(xiàn)的SortedSet
...............●..排序后按升序排列元素
...............●..非線程安全

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　
Iterator ..
●..對Set、List進行單向遍歷的迭代器

..........ListIterator.
..........●..對List進行雙向遍歷的迭代器

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

Map
●..鍵值對，鍵和值一一對應(yīng)
●..不允許重復的鍵.

.....Hashtable.
.....●..用作鍵的對象必須實現(xiàn)了hashcode()、equals()方法，也就是說只有Object及其子類可用作鍵
.....●..鍵、值都不能是空對象
.....●..多次訪問，映射元素的順序相同
.....●..線程安全的

..........Properties
..........●..鍵和值都是字符串

.....HashMap
.....●..鍵和值都可以是空對象
.....●..不保證映射的順序
.....●..多次訪問，映射元素的順序可能不同
.....●..非線程安全

...............LinkedHashMap
...............●..多次訪問，映射元素的順序是相同的
...............●..性能比HashMap差

.....WeakHashMap ..
.....●..當某個鍵不再正常使用時，垃圾收集器會移除它，即便有映射關(guān)系存在
.....●..非線程安全

.....SortedMap.
.....●..鍵按升序排列
.....●..所有鍵都必須實現(xiàn).Comparable.接口.

...............TreeMap .
...............●..基于紅黑樹的SortedMap實現(xiàn)
...............●..非線程安全

Collection

Collection主要有List和Set兩種，主要成員結(jié)構(gòu)如下：

Collection
|-List-
| |-LinkedList
| |-ArrayList(:>AbstractList:>AbstractCollection:>Collection implements List)
| |-Vector-
| | |-Stack
|-Set-
| |-HashSet-
| | |-LinkedHashSet
| |-TreeSet

遍歷
Collection繼承Iterable，所以要通過iterator來遍歷數(shù)據(jù)，這其實是一個迭代器模式。
Collection只能iterate，不能get
Collections
java.util.Collections是一個幫助類，可以幫助各種collection對象sort、max等函數(shù)操作。
List
有序數(shù)據(jù)集合，重要的是次序，元素可以重復出現(xiàn)，可以通過下標直接找到元素，List可以get。
其中：
LinkedList是鏈表，插入刪除更快。另外，linkedlist可以對鏈表的最前面和最后面進行處理，這樣就可以把它用作棧、隊列、雙向隊列。
ArrayList、Vector是數(shù)組，數(shù)組的隨機訪問效率更高（直接下標找到元素）。
ArrayList是可變數(shù)組，capacity容量可以自動增加，增加方式是((舊容量 * 3) / 2) + 1，如果需要插入大量元素，可以用ensureCapacity來自主增加容量，也可以在初始化時指定初始容量List<String> lst=new ArrayList<>(500)。
ArrayList里專門用一個size變量管理元素的真正個數(shù)，而不是容器的容量。
Vector在操作方法上加了Synchronized同步，實現(xiàn)線程安全（并不是絕對安全，因為在鎖方法之外的配合會出問題）。
Vector增加了同步機制，所以使用迭代器時可能與修改操作沖突，此時會拋出異常ConcurrentModificationException，必須捕獲。
Vector實現(xiàn)了Cloneable，在clone中調(diào)的是系統(tǒng)的System.arraycopy函數(shù)，這是個native函數(shù)，不是在java層做的，而是交給了更底層，所以效率更高。
Vector擴容時，增加方式是原容量+增長系數(shù)capacityIncrement，如果該系數(shù)<=0，就直接原容量*2。
Vector不支持序列化，而ArrayList支持序列化。
Stack在Vector的基礎(chǔ)上實現(xiàn)了先進后出，增加了push、pop、peek等方法。
LinkedList其實同時實現(xiàn)了List接口和Deque雙鏈表接口，這兩個接口又都是Collection的子接口：

LinkedList的繼承關(guān)系

Map

Map中的key是一個set，value是一個collection，這樣key不可重復，value可以重復。
Collection和Map
Collection是對象的集合，Collection接口繼承了Iterable
Map是鍵值對的集合，Map接口沒有父接口。
Collection和Map沒有直接關(guān)系。
Map
Java中用Map存儲健值對，鍵不可以重復，值可以重復。
java.util.Map有四個實現(xiàn)類：

Map
|-HashTable
|-HashMap-
| |-LinkedHashMap
| |-WeakHashMap
|-TreeMap
|-IdentityHashMap

Map中的元素有內(nèi)置的順序，如果要保持添加順序，可以使用LinkedHashMap，如果要按照大小排序，可以使用TreeMap。
Map通過Hash散列存儲數(shù)據(jù)，速度比ArrayList更快。

HashTable有內(nèi)置同步，是線程安全的，不能存儲null值。
HashMap沒有做同步，但是可以存儲1個null值。

HashMap的實現(xiàn)原理

HashMap鏈表散列，是數(shù)組+鏈表的結(jié)合，默認使用一個長度16的數(shù)組，數(shù)組中每個元素都是一個鏈表的表頭。
Entry，數(shù)組和鏈表中，每個節(jié)點都是一個HashMapEntry，HashMapEntry包括key、value、hash（int值），next（指向下一個HashMapEntry）。
hash值和分配，對于每個數(shù)據(jù)，都會計算一個int型的hash值（key和value對象各自作為object的hashcode，做異或操作），hashCode是基類Object定義的方法（具體算法在c++實現(xiàn)，與地址、偏向鎖等有關(guān)），這個hash值對數(shù)組的長度（默認16）取余，根據(jù)得到的余數(shù)，分配到數(shù)組中的對應(yīng)鏈表的最后面（解決hash沖突）（Android是放到最后面）。
hashcode和equal
equal就是利用hashcode，如果覆寫了其中一個，就要一起配套的覆寫另一個。
內(nèi)存使用，占用比較大，原因包括：
1.數(shù)組本身默認長度16，會占用內(nèi)存
2.容量擴充時，每次2，判斷是否需要擴容的公式是：數(shù)據(jù)量>容量加載因子(默認0.75)，擴容時是移位運算+或運算，最后加1，可以快速得到一個2的N次冪作為目標容量值。
3.每次擴容時新建一個Entry數(shù)組，在舊數(shù)組中遍歷鏈表，重新分配位置（如果不在原位置，就向后移動2次冪的位置）
4.擴容后的最大值不超過2^{31-1（如果當期值是2}30，則直接賦值為2^31）
遍歷，刪改查元素時，先計算hash值定位到數(shù)組位置，然后遍歷查找鏈表。
key重復，因為key根據(jù)hash值判斷重復，所以如果key是個對象，加入HashMap后，又修改了key，hash值變化，就會重復插入，且舊的key就無法再查詢到。
HashTable
HashTable和HashMap的結(jié)構(gòu)和操作基本一致，但是HashTable增加了線程安全。
HashMap的key和value都可以為null。
但是因為同步的原因，HashTable的key/value值不允許為空，concurrent包里的ConcurrentHashMap的value值也不允許為空。從源碼上，遇到null的value值會拋出nullpointexception異常；從設(shè)計上，因為是并發(fā)操作可能刪除鍵值對，這樣在取出key的value時，無法判斷是key沒有對應(yīng)的value還是對應(yīng)的value為null。
ConcurrentHashMap
ConcurrentHashMap和HashMap的結(jié)構(gòu)和操作也基本一致，也是實現(xiàn)了線程安全，但是HashTable是鎖住整個表，ConcurrentHashMap只會鎖住要操作的節(jié)點，只在處理size時鎖整個表
WeakHashMap
WeakHashMap是對key做了弱引用，這樣不影響回收。
LinkedHashMap的實現(xiàn)原理
LinkedHashMap是HashMap的子類，但他輸出和順序和輸入的順序相同，因而適合LRU等操作。
LinkedHashMapEntry在HashMap中Entry的基礎(chǔ)上，增加了兩個指針before和after，這樣既是Hash表，又是雙向鏈表，鏈表順序就是讀寫順序。
LinkedHashMap有一個固定位置的header，如果在LRU模式下，讀過的Entry會插到header前面，所以header前一定是最近訪問過的，header后一定是最久沒訪問過的。
LinkedHashMap遍歷速度一般比HashMap慢，因為鏈表比數(shù)組慢，速度只和數(shù)據(jù)量有關(guān)，而HashMap和容量有關(guān)，如果容量巨大數(shù)據(jù)量很小，HashMap反而不占優(yōu)勢。
TreeMap的實現(xiàn)原理
TreeMap是數(shù)據(jù)是排序過的，實現(xiàn)了SortMap接口，保存的數(shù)據(jù)是按鍵值排序的（comparator），它是個紅黑樹數(shù)據(jù)結(jié)構(gòu)，是唯一有subMap()方法的Map。
IdentifyHashMap
用==代替equals對鍵值做比較。
SparseArray和ArrayMap
SparseArray稀疏數(shù)組，是兩個數(shù)組的結(jié)合，是Android特有的api，優(yōu)點是特別節(jié)省內(nèi)存，效率上在小數(shù)據(jù)量時占優(yōu)，大數(shù)據(jù)量不占優(yōu)。
SparseArray中的key是int值，LongSparseArray中的key是long值。
ArrayMap中的key是object值。
SparseArray和ArrayMap的實現(xiàn)原理類似，都是用兩個數(shù)組結(jié)合，一個存放key，一個存放value，對key使用二分法從小到大排序，查找/添加/刪除/都需要先使用二分法查找，找到key所在的index后，根據(jù)index進行操作（keyAt(index)，valueAt(index)）。
SparseArray和ArrayMap都適用于千級以下的數(shù)據(jù)，數(shù)據(jù)量過大時，二分查找性能退化嚴重。

TreeMap的紅黑樹

TreeMap其實就是維持了一個紅黑樹，紅黑樹實現(xiàn)非常復雜，但它性能很好，在最壞情況下也能保持很好的性能，查找/插入/刪除的事件復雜度為O(log n)，因為它的平衡性非常好，從根到葉子的最長可能路徑不超過最短可能路徑的兩倍，紅黑樹有4個特定：
1.節(jié)點是紅或黑
2.根是黑的
3.葉子是黑
4.每個紅節(jié)點的兩個子節(jié)點都是黑（從根到葉沒有連續(xù)的紅）
5.任一節(jié)點到每個葉子，黑節(jié)點數(shù)量相同
4+5合起來，就是最長不超過最短的兩倍。
插入操作
插入時總是插入紅節(jié)點，這樣可以避免對紅黑樹做調(diào)整，而且只可能破壞性質(zhì)2或者性質(zhì)4，這可以分情況遞歸調(diào)整。
刪除操作
普通二叉樹的刪除中，葉子節(jié)點和獨生子節(jié)點的刪除相對簡單，有兩個子節(jié)點的時候刪除就比較麻煩，需要使用左子樹的最大元素（所有右子樹中沒有子樹的那個節(jié)點就是最大元素）或右子樹的最小元素，并調(diào)整二叉樹。
紅黑樹的刪除增加了刪除后空節(jié)點的黑色屬性，新的節(jié)點是原色+黑色，如果是紅+黑就不用處理，如果是黑+黑就要分情況討論，遞歸處理。
經(jīng)典數(shù)據(jù)結(jié)構(gòu)-紅黑樹詳解

Collections和Arrays

Collections是個數(shù)據(jù)集合的輔助類，提供了各種查找和排序方法，如折半查找、逆序、交換等；Collections還能封裝，把集合轉(zhuǎn)換成特殊集合，如同步集合、只讀集合等。
Arrays是個數(shù)組的輔助類，可以對數(shù)組中的值進行比較、查找、刪改、排序。

Iterator、ListIterator和Foreach

Iterator是對列表單向遍歷，不需要知道集合及其元素的類型（所以可以抽象出迭代器設(shè)計模式），并可以直接在迭代中增刪改數(shù)據(jù)。
ListIterator可以對列表雙向遍歷。
Foreach是基于Iterator實現(xiàn)的，但是它需要知道集合中元素的類型。
For是按照數(shù)組下標查詢，所以在數(shù)組中效率最高，在鏈表中效率最低

Cuncurrent包

Java從5.0提供了java.util.cuncurrent.*并發(fā)包，主要是基于volatile變量和AbstractQueuedSynchronizer（AQS同步器）
volatile易變變量一方面在寫內(nèi)存時有內(nèi)存屏障鎖，避免指令重排序，另一方面在讀之前會立即從主內(nèi)存同步數(shù)據(jù)，原子性、一致性和有序性，他能做到后兩者。
AQS同步器是通過1個整型的volatile變量維持同步狀態(tài)，
并發(fā)容器，并發(fā)容器比較注重并發(fā)性，盡量不用鎖，比如CopyOnWrite側(cè)重于多讀少寫的場景，寫的時候重建容器，確保正在讀的線程不受影響；Cuncurrent也是多用volatile實現(xiàn)讀不加鎖，僅在put等修改操作上加鎖。
cuncurrent包中具體提供了如下結(jié)構(gòu)：
CunCurrentHashMap，
ReentrantLock，
Condition，
CopyOnWriteArrayList，
CopyOnWriteArraySet，
ArrayBlockingQueue，
ThreadPoolExecutor，
Future、FutureTask，

引用

Java集合及concurrent并發(fā)包總結(jié)（轉(zhuǎn)）
Android HashMap源碼詳解
Android內(nèi)存優(yōu)化（使用SparseArray和ArrayMap代替HashMap）
設(shè)計模式匯總：結(jié)構(gòu)型模型（上）
JAVA LinkedList和ArrayList的使用及性能分析
Collection，List，Set和Map用法和區(qū)別
Android HashMap源碼詳解
HashMap的擴容機制---resize()
經(jīng)典數(shù)據(jù)結(jié)構(gòu)-紅黑樹詳解
HashSet的存儲方式是把HashMap中的Key作為Set的對應(yīng)存儲項