Java基礎篇——集合淺談
原創不易,如需轉載,請註明出處 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(不重複、有序、非執行緒安全的集合)
-
底層實現,原始碼如下:
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; } }
我去,又是這個尿性,基於TreeMap來實現的
- 注意:
- 首先要正確重寫equals方法和hashCode方法,以保證放入Set物件的唯一性
- 需要實現Comparable介面,從而實現有序儲存
LinkedHashSet(不重複、位置有序、非執行緒安全的集合)
-
底層實現,原始碼如下:
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); } }
都是super,實現了把HashSet中預留的構造方法啟用了,因而可以實現有序插入(LinkedHashMap再談究竟)
- 注意:
- 首先要正確重寫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