Java中的集合類:有 Map 和 Collection 兩個接口。
Collection 接口的實現(xiàn)類是單個集合。而 Map 是鍵值對的形式。
1.ArrayList 與 LinkedList
ArrayList 底層是 Object 數(shù)組,默認長度是 10,以 1.5 倍擴容。對于數(shù)組,可以通過索引查找元素,而添加 和 刪除元素,需要 把該位置之后的元素挨個賦值,效率低。要注意它有個 remove(Object o)方法,會從頭到尾遍歷,刪除第一次出現(xiàn)的元素,還有個 remove(int index),刪除指定下標的元素。如果是整型數(shù)組,要刪除指定元素需要將傳入的參數(shù)轉(zhuǎn)化成 Integer 類型,否則會被作為下標對待。
LinkedList 是雙向鏈表,不存在容量和擴容,它的空間消耗體現(xiàn)在 前驅(qū)節(jié)點 和 后繼節(jié)點。對于鏈表,查找元素效率比較低,根據(jù)長度和下標的關(guān)系,從頭或從尾遍歷鏈表,而添加 和 刪除效率較高。
2.ArrayList 與 Vector
Vector 默認長度也是 10,擴容時可以指定容量增長因子,默認擴容是 2 倍。
ArrayList 是線程不安全的,而 Vector 使用 synchronized 保證線程安全。
3.ArrayList 線程不安全的體現(xiàn)
比如說現(xiàn)在數(shù)組容量是 9,添加元素前會使用 ensureCapacityInternal(size+1),線程 A 先判斷不需要擴容,接下來 線程 B 添加了一個元素,這時數(shù)組容量變?yōu)?10,然后 CPU 切換回線程 A,而線程 A 之前判斷過不需要擴容,就會向數(shù)組添加新元素,就會拋出 ArrayIndexOutofBounds 異常。
再有:添加元素時,檢查完容量之后, elementData[size]=e; size++;比如說 size=8,如果線程 A 先 element[8]賦值,接下來 CPU 時間片切換到 線程 B,線程 B 給 elementData[8] 賦值,這樣會導(dǎo)致 [8] 被重復(fù)賦值了,而 [9]沒有被賦值,size 變?yōu)?10。
4.HashMap
以 key-value 形式存儲元素,底層是 Node 類型的數(shù)組,每個Node 是鏈表,鏈表長度達到 8 會轉(zhuǎn)化成紅黑樹。根據(jù)給定的 key,會調(diào)用本地方法 HashCode ,為不同的對象求得不同的整數(shù)值,這個值會與它右移 16 位的值相與,增加隨機性。然后對數(shù)組長度取余,為方便計算,數(shù)組長度總是 2 的冪次方,取余操作就優(yōu)化成 &(數(shù)組長度-1),可求得 key 對應(yīng)的下標,如果下標對應(yīng)的元素是 null,就直接賦值,如果不為 null,就通過 hashCode() 和 equals()比較 key 值是否重復(fù),不重復(fù)的話會尾插鏈表,否則會覆蓋舊值,并返回舊值。數(shù)組達到閾值會以 2 倍擴容,閾值是數(shù)組容量 * 負載因子,默認情況下是 16 * 0.75。
tableSizeFor()方法:
實現(xiàn)求 比指定數(shù)字大的 最小的 2 的倍數(shù)。
需要把最高位的 1 后面的位都變成 1 ,然后+1。 依次無符號右移 1,2,4,8,16,而且每次會進行 或 運算。最后給結(jié)果 +1 即可得到 比它大的 最小的 2 的倍數(shù)。
如果一開始已經(jīng)是 偶數(shù),就需要 先給數(shù)字 -1。
put()方法:
首先會看原來數(shù)組是否為null,是的話會調(diào)用 resize() 方法。
resize()方法:
除了擴容之外,還會將原來數(shù)組中的元素遷移到擴容后的數(shù)組中。
如果原來數(shù)組沒有鏈鏈表,遷移時會根據(jù)新數(shù)組的長度重新計算下標。
如果原來數(shù)組鏈的是紅黑樹,會調(diào)用紅黑樹的方法 split()。
如果原來數(shù)組鏈的是鏈表,會使用 HashCode 與 舊容量 相與,如果結(jié)果是 0 ,說明到新數(shù)組中下標不變;如果 是 1,說明到新數(shù)組的下標值是原下標值+原數(shù)組長度,會為 下標不改變的元素 和 下標要改變的元素 分別生成兩個鏈表,依次鏈到新數(shù)組中。
5.HashSet為什么不會重復(fù):
HashSet 底層有個 HashMap,而 HashSet 的 add() 方法返回值是 put(e,PRESENT)==null,PRESENT 是一個固定的 Object 類型的常量 。
添加元素時,如果根據(jù) key 值求得的下標,如果下標處是 null,就會把添加的元素作為 key值,把 PRESENT 作為 value,返回 null,那么對應(yīng)的 add() 方法返回值是 true,添加成功;否則說明元素重復(fù),還是以 PRESENT 作為value 覆蓋,返回的是原值 PRESENT,而對應(yīng) add()方法的返回值是 false,添加失敗,只會有一個元素,不允許重復(fù)。
6.紅黑樹
是一個二叉搜索樹。滿足 5 個條件:
(1)每個節(jié)點不是紅色,就是黑色。
(2)根節(jié)點必須是黑色。
(3)紅黑樹的葉子節(jié)點( null 節(jié)點)必須是黑色。
(4)紅色節(jié)點的兩個子樹必須是黑色。
(5)任意節(jié)點到葉子節(jié)點的路徑中 黑色節(jié)點的個數(shù)相同(這個意義上來說是平衡的)。