HashMap

1.7中的HashMap

負(fù)載因子: 給定默認(rèn)容量為16 負(fù)載因子為0.75

• Map在使用過程中不斷的往里面存放元素 當(dāng)數(shù)量達(dá)到16*0.75=12時(shí) 就需要將當(dāng)前的默認(rèn)容量擴(kuò)容 而擴(kuò)容的過程設(shè)計(jì)reHash 復(fù)制數(shù)組等操作,非常損耗性能
• 建議提前預(yù)估HashMap的初始大小,盡量減少HashMap的擴(kuò)容帶來的性能損耗

其實(shí)真正存放數(shù)據(jù)的是 Entry<K,V>[] table，Entry 是 HashMap 中的一個(gè)靜態(tài)內(nèi)部類轻腺，它有key梦皮、value挠蛉、next堂湖、hash（key的hashcode）成員變量 多個(gè)Entry就構(gòu)成hashMap的數(shù)據(jù)結(jié)構(gòu) 數(shù)組+鏈表

put()

• 判斷當(dāng)前的數(shù)組是否需要初始化
• 如果Key為Null 則put一個(gè)空值進(jìn)去
• 根據(jù)key計(jì)算出hashCode
• 根據(jù)計(jì)算出來的HashCode定位出所在的數(shù)組位置(頭插法)
• 如果數(shù)組位置是一個(gè)鏈表則需要遍歷判斷里面的HashCode key 是否和傳入的相等, 如果相同就進(jìn)行覆蓋,并且返回被覆蓋的值
• 如果這個(gè)數(shù)組位置是空的,new 一個(gè)Entry對(duì)象寫入到當(dāng)前位置,(調(diào)用addEnrty 寫入Entry時(shí)需要判斷是否需要擴(kuò)容,擴(kuò)容就是2倍 并將當(dāng)前的key 重新hash并定位, 而在createEntry中將當(dāng)前位置的數(shù)組算元傳入到新建的數(shù)組位置中 如果當(dāng)前數(shù)組位置有值就會(huì)形成鏈表)

get()

• 根據(jù)計(jì)算出來的HashCode找倒對(duì)應(yīng)的HashEnrty位置 如果在數(shù)組上直接返回
• 判斷是否為鏈表 不是鏈表就根據(jù)Key .key以及HashCode 是否相等來返回
• 為鏈表的需要遍歷到key以及hashcode相等再返回
• 啥都沒有取到就返回Null

1.8中的HashMap

當(dāng)Hash沖突嚴(yán)重時(shí),在桶上形成的鏈表越來越長(zhǎng),這樣在查詢時(shí)的效率就會(huì)越來越低,時(shí)間復(fù)雜度為o(N)

TREEIFY_THRESHOLD = 8 用于判斷是否將鏈表轉(zhuǎn)為紅黑樹的閾值

桶中存放的數(shù)據(jù)結(jié)構(gòu)為Node

put()

• 判斷當(dāng)前桶是否為空 空就需要初始化(resize方法中會(huì)判斷是否進(jìn)行初始化)
• 根據(jù)當(dāng)前的key的hashcode定位到具體的桶中并且判斷桶是否為空,為空表名沒有Hash沖突直接在當(dāng)前位置新建一個(gè)桶即可
• 如果存在Hash沖突 那么就要比較桶中的key.key的hashCode與寫入的key是相等,如果相等.就賦值給e,等待循環(huán)結(jié)束后替換
• 如果當(dāng)前桶是個(gè)紅黑樹 那就要按照紅黑樹的范式寫入數(shù)據(jù)
• 如果是一個(gè)鏈表就需要將當(dāng)前的key value封裝成一個(gè)新節(jié)點(diǎn)Node寫入到當(dāng)前桶的第一個(gè)位置 (尾插法)
• 接著判斷當(dāng)前鏈表大小是否大于預(yù)設(shè)的鏈表閾值 大于就轉(zhuǎn)成紅黑樹
• 如果遍歷過程中找到key相同值時(shí)直接退出遍歷
• 如果e!=null 就相當(dāng)于存在相同的key 就替換存在的值 返回原值
• 最后判斷是否需要進(jìn)行擴(kuò)容

get()

• 根據(jù)計(jì)算出來的HashCode找倒對(duì)應(yīng)桶的位置 如果在數(shù)組上直接返回 如果為空返回null
• 如果第一個(gè)不匹配則判斷它的下一個(gè)是紅黑樹還是鏈表
• 紅黑樹就按照樹的查找方法返回
• 鏈表就需要遍歷匹配返回值

但是 HashMap 原有的問題也都存在，比如在并發(fā)場(chǎng)景下使用時(shí)容易出現(xiàn)死循環(huán)

• 在 HashMap 擴(kuò)容的時(shí)候會(huì)調(diào)用 resize() 方法侦讨，就是這里的并發(fā)操作容易在一個(gè)桶上形成環(huán)形鏈表窘面；這樣當(dāng)獲取一個(gè)不存在的 key 時(shí)，計(jì)算出的 index 正好是環(huán)形鏈表的下標(biāo)就會(huì)出現(xiàn)死循環(huán)：在 1.7 中 hash 沖突采用的頭插法形成的鏈表件相，在并發(fā)條件下會(huì)形成循環(huán)鏈表再扭，一旦有查詢落到了這個(gè)鏈表上，當(dāng)獲取不到值時(shí)就會(huì)死循環(huán)夜矗。

HashMap何時(shí)擴(kuò)容

當(dāng)向容器添加元素的時(shí)候泛范，會(huì)判斷當(dāng)前容器的元素個(gè)數(shù)，如果大于等于閾值(默認(rèn)12)---即大于當(dāng)前數(shù)組的長(zhǎng)度乘以加載因子的值的時(shí)候紊撕，就要自動(dòng)擴(kuò)容罢荡。

HashMap擴(kuò)容算法

擴(kuò)容(resize) 就是重新計(jì)算容量,數(shù)組無法自動(dòng)擴(kuò)容 方法就是使用一個(gè)新數(shù)組代替已有的容量小的數(shù)組 2倍擴(kuò)容

Hashmap如何解決散列碰撞

HashMap是利用拉鏈法 處理hashcode的碰撞問題 在調(diào)用HashMap的put或者get方法時(shí),都會(huì)調(diào)用Hashcode方法區(qū)查找相關(guān)的key 當(dāng)有沖突時(shí)在調(diào)用equals方法

HashMap基于hashing原理 通過put和get方法存取對(duì)象,當(dāng)我們將鍵值對(duì)傳遞給put方法時(shí),他調(diào)用對(duì)象的hashCode方法計(jì)算Hashcode 知道哦啊哦哈系統(tǒng)位置來存儲(chǔ)對(duì)象,當(dāng)獲取對(duì)象時(shí)，通過鍵對(duì)象的equals()方法找到正確的鍵值對(duì)对扶，然后返回值對(duì)象区赵。

HashMap使用鏈表來解決碰撞問題，當(dāng)碰撞發(fā)生了浪南，對(duì)象將會(huì)存儲(chǔ)在鏈表的下一個(gè)節(jié)點(diǎn)中笼才。hashMap在每個(gè)鏈表節(jié)點(diǎn)存儲(chǔ)鍵值對(duì)對(duì)象。當(dāng)兩個(gè)不同的鍵卻有相同的hashCode時(shí)络凿，他們會(huì)存儲(chǔ)在同一個(gè)bucket位置的鏈表中骡送。鍵對(duì)象的equals()來找到鍵值對(duì)絮记。

Hashmap底層為什么是線程不安全的摔踱？

• 并發(fā)場(chǎng)景下使用時(shí)容易出現(xiàn)死循環(huán) 在 HashMap 擴(kuò)容的時(shí)候會(huì)調(diào)用 resize() 方法，就是這里的并發(fā)操作容易在一個(gè)桶上形成環(huán)形鏈表怨愤；這樣當(dāng)獲取一個(gè)不存在的 key 時(shí)派敷，計(jì)算出的 index 正好是環(huán)形鏈表的下標(biāo)就會(huì)出現(xiàn)死循環(huán)
• 在 1.7 中 hash 沖突采用的頭插法形成的鏈表，在并發(fā)條件下會(huì)形成循環(huán)鏈表，一旦有查詢落到了這個(gè)鏈表上篮愉，當(dāng)獲取不到值時(shí)就會(huì)死循環(huán)般眉。

ConcurrentHashMap

1.7 中ConcurrentHashMap

ConcurrentHashMap在jdk1.7中使用了分段鎖,其中segment繼承于ReentranLock ,不會(huì)像HashTable那樣不管是put還是get都去做同步處理,理論上ConcurrentHashMap支持CurrencyLevel(Segment數(shù)組數(shù)量)的線程并發(fā),當(dāng)每個(gè)線程占用鎖訪問一個(gè)Segment時(shí),不會(huì)影響到其他的Segment

數(shù)據(jù)結(jié)構(gòu)和HashMap一致 數(shù)組+鏈表

分段鎖

ConcurrentHashMap里面元素存放在table數(shù)組中,分段鎖就是把這個(gè)table分成多段,每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時(shí)潜支，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)甸赃，從而可以有效的提高并發(fā)訪問效率,在ConcurrentHashMap中使用了一個(gè)包含16個(gè)鎖的數(shù)組，每個(gè)鎖保護(hù)所有散列桶的1/16冗酿，其中第N個(gè)散列桶由第（N mod 16）個(gè)鎖來保護(hù)埠对。假設(shè)使用合理的散列算法使關(guān)鍵字能夠均勻的分部，那么這大約能使對(duì)鎖的請(qǐng)求減少到越來的1/16裁替。也正是這項(xiàng)技術(shù)使得ConcurrentHashMap支持多達(dá)16個(gè)并發(fā)的寫入線程项玛。

put()

首先通過Key定位到Segment,之后再對(duì)應(yīng)的Segment中具體的put元素

• 雖然HashEntry中的Value是用Volatile關(guān)鍵字修飾,但是并不能保證并發(fā)的原子性,所以put操作時(shí)任然需要加鎖處理
• 首先第一步的時(shí)候會(huì)去嘗試獲取鎖, 如果鎖獲取失敗肯定就存在與其他線程存在競(jìng)爭(zhēng),利用scanAdnLockForPut()自選獲取鎖,如果獲取次數(shù)達(dá)到了Max_SCAN_RETRIES,則改為阻塞鎖獲取,保證能獲取鎖成功
• 將當(dāng)前的Segment中的table通過key的hashCode定位到HashEntry
• 遍歷該HashEntry 如果不為空則判斷傳入的key和當(dāng)前遍歷的Key是否相等,相等則覆蓋舊的Key
• 為空則需要新建一個(gè)HashEntry并加入到Segment中,同時(shí)還會(huì)判斷是否需要擴(kuò)容
• 最后會(huì)使用unLock解除當(dāng)前Segment的鎖

get()

• 只需要將Key通過 Hash之后定位到具體的Segment 再通過一次Hash定位到元素上
• 由于HashEntry 中的Value屬性是用Volitile 關(guān)鍵字修飾,保證了內(nèi)存的可見性,所以每次都可以實(shí)時(shí)獲取最新值
• ConCurrentHashMap的get方法是相對(duì)高效的,因?yàn)檎麄€(gè)過程不需要加鎖

1.8中的ConCurrentHashMap

在1.7中已經(jīng)解決了HashMap的并發(fā)問題 ,并且支持N個(gè)Segment這個(gè)多次數(shù)的并發(fā),但是任然存在1.7中HashMap的問題,查詢遍歷鏈表效率低, 和1.8中的HashMap結(jié)構(gòu)類似, 其中拋棄可原有的分段鎖,采用了CAS+Synchronized來保證并發(fā)的安全

CAS

如果Obj內(nèi)的Value和Expect相同 就證明沒有其他線程改變過這個(gè)變量,name就更新它為update 如果這一步的CAS沒有成功,那么就采用自選的方式繼續(xù)進(jìn)行CAS操作

對(duì)CAS的理解，CAS是一種無鎖算法弱判，CAS有3個(gè)操作數(shù)襟沮，內(nèi)存值V，舊的預(yù)期值A(chǔ)昌腰，要修改的新值B开伏。當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)，將內(nèi)存值V修改為B遭商，否則什么都不做

CAS ABA問題

• 問題描述 現(xiàn)在在對(duì)象中存入一Value A 但是另一個(gè)線程把Value的值從A改到B 又從B重新變?yōu)锳 'eg :插進(jìn)去 取出來等于沒插?'
  • 解決 目前在JDK的atomic包里提供了一個(gè)類AtomicStampedReference來解決ABA問題,這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用固灵，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等劫流，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值巫玻。
• 如果CAS不成功 則會(huì)原地自旋,時(shí)間長(zhǎng)會(huì)給CPU帶來巨大開銷
• 其實(shí)除了AtomicStampedReference類，還有一個(gè)原子類也可以解決祠汇，就是AtomicMarkableReference仍秤，它不是維護(hù)一個(gè)版本號(hào)，而是維護(hù)一個(gè)boolean類型的標(biāo)記可很，用法沒有AtomicStampedReference靈活诗力。因此也只是在特定的場(chǎng)景下使用。

數(shù)據(jù)結(jié)構(gòu)和HashMap一致 數(shù)組+鏈表+紅黑樹

put()

• 根據(jù)Key計(jì)算出HashCode
• 判斷當(dāng)前數(shù)組table是否需要初始化
• 如果當(dāng)前Key定位出的Node為空 表示可以寫入數(shù)據(jù),利用CAS嘗試寫入,失敗則自旋保證成功
• 如果當(dāng)前位置的Hashcode==MOVE==-1 則需要擴(kuò)容
• 如果都不滿足 則利用Synchronized鎖寫入數(shù)據(jù)
• 最后判斷如果數(shù)組長(zhǎng)度大于TREEIFY_THRESHOLD(8) 則要轉(zhuǎn)化成紅黑樹

get()

• 根據(jù)計(jì)算出來的HashCode找倒對(duì)應(yīng)的NodeBin位置 如果在數(shù)組上直接返回
• 如果是紅黑樹就按照數(shù)的遍歷方式來獲取
• 如果都不滿足 就按照鏈表的方式遍歷獲取值

1.8 在 1.7 的數(shù)據(jù)結(jié)構(gòu)上做了大的改動(dòng)根穷，采用紅黑樹之后可以保證查詢效率（O(logn)）姜骡，甚至取消了 ReentrantLock(可重入鎖) 改為了 synchronized(獨(dú)占鎖)，這樣可以看出在新版的 JDK 中對(duì) synchronized 優(yōu)化是很到位的屿良。

ArrayMap

ArrayMap利用兩個(gè)數(shù)組，mHashes用來保存每一個(gè)key的hash值惫周，mArrray大小為mHashes的2倍尘惧，依次保存key和value

mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;

當(dāng)插入時(shí)，根據(jù)key的hashcode()方法得到hash值递递，計(jì)算出在mArrays的index位置喷橙，然后利用二分查找找到對(duì)應(yīng)的位置進(jìn)行插入啥么，當(dāng)出現(xiàn)哈希沖突時(shí)，會(huì)在index的相鄰位置插入贰逾。

SparseArray

SparseArray比HashMap更省內(nèi)存悬荣，在某些條件下性能更好，主要是因?yàn)樗苊饬藢?duì)key的自動(dòng)裝箱（int轉(zhuǎn)為Integer類型）疙剑，它內(nèi)部則是通過兩個(gè)數(shù)組來進(jìn)行數(shù)據(jù)存儲(chǔ)的氯迂，一個(gè)存儲(chǔ)key，另外一個(gè)存儲(chǔ)value言缤，為了優(yōu)化性能嚼蚀，它內(nèi)部對(duì)數(shù)據(jù)還采取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)，從而節(jié)約內(nèi)存空間管挟，我們從源碼中可以看到key和value分別是用數(shù)組表示：

private int[] mKeys; 
private Object[] mValues;

同時(shí)轿曙，SparseArray在存儲(chǔ)和讀取數(shù)據(jù)時(shí)候，使用的是二分查找法僻孝。也就是在put添加數(shù)據(jù)的時(shí)候导帝，會(huì)使用二分查找法和之前的key比較當(dāng)前我們添加的元素的key的大小，然后按照從小到大的順序排列好穿铆，所以舟扎，SparseArray存儲(chǔ)的元素都是按元素的key值從小到大排列好的。 而在獲取數(shù)據(jù)的時(shí)候悴务，也是使用二分查找法判斷元素的位置睹限，所以，在獲取數(shù)據(jù)的時(shí)候非逞堕埽快羡疗，比HashMap快的多。

假設(shè)數(shù)據(jù)量都在千級(jí)以內(nèi)的情況下：

1. 如果key的類型已經(jīng)確定為int類型别洪，那么使用SparseArray叨恨，因?yàn)樗苊饬俗詣?dòng)裝箱的過程，

2. 如果key為long類型挖垛，它還提供了一個(gè)LongSparseArray來確保key為long類型時(shí)的使用

3. 如果key類型為其它的類型痒钝，則使用ArrayMap。