原創不易，如需轉載，請註明出處 "https://www.cnblogs.com/baixianlong/p/10703558.html" ，否則將追究法律責任！！！ Set（基於Map來實現的，不細說） HashSet（不重覆、無序、非線程安全的集合） 底層實現，源碼如下： public clas ...
原創不易，如需轉載，請註明出處https://www.cnblogs.com/baixianlong/p/10703558.html，否則將追究法律責任！！！
Set（基於Map來實現的，不細說）
HashSet（不重覆、無序、非線程安全的集合）
底層實現，源碼如下：
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; //賣個關子，這裡為啥要用transient關鍵字? 評論區見哦！ private transient HashMap<E,Object> map; private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } public boolean add(E e) { return map.put(e, PRESENT)==null; } ... }不用多說，是不沒想到，原來HashSet是基於HashMap實現的，元素都存到HashMap鍵值對的Key上面，而Value時有一個統一的值private static final Object PRESENT = new Object();
- 註意：
- 對於HashSet中保存的對象，主要要正確重寫equals方法和hashCode方法，以保證放入Set對象的唯一性
- HashSet沒有提供get()方法，願意是同HashMap一樣，Set內部是無序的，只能通過迭代的方式獲得
TreeSet（不重覆、有序、非線程安全的集合）
底層實現，源碼如下：
我去，又是這個尿性，基於TreeMap來實現的public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { private transient NavigableMap<E,Object> m; private static final Object PRESENT = new Object(); TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() { this(new TreeMap<E,Object>()); } public boolean add(E e) { return m.put(e, PRESENT)==null; } }- 註意：
- 首先要正確重寫equals方法和hashCode方法，以保證放入Set對象的唯一性
- 需要實現Comparable介面，從而實現有序存儲
LinkedHashSet（不重覆、位置有序、非線程安全的集合）
底層實現，源碼如下：
都是super,實現了把HashSet中預留的構造方法啟用了，因而可以實現有序插入（LinkedHashMap再談究竟）public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2851667679971038690L; public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } }- 註意：
- 首先要正確重寫equals方法和hashCode方法，以保證放入Set對象的唯一性
- 內部實現了有序插入，所以使用時不需要考慮
Map
HashMap（無序、線程不安全）
Jdk1.7數據存儲結構（採用數組+鏈表）
Jdk1.8數據存儲結構（採用數組+鏈表+紅黑樹）
註意：在鏈表長度大於8後，查詢複雜度由O(n)變為O(logn)，將鏈表存儲轉換成紅黑樹存儲（也就是TreeMap）
紅黑樹R-B Tree簡介(本質其實是2-3-4樹):
二叉樹特性： （1）左字數上所有的節點的值都小於或等於他的根節點上的值 （2）右子樹上所有節點的值均大於或等於他的根節點的值 （3）左、右子樹也分別為二叉樹 紅黑樹特點（一種平衡二叉樹）： （1）每個結點要麼是紅的要麼是黑的。 （2）根結點是黑的。 （3）每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）都是黑的。 （4）如果一個結點是紅的，那麼它的兩個兒子都是黑的。 （5）對於任意結點而言，其到葉結點樹尾端NIL指針的每條路徑都包含相同數目的黑結點 節點操作： （1）左旋 （2）右旋 （3）變色
TreeMap（有序、線程不安全）
- 底層就是紅黑二叉樹
LinkedHashMap（有序、線程不安全）
底層實現，源碼如下：
static class Entry<K,V> extends HashMap.Node<K,V> { //這裡維護了一個before和after的Entry， 見名思意， 就是每個Entry<K,V>都維護它的上一個元素和下一個元素的關係。這也是LinkedHashMap有序的關鍵所在。 Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }LinkedHashMap是繼承HashMap， 也就是說LinkedHashMap的結構也是和HashMap那樣(數組+鏈表)
註意：LinkedHashMap分為插入的順序排列和訪問的順序排列兩種方式，通過accessOrder參數來控制
Hashtable（線程安全）
- 底層數據結構同HashMap。線程安全，效率低，沒什麼卵用，需要使用線程安全的Map可以使用ConcurrentHashMap
List
ArrayList(位置有序、可重覆、線程不安全)
- 底層數據結構是數組,查詢快
LinkedList（有序、線程不安全）
- 底層數據結構是雙向鏈表,查詢慢,增刪快
Vector（有序、線程安全）
- 底層數據結構是數組,查詢快,增刪慢
併發集合
ConcurrentHashMap（線程安全）
- 利用了鎖分段的思想提高了併發度,把Map分成了N個Segment,每個Segment相當於HashTable
CopyOnWriteArrayList(線程安全)
- 讀寫分離，寫時複製出一個新的數組，完成插入、修改或者移除操作後將新數組賦值給array
Queue
非阻塞隊列
- PriorityQueue ：實質上維護了一個有序列表
- ConcurrentLinkedQueue ：基於鏈接節點的、線程安全的隊列
阻塞隊列
- ArrayBlockingQueue ：一個由數組支持的有界隊列。
- LinkedBlockingQueue ：一個由鏈接節點支持的可選有界隊列。
- PriorityBlockingQueue ：一個由優先順序堆支持的無界優先順序隊列。
- DelayQueue ：一個由優先順序堆支持的、基於時間的調度隊列。
- SynchronousQueue ：一個利用 BlockingQueue 介面的簡單聚集（rendezvous）機制。
總結
- 本來想詳細的總結一下各種集合的使用和底層實現，但發現說來說去還是數據結構的事，你要能把數組、鏈表、二叉樹、紅黑樹等數據結構弄明白，這些所謂的集合也就是不同的實現而已。
- 以後有機會還是直接來搞數據結構、演算法吧！
個人博客地址：
csdn:https://blog.csdn.net/tiantuo6513
cnblogs:https://www.cnblogs.com/baixianlong
segmentfault:https://segmentfault.com/u/baixianlong
github:https://github.com/xianlongbai
