Java基礎(chǔ)-集合
Java基礎(chǔ)-集合
List
ArrayList
ArrayList?的底層是數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。與 Java 中的數(shù)組相比，它的容量能動(dòng)態(tài)增長(zhǎng)。在添加大量元素前，應(yīng)用程序可以使用ensureCapacity操作來(lái)增加?ArrayList?實(shí)例的容量。這可以減少遞增式再分配的數(shù)量。
ArrayList繼承于?AbstractList?，實(shí)現(xiàn)了?List,?RandomAccess,?Cloneable,?java.io.Serializable?這些接口。
RandomAccess?是一個(gè)標(biāo)志接口，表明實(shí)現(xiàn)這個(gè)這個(gè)接口的 List 集合是支持快速隨機(jī)訪(fǎng)問(wèn)的。在?ArrayList?中，我們即可以通過(guò)元素的序號(hào)快速獲取元素對(duì)象，這就是快速隨機(jī)訪(fǎng)問(wèn)。ArrayList?實(shí)現(xiàn)了?Cloneable?接口?，即覆蓋了函數(shù)clone()，能被克隆。ArrayList?實(shí)現(xiàn)了?java.io.Serializable?接口，這意味著ArrayList支持序列化，能通過(guò)序列化去傳輸。
與Vector的區(qū)別
ArrayList?是?List?的主要實(shí)現(xiàn)類(lèi)，底層使用?Object[ ]存儲(chǔ)，適用于頻繁的查找工作，線(xiàn)程不安全 ；Vector?是?List?的古老實(shí)現(xiàn)類(lèi)，底層使用?Object[ ]存儲(chǔ)，線(xiàn)程安全的。
與LinkedList區(qū)別
是否保證線(xiàn)程安全：?
ArrayList?和?LinkedList?都是不同步的，也就是不保證線(xiàn)程安全；底層數(shù)據(jù)結(jié)構(gòu)：?
Arraylist?底層使用的是?Object?數(shù)組；LinkedList?底層使用的是?雙向鏈表?數(shù)據(jù)結(jié)構(gòu)（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別，下面有介紹到?。?/p>插入和刪除是否受元素位置的影響：?①?
ArrayList?采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。?比如：執(zhí)行add(E e)方法的時(shí)候，?ArrayList?會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話(huà)（add(int index, E element)）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。 ②?LinkedList?采用鏈表存儲(chǔ)，所以對(duì)于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，近似 O(1)，如果是要在指定位置i插入和刪除元素的話(huà)（(add(int index, E element)） 時(shí)間復(fù)雜度近似為o(n))因?yàn)樾枰纫苿?dòng)到指定位置再插入。是否支持快速隨機(jī)訪(fǎng)問(wèn)：?
LinkedList?不支持高效的隨機(jī)元素訪(fǎng)問(wèn)，而?ArrayList?支持。快速隨機(jī)訪(fǎng)問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于get(int index)方法)。內(nèi)存空間占用：?
ArrayList?的空 間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而?LinkedList?的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比?ArrayList?更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。
擴(kuò)容機(jī)制
JDK8）ArrayList 有三種方式來(lái)初始化，構(gòu)造方法源碼如下：
細(xì)心的同學(xué)一定會(huì)發(fā)現(xiàn) ：以無(wú)參數(shù)構(gòu)造方法創(chuàng)建 ArrayList 時(shí)，實(shí)際上初始化賦值的是一個(gè)空數(shù)組。當(dāng)真正對(duì)數(shù)組進(jìn)行添加元素操作時(shí)，才真正分配容量。即向數(shù)組中添加第一個(gè)元素時(shí)，數(shù)組容量擴(kuò)為 10。?下面在我們分析 ArrayList 擴(kuò)容時(shí)會(huì)講到這一點(diǎn)內(nèi)容！
補(bǔ)充：JDK7 new無(wú)參構(gòu)造的ArrayList對(duì)象時(shí)，直接創(chuàng)建了長(zhǎng)度是10的Object[]數(shù)組elementData 。jdk7中的ArrayList的對(duì)象的創(chuàng)建類(lèi)似于單例的餓漢式，而jdk8中的ArrayList的對(duì)象的創(chuàng)建類(lèi)似于單例的懶漢式。JDK8的內(nèi)存優(yōu)化也值得我們?cè)谄綍r(shí)開(kāi)發(fā)中學(xué)習(xí)。
當(dāng)我們要 add 進(jìn)第 1 個(gè)元素到 ArrayList 時(shí)，elementData.length 為 0 （因?yàn)檫€是一個(gè)空的 list），因?yàn)閳?zhí)行了?
ensureCapacityInternal()?方法 ，所以 minCapacity 此時(shí)為 10。此時(shí)，minCapacity - elementData.length > 0成立，所以會(huì)進(jìn)入?grow(minCapacity)?方法。當(dāng) add 第 2 個(gè)元素時(shí)，minCapacity 為 2，此時(shí) e lementData.length(容量)在添加第一個(gè)元素后擴(kuò)容成 10 了。此時(shí)，
minCapacity - elementData.length > 0?不成立，所以不會(huì)進(jìn)入 （執(zhí)行）grow(minCapacity)?方法。添加第 3、4···到第 10 個(gè)元素時(shí)，依然不會(huì)執(zhí)行 grow 方法，數(shù)組容量都為 10。
直到添加第 11 個(gè)元素，minCapacity(為 11)比 elementData.length（為 10）要大。進(jìn)入 grow 方法進(jìn)行擴(kuò)容。
grow()方法
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉?lái)的 1.5 倍左右（oldCapacity 為偶數(shù)就是 1.5 倍，否則是 1.5 倍左右）！?奇偶不同，比如 ：10+10/2 = 15, 33+33/2=49。如果是奇數(shù)的話(huà)會(huì)丟掉小數(shù).
“>>”（移位運(yùn)算符）：>>1 右移一位相當(dāng)于除 2，右移 n 位相當(dāng)于除以 2 的 n 次方。這里 oldCapacity 明顯右移了 1 位所以相當(dāng)于 oldCapacity /2。對(duì)于大數(shù)據(jù)的 2 進(jìn)制運(yùn)算,位移運(yùn)算符比那些普通運(yùn)算符的運(yùn)算要快很多,因?yàn)槌绦騼H僅移動(dòng)一下而已,不去計(jì)算,這樣提高了效率,節(jié)省了資源
我們?cè)賮?lái)通過(guò)例子探究一下grow()?方法 ：
當(dāng) add 第 1 個(gè)元素時(shí)，oldCapacity 為 0，經(jīng)比較后第一個(gè) if 判斷成立，newCapacity = minCapacity(為 10)。但是第二個(gè) if 判斷不會(huì)成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，則不會(huì)進(jìn)入?
hugeCapacity?方法。數(shù)組容量為 10，add 方法中 return true,size 增為 1。當(dāng) add 第 11 個(gè)元素進(jìn)入 grow 方法時(shí)，newCapacity 為 15，比 minCapacity（為 11）大，第一個(gè) if 判斷不成立。新容量沒(méi)有大于數(shù)組最大 size，不會(huì)進(jìn)入 hugeCapacity 方法。數(shù)組容量擴(kuò)為 15，add 方法中 return true,size 增為 11。
以此類(lèi)推······
這里補(bǔ)充一點(diǎn)比較重要，但是容易被忽視掉的知識(shí)點(diǎn)：
java 中的?
length屬性是針對(duì)數(shù)組說(shuō)的,比如說(shuō)你聲明了一個(gè)數(shù)組,想知道這個(gè)數(shù)組的長(zhǎng)度則用到了 length 這個(gè)屬性.java 中的?
length()?方法是針對(duì)字符串說(shuō)的,如果想看這個(gè)字符串的長(zhǎng)度則用到?length()?這個(gè)方法.java 中的?
size()?方法是針對(duì)泛型集合說(shuō)的,如果想看這個(gè)泛型有多少個(gè)元素,就調(diào)用此方法來(lái)查看!
LinkedList
LinkedList是一個(gè)實(shí)現(xiàn)了List接口和Deque接口的雙端鏈表。 LinkedList底層的鏈表結(jié)構(gòu)使它支持高效的插入和刪除操作，另外它實(shí)現(xiàn)了Deque接口，使得LinkedList類(lèi)也具有隊(duì)列的特性; LinkedList不是線(xiàn)程安全的，如果想使LinkedList變成線(xiàn)程安全的，可以調(diào)用靜態(tài)類(lèi)Collections類(lèi)中的synchronizedList方法：
如下圖所示：
看完了圖之后，我們?cè)倏碙inkedList類(lèi)中的一個(gè)
內(nèi)部私有類(lèi)Node
就很好理解了：
這個(gè)類(lèi)就代表雙端鏈表的節(jié)點(diǎn)Node。這個(gè)類(lèi)有三個(gè)屬性，分別是前驅(qū)節(jié)點(diǎn)，本節(jié)點(diǎn)的值，后繼結(jié)點(diǎn)。
HashMap
HashMap 主要用來(lái)存放鍵值對(duì)，它基于哈希表的Map接口實(shí)現(xiàn)，是常用的Java集合之一。
JDK1.8 之前 HashMap 由 數(shù)組+鏈表 組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8 以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為 8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)（將鏈表轉(zhuǎn)換成紅黑樹(shù)前會(huì)判斷，如果當(dāng)前數(shù)組的長(zhǎng)度小于 64，那么會(huì)選擇先進(jìn)行數(shù)組擴(kuò)容，而不是轉(zhuǎn)換為紅黑樹(shù)），以減少搜索時(shí)間，具體可以參考?treeifyBin方法。
底層結(jié)構(gòu)
1.8前
JDK1.8 之前 HashMap 底層是?數(shù)組和鏈表?結(jié)合在一起使用也就是?鏈表散列。HashMap 通過(guò) key 的 hashCode 經(jīng)過(guò)擾動(dòng)函數(shù)處理過(guò)后得到 hash 值，然后通過(guò)?(n - 1) & hash?判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話(huà)，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話(huà)，直接覆蓋，不相同就通過(guò)拉鏈法解決沖突。
所謂擾動(dòng)函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動(dòng)函數(shù)是為了防止一些實(shí)現(xiàn)比較差的 hashCode() 方法 換句話(huà)說(shuō)使用擾動(dòng)函數(shù)之后可以減少碰撞。
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡(jiǎn)化，但是原理不變。
對(duì)比一下 JDK1.7的 HashMap 的 hash 方法源碼.
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了 4 次。
所謂?“拉鏈法”?就是：將鏈表和數(shù)組相結(jié)合。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。
1.8后
相比于之前的版本，jdk1.8在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。
類(lèi)的屬性：
loadFactor加載因子
loadFactor加載因子是控制數(shù)組存放數(shù)據(jù)的疏密程度，loadFactor越趨近于1，那么 數(shù)組中存放的數(shù)據(jù)(entry)也就越多，也就越密，也就是會(huì)讓鏈表的長(zhǎng)度增加，loadFactor越小，也就是趨近于0，數(shù)組中存放的數(shù)據(jù)(entry)也就越少，也就越稀疏。
loadFactor太大導(dǎo)致查找元素效率低，太小導(dǎo)致數(shù)組的利用率低，存放的數(shù)據(jù)會(huì)很分散。loadFactor的默認(rèn)值為0.75f是官方給出的一個(gè)比較好的臨界值。
給定的默認(rèn)容量為 16，負(fù)載因子為 0.75。Map 在使用過(guò)程中不斷的往里面存放數(shù)據(jù)，當(dāng)數(shù)量達(dá)到了 16 * 0.75 = 12 就需要將當(dāng)前 16 的容量進(jìn)行擴(kuò)容，而擴(kuò)容這個(gè)過(guò)程涉及到 rehash、復(fù)制數(shù)據(jù)等操作，所以非常消耗性能。
threshold
threshold = capacity \ loadFactor*，當(dāng)Size>=threshold的時(shí)候，那么就要考慮對(duì)數(shù)組的擴(kuò)增了，也就是說(shuō)，這個(gè)的意思就是?衡量數(shù)組是否需要擴(kuò)增的一個(gè)標(biāo)準(zhǔn)。
put方法（擴(kuò)容）
HashMap只提供了put用于添加元素，putVal方法只是給put方法調(diào)用的一個(gè)方法，并沒(méi)有提供給用戶(hù)使用。
對(duì)putVal方法添加元素的分析如下：
①如果定位到的數(shù)組位置沒(méi)有元素 就直接插入。
②如果定位到的數(shù)組位置有元素就和要插入的key比較，如果key相同就直接覆蓋，如果key不相同，就判斷p是否是一個(gè)樹(shù)節(jié)點(diǎn)，如果是就調(diào)用
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value)將元素添加進(jìn)入。如果不是就遍歷鏈表插入(插入的是鏈表尾部)。
ps:下圖有一個(gè)小問(wèn)題，來(lái)自 issue#608指出：直接覆蓋之后應(yīng)該就會(huì) return，不會(huì)有后續(xù)操作。參考 JDK8 HashMap.java 658 行。
我們?cè)賮?lái)對(duì)比一下 JDK1.7 put方法的代碼
對(duì)于put方法的分析如下：
①如果定位到的數(shù)組位置沒(méi)有元素 就直接插入。
②如果定位到的數(shù)組位置有元素，遍歷以這個(gè)元素為頭結(jié)點(diǎn)的鏈表，依次和插入的key比較，如果key相同就直接覆蓋，不同就采用頭插法插入元素。
resize方法
進(jìn)行擴(kuò)容，會(huì)伴隨著一次重新hash分配，并且會(huì)遍歷hash表中所有的元素，是非常耗時(shí)的。在編寫(xiě)程序中，要盡量避免resize。
作者:Honesty
鏈接:https://blog.hehouhui.cn/archives/44.html
聲明:本文采用 CC BY-NC-SA 4.0 許可協(xié)議，轉(zhuǎn)載請(qǐng)注明出處。
