JAVA容器相關(guān)知識點整理

簡介

  1. 整理容器的基本知識
  2. 整理關(guān)于不同容器線程安全方面的知識

根據(jù)以下資料整理

http://www.itdecent.cn/p/047e33fdefd2
http://blog.csdn.net/jiyiqinlovexx/article/details/51030720

常用容器關(guān)系圖

快速了解

Collection（接口）
  1. 代表的是單個元素對象的序列，（可以有序/無序，可重復(fù)/不可重復(fù) 等，具體依據(jù)具體的子接口Set，List，Queue等）；
  2. 調(diào)用toArray(T[] a)可以轉(zhuǎn)為數(shù)組
  3. 區(qū)別于java.util.Collections:Collections是一個正對于Conllection的工具類，提供了許多實用的靜態(tài)方法
Map（接口）
  1. 代表的是“鍵值對”對象的集合（同樣可以有序/無序 等依據(jù)具體實現(xiàn)）
  2. 提供了三種遍歷方式：
  3. Set<K> keySet(): 返回所有key的Set集合
  4. Collection<V> values(): 返回所有values的集合
  5. Set< Map.Entry< K, V>> entrySet()： 是將整個Entry對象（也就是返回鍵-值形式的集合）作為元素返回所有的數(shù)據(jù)，這種方式比先通過keySet()獲取所有key再根據(jù)key獲取值效率要高
List（Collection的子接口）
  1. 一個有序的Collection（或者叫做序列）。使用這個接口可以精確掌控元素的插入，還可以根據(jù)index獲取相應(yīng)位置的元素。
  2. 可重復(fù)
  3. 有順序
  4. 提供了特殊的iterator遍歷器，叫做ListIterator。這種遍歷器允許遍歷時插入，替換，刪除，雙向訪問。 并且還有一個重載方法允許從一個指定位置開始遍歷。
ArrayList（List接口的實現(xiàn)）
  1. ArrayList是一個實現(xiàn)了List接口的可變數(shù)組
  2. 可以插入null
  3. 它的size, isEmpty, get, set, iterator,add這些方法的時間復(fù)雜度是O(1),如果add n個數(shù)據(jù)則時間復(fù)雜度是O(n).
  4. ArrayList不是synchronized的。
LinkedList（List接口的實現(xiàn)）
  1. LinkedList是一個鏈表維護的序列容器。和ArrayList都是序列容器，一個使用數(shù)組存儲，一個使用鏈表存儲。
  2. 數(shù)組和鏈表2種數(shù)據(jù)結(jié)構(gòu)的對比：
  3. 查找方面。數(shù)組的效率更高，可以直接索引出查找，而鏈表必須從頭查找。
  4. 插入刪除方面。特別是在中間進行插入刪除，這時候鏈表體現(xiàn)出了極大的便利性，只需要在插入或者刪除的地方斷掉鏈然后插入或者移除元素，然后再將前后鏈重新組裝，但是數(shù)組必須重新復(fù)制一份將所有數(shù)據(jù)后移或者前移。
  5. 在內(nèi)存申請方面，當(dāng)數(shù)組達到初始的申請長度后，需要重新申請一個更大的數(shù)組然后把數(shù)據(jù)遷移過去才行（所以當(dāng)創(chuàng)建ArrayList，最好能給一個合理的初始大小）。而鏈表只需要動態(tài)創(chuàng)建即可。
  6. LinkedList還實現(xiàn)了Deque接口，Deque接口是繼承Queue的。所以LinkedList還支持隊列的pop，push，peek操作
mark
Set（Collection的子接口）
  1. 存儲不重復(fù)的元素集合
HashSet（Set接口的實現(xiàn)）
  1. 基于HashMap進行存儲（所以所有的add，remove等操作其實都是HashMap的add、remove操作。遍歷操作其實就是HashMap的keySet的遍歷）
  2. 不保證順序，且不保證下次遍歷的順序和之前一樣
  3. 允許null元素
LinkedHashSet（Set接口的實現(xiàn)）
  1. 基于LinkedHashMap
  2. 相對于HashSet來說就是一個可以保持順序的Set集合
TreeSet（Set接口的實現(xiàn)）
  1. 基于TreeMap
  2. TreeSet內(nèi)的元素必須實現(xiàn)Comparable接口
  3. 一組有次序的集合，如果沒有指定排序規(guī)則Comparator，則會按照自然排序。（自然排序即e1.compareTo(e2) == 0作為比較）
mark
Queue（Collection的子接口）
Map
HashMap
  1. 最基礎(chǔ)最常用的一種Map，它無序，以散列表的方式進行存儲
LinkedHashMap
  1. 相對于HashMap來說區(qū)別是，LinkedHashMap遍歷的時候具有順序，可以保存插入的順序，（還可以設(shè)置最近訪問的元素也放在前面，即LRU）
  2. 其實LinkedHashMap的存儲還是跟HashMap一樣，采用哈希表方法存儲，只不過LinkedHashMap多維護了一份head，tail鏈表。
TreeMap
  1. TreeMap平時用的不多，TreeMap會實現(xiàn)SortMap接口，定義一個排序規(guī)則，這樣當(dāng)遍歷TreeMap的時候，會根據(jù)規(guī)定的排序規(guī)則返回元素。
WeakHashMap
  1. 特點是，當(dāng)除了自身有對key的引用外，此key沒有其他引用那么此map會自動丟棄此值
mark

以上，感謝http://www.itdecent.cn/p/047e33fdefd2 ，如有冒犯，請聯(lián)系我刪除

關(guān)于容器的線程安全

同步容器類

JDK1.0開始有兩個很老的同步容器類：Vector和HashTable
JDK1.2之后Collections工具類中添加了一些工廠方法返回類似的同步封裝器類：
Collections.synchronizedXXX(XXX xxx)

實現(xiàn)方式：

將它們的狀態(tài)封裝起來，并對每一個公有方法進行同步。
其中Vector就是Object[]+synchronized方法，Hashtable是HashtableEntry[]+synchronized方法。而synchronizedXXX()方法返回的同步封裝器類更是簡單地將傳進來的Collection的所有方法封裝為synchronized方法而已。

缺點：
  1. 通過同步方法將訪問操作串行化，導(dǎo)致并發(fā)環(huán)境下效率低下
  1. 復(fù)合操作（迭代、條件運算如沒有則添加等）非線程安全，需要客戶端代碼來實現(xiàn)加鎖。
并發(fā)容器類

并發(fā)容器出現(xiàn)的最大的需求就是提升同步容器類的性能！
可以對比（非并發(fā)容器類）看看，將單線程版本和并發(fā)版本做一個比較。

HashMap和HashSet的并發(fā)版本

  1. ConcurrentHashMap<K, V>（HashMap的并發(fā)版本）
    版本：JDK5
    目標(biāo)：代替Hashtable、synchronizedMap，支持復(fù)合操作
    原理：采用一種更加細粒度的加鎖機制“分段鎖”，任意數(shù)量讀取線程可以并發(fā)讀取，任意數(shù)量的讀取線程和一個寫線程可以并發(fā)訪問，一定數(shù)量的寫入線程可以并發(fā)訪問。并發(fā)環(huán)境下ConcurrentHashMap帶來了更高的吞吐量，而在單線程環(huán)境下只損失了很小的性能。

  2. CopyOnWriteArraySet<E>（HashSet的并發(fā)版本）
    版本：JDK5
    目標(biāo)：代替synchronizedSet
    原理：CopyOnWriteArraySet基于CopyOnWriteArrayList實現(xiàn)，其唯一的不同是在add時調(diào)用的是CopyOnWriteArrayList的addIfAbsent方法，其遍歷當(dāng)前Object數(shù)組，如Object數(shù)組中已有了當(dāng)前元素，則直接返回，如果沒有則放入Object數(shù)組的尾部，并返回。

TreeMap和TreeSet的并發(fā)版本

  1. ConcurrentSkipListMap<K, V>（TreeMap的并發(fā)版本）
    版本：JDK6
    目標(biāo)：代替synchronizedSortedMap(TreeMap)
    原理：Skip list（跳表）是一種可以代替平衡樹的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)是按照Key值升序的。Skip list讓已排序的數(shù)據(jù)分布在多層鏈表中，以0-1隨機數(shù)決定一個數(shù)據(jù)的向上攀升與否，通過"空間來換取時間"的一個算法。ConcurrentSkipListMap提供了一種線程安全的并發(fā)訪問的排序映射表。內(nèi)部是SkipList（跳表）結(jié)構(gòu)實現(xiàn)，在理論上能夠在O（log（n））時間內(nèi)完成查找、插入、刪除操作。

  2. ConcurrentSkipListSet<E>（TreeSet的并發(fā)版本）
    版本：JDK6
    目標(biāo)：代替synchronizedSortedSet
    原理：內(nèi)部基于ConcurrentSkipListMap實現(xiàn)！

ArrayList和LinkedList的并發(fā)版本

  1. CopyOnWriteArrayList<E>（ArrayList的并發(fā)版本）
    目標(biāo)：代替Vector、synchronizedList
    原理：CopyOnWriteArrayList的核心思想是利用高并發(fā)往往是讀多寫少的特性，對讀操作不加鎖，對寫操作，先復(fù)制一份新的集合，在新的集合上面修改，然后將新集合賦值給舊的引用，并通過volatile 保證其可見性，當(dāng)然寫操作的鎖是必不可少的了。

  2. ConcurrentLinkedQueue<E>（LinkedList的并發(fā)版本）
    目標(biāo)：代替Vector、synchronizedList
    特點：基于鏈表實現(xiàn)的FIFO隊列，特別注意單線程環(huán)境中LinkedList除了可以用作鏈表，也可用作隊列，并發(fā)版本也一樣

阻塞隊列：BlockingQueue

版本：JDK1.5
特點：拓展了Queue，增加了可阻塞的插入和獲取等操作
實現(xiàn)類
LinkedBlockingQueue：基于鏈表實現(xiàn)的可阻塞的FIFO隊列
ArrayBlockingQueue：基于數(shù)組實現(xiàn)的可阻塞的FIFO隊列
PriorityBlockingQueue：按優(yōu)先級排序的隊列
原理：通過ReentrantLock實現(xiàn)線程安全，通過Condition實現(xiàn)阻塞和喚醒。

以上，感謝http://blog.csdn.net/jiyiqinlovexx/article/details/51030720 ，如有冒犯，請聯(lián)系我刪除

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Java SE 基礎(chǔ)： 封裝、繼承、多態(tài) 封裝： 概念：就是把對象的屬性和操作（或服務(wù)）結(jié)合為一個獨立的整體，并盡...
    Jayden_Cao閱讀 2,234評論 0贊 8
  • java基礎(chǔ) 集合承繼包含圖 Collection vs Collections 首先，"Collection" ...
    onlyHalfSoul閱讀 1,427評論 0贊 5
  • Java集合類可用于存儲數(shù)量不等的對象,并可以實現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)如棧,隊列等,Java集合還可以用于保存具有映射關(guān)...
    小徐andorid閱讀 2,079評論 0贊 13
  • List： 1.可以允許重復(fù)的對象。 2.可以插入多個null元素。 3.是一個有序容器，保持了每個元素的插入順序...
    雪飄千里閱讀 256評論 0贊 1
  • 本系列出于AWeiLoveAndroid的分享，在此感謝，再結(jié)合自身經(jīng)驗查漏補缺，完善答案。以成系統(tǒng)。 Java基...
    濟公大將閱讀 1,610評論 1贊 6

友情鏈接更多精彩內(nèi)容