首頁»Java WEB»Java集合的小抄 Java初學者必備

Java集合的小抄 Java初學者必備

來源:花錢的年華 的博客 發布時間:2015-07-08 閱讀次數:

  在盡可能短的篇幅里,將所有集合與并發集合的特征,實現方式,性能捋一遍。適合所有"精通Java"其實還不那么自信的人閱讀。

 List

  ArrayList

  以數組實現。節約空間,但數組有容量限制。超出限制時會增加50%容量,用System.arraycopy()復制到新的數組,因此最好能給出數組大小的預估值。默認第一次插入元素時創建大小為10的數組。

  按數組下標訪問元素--get(i)/set(i,e) 的性能很高,這是數組的基本優勢。

  直接在數組末尾加入元素--add(e)的性能也高,但如果按下標插入、刪除元素--add(i,e), remove(i), remove(e),則要用System.arraycopy()來移動部分受影響的元素,性能就變差了,這是基本劣勢。

  LinkedList

  以雙向鏈表實現。鏈表無容量限制,但雙向鏈表本身使用了更多空間,也需要額外的鏈表指針操作。

  按下標訪問元素--get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動到位(如果i>數組大小的一半,會從末尾移起)。

  插入、刪除元素時修改前后節點的指針即可,但還是要遍歷部分鏈表的指針才能移動到下標所指的位置,只有在鏈表兩頭的操作--add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指針的移動。

  CopyOnWriteArrayList

  并發優化的ArrayList。用CopyOnWrite策略,在修改時先復制一個快照來修改,改完再讓內部指針指向新數組。

  因為對快照的修改對讀操作來說不可見,所以只有寫鎖沒有讀鎖,加上復制的昂貴成本,典型的適合讀多寫少的場景。如果更新頻率較高,或數組較大時,還是Collections.synchronizedList(list),對所有操作用同一把鎖來保證線程安全更好。

  增加了addIfAbsent(e)方法,會遍歷數組來檢查元素是否已存在,性能可想像的不會太好。

  補充

  無論哪種實現,按值返回下標--contains(e), indexOf(e), remove(e) 都需遍歷所有元素進行比較,性能可想像的不會太好。

  沒有按元素值排序的SortedList,在線程安全類中也沒有無鎖算法的ConcurrentLinkedList,湊合著用Set與Queue中的等價類時,會缺少一些List特有的方法。

 Map

  HashMap

  以Entry[]數組實現的哈希桶數組,用Key的哈希值取模桶數組的大小可得到數組下標。

  插入元素時,如果兩條Key落在同一個桶(比如哈希值1和17取模16后都屬于第一個哈希桶),Entry用一個next屬性實現多個Entry以單向鏈表存放,后入桶的Entry將next指向桶當前的Entry。

  查找哈希值為17的key時,先定位到第一個哈希桶,然后以鏈表遍歷桶里所有元素,逐個比較其key值。

  當Entry數量達到桶數量的75%時(很多文章說使用的桶數量達到了75%,但看代碼不是),會成倍擴容桶數組,并重新分配所有原來的Entry,所以這里也最好有個預估值。

  取模用位運算(hash & (arrayLength-1))會比較快,所以數組的大小永遠是2的N次方, 你隨便給一個初始值比如17會轉為32。默認第一次放入元素時的初始值是16。

  iterator()時順著哈希桶數組來遍歷,看起來是個亂序。

  在JDK8里,新增默認為8的閥值,當一個桶里的Entry超過閥值,就不以單向鏈表而以紅黑樹來存放以加快Key的查找速度。

  LinkedHashMap

  擴展HashMap增加雙向鏈表的實現,號稱是最占內存的數據結構。支持iterator()時按Entry的插入順序來排序(但是更新不算, 如果設置accessOrder屬性為true,則所有讀寫訪問都算)。

  實現上是在Entry上再增加屬性before/after指針,插入時把自己加到Header Entry的前面去。如果所有讀寫訪問都要排序,還要把前后Entry的before/after拼接起來以在鏈表中刪除掉自己。

  TreeMap

  以紅黑樹實現,篇幅所限詳見入門教程。支持iterator()時按Key值排序,可按實現了Comparable接口的Key的升序排序,或由傳入的Comparator控制。可想象的,在樹上插入/刪除元素的代價一定比HashMap的大。

  支持SortedMap接口,如firstKey(),lastKey()取得最大最小的key,或sub(fromKey, toKey), tailMap(fromKey)剪取Map的某一段。

  ConcurrentHashMap

  并發優化的HashMap,默認16把寫鎖(可以設置更多),有效分散了阻塞的概率,而且沒有讀鎖。

  數據結構為Segment[],Segment里面才是哈希桶數組,每個Segment一把鎖。Key先算出它在哪個Segment里,再算出它在哪個哈希桶里。

  支持ConcurrentMap接口,如putIfAbsent(key,value)與相反的replace(key,value)與以及實現CAS的replace(key, oldValue, newValue)。

  沒有讀鎖是因為put/remove動作是個原子動作(比如put是一個對數組元素/Entry 指針的賦值操作),讀操作不會看到一個更新動作的中間狀態。

  ConcurrentSkipListMap

  JDK6新增的并發優化的SortedMap,以SkipList實現。SkipList是紅黑樹的一種簡化替代方案,是個流行的有序集合算法,篇幅所限見入門教程。Concurrent包選用它是因為它支持基于CAS的無鎖算法,而紅黑樹則沒有好的無鎖算法。

  很特殊的,它的size()不能隨便調,會遍歷來統計。

  補充

  關于null,HashMap和LinkedHashMap是隨意的,TreeMap沒有設置Comparator時key不能為null;ConcurrentHashMap在JDK7里value不能為null(這是為什么呢?),JDK8里key與value都不能為null;ConcurrentSkipListMap是所有JDK里key與value都不能為null。

 Set

  Set幾乎都是內部用一個Map來實現, 因為Map里的KeySet就是一個Set,而value是假值,全部使用同一個Object。Set的特征也繼承了那些內部Map實現的特征。

  HashSet:內部是HashMap。

  LinkedHashSet:內部是LinkedHashMap。

  TreeSet:內部是TreeMap的SortedSet。

  ConcurrentSkipListSet:內部是ConcurrentSkipListMap的并發優化的SortedSet。

  CopyOnWriteArraySet:內部是CopyOnWriteArrayList的并發優化的Set,利用其addIfAbsent()方法實現元素去重,如前所述該方法的性能很一般。

  補充:好像少了個ConcurrentHashSet,本來也該有一個內部用ConcurrentHashMap的簡單實現,但JDK偏偏沒提供。Jetty就自己封了一個,Guava則直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 實現。

 Queue

  Queue是在兩端出入的List,所以也可以用數組或鏈表來實現。

  --普通隊列--

  LinkedList

  是的,以雙向鏈表實現的LinkedList既是List,也是Queue。它是唯一一個允許放入null的Queue。

  ArrayDeque

  以循環數組實現的雙向Queue。大小是2的倍數,默認是16。

  普通數組只能快速在末尾添加元素,為了支持FIFO,從數組頭快速取出元素,就需要使用循環數組:有隊頭隊尾兩個下標:彈出元素時,隊頭下標遞增;加入元素時,如果已到數組空間的末尾,則將元素循環賦值到數組[0](如果此時隊頭下標大于0,說明隊頭彈出過元素,有空位),同時隊尾下標指向0,再插入下一個元素則賦值到數組[1],隊尾下標指向1。如果隊尾的下標追上隊頭,說明數組所有空間已用完,進行雙倍的數組擴容。

  PriorityQueue

  用二叉堆實現的優先級隊列,詳見入門教程,不再是FIFO而是按元素實現的Comparable接口或傳入Comparator的比較結果來出隊,數值越小,優先級越高,越先出隊。但是注意其iterator()的返回不會排序。

  --線程安全的隊列--

  ConcurrentLinkedQueue/ConcurrentLinkedDeque

  有暗香盈袖界的并發優化的Queue,基于鏈表,實現了依賴于CAS的無鎖算法。

  ConcurrentLinkedQueue的結構是單向鏈表和head/tail兩個指針,因為入隊時需要修改隊尾元素的next指針,以及修改tail指向新入隊的元素兩個CAS動作無法原子,所以需要的特殊的算法,篇幅所限見入門教程

  PriorityBlockingQueue

  有暗香盈袖界的并發優化的PriorityQueue,也是基于二叉堆。使用一把公共的讀寫鎖。雖然實現了BlockingQueue接口,其實沒有任何阻塞隊列的特征,空間不夠時會自動擴容。

  DelayQueue

  內部包含一個PriorityQueue,同樣是無有暗香盈袖界的。元素需實現Delayed接口,每次調用時需返回當前離觸發時間還有多久,小于0表示該觸發了。
pull()時會用peek()查看隊頭的元素,檢查是否到達觸發時間。ScheduledThreadPoolExecutor用了類似的結構。

  --線程安全的阻塞隊列--

  BlockingQueue的隊列長度受限,用以保證生產者與消費者的速度不會相差太遠,避免內存耗盡。隊列長度設定后不可改變。當入隊時隊列已滿,或出隊時隊列已空,不同函數的效果見下表:

  可能報異常 返回布爾值 可能阻塞等待 可設定等待時間
入隊 add(e) offer(e) put(e) offer(e, timeout, unit)
出隊 remove() poll() take() poll(timeout, unit)
查看 element() peek()

  ArrayBlockingQueue

  定長的并發優化的BlockingQueue,基于循環數組實現。有一把公共的讀寫鎖與notFull、notEmpty兩個Condition管理隊列滿或空時的阻塞狀態。

  LinkedBlockingQueue/LinkedBlockingDeque

  可選定長的并發優化的BlockingQueue,基于鏈表實現,所以可以把長度設為Integer.MAX_VALUE。利用鏈表的特征,分離了takeLock與putLock兩把鎖,繼續用notEmpty、notFull管理隊列滿或空時的阻塞狀態。

  補充

  JDK7有個LinkedTransferQueue,transfer(e)方法保證Producer放入的元素,被Consumer取走了再返回,比SynchronousQueue更好,有空要學習下。

QQ群:WEB開發者官方群(515171538),驗證消息:10000
微信群:加小編微信 849023636 邀請您加入,驗證消息:10000
提示:更多精彩內容關注微信公眾號:全棧開發者中心(fsder-com)
網友評論(共0條評論) 正在載入評論......
理智評論文明上網,拒絕惡意謾罵 發表評論 / 共0條評論
登錄會員中心
6十1选号器