我的博客java篇-HashMap
概括
HashMap 散列表，通過數(shù)組加鏈表的形式構(gòu)成，在jdk1.8以后，當(dāng)鏈表長度大于8的時(shí)候，會轉(zhuǎn)化成紅黑樹的形式存儲。
允許null值，同時(shí)非有序，非同步(即線程不安全)
put 方法原理
- 根據(jù)
key的hasCode，通過哈希函數(shù)算出存儲位置index值。 - 如果改位置沒有元素，則直接存儲
- 如果已經(jīng)有了元素，就判斷該元素的
key值和key的hashCode是否一致，一致就直接覆蓋value - 如果不一致，就產(chǎn)生了
hash沖突，就在鏈表上插入新的結(jié)點(diǎn)存儲，如果鏈表長度大于8的話，就轉(zhuǎn)化成紅黑樹進(jìn)行存儲 - 插入后，如果數(shù)量大于閾值則進(jìn)行擴(kuò)容
get 方法原理
- 根據(jù)
key做Hash映射，得到對應(yīng)的index - 遍歷鏈表或者紅黑樹，查找
key值和key的hashCode都相等的節(jié)點(diǎn)，返回value
HashMap 的容量為什么一定要是 2 的 n 次方
HashMap的默認(rèn)初始長度是16，并且每次自動(dòng)擴(kuò)展或者手動(dòng)初始化時(shí)，長度必須為2的冪
因?yàn)闉榱俗屧啬軌蚓鶆蚍峙洌?code>HashMap需要將key映射到index
計(jì)算方法 index = key的hash值 & (Length - 1) 將key的hash值和數(shù)組的長度-1取邏輯與運(yùn)算
當(dāng)HashMap的容量為2的n次方的時(shí)候，length-1的值所有二進(jìn)制為都為1，這樣能讓index的計(jì)算結(jié)果分布更加均勻
擾動(dòng)函數(shù)（hash 函數(shù)）
在計(jì)算數(shù)組的index值的時(shí)候，并不是直接通過key的hashcode和lengh-1取邏輯與運(yùn)算的，這里有很多文章都是錯(cuò)誤的講解，需要先將hashcode通過hash函數(shù)計(jì)算出hash值，在和數(shù)組的lengh-1取邏輯與運(yùn)算
///jdk1.8源碼
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我們需要hash值是足夠散列的，這樣才能減少hash碰撞的概率
任意一個(gè)Objec類型的hashCode方法得到的hashCode值是一個(gè)int類型，有32位。
顯然很少有HashMap的數(shù)組有40億這么長。如果只是取低幾位的hash值的話，那么那些低位相同，高位不同的hash值就碰撞了，如：
/// Hash碰撞示例：
H1: 00000000 00000000 00000000 00000101 & 1111 = 0101
H2: 00000000 11111111 00000000 00000101 & 1111 = 0101
為了解決這類問題，HashMap想了一種辦法（擾動(dòng)）：將hash值的高16位右移并與原hash值取異或運(yùn)算^，混合高16位和低16位的值，得到一個(gè)更加散列的低16位的hash值。如：
00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5
00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250
這樣將hashcode通過擾動(dòng)函數(shù)生成hash值，就可以減少hash碰撞的概率了
負(fù)載因子
負(fù)載因子loadFactor表示哈希表空間的使用程度，當(dāng)size到達(dá)數(shù)組的容量*負(fù)載因子的時(shí)候，會觸發(fā)擴(kuò)容
當(dāng)負(fù)載因子越大，則HashMap的裝載程度就越高。也就是能容納更多的元素，元素多了，發(fā)生hash碰撞的幾率就會加大，從而鏈表就會拉長，此時(shí)的查詢效率就會降低。
當(dāng)負(fù)載因子越小，則鏈表中的數(shù)據(jù)量就越稀疏，此時(shí)會對空間造成浪費(fèi)，但是此時(shí)查詢效率高。
擴(kuò)容機(jī)制
條件： HashMap.Size >= Capacity * LoadFactor
步驟：
1.擴(kuò)容
創(chuàng)建一個(gè)新的Entry空數(shù)組，長度是原數(shù)組的 2 倍。
2.ReHash
遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組。為什么要重新Hash呢？因?yàn)殚L度擴(kuò)大以后，index的計(jì)算規(guī)則也會改變，需要重新計(jì)算分布
HashMap 為什么是非線程安全的
當(dāng)
a線程準(zhǔn)備插入的時(shí)候，線程阻塞，b線程插入成功，a線程繼續(xù)運(yùn)行的話，會覆蓋b線程的值ReHash在并發(fā)的情況下可能會形成鏈表環(huán)（java8之前）
頭插法和尾插法
在java8之前是頭插法，java8之后是尾插法
使用頭插法，在高并發(fā)的場景下會出現(xiàn)鏈表成環(huán)的問題
使用頭插會改變鏈表的上的順序，但是如果使用尾插，在擴(kuò)容時(shí)會保持鏈表元素原本的順序，就不會出現(xiàn)鏈表成環(huán)的問題了
為啥我們重寫 equals 方法的時(shí)候需要重寫 hashCode 方法呢
如何重寫了equals方法，會導(dǎo)致原先不相同的兩個(gè)對象，現(xiàn)在相同了，但是他們的hashcode還是不相同，違背了相同的對象返回相同的 hash 值，不同的對象返回不同的 hash 值的設(shè)計(jì)初衷
使用HashMap時(shí)，謹(jǐn)慎使用可變對象作為key鍵
如果key對象是可變的，那么key的哈希值就可能改變。在HashMap中可變對象作為Key會造成數(shù)據(jù)丟失。因?yàn)槲覀冊龠M(jìn)行hash & (length - 1)取模運(yùn)算計(jì)算位置查找對應(yīng)元素時(shí)，位置可能已經(jīng)發(fā)生改變，導(dǎo)致數(shù)據(jù)丟失
最好選擇不可變對象作為key。例如String，Integer等不可變類型作為key是非常明智的
HashMap 和 HashTable 的區(qū)別
- HashMap 的 key 和 value 都允許為 null，Hashtable 的 key 和 value 都不允許為 null
- HashMap 的初始化容量為 16，并且容器容量一定是 2 的 n 次方，擴(kuò)容時(shí)，是以原容量 2 倍 的方式 進(jìn)行擴(kuò)容。Hashtable 初始化容量為 11 擴(kuò)容時(shí)，是以原容量 2 倍 再加 1 的方式進(jìn)行擴(kuò)容。即
int newCapacity = (oldCapacity << 1) + 1 - 散列分布方式
-
HashMap是先將key鍵的hashCode經(jīng)過擾動(dòng)函數(shù)擾動(dòng)后得到hash值，然后再利用hash & (length - 1)的方式代替取模，得到元素的存儲位置 -
Hashtable則是除留余數(shù)法進(jìn)行計(jì)算存儲位置的（因?yàn)槠淠J(rèn)容量也不是2的n次方。所以也無法用位運(yùn)算替代模運(yùn)算），int index = (hash & 0x7FFFFFFF) % tab.length
-
- 線程安全
-
HashMap不是線程安全，如果想線程安全，可以通過調(diào)用synchronizedMap(Map m)使其線程安全。但是使用時(shí)的運(yùn)行效率會下降，所以建議使用ConcurrentHashMap容器以此達(dá)到線程安全。 -
Hashtable則是線程安全的，每個(gè)操作方法前都有synchronized修飾使其同步，但運(yùn)行效率也不高，所以還是建議使用ConcurrentHashMap容器以此達(dá)到線程安全。
-
Hashtable是一個(gè)遺留容器，如果我們不需要線程同步，則建議使用HashMap，如果需要線程同步，則建議使用ConcurrentHashMap
