[Java]集合的小抄 Java初学者必备
生活随笔
收集整理的這篇文章主要介紹了
[Java]集合的小抄 Java初学者必备
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 【背景】
- Collections
- List
- ArrayList
- 優勢操作
- 劣勢操作
- LinkedList
- 優勢
- 劣勢
- 最基本的兩種檢索集合中的所有對象的方法：
- CopyOnWriteArrayList
- 補充說明
- Stack
- Map
- Map 的常用方法：
- HashMap
- LinkedHashMap
- TreeMap
- ConcurrentHashMap
- ConcurrentSkipListMap
- 補充說明
- 關于null
- Set
- Set接口主要實現了兩個實現類：
- 補充說明
- Queue
- 注意
- LinkedList
- ArrayDeque
- PriorityQueue
- ConcurrentLinkedQueue/ConcurrentLinkedDeque
- PriorityBlockingQueue
- DelayQueue
- ArrayBlockingQueue
- LinkedBlockingQueue/LinkedBlockingDeque
- SynchronousQueue
- 補充說明
【背景】
在盡可能短的篇幅里，將所有集合與并發集合的特征，實現方式，性能捋一遍。適合所有”精通Java”其實還不那么自信的人閱讀。
Collections
Set 和List 都繼承了Conllection,Map沒有
Collection接口的方法：
- boolean add(Object o) :向集合中加入一個對象的引用
- void clear() :刪除集合中所有的對象，即不再持有這些對象的引用
- boolean isEmpty() :判斷集合是否為空
- boolean contains(Object o): 判斷集合中是否持有特定對象的引用
- Iterartor iterator() : 返回一個Iterator對象，可以用來遍歷集合中的元素
- boolean remove(Object o):從集合中刪除一個對象的引用
- int size() :返回集合中元素的數目
- Object[] toArray() :返回一個數組，該數組中包括集合中的所有元素
- 關于：Iterator() 和toArray() 方法都用于集合的所有的元素，前者返回一個Iterator對象，后者返回一個包含集合中所有元素的數組。
Iterator接口聲明了如下方法: - hasNext(): 判斷集合中元素是否遍歷完畢，如果沒有，就返回true
- next() :返回下一個元素
- remove():從集合中刪除上一個有next()方法返回的元素。
Set 的 add()方法是如何判斷對象是否已經存放在集合中？
List
- List的特征是其元素以線性方式存儲,集合中可以存放重復對象。
ArrayList
- 以數組實現。節約空間，但數組有容量限制。
- 超出限制時會增加50%容量，默認第一次插入元素時創建大小為10的數組。
優勢操作
- get(i)/set(i,e) 訪問
- add(e) 末尾插入
劣勢操作
System.arraycopy()來移動部分受影響的元素，性能變差
- add–add(i,e) 按下標插入
- add(i,e), remove(i), remove(e) 刪除元素
LinkedList
- 以雙向鏈表實現,鏈表無容量限制
- 雙向鏈表本身使用了更多空間，需要額外的鏈表指針操作
優勢
在鏈表兩頭的操作能省掉指針的移動
- add()
- addFirst()
- removeLast()
- iterator()上的remove()
劣勢
- 按下標訪問元素–get(i)/set(i,e) 要遍歷鏈表將指針移動到位(如果i>數組大小的一半，會從末尾移起)
- 插入、刪除元素時修改前后節點的指針即可，仍要遍歷部分鏈表的指針才能移動到下標所指的位置
最基本的兩種檢索集合中的所有對象的方法：
1: 用for循環和get()方法：for(int i=0; i<list.size();i++){System.out.println(list.get(i));}2: 使用 迭代器（Iterator）:Iterator it=list.iterator();while(it.hashNext){System.out.println(it.next);}CopyOnWriteArrayList
- 支持讀多寫少的并發情況
-增加了addIfAbsent(e)方法，會遍歷數組來檢查元素是否已存在，性能可想像的不太好 - 如果更新頻率較高，或數組較大時使用Collections.synchronizedList(list)，對所有操作用同一把鎖來保證線程安全更好
補充說明
- 按值返回下標–contains(e), indexOf(e), remove(e) 都需遍歷所有元素進行比較，性能可想像的不太好
- 沒有按元素值排序的SortedList，在線程安全類中也沒有無鎖算法的ConcurrentLinkedList，湊合著用Set與Queue中的等價類時，會缺少一些List特有的方法
Stack
- Stack 的常用方法：
Map
- Map 是一種把鍵對象和值對象映射的集合，它的每一個元素都包含一對鍵對象和值對象,鍵對象不允許重復。
- Map沒有繼承于Collection接口
- 從Map集合中檢索元素時，只要給出鍵對象，就會返回對應的值對象。
Map 的常用方法：
1 添加，刪除操作：Object put(Object key, Object value): 向集合中加入元素Object remove(Object key): 刪除與KEY相關的元素void putAll(Map t): 將來自特定映像的所有元素添加給該映像void clear(): 從映像中刪除所有映射2 查詢操作：Object get(Object key): 獲得與關鍵字key相關的值HashMap
- 以Entry[]數組實現的哈希桶數組，用Key的哈希值取模桶數組的大小可得到數組下標
- 插入元素時，如果兩條Key落在同一個桶(如哈希值1和17取模16后都屬于第一個哈希桶)。Entry用一個next屬性實現多個Entry以單向鏈表存放，后入桶的Entry將next指向桶當前的Entry
- 查找key時(如哈希值為17的)，先定位到第一個哈希桶，然后以鏈表遍歷桶里所有元素，逐個比較其key值
- 當Entry數量達到桶數量的**75%**時(很多文章說使用的桶數量達到了75%，但看代碼不是)，會成倍擴容桶數組，并重新分配所有原來的Entry
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把寫鎖(可以設置更多)，有效分散了阻塞的概率，而且沒有讀鎖（因為put/remove動作是個原子動作(比如put是一個對數組元素/Entry 指針的賦值操作)，讀操作不會看到一個更新動作的中間狀態）
- 數據結構為Segment[]，Segment里面才是哈希桶數組，每個Segment一把鎖。Key先算出它在哪個Segment里，再算出它在哪個哈希桶里
- 支持ConcurrentMap接口，如putIfAbsent(key，value)與相反的replace(key，value)與以及實現CAS的replace(key, oldValue, newValue)
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對每個對象只接受一次，并使用自己內部的排序方法
- Set幾乎都是內部用一個Map來實現, 因為Map里的KeySet就是一個Set，而value是假值，全部使用同一個Object。
- Set的特征也繼承了那些內部Map實現的特征。
Set接口主要實現了兩個實現類：
- HashSet : HashSet類按照哈希算法來存取集合中的對象，存取速度比較快,內部是HashMap
- TreeSet : TreeSet類實現了SortedSet接口，能夠對集合中的對象進行排序。
- LinkedHashSet：內部是LinkedHashMap。
- ConcurrentSkipListSet：內部是ConcurrentSkipListMap的并發優化的SortedSet。
- CopyOnWriteArraySet：內部是CopyOnWriteArrayList的并發優化的Set，利用其addIfAbsent()方法實現元素去重，如前所述該方法的性能很一般。
補充說明
- 好像少了個ConcurrentHashSet，本來也該有一個內部用ConcurrentHashMap的簡單實現，但JDK偏偏沒提供。Jetty就自己封了一個，Guava則直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 實現
Jetty 是一個開源的servlet容器，它為基于Java的web容器
Guava是一種基于開源的Java庫,谷歌很多項目使用它的很多核心庫
Queue
Queue是在兩端出入的List，所以也可以用數組或鏈表來實現。
- add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
- remove 移除并返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
- element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
- offer 添加一個元素并返回true 如果隊列已滿，則返回false
- poll 移除并返問隊列頭部的元素 如果隊列為空，則返回null
- peek 返回隊列頭部的元素 如果隊列為空，則返回null
- put 添加一個元素 如果隊列滿，則阻塞
- take 移除并返回隊列頭部的元素 如果隊列為空，則阻塞
注意
-
remove、element、offer 、poll、peek 其實是屬于Queue接口。
-
add remove element操作在隊滿或者隊空的時候會報異常。
-
offer poll peek 在隊滿或者隊空的時候不會報異常。
-
put take操作屬于阻塞操作。隊滿隊空均會阻塞。
–普通隊列–
LinkedList
- 以雙向鏈表實現的LinkedList既是List，也是Queue。
- 它是唯一一個允許放入null的Queue。
ArrayDeque
以循環數組實現的雙向Queue。大小是2的倍數，默認是16。
普通數組只能快速在末尾添加元素，為了支持FIFO，從數組頭快速取出元素，就需要使用循環數組n有隊頭隊尾兩個下標：
- 彈出元素時，隊頭下標遞增；
- 加入元素時，如果已到數組空間的末尾，則將元素循環賦值到數組0，同時隊尾下標指向0，再插入下一個元素則賦值到數組[1]，隊尾下標指向1。
- 如果隊尾的下標追上隊頭，說明數組所有空間已用完，進行雙倍的數組擴容。
PriorityQueue
- PriorityQueue 類實質上維護了一個有序列表。加入到 Queue 中的元素根據它們的天然排序（通過其 java.util.Comparable 實現）或者根據傳遞給構造函數的 java.util.Comparator 實現來定位。
- 用二叉堆實現的優先級隊列，詳見入門教程
- 不再是FIFO而是按元素實現的Comparable接口或傳入Comparator的比較結果來出隊，數值越小，優先級越高，越先出隊
- 注意其iterator()的返回不會排序。
–線程安全的隊列–
ConcurrentLinkedQueue/ConcurrentLinkedDeque
-
ConcurrentLinkedQueue 是基于鏈接節點的、線程安全的隊列。并發訪問不需要同步。因為它在隊列的尾部添加元素并從頭部刪除它們，所以只要不需要知道隊列的大 小，
-
ConcurrentLinkedQueue 對公共集合的共享訪問就可以工作得很好。收集關于隊列大小的信息會很慢，需要遍歷隊列。
-
無界的并發優化的Queue，基于鏈表，實現了依賴于CAS的無鎖算法。
-
ConcurrentLinkedQueue的結構是單向鏈表和head/tail兩個指針，因為入隊時需要修改隊尾元素的next指針，以及修改tail指向新入隊的元素兩個CAS動作無法原子，所以需要的特殊的算法，篇幅所限見入門教程。
–線程安全的阻塞隊列–
- BlockingQueue的隊列長度受限，用以保證生產者與消費者的速度不會相差太遠，避免內存耗盡
- 隊列長度設定后不可改變
- 當入隊時隊列已滿，或出隊時隊列已空，不同函數的效果見下表：
PriorityBlockingQueue
- 一個由優先級堆支持的無界優先級隊列。（無容量限制）
- 無界的并發優化的PriorityQueue，也是基于二叉堆。
- 使用一把公共的讀寫鎖。雖然實現了BlockingQueue接口，其實沒有任何阻塞隊列的特征，空間不夠時會自動擴容。
DelayQueue
- 一個由優先級堆支持的、基于時間的調度隊列。
- 內部包含一個PriorityQueue，同樣是無界的。
- 元素需實現Delayed接口，每次調用時需返回當前離觸發時間還有多久，小于0表示該觸發了。
- pull()時會用peek()查看隊頭的元素，檢查是否到達觸發時間。ScheduledThreadPoolExecutor用了類似的結構。
- 一個存放Delayed 元素的無界阻塞隊列，只有在延遲期滿時才能從中提取元素。該隊列的頭部是延遲期滿后保存時間最長的 Delayed 元素。如果延遲都還沒有期滿，則隊列沒有頭部，并且poll將返回null。當一個元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一個小于或等于零的值時，則出現期滿，poll就以移除這個元素了。此隊列不允許使用 null 元素。
ArrayBlockingQueue
- 一個由數組支持的有界隊列（指定容量）
- 定長的并發優化的BlockingQueue，基于循環數組實現。
- 有一把公共的讀寫鎖與notFull、notEmpty兩個Condition管理隊列滿或空時的阻塞狀態。
- 可以選擇是否需要公平性，如果公平參數被設置true，等待時間最長的線程會優先得到處理（其實就是通過將ReentrantLock設置為true來 達到這種公平性的：即等待時間最長的線程會先操作）。通常，公平性會使你在性能上付出代價，只有在的確非常需要的時候再使用它。它是基于數組的阻塞循環隊 列，此隊列按 FIFO（先進先出）原則對元素進行排序。
LinkedBlockingQueue/LinkedBlockingDeque
- 一個由鏈接節點支持的可選有界隊列。
- 可選定長的并發優化的BlockingQueue，基于鏈表實現，所以可以把長度設為Integer.MAX_VALUE。
- 利用鏈表的特征，分離了takeLock與putLock兩把鎖，繼續用notEmpty、notFull管理隊列滿或空時的阻塞狀態。
SynchronousQueue
- 一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制
補充說明
JDK7有個LinkedTransferQueue，transfer(e)方法保證Producer放入的元素，被Consumer取走了再返回，比SynchronousQueue更好，有空要學習下。
來源：http://www.topthink.com/topic/11679.html
參考文章：https://blog.csdn.net/imbingoer/article/details/85886312
參考文章：https://blog.csdn.net/imbingoer/article/details/85884474
總結
以上是生活随笔為你收集整理的[Java]集合的小抄 Java初学者必备的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： hibernate（nested tra
- 下一篇： 云智推任务提交版拉新系统源码-任务分销系