集合類存放在java.util包中，主要有三種：set（集），list（列表包括Queue）和map（映射）。
Collection：Collection是集合List、Set、Queue的最基本的接口。
Iterator：迭代器，可以通過迭代器遍歷集合中的數(shù)據(jù)。
Map：是映射表的基礎接口 。
ArrayList內(nèi)部是通過數(shù)組實現(xiàn)的，它允許對元素進行快速隨機訪問。
缺點是每個元素之間不能有間隔，當數(shù)組大小不滿足時需要增加存儲能力，就要將已經(jīng)有數(shù)組的數(shù)據(jù)復制到新的存儲空間中。當從 ArrayList 的中間位置插入或者刪除元素時，需要對數(shù)組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
LinkedList是用鏈表結構存儲數(shù)據(jù)的，很適合數(shù)據(jù)的動態(tài)插入和刪除，隨機訪問和遍歷速度比較慢。另外，它還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
HashMap根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。
HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有線程安全的能力，或者使用 ConcurrentHashMap。
HashMap里面是一個數(shù)組，然后數(shù)組中每個元素是一個單向鏈表。上圖中，每個綠色的實體是嵌套類Entry 的實例，Entry包含四個屬性：key, value, hash值和用于單向鏈表的next。
capacity：當前數(shù)組容量，始終保持 2^n，可以擴容，擴容后數(shù)組大小為當前的 2 倍。
loadFactor：負載因子，默認為 0.75。
threshold：擴容的閾值，等于capacity * loadFactor 。
Java 8 對 HashMap 進行了一些修改，最大的不同就是利用了紅黑樹，所以其由數(shù)組+鏈表+紅黑樹組成。
根據(jù) Java 7 HashMap 的介紹，我們知道，查找的時候，根據(jù) hash 值我們能夠快速定位到數(shù)組的 具體下標，但是之后的話，需要順著鏈表一個個比較下去才能找到我們需要的，時間復雜度取決于鏈表的長度，為 O(n)。為了降低這部分的開銷，在Java8 中，當鏈表中的元素超過了8個以后， 會將鏈表轉換為紅黑樹，在這些位置進行查找的時候可以降低時間復雜度為 O(log N)。
