集合有兩個分支,一是Collection? ?另一個是Map

Collection的子類有Set ,? List??

List:
?----arrayList? 底層通過數(shù)組實現(xiàn), 帶索引,但是一旦改動數(shù)據(jù)就會使數(shù)據(jù)重新排序,所以優(yōu)點是查詢快,缺點是增刪慢
-----linkedLIst 底層通過鏈表實現(xiàn),通過下標實現(xiàn)排序,優(yōu)缺點正好與arraylist相反
-----vector 線程安全的集合

(ArrayList 補充) : arraylist 初始長度默認是10 , 每次擴容默認擴原來的1.5倍
(linkedLIst? 補充):? ? ?

? ? ? ? linkedList底層是雙向鏈表,每一個元素都有三部分,頭,中,尾? .? ?頭指向上一個元素,尾部指向下一個元素,頭指向為空的元素,就是第一個元素,尾部指向元素為空的,就是最后一個元素,

? ? ? ? 增刪快的原因: 刪除元素后,只需要改變上一個元素的尾部指向,跟下一個元素的頭部指向,不需要移動鏈表

? ? ? ? 查詢慢的原因: 鏈表要查詢某個位置上的元素,需要通過下標一個個找,效率低下.

Set: hashSet底層實際就是一個HashMap,通過hashmap的key值不能重復的特點實現(xiàn)set的元素唯一性,map的value值存的都是new Object();

? ? ? ? treeSet: treeSet底層就是一個treeMap;

Map

HashMap?HashMap 的優(yōu)點是 :結合了arraylist跟linkedList的優(yōu)點,既查詢快,增刪也快

實現(xiàn)原理 : hashmap是基于哈希表實現(xiàn)的。如上圖, map在調用put的時候,會將key的哈希碼取出,將key進行算法運算后分配到entry[] 數(shù)組中相應的位置, 如:HashMap默認長度為16(當使用量達到75%時,會進行擴容到原來的兩倍),索引值為hashCode%16的方式(效率最低的算法是hashCode/hashCode, 即退化成一個單向鏈表),當確定索引后,會將數(shù)據(jù)以鏈表形式存入數(shù)組,(? ?hash|key |? value |? next? ? ?) , jdk8以后,當鏈表長度大于8,會轉換為紅黑樹,進而增加查詢效率

取數(shù)據(jù)的實現(xiàn)如下圖

HashTable: hashTable 基本與hashMap相似,但是hashTable是線程安全的,效率較低,并且hashTable是不允許key跟value為null的

TreeMap: treeMap是基于紅黑二叉樹實現(xiàn)的,是可排序的map集合,如果是對象需要排序,對象需要實現(xiàn)Comparable接口,并重寫 CompartTo方法實現(xiàn)排序