Java的Collection一直都是很經(jīng)典的一個話題，花了些時間把常用的幾個類做了一下整理。記錄一下自己的學(xué)習(xí)并分享心得！
Java集合框架Collection是由一套設(shè)計優(yōu)良的接口和類組成的，使我們操作成批的數(shù)據(jù)或?qū)ο笤貥O為方便，這些接口和類有很多對抽象數(shù)據(jù)類型操作的API。并且Java用面向?qū)ο蟮脑O(shè)計對這些數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行了封裝，這就極大的減化了我們在編程上的工作量。
下面的圖是一張Java Collection的UML, (從CSDN的一個博客上拿的，總結(jié)很詳細(xì)，訪問更清晰的圖片：https://blog.csdn.net/u010887744/article/details/50575735)
我們常用的類有如下幾個：Vector, ArrayList, LinkedList, HashSet,HashTable, HashMap
Vector, ArrayList, LinkedList都實現(xiàn)的List接口，繼承的AbstractList抽象類
HashSet實現(xiàn)的是set接口，繼承的AbstractSet抽象類
HashMap實現(xiàn)的是map接口，繼承的AbstractMap抽象類，
HashTable實現(xiàn)的是map接口，繼承的Dictionary類
一：List
? ? List存儲一組不唯一，有序（按插入順序存儲）的對象，類似于Java數(shù)組，能夠通過索引(元素在List中位置，類似于數(shù)組的下標(biāo))來訪問List中的元素。
1：Vectory
? ? 內(nèi)部維護(hù)了一個Object的數(shù)組，在源碼中Vectory定義了一個Object[]的成員變量
? ? protectedObject[] elementData;
? ? 可以插入重復(fù)的元素，在源碼中可以看到，只要數(shù)組有空間，就直接加到樹組的下一個單元
? ? public synchronized voidadd (E obj) {
? ? ? ? modCount++;
? ? ? ? ensureCapacityHelper(elementCount + 1);
? ? ? ? elementData[elementCount++] = obj;
? ? ? ? }
? ? 存儲的順序和插入的順序一至，因為，Vectory的內(nèi)部實現(xiàn)就是一個對象數(shù)組，如果我們不指定插入的位置，那默認(rèn)就是將新元素插入到尾斷
? ? 查詢速度快,可以通過索引快速隨機(jī)讀取
? ? 添加,刪除慢,需要移動數(shù)據(jù)
? ? 線程安全，Vectory里面的所有函數(shù)都添加了synchronized關(guān)鍵字，Vectory是一個線程安全的collection
? ? Vectory的遍歷方式：
2: ArrayList
? ? 和Vectory一樣，內(nèi)部實現(xiàn)也是一個object數(shù)組，用來存儲存儲一組不唯一，有序（按插入順序存儲）的對象，不同的是，ArrayList是非同步的，所以在單線程環(huán)境中一般使用ArrayList,在多線程環(huán)境中使用Vectory
? ? 內(nèi)部維護(hù)了一個Object的數(shù)組，在源碼中ArrayList定義了一個Object[]的成員變量
? ? private transientObject[] elementData;
? ? 可以插入重復(fù)的元素，在源碼中可以看到，只要數(shù)組有空間，就直接加到數(shù)組的下一個單元
? ? public booleanadd(E e) {
? ? ? ? ? ensureCapacity(size + 1);
? ? ? ? elementData[size++] = e;
? ? ? ? ? return true;
? ? ? }
? ? 存儲的順序和插入的順序一致
? ? 查詢速度快,可以通過索引快速隨機(jī)讀取
? ? 添加,刪除慢,需要移動數(shù)據(jù)
? ? 線程不安全, ArrayList里面的所有函數(shù)都沒有同步
? ArrayList的遍歷方法：
3: LinkedList
? ? LinkedList和ArrayList,Vectory都不一樣，它是一個雙向鏈表。用來存儲存儲一組不唯一，有序（按插入順序存儲）的對象
? ? 在LinkedList內(nèi)部維護(hù)了2個Node結(jié)點(diǎn)，一個Prev,一個next.
? ? transient Node<E> first; //鏈表的頭結(jié)點(diǎn)
? ? transient Node<E> last; //鏈表的尾節(jié)點(diǎn)
? ? 可以插入重復(fù)的元素，而且存儲的順序和插入的順序一至，在源碼中每次添加新元素都是添加到末尾
public boolean add(E e) {
? ? final Node<E> l = last;
? ? final Node<E> newNode = new Node<>(l, e, null);
? ? last = newNode;
? ? if (l == null)
? ? ? ? first = newNode;//原來鏈表為空，這是插入的第一個元素
? ? else
? ? ? ? l.next = newNode;
? ? size++;
? ? return true;
}
? ? 查詢慢,需要移動指針來遍歷
? ? 添加,刪除較快
? ? 線程不安全，和LinkedList所有函數(shù)都沒有同步
? LinkedList的遍歷方法：
二：Set
? ? 是一種無序，不包含重復(fù)元素的Collection, Set和 List雖然都是存儲的對象但是實現(xiàn)方式卻完全不一樣，List是以樹組為基礎(chǔ)實現(xiàn)的而set是以hashMap為基礎(chǔ)實現(xiàn)的
1: HashSet
? ? 內(nèi)部通過HashMap實現(xiàn)，從源碼中可以看到，內(nèi)部維護(hù)了一個HashMap的對象
? ? private transient HashMap map;
? ? 不允許重復(fù)元素插入(當(dāng)插入重復(fù)元素后，會將原有的元素的值都覆蓋掉)，從源碼中可? ? ? 以看到當(dāng)有新元素添加到map中時，會加到map的key中,而value用object代替
? ? private static final Object PRESENT = new Object(); //hashMap中的value
? ? public boolean add(E e) {
? ? ? ? return map.put(e, PRESENT)==null;
? ? }
? ? 元素插入的順序和存儲的順序不一至
? ? 允許null元素
? ? 沒有做線程安全，因為所有函數(shù)都沒有同步
? ? HashSet的遍歷方法：
三：Map
? ? Map是一種儲存鍵值對 (key-value)對像的collection,在key-value的結(jié)果儲存中，key不能重復(fù)，value可以重復(fù)。
1：hashMap
? ? 是一個散列表，通過鏈地址法來解決沖突。
? ? 內(nèi)部實現(xiàn)是個Entry(Entry是一個可以構(gòu)成單向鏈表的類)的數(shù)組，在源碼中內(nèi)部定義了一個Entry成員變量：
? ? private transient Entry[] table;
? ? 使用鏈地址法來處理沖突，在源碼中可以發(fā)現(xiàn)HashMap是先通過hash(key)生成hash值，然后通過hash值計算存儲的位置
? ? ? ? int hash = hash(key);
? ? ? ? int index = hash &(table.length-1);
? ? HashMap在添加新元素時，找到了儲存的數(shù)組位置 index后會遍歷鏈表tab[index]，如果在鏈表tab[index]中找到相同的key,替換該key對應(yīng)的value,找不到新建一個Entry,并插入到tab[index]鏈表
? ? for (Entry e =table[index]; e != null; e = e.next) {
? ? ? ? Object k；
? ? ? ? if (e.hash == hash && ((k =e.key) == key || key.equals(k))) {
? ? ? ? ? ? V oldValue =e.value;
? ? ? ? ? ? e.value = value;
? ? ? ? ? ? e.recordAccess(this);
? ? ? ? ? ? return oldValue;
? ? ? ? }
? ? }
? ? modCount++;
? ? addEntry(hash, key, value, index);
? ? 元素插入的順序和存儲的順序不一至
? ? key允許為null(但只能有一條并且放在tbl[0]，如果再寫入會將第一次的value覆蓋掉)
? ? 非線程安全，因為所有函數(shù)都沒有同步
? HashMap的遍歷方法：
? 2：HashTable
? ? 是一個散列表，用來儲存鍵值對(key-value)對像的collection。它是繼承自Dictionary,實現(xiàn)的Map接口。
? ? 內(nèi)部實現(xiàn)是個Entry的數(shù)組和HashMap一樣，在內(nèi)部維護(hù)了一個Entry數(shù)組的成員變量：
? ? private transient Entry[] table;
? ? 使用鏈地址法來處理沖突， 和HashMap一樣也是先通過hash(key)生成hash值，然后通過hash值計算存儲的位置。但是不一樣的是他們的index計算方式，HashMap是用Hash值 “與”運(yùn)算數(shù)組的長度-1，而HashTable是Hash值除數(shù)組的長度取余數(shù)。
? ? int hash = hash(key);
? ? int index = (hash &0x7FFFFFFF) % tab.length;
? ? 添加元素和HashMap一樣，找到了儲存的數(shù)組位置 index后會遍歷鏈表tab[index]，如果在鏈表tab[index]中找到相同的key,替換該key對應(yīng)的value,找不到新建一個Entry,并插入到tab[index]鏈表中
? ? Entry e = tab[index];
? ? tab[index] = newEntry<>(hash, key, value, e);
? ? 元素插入的順序和存儲的順序不一至
? ? key和value都不能插入null
? ? 線程安全，因為HashTable的函數(shù)都是加了synchronized
? ? public synchronized V put(K key, V value){
? ? 。。。。}
? ? HashTable的遍歷方法：
? ? 從上面的遍歷方式我們可以看出來，HashTable比HashMap多了Elements的遍歷，所以HashTable和HashMap繼承類是不一樣的。
3：ConcurrentHashMap
? ? 和HashMap,HashTable一樣都是儲存鍵值對(key-value)對像的collection，HashMap是非線程安全，而HashTable是線程安全，所以在多線程中，我們一般使用HashTable,但HashTable是對整個hash表結(jié)構(gòu)做鎖定操作的，這樣在鎖表的期間，別的線程就需要等待了，性能不是很好。
? ? ConcurrentHashMap就解決HashTable的缺陷，因為在ConCurrentHashMap中，加鎖是采用的分段加鎖技術(shù)。
? ? ConcurrentHashMap內(nèi)部是由一個Segment數(shù)組和一個HashEntry鏈表構(gòu)成的，在每一個Segment段都設(shè)置了一把鎖，所以對于不同Segment的數(shù)據(jù)進(jìn)行操作是不用考慮鎖競爭的
? ? final Segment[] segments;
segment類似于hashmap,內(nèi)部實現(xiàn)是一個HashEntry數(shù)組
? ? transient volatileHashEntry[] table;(HashEntry是一個可以構(gòu)成單向鏈表的類)
? ? ConcurrentHashMap的沖突解決方式和HashTable, HashMap都一樣，先計算key的hash值，然后將該hash值右移segmentShift位（segmentShift? = 32 - segments.length 2次開方的值）然后 “與”運(yùn)算segmentMask（segmentMask? = segments.length -1）
? ? int hash = hash(key);
? ? int j = (hash>>> segmentShift) & segmentMask;
? ? 在ConcurrentHashMap中執(zhí)行put操作時，ConcurrentHashMap就會調(diào)用Segment的put操作，但這個時候并不加鎖，只是確定Segment的index位置。
? ? public V put(K key, V value) {
? ? Segment s;
? ? 。。。。。。
? ? return s.put(key, hash,value, false);
? ? }
? ? 在Segment中執(zhí)行put操作時，1:加鎖，2:添加到HashEntry的鏈表中，3:釋放鎖
? ? final V put(K key, int hash, V value, boolean onlyIfAbsent) {
? ? HashEntrynode = tryLock() ? null : scanAndLockForPut(key, hash, value);
? ? Try{
? ? ? ? 。。。。? ? ? ?
? ? }finally {
? ? ? ? unlock();
? ? }
}
? ? key和value都不能插入null
? ? 不允許重復(fù)的key插入(如果重復(fù)key對應(yīng)的value會被覆蓋)，value可重復(fù)
ConcurrentHashMap的遍歷方法：
