單列集合Collection分為list集合和set集合

list集合分為ArrayList和LinkedList

ArrayList--底層數據結構是數組

1.通過索引查詢快

2.增刪要重構索引,增刪慢 ??

LinkedList--底層數據結構是鏈表

1.無索引查詢慢

2.通過改變前節點的尾指針和后節點的前指針指向可快速增刪,增刪快

set集合(不可重復，沒有索引，迭代器遍歷)分為HashSet和TreeSet

HashSet存儲數據原理-數組加鏈表/數組加紅黑樹,數組內存連續查詢效率高，鏈表內存分散增刪改效率高，哈希表的默認長度是16，超過這個長度時開始進行擴容(數組長度乘2),當鏈表節點個數大于8時鏈表會轉化為紅黑樹,哈希表采用此種存儲數據的形式極大的提高操作數據的效率

1.存儲數據時會先操作(元素值作Key)key調用.hashcode（）方法得出hash值，然后再通過哈希算法轉換成數組的一個下標，對應的就是在數組上的的存儲位置。

2.如果該位置沒有數據，則直接存儲。如果該位置有數據，則會發生數據碰撞。數據碰撞的時候遍歷該位置上鏈表中的所有數據，并且通過equals()方法來比對每個數據的key。如果key相同的話，會將鏈表上該位置的數據進行覆蓋。如果key不相同的話，在JDK1.8之前是實行的頭插法，數據存儲在鏈表頭部，1.8之后實行的是尾插法數據存儲在鏈表尾部。

3.JDK1.8之后，當鏈表上的節點個數（數據個數）大于等于8時并且數組長度不小于64的時候，鏈表數據結構自動進行樹化轉化成紅黑樹，當鏈表上的數據小于等于6時，又會自動退化成鏈表,當鏈表上的數據大于64時會進行擴容

TreeSet存儲數據原理-紅黑樹

紅黑樹是一種自平衡二叉查找樹，它具有以下特點：

1.紅黑樹規則

每個節點要么是紅色，要么是黑色。

根節點是黑色的。

所有葉子節點（NULL節點）是黑色的。

如果一個節點是紅色的，那么它的子節點必須是黑色的。

從根節點到每個葉子節點的路徑上，黑色節點的數量相同。

2.紅黑樹添加節點規則

紅黑樹添加節點默認是紅色的，添加的是根節點自動變黑。添加的是非根節點位置看父節點，父黑，不操作，父紅，叔紅，父叔變黑，祖父變紅，若祖父為根節點，變黑。添加的是非根節點位置看父節點，父黑，不操作，父紅，叔黑，父變黑，祖父變紅，以祖父為節點進行旋轉平衡二叉樹要通過選擇保持平衡，增刪效率低，紅黑樹不用通過大量的旋轉來維持平衡，所以增加了增刪效率

雙列集合Map

1.HashMap存儲數據原理-數組加鏈表/數組加紅黑樹

2.TreeMap存儲數據原理-紅黑樹