Java 集合
fail-fast機制
在java集合類中,使用modCount來檢查數組的狀態.
當在迭代集合的時候,(通常會實現 iterator()方法來獲取迭代對象,或者 foreach),
集合里面的數據,在其他地方被修改了,這個時候 modCount就會被修改,與迭代過程的modCount不一致.將拋出ConcurrentModificationException異常,這個過程就叫 fail-fast
List 篇
主要介紹 ArrayList,Vector和LinkedList,CopyOnWriteArrayList
ArrayList
是一個數組長度可自增長的線程不安全的列表.內部使用數組實現. Object[] elementData.
時間復雜度 :
根據索引查詢,復雜度為 O(1).
根據元素查詢,復雜度為 O(N).
插入和刪除,如果在列首復雜度為 O(N);在列尾復雜度為 O(1);平均復雜為 O(N)
插入和刪除非列尾數據, 將會導致數組移動數據.
RandomAccess 接口
RandomAccess 是一個標記接口(沒有任何方法).
如果實現了 RandomAccess 接口,表示該集合可以進行隨機快速訪問(通常底層是 數組形式的集合),如 ArrayList.
可以快速訪問的集合,使用
未實現 RandomAccess接口的集合,如LinkedList,使用迭代器效率更高.
for (Iterator i=list.iterator(); i.hasNext(); )i.next();使用 instanceof RandomAccess來判斷是否 支持隨機快速訪問.
Vector
是一個數組長度可自增長的線程安全的列表,內部使用數組實現.
線程安全的vector,照樣可以觸發 fail-fast.
時間復雜度與 arraylist 一樣.
在不涉及線程安全的前提下,arraylist效率更高.
fun main(args: Array<String>) {val vector = Vector(listOf(1, 2, 3, 4, 5))singleThread(vector)multiThread(vector)multiThreadSynchronized(vector) }/*** 單線程下,迭代拋出 ConcurrentModificationException*/ fun singleThread(vector: Vector<Int>) {val it = vector.iterator()while (it.hasNext()) {println(it.next())vector.add(1)} }/*** 多線程下,迭代拋出 ConcurrentModificationException*/ fun multiThread(vector: Vector<Int>) {thread {repeat(10000) {vector.add(it)}}thread {vector.forEach { println(it) }} }/*** 多線程下,修改vector是添加同步鎖,避免同時迭代同時修改*/ fun multiThreadSynchronized(vector: Vector<Int>) {thread {synchronized(vector) {repeat(10000) {vector.add(it)}}}thread {vector.forEach { println(it) }} }Stack
繼承自 vector,線程安全,棧結構,先進后出.
LinkedList
是以雙向鏈表方式實現的非線程安全的集合.
時間復雜度:
刪除和插入元素,復雜度為 O(1).
查詢時,由于采用雙向鏈表,判斷離哪頭近,從哪頭開始找.
最糟糕的情況是O(N/2),所以它的復雜度為 O(N).
CopyOnWriteArrayList
CopyOnWriteArrayList是并發包中的實現.使用 ReenterLock和System.arraycopy來實現數組讀寫的線程安全.
在讀取的時不加鎖,所以可以支持多線程同時讀取數據,并且同時讀取數不受限制.
在寫入(add,set,remove等操作)的時候,使用 ReenterLock鎖住方法,然后操作數據時先將原數組拷貝一份,對拷貝數據進行操作,操作完后將拷貝的原來的數據引用指向拷貝的數組引用,實現數據的更新操作,更新完后釋放鎖. 和其名字操作一致(寫時拷貝).
沒有設置初始長度的方法和擴容的策略. 因為該數組在每次 添加數據是, 都會使用 System.arraycopy拷貝一份比當前數據 +1 的數組.
public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}}ArrayList,Vector和LinkedList的區別
ArrayList和Vector內部都是使用數組實現的.它們的主要區別在于
在不考慮線程安全的情況下,優先使用 ArrayList,如果在使用前,能夠預估大概有元素,創建時指定個數,效果更好.
LinkedList 使用雙向鏈表實現,也是線程不安全的.與ArrayList的區別在于
如果主要需要對列表進行遍歷,以及增刪操作,使用LinkedList其他情況使用ArrayList.
如果需要用到線程安全的列表,請使用 CopyOnWriteArrayList
Map篇
Map 是以鍵值對形式存儲的集合.
主要介紹 HashMap,TreeMap和 Hashtable,ConcurrentHashMap
HashMap
HashMap 內部混合使用數組,鏈表,紅黑樹的結構來構建的鍵值對集合.
HashMap的本質基礎是基于數組的. 數組的各個元素,使用單向鏈表的結構.(Node(int hash, K key, V value, Node<K,V> next)).
HashMap通過哈希函數(hash())來完成key對index的映射.
當出現hash后index沖突(index位置已經存在不同的key的鍵值對)時,數據將在index位置,使用單向鏈表或紅黑樹(當鏈表長度大于等8個時,鏈表中的所有元素改用紅黑樹存放)來存放元素.
當使用掉的索引 占用了 數組長度的一定比例時(填裝因子),HashMap將進行擴容(擴容為原來的兩倍,key與index重新映射).
HashMap的性能瓶頸:
理想的狀態是,每一個鍵值對的存放,能夠比較均勻適當的分布在數組的索引上,盡量避免過多的hash值沖突.
// java 8 中的實現static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} // index = (n - 1) & hash , 2的次方來說就是取余操作. // 由于 (n -1)的二進制 高位都是0,地位都是1. // hashcode 與 它進行 & 操作的話, hashcode的高位變化低位不變,則計算出來的index值講不變. // 為了消除高位變化 不影響 index 的值, 于是將 hashcode 的 高16位 移動到低16位,再和 hashcode進行 ^ 操作. // 這樣高位的變化,也能影響index值, 降低了沖突的概率.過低的填裝因子,如填裝因子=0.5,容量剩余一半的時候就擴容,可能導致空間上的浪費.
過高的填裝因子,可能導致為了命中未使用的索引,而頻繁出現 沖突.
HashMap實現中,填裝因子默認使用 0.75的值.
特點 :
時間復雜度 :
查詢,插入和刪除操作的平均時間復雜度為 O(1).
極端情況下(全部發生沖突),若長度小于8,使用單項鏈表,復雜度為 O(n),如果長度大于等于8,使用紅黑樹,復雜度為O(logn)
LinkedHashMap
繼承自 HashMap, 底層使用哈希表與雙向鏈表來保存元素,與HashMap的差異就在于 訪問順序上.
構造中,accessOrder 默認為 false，代表按照插入順序進行迭代；為 true，代表以訪問順序進行迭代(最常訪問的在前,最不經常訪問的在后LRU)。
TreeMap
TreeMap內部使用 紅黑樹來實現的鍵值對集合.與HashMap相比，TreeMap是一個能比較元素大小的Map集合，會對傳入的key進行了大小排序。其中，可以使用元素的自然順序，也可以使用集合中自定義的比較器來進行排序.
特點 :
時間復雜度 :
紅黑樹是自平衡的二叉搜索樹, 查詢,添加刪除 效率都是 O(logn).
HashTable
HashTable 內部使用數組和單項鏈表實現的鍵值對集合.
HashTable的哈希函數 (hash & 0x7FFFFFFF) % tab.length,只是對key的hashcod進行取整和取余操作.
HashTable默認的初始大小為11，之后每次擴充為原來的2n+1。
也就是說，HashTable的鏈表數組的默認大小是一個素數、奇數。之后的每次擴充結果也都是奇數。
由于HashTable會盡量使用素數、奇數作為容量的大小。當哈希表的大小為素數時，簡單的取模哈希的結果會更加均勻。（這個是可以證明出來 的，可參考：http://zhaox.github.io/algorithm/2015/06/29/hash）
特點 :
時間復雜度 :
和HashMap一致
ConcurrentHashMap (java.util.concurrent)
和HashMap一樣,是內部使用數組,鏈表,紅黑樹的結構來構建的鍵值對集合,因為需要保證線程安全,所以內部實現更加復雜.
哈希函數 (h ^ (h >>> 16)) & HASH_BITS , 和HashMap類似,與高位進行異或操作的方式,來消除高位數據變化導致索引不變的情況,多加了一步正數的操作.
當沖突的鏈表中個數超過8個, 如果數組長度小于64,則擴容,否則,將鏈表數據轉化為 紅黑樹結構存儲.
ConcurrentHashMap 采用 CAS(Compare and Swap)原子類型操作,來保證線程的安全性. 較 jdk1.7 的分段鎖機制性能更好.
特點 :
構造函數為 : ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
沒有默認的裝填因子,傳入 初始容量和裝填因子后,會被算法調整為 2次方,最小容量為 16.
并發級別,表示 可以同時對數據進行寫操作的線程數, 最大可達16. 讀取不受限制.
時間復雜度 :
和HashMap一致
HashMap和HashTable , ConcurrentHashMap對比
HashMap 線程不安全 , HashTable線程安全,但還是存在fail-fast問題 , ConcurrentHashMap線程安全,不存在fail-fast問題.
HashMap 和 ConcurrentHashMap 內部都是用 數組,鏈表 加紅黑樹來構建.(較高效) HashTable 使用數組加鏈表.
HashMap 和 ConcurrentHashMap 都是用 高位異或的哈希算法. HashTable 采用 數組長度為素數,直接取余的哈希算法.
HashMap 允許插入 null鍵值對, HashTable , ConcurrentHashMap 不允許.
結論 : 不考慮線程安全的情況下使用 HashMap, 線程安全則使用 ConcurrentHashMap.
如果知道 大概會存多少數據,指定 初始容量 會更高效, 避免擴容和重新hash映射產生的效率問題.
Set篇
Set 是沒有重復元素的單元素集合.
TreeSet 內部使用 TreeMap實現.
HashSet 內部使用 HashMap實現. 當構造參數為三個時 LinkedHashMap實現.
LinkedHashSet 繼承自 HashSet,但是都是調用 HashSet中有三個構造參數的LinkedHashMap來實現.
總結
- 上一篇： 我是如何使用python控制迅雷自动下载
- 下一篇： 害怕抑郁症？该系统通过日常交流就能判断你