資訊專欄INFORMATION COLUMN
摘要：訪問順序調(diào)用過訪問的元素會放到鏈尾，迭代會從鏈?zhǔn)组_始插入順序按插入順序迭代出來內(nèi)部是基于紅黑樹實現(xiàn)的，并且默認(rèn)會通過按照類型進(jìn)行自然排序。
對于常用的集合大家都不陌生，但是深入到內(nèi)部原理可能都是一知半解，通過閱讀源碼理解如下。
ArrayListArrayList內(nèi)部就是一個默認(rèn)大小為10的動態(tài)對象數(shù)組容器，每當(dāng)add一個新數(shù)據(jù)的時候，如果大于原來的容器大小，則會通過Arrays.copyOf把容器大小增加到原來的1.5倍，以此類推。當(dāng)可以預(yù)知數(shù)據(jù)大小，可以通過initialCapacity來默認(rèn)設(shè)置動態(tài)數(shù)據(jù)的大小，減少擴(kuò)容帶來的資源消耗。
時間復(fù)雜度：
get() - 直接讀取下標(biāo) - O(1)
add(E) - 直接在后面添加 - O(1)
add(idnex, E) - 插入數(shù)據(jù)后需要移動后面的數(shù)據(jù) - O(n)
remove(index) - 刪除后需要移動 - O(n)
LinkedList內(nèi)部是一個雙向鏈表，add新數(shù)據(jù)的時候，其實就是調(diào)用linklast在鏈表尾部插入數(shù)據(jù)。刪除的時候直接找到對應(yīng)數(shù)據(jù)，替換掉鏈表的前后節(jié)點即可。
時間復(fù)雜度：
get() - 需要遍歷 - O(n)
add(E) - 調(diào)用linklast直接添加在最后 - O(1)
add(index, E) - 需要先查找到原來index位置的數(shù)據(jù)，再重新指定鏈表前后的數(shù)據(jù) - O(n)
remove() - 直接調(diào)用removeLast刪除最后數(shù)據(jù) - O(1)
remove(index) - 需要先查找到原來index位置的數(shù)據(jù) - O(n)
HashMap內(nèi)部其實是一個數(shù)組，每個數(shù)組下是一個單向鏈表。HashMap中的數(shù)組是一個取名為Entry的類，類包含(key, value, next)這幾個屬性。存放規(guī)則為，數(shù)組下標(biāo)按hash(key)%len獲得，取得數(shù)組后則查找對應(yīng)數(shù)組的值。HashMap還有個負(fù)載因子（默認(rèn)0.75），當(dāng)里面數(shù)組填滿了75%的時候，會進(jìn)行擴(kuò)展到原來大小的2倍。
那么問題來了，如果在put的時候，取到hash(key)%len的值相等時不就沖突了？
HashMap的處理方法是：原來有一個Entry[0] = A，此時來一個index也是0的B，則會把Entry[0] = B，B.next = A，又來一個C的時候，則會把Entry[0] = C，C.next = B，以此類推。這樣Entry就會形成一個鏈表，取的時候則是遍歷鏈表取值。
這里需要提到的是，使用hashMap的時候，引入的key對象必須重寫hashCode()和equal()兩個函數(shù)，原因可以參考源碼判斷條件(if (e.hash == hash && ((k = e.key) == key || key.equals(k))))，如果hashCode()沒重寫，則壓根找不到對應(yīng)數(shù)組，如果equal()沒重寫，則無法判斷key值的內(nèi)容是否相等。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null總是放在數(shù)組的第一個鏈表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//遍歷鏈表
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//如果key在鏈表中已存在，則替換為新value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
補充：
在Java 8之后hashmap進(jìn)行了優(yōu)化：由于單向鏈表的查詢時間復(fù)雜度為O(n)，在極端情況下(每次都查找)可能存在性能問題，于是Java 8針對鏈表長度大于8的情況會使用時間復(fù)雜度為O(log n)的紅黑樹進(jìn)行存儲來提升存儲查詢的效率，時間復(fù)雜度就從原來的O(1)+O(n)變成了O(1)+O(log n)，優(yōu)化了極端情況導(dǎo)致的性能問題。
LinkedHashMap內(nèi)部雙向鏈表和HashMap的結(jié)合，支持多種迭代順序，默認(rèn)按插入順序，也可以按訪問順序。
訪問順序（accessOrder=true）：調(diào)用過get訪問的元素會放到鏈尾，迭代會從鏈?zhǔn)组_始
插入順序（accessOrder=false）：按插入順序迭代出來
TreeMap內(nèi)部是基于紅黑樹實現(xiàn)的，并且默認(rèn)會通過compareTo按照key類型進(jìn)行自然排序。TreeSet的底層是TreeMap。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69866.html
摘要：原文地址游客前言金三銀四，很多同學(xué)心里大概都準(zhǔn)備著年后找工作或者跳槽。最近有很多同學(xué)都在交流群里求大廠面試題。 最近整理了一波面試題，包括安卓JAVA方面的，目前大廠還是以安卓源碼，算法，以及數(shù)據(jù)結(jié)構(gòu)為主，有一些中小型公司也會問到混合開發(fā)的知識，至于我為什么傾向于混合開發(fā)，我的一句話就是走上編程之路，將來你要學(xué)不僅僅是這些，豐富自己方能與世接軌，做好全棧的裝備。 原文地址：游客kutd...
摘要：百度網(wǎng)盤提取碼一面試題熟練掌握是很關(guān)鍵的，大公司不僅僅要求你會使用幾個，更多的是要你熟悉源碼實現(xiàn)原理，甚至要你知道有哪些不足，怎么改進(jìn)，還有一些有關(guān)的一些算法，設(shè)計模式等等。 ??百度網(wǎng)盤??提取碼：u6C4?一、java面試題熟練掌握java是很關(guān)鍵的，大公司不僅僅要求你會使用幾個api，更多的是要你熟悉源碼實現(xiàn)原理，甚...
摘要：基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識點總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時間和時間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對象鎖和類鎖的區(qū)別，，優(yōu)缺點及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
摘要：基礎(chǔ)問題的的性能及原理之區(qū)別詳解備忘筆記深入理解流水線抽象關(guān)鍵字修飾符知識點總結(jié)必看篇中的關(guān)鍵字解析回調(diào)機(jī)制解讀抽象類與三大特征時間和時間戳的相互轉(zhuǎn)換為什么要使用內(nèi)部類對象鎖和類鎖的區(qū)別，，優(yōu)缺點及比較提高篇八詳解內(nèi)部類單例模式和 Java基礎(chǔ)問題 String的+的性能及原理 java之yield(),sleep(),wait()區(qū)別詳解-備忘筆記 深入理解Java Stream流水...
閱讀 1819·2019-08-30 13:54
閱讀 2734·2019-08-29 17:27
閱讀 1123·2019-08-29 17:23
閱讀 3357·2019-08-29 15:20
閱讀 1234·2019-08-29 11:28
閱讀 1577·2019-08-26 10:39
閱讀 1324·2019-08-26 10:29
閱讀 649·2019-08-26 10:13
