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