關于集合的體系是每個人都應該爛熟于心的,尤其是對我們經常使用的List,Map的原理更該如此.這里我們看這張圖即可:
List、Set 是,Map 不是。Map是鍵值對映射容器,與List和Set有明顯的區別,而Set存儲的零散的元素且不允許有重復元素(數學中的集合也是如此),List是線性結構的容器,適用于按數值索引訪問元素的情形。
ArrayList 和Vector都是使用數組方式存儲數據,此數組元素數大于實際存儲的數據以便增加和插入元素,它們都允許直接按序號索引元素,但是插入元素要涉及數組元素移動等內存操作,所以索引數據快而插入數據慢。Vector中的方法由于添加了synchronized修飾,因此Vector是線程安全的容器,但性能上較ArrayList差,因此已經是Java中的遺留容器。
LinkedList使用雙向鏈表實現存儲(將內存中零散的內存單元通過附加的引用關聯起來,形成一個可以按序號索引的線性結構,這種鏈式存儲方式與數組的連續存儲方式相比,內存的利用率更高),按序號索引數據需要進行前向或后向遍歷,但是插入數據時只需要記錄本項的前后項即可,所以插入速度較快。
Vector屬于遺留容器(Java早期的版本中提供的容器,除此之外,Hashtable、Dictionary、BitSet、Stack、Properties都是遺留容器),已經不推薦使用,但是由于ArrayList和LinkedListed都是非線程安全的,如果遇到多個線程操作同一個容器的場景,則可以通過工具類Collections中的synchronizedList方法將其轉換成線程安全的容器后再使用(這是對裝潢模式的應用,將已有對象傳入另一個類的構造器中創建新的對象來增強實現)。
Collection是一個接口,它是Set、List等容器的父接口;Collections是個一個工具類,提供了一系列的靜態方法來輔助容器操作,這些方法包括對容器的搜索、排序、線程安全化等等。
List以特定索引來存取元素,可以有重復元素。
Set不能存放重復元素(用對象的equals()方法來區分元素是否重復)。
Map保存鍵值對(key-value pair)映射,映射關系可以是一對一或多對一。
Set和Map容器都有基于哈希存儲和排序樹的兩種實現版本,基于哈希存儲的版本理論存取時間復雜度為O(1),而基于排序樹版本的實現在插入或刪除元素時會按照元素或元素的鍵(key)構成排序樹從而達到排序和去重的效果。
Set是最簡單的一種集合。集合中的對象不按特定的方式排序,并且沒有重復對象。
HashSet: HashSet類按照哈希算法來存取集合中的對象,存取速度比較快
TreeSet :TreeSet類實現了SortedSet接口,能夠對集合中的對象進行排序。
List的特征是其元素以線性方式存儲,集合中可以存放重復對象。
ArrayList() : 代表長度可以改變得數組??梢詫υ剡M行隨機的訪問,向ArrayList()中插入與刪除元素的速度慢。
LinkedList(): 在實現中采用鏈表數據結構。插入和刪除速度快,訪問速度慢。
PriorityQueue 是一個優先級隊列,保證最高或者最低優先級的的元素總是在隊列頭部,但是 LinkedHashMap 維持的順序是元素插入的順序。當遍歷一個 PriorityQueue 時,沒有任何順序保證,但是 LinkedHashMap 課保證遍歷順序是元素插入的順序。
WeakHashMap 的工作與正常的 HashMap 類似,但是使用弱引用作為 key,意思就是當 key 對象沒有任何引用時,key/value 將會被回收。
最明顯的區別是 ArrrayList底層的數據結構是數組,支持隨機訪問,而 LinkedList 的底層數據結構是雙向循環鏈表,不支持隨機訪問。使用下標訪問一個元素,ArrayList 的時間復雜度是 O(1),而 LinkedList 是 O(n)。
相對于ArrayList,LinkedList的插入,添加,刪除操作速度更快,因為當元素被添加到集合任意位置的時候,不需要像數組那樣重新計算大小或者是更新索引。
LinkedList比ArrayList更占內存,因為LinkedList為每一個節點存儲了兩個引用,一個指向前一個元素,一個指向下一個元素。
Array可以容納基本類型和對象,而ArrayList只能容納對象。
Array是指定大小的,而ArrayList大小是固定的
ArrayList和Vector在很多時候都很類似。
兩者都是基于索引的,內部由一個數組支持。
兩者維護插入的順序,我們可以根據插入順序來獲取元素。
ArrayList和Vector的迭代器實現都是fail-fast的。
ArrayList和Vector兩者允許null值,也可以使用索引值對元素進行隨機訪問。
以下是ArrayList和Vector的不同點。
Vector是同步的,而ArrayList不是。然而,如果你尋求在迭代的時候對列表進行改變,你應該使用CopyOnWriteArrayList。
ArrayList比Vector快,它因為有同步,不會過載。
ArrayList更加通用,因為我們可以使用Collections工具類輕易地獲取同步列表和只讀列表。
HashMap和Hashtable都實現了Map接口,因此很多特性非常相似。但是,他們有以下不同點:
HashMap允許鍵和值是null,而Hashtable不允許鍵或者值是null。
Hashtable是同步的,而HashMap不是。因此,HashMap更適合于單線程環境,而Hashtable適合于多線程環境。
HashMap提供了可供應用迭代的鍵的集合,因此,HashMap是快速失敗的。另一方面,Hashtable提供了對鍵的列舉(Enumeration)。
一般認為Hashtable是一個遺留的類。
HashSet實現了Set接口,它不允許集合中有重復的值。它存儲的是對象
HashMap實現了Map接口,Map接口對鍵值對進行映射。Map中不允許重復的鍵。Map接口有兩個基本的實現,HashMap和TreeMap。
ConcurrentHashMap對整個桶數組進行了分段,而HashMap則沒有。
ConcurrentHashMap在每一個分段上都用鎖進行保護,從而讓鎖的粒度更精細一些,并發性能更好,而HashMap沒有鎖機制,不是線程安全的。
引入ConcurrentHashMap是為了在同步集合HashTable之間有更好的選擇,HashTable與HashMap、ConcurrentHashMap主要的區別在于HashMap不是同步的、線程不安全的和不適合應用于多線程并發環境下,而ConcurrentHashMap是線程安全的集合容器,特別是在多線程和并發環境中,通常作為Map的主要實現。
Comparable 接口用于定義對象的自然順序,而 comparator 通常用于定義用戶定制的順序。Comparable 總是只有一個,但是可以有多個 comparator 來定義對象的順序。
poll() 和 remove() 都是從隊列中取出一個元素,但是 poll() 在獲取元素失敗的時候會返回空,但是 remove() 失敗的時候會拋出異常。
ArrayList 的默認大小是 10 個元素。擴容點規則是,新增的時候發現容量不夠用了,就去擴容;擴容大小規則是:擴容后的大小= 原始大小+原始大小/2 + 1。
HashMap 的默認大小是16個元素(必須是2的冪)。擴容因子默認0.75,擴容機制.(當前大小 和 當前容量 的比例超過了 擴容因子,就會擴容,擴容后大小為 一倍。例如:初始大小為 16 ,擴容因子 0.75 ,當容量為12的時候,比例已經是0.75 。觸發擴容,擴容后的大小為 32.)
LinkedList 是一個雙向鏈表,沒有初始化大小,也沒有擴容的機制,就是一直在前面或者后面新增就好。
private?static?final?int?DEFAULT_CAPACITY?=?10; //from?HashMap.java?JDK?7 static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;?//?aka?16
你可以使用有序集合,如 TreeSet 或 TreeMap,你也可以使用有順序的的集合,如 list,然后通過 Collections.sort() 來排序。
你可以使用 Arrays.toString() 和 Arrays.deepToString() 方法來打印數組。由于數組沒有實現 toString() 方法,所以如果將數組傳遞給 System.out.println() 方法,將無法打印出數組的內容,但是 Arrays.toString() 可以打印每個元素。
雙向循環列表,具體實現自行查閱源碼.
采用紅黑樹實現,具體實現自行查閱源碼.
該問題的關鍵在于面試者使用的是 ArrayList 的 remove() 還是 Iterator 的 remove()方法。這有一段示例代碼,是使用正確的方式來實現在遍歷的過程中移除元素,而不會出現 ConcurrentModificationException 異常的示例代碼。
ArrayMap是Android SDK中提供的,非Android開發者可以略過。
ArrayMap是用兩個數組來模擬map,更少的內存占用空間,更高的效率。
具體參考這篇文章:ArrayMap VS HashMap:http://lvable.com/?p=217%5D
對于在Map中插入、刪除和定位元素這類操作,HashMap是最好的選擇。然而,假如你需要對一個有序的key集合進行遍歷,TreeMap是更好的選擇?;谀愕腸ollection的大小,也許向HashMap中添加元素會更快,將map換為TreeMap進行有序key的遍歷。
HashMap概述: HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作,并允許使用null值和null鍵。此類不保證映射的順序,特別是它不保證該順序恒久不變。
HashMap的數據結構: 在java編程語言中,最基本的結構就是兩種,一個是數組,另外一個是模擬指針(引用),所有的數據結構都可以用這兩個基本結構來構造的,HashMap也不例外。HashMap實際上是一個“鏈表散列”的數據結構,即數組和鏈表的結合體。
當我們往Hashmap中put元素時,首先根據key的hashcode重新計算hash值,根絕hash值得到這個元素在數組中的位置(下標),如果該數組在該位置上已經存放了其他元素,那么在這個位置上的元素將以鏈表的形式存放,新加入的放在鏈頭,最先加入的放入鏈尾.如果數組中該位置沒有元素,就直接將該元素放到數組的該位置上.
需要注意Jdk 1.8中對HashMap的實現做了優化,當鏈表中的節點數據超過八個之后,該鏈表會轉為紅黑樹來提高查詢效率,從原來的O(n)到O(logn)
ConcurrentHashMap具體是怎么實現線程安全的呢,肯定不可能是每個方法加synchronized,那樣就變成了HashTable。
從ConcurrentHashMap代碼中可以看出,它引入了一個“分段鎖”的概念,具體可以理解為把一個大的Map拆分成N個小的HashTable,根據key.hashCode()來決定把key放到哪個HashTable中。
在ConcurrentHashMap中,就是把Map分成了N個Segment,put和get的時候,都是現根據key.hashCode()算出放到哪個Segment中。
Iterator的fail-fast屬性與當前的集合共同起作用,因此它不會受到集合中任何改動的影響。Java.util包中的所有集合類都被設計為fail->fast的,而java.util.concurrent中的集合類都為fail-safe的。當檢測到正在遍歷的集合的結構被改變時,Fail-fast迭代器拋出ConcurrentModificationException,而fail-safe迭代器從不拋出ConcurrentModificationException。
這是我在使用 Java 中 Collectionc 類的一些最佳實踐:
使用正確的集合類,例如,如果不需要同步列表,使用 ArrayList 而不是 Vector。
優先使用并發集合,而不是對集合進行同步。并發集合提供更好的可擴展性。
使用接口代表和訪問集合,如使用List存儲 ArrayList,使用 Map 存儲 HashMap 等等。
使用迭代器來循環集合。
使用集合的時候使用泛型。
Java.util.concurrent.BlockingQueue是一個隊列,在進行檢索或移除一個元素的時候,它會等待隊列變為非空;當在添加一個元素時,它會等待隊列中的可用空間。BlockingQueue接口是Java集合框架的一部分,主要用于實現生產者-消費者模式。我們不需要擔心等待生產者有可用的空間,或消費者有可用的對象,因為它都在BlockingQueue的實現類中被處理了。Java提供了集中BlockingQueue的實現,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue
棧和隊列兩者都被用來預存儲數據。java.util.Queue是一個接口,它的實現類在Java并發包中。隊列允許先進先出(FIFO)檢索元素,但并非總是這樣。Deque接口允許從兩端檢索元素。
棧與隊列很相似,但它允許對元素進行后進先出(LIFO)進行檢索。
Stack是一個擴展自Vector的類,而Queue是一個接口。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。