HashMap全方位剖析

常見HashMap面試問答

HashMap是不是有序的？

不是有序的。

有沒有有序的Map實(shí)現(xiàn)類？

TreeMap和linkedHashMap。

TreeMap和LinkedHashMap是如何保證它的順序的？

TreeMap是通過實(shí)現(xiàn)SortMap接口，能夠把它保存的鍵值對(duì)根據(jù)key排序，基于紅黑樹，從而保證TreeMap中所有鍵值對(duì)處于有序狀態(tài)。LinkedHashMap則是通過插入排序（就是PUT的時(shí)候的順序是什么，取出來的時(shí)候就是什么順序）和訪問順序（改變排序把訪問過的放到底部）讓鍵值有序。

TreeMap和LinkedHashMap的有序?qū)崿F(xiàn)那個(gè)更好呢？

為什么要用HashMap？

HashMap是一個(gè)散列桶（數(shù)組和鏈表），它存儲(chǔ)的內(nèi)容是鍵值對(duì)key-value映射
HashMap采用了數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，能在查詢和修改方便繼承了數(shù)組的線性查找和鏈表的尋址修改
HashMap是非synchronized,所以HashMap很快
HashMap可以接受null鍵和值，而HashTable則不能（原因就是equals() 方法需要對(duì)象，因?yàn)镠ashMap是活出的API經(jīng)過處理才可以）

HashMap的工作原理是什么？

HashMap 是基于hashing的原理
當(dāng)我們使用put(key,value)存儲(chǔ)對(duì)象到hashMap中，使用get(key)從HashMap中獲取對(duì)象。當(dāng)我們給put()方法傳遞鍵和值時(shí)，我們先對(duì)鍵調(diào)用HashCode()方法，計(jì)算并返回的HashCode 是用于找到Map 數(shù)組的bucket位置來存儲(chǔ)Node對(duì)象。
這里關(guān)鍵點(diǎn)在于指出，HashMap是在bucket中儲(chǔ)存鍵對(duì)象和值對(duì)象，作為Map.Node。

bucket模型圖

HashMap的簡(jiǎn)化的模擬數(shù)據(jù)結(jié)構(gòu):

Node[] table = new Node[16];//散列桶初始化，Table
class Node {
    hash; //hash值
    key; //鍵
    value; //值
    node next; //用于指向鏈表的下一層（產(chǎn)生沖突，使用拉鏈法）
}

以下是具體的put過程（1.8）

對(duì)key求Hash值，然后再計(jì)算下標(biāo)
如果沒有碰撞，直接放入桶中（碰撞的意思是計(jì)算得到的Hash值相同，需要放到一個(gè)bucket中）
如果碰撞發(fā)生了，以鏈表的方式鏈接到后面
如果鏈表長(zhǎng)度超過閾值（TREEIFY THRESHOLD==8），就把鏈表轉(zhuǎn)成紅黑樹，鏈表長(zhǎng)度低于6，就把紅黑樹轉(zhuǎn)回鏈表
如果節(jié)點(diǎn)已經(jīng)存在就替換舊值
如果桶滿了（容量16*加載因子0.75），就需要resize（擴(kuò)容2倍后重排）

以下是具體get過程
考慮特殊情況：如果兩個(gè)鍵的HashCode相同，如何獲取值對(duì)象？
當(dāng)我們調(diào)用get()方法，HashMap會(huì)使用鍵對(duì)象的HashCode找到bucket位置，找到bucket位置之后，會(huì)調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點(diǎn)，最終找到要找的對(duì)象。

有什么方法可以減少碰撞？

擾動(dòng)函數(shù)可以減少碰撞

原理：兩個(gè)不相等的對(duì)象返回不同的HashCode，碰撞可能發(fā)生的機(jī)會(huì)小一些。同時(shí)也意味著存鏈表結(jié)構(gòu)減小，使用GET方法取值的話就不會(huì)頻繁調(diào)用equal()方法，從而提高HashMap的性能，擾動(dòng)函數(shù)的作用就是Hash()方法內(nèi)部的算法實(shí)現(xiàn)，目的是讓不同對(duì)象返回不同的HashCode。

使用不變的、聲明做final對(duì)象，并且采用合適的equals()和HashCode()方法，將會(huì)減少碰撞發(fā)生
不可變性使得能夠魂村不同鍵的HashCode，這將提高整個(gè)獲取對(duì)象的速度，使用String、Integer這樣的wrapper類作為鍵是非常好的選擇。
為什么String、Integer這樣的wrapper類適合作為鍵？
因?yàn)镾tring是常量類final類型的，在內(nèi)部實(shí)現(xiàn)過程中已經(jīng)重寫equals()和HashCode()方法，常量類型不可變性作為前提條件，要計(jì)算HashCode(),必須保證鍵值改變，如果鍵值在put和get時(shí)返回的HashCode不同，就會(huì)導(dǎo)致HashMap中找不到相應(yīng)的對(duì)象。

HashMap 中hash函數(shù)是如何實(shí)現(xiàn)的？

HashMap中想要找到某個(gè)元素，需要根據(jù)key的hash值來找到對(duì)應(yīng)數(shù)據(jù)中具體的位置。
由于HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表結(jié)合，一般情況我們希望HashMap中的元素位置盡可能均勻分布，最好的情況就是每個(gè)位置上只有一個(gè)元素。這樣使用hash算法計(jì)算這個(gè)位置的時(shí)候，立刻就能知道對(duì)應(yīng)位置的元素是我們需要的，同時(shí)也不用去遍歷鏈表。因此，首先需要把HashCode對(duì)數(shù)組長(zhǎng)度取模運(yùn)算，這樣的好處就是元素分布的相對(duì)均勻。
但由于取模運(yùn)算消耗相對(duì)比較大，有沒有更快速、消耗更小的方式處理，通過讀JDK1.8源碼了解到如下：

Jdk源碼hash()方法

static final int hash(Object key){
    if(key == null){
        return 0；
    }
    int h;
    h = key.hashCode();返回散列值也就是HashCode
    
    return （n-1）&(h ^ (h >>> 16));
}

h = hashCode(): 1111 1111 1111 1111 1111 0000 1110 1010
調(diào)用hashCode()

h: 1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16: 0000 0000 0000 0000 1111 1111 1111 1111
計(jì)算Hash

hash = h ^(h >>> 16): 1111 1111 1111 1111 0000 1111 0001 0101

(n-1) & hash: 0000 0000 0000 0000 0000 0000 0000 1111
1111 1111 1111 1111 1111 1111 0001 0101
計(jì)算下標(biāo)

0101 = 5

簡(jiǎn)單來說就是：

高16bit不變，低16bit做了一個(gè)異或（得到的HashCode轉(zhuǎn)化為32位二進(jìn)制，前16位和后16位低16bit和高16bit做了一個(gè)異或）
(n-1)&hash = 得到下標(biāo)

拉鏈法導(dǎo)致的鏈表過深，選擇紅黑樹的好處是什么，為什么不用二叉樹代替？但在鏈表長(zhǎng)度比較短的時(shí)候又不選擇使用紅黑樹？

不選擇二叉樹的原因就是二叉查找樹在特殊情況下會(huì)變成一條線性結(jié)構(gòu)（就跟原有鏈表結(jié)構(gòu)是相同的，造成了很深的層次），遍歷查找會(huì)非常慢。而紅黑樹在插入新數(shù)據(jù)后可以通過使用左旋、右旋、變色這些操作來保持平衡。引入紅黑樹為了查找數(shù)據(jù)快，解決鏈表查詢深度的問題。我們知道紅黑樹屬于平衡二叉樹，為了保持“平衡”是需要付出代價(jià)的，但是該代價(jià)所消耗的資源要比遍歷線性鏈表要少，所以在長(zhǎng)度比較短的情況下，根本不需要引入紅黑樹，移入反而更慢；但是在長(zhǎng)度大于閾值8的情況下，選擇使用紅黑樹更快。

6. 對(duì)紅黑樹的認(rèn)知

[ ] 每個(gè)節(jié)點(diǎn)非紅即黑
[ ] 根節(jié)點(diǎn)的顏色總是黑色的
[ ] 如果節(jié)點(diǎn)是紅色的，則它的每個(gè)子節(jié)點(diǎn)必須是黑色的（反之不一定）
[ ] 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）
[ ] 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度）

7. 解決hash碰撞的更多方法？

開放定址法
當(dāng)沖突發(fā)生時(shí)，使用某種探測(cè)技術(shù)在散列表中形成一個(gè)探查序列。沿此探測(cè)序列逐個(gè)單元的去查找，知道找到給定的地址。按照形成探查序列的方法不同，可將開放定址法區(qū)分為限行探測(cè)方法、二次探測(cè)法、雙重散列法等。
下面給一個(gè)限行探查法的例子：
問題：已知一組關(guān)鍵字為（26、36、41、38、44、15、68、12、06、51），用除余法因子是13的散列函數(shù)計(jì)算出的上述關(guān)鍵字的散列表。
為了減少?zèng)_突，通常令裝填因子α由除余法因子是13的散列函數(shù)計(jì)算出的上述關(guān)鍵字序列的散列地址為（0，10，2，12，5，2，3，12，6，12）
前5個(gè)關(guān)鍵字插入時(shí)，其相應(yīng)的地址均為開放地址，故將他們直接插入T[0]、T[10]、T[2]、T[12]和T[5]中。
當(dāng)插入第5個(gè)關(guān)鍵字15時(shí)，其散列地址2（即h(15)= 15%13=2）已被關(guān)鍵字41（15和41互為同義詞）占用。探查到h1(2+1)%13=3,此地址開放，所以講15放入T[3]中。
當(dāng)插入第7個(gè)關(guān)鍵字68時(shí)，散列地址3已被非同義詞15先占用，故將其插入到T[4]中。
當(dāng)插入第8個(gè)關(guān)鍵字12時(shí)，散列地址12已被同義詞38占用，故探查h1=(2+3)%13=0,而T[0]也被26占用
再探查h2=(12+2)%13=1，此地址開放，可將12插入其中。
類似的，第9個(gè)關(guān)鍵字06直接插入T[6]中；而最后一個(gè)關(guān)鍵字51插入時(shí)，因探測(cè)地址12，0，1，。。。6均為非空，故51插入T[7]中。

8.如果HashMap的大小超過了負(fù)載因子（load factor）定義的容量怎么辦？

HashMap默認(rèn)的負(fù)載因子大小為0.75.也就是說，當(dāng)一個(gè)Map填滿75%的bucket時(shí)候，和其他集合類一樣（比如ArrayList），將會(huì)創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組來重新調(diào)整Map大小，并將原來的對(duì)象放入新的bucket數(shù)組中。這個(gè)過程叫做rehashing。
因?yàn)樗{(diào)用hash方法找到新的bucket位置。這個(gè)值只可能在兩個(gè)地方，一個(gè)是原下標(biāo)的位置，另一種是在下標(biāo)為<原下標(biāo)+原容量>的位置。

9.重新調(diào)整HashMap大小存在什么問題

重新調(diào)整HashMap的大小的時(shí)候，確實(shí)存在條件競(jìng)爭(zhēng)。
因?yàn)槿绻麅蓚€(gè)線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，他們會(huì)同時(shí)試著調(diào)整大小。在調(diào)整大小的過程中，存儲(chǔ)在鏈表中的元素的次序有可能會(huì)反過來。因?yàn)橐苿?dòng)到新的bucket位置的時(shí)候，HashMap并不會(huì)將元素放在鏈表的尾部，而是放在頭部。是由于避免尾部遍歷（tail traversing）。如果條件競(jìng)爭(zhēng)發(fā)生了，那么久死循環(huán)了。多線程的環(huán)境下不使用HashMap。
為什么多線程會(huì)導(dǎo)致死循環(huán)，它是怎么發(fā)生的？
HashMap的容量是有限的。當(dāng)經(jīng)過多次元素插入，使得HashMap達(dá)到一定飽和度時(shí)，key映射位置發(fā)生沖突的幾率會(huì)逐漸提高。這時(shí)候，HashMap需要擴(kuò)展它的長(zhǎng)度，也就是進(jìn)行Resize.

擴(kuò)容：創(chuàng)建一個(gè)新的Entry空數(shù)組，長(zhǎng)度是原數(shù)組的2倍
rehash：遍歷原來的Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組

10.HashTable

數(shù)組 + 鏈表方式存儲(chǔ)
默認(rèn)容量：11（質(zhì)數(shù)為宜）
put操作:首先進(jìn)行所以計(jì)算（key.hashCode()&0x7FFFFFFF）%table.length;若在鏈表中找到了，則替換舊值，若未找到則繼續(xù)；當(dāng)總元素個(gè)數(shù)超過容量 * 加載因子時(shí)，擴(kuò)容為原來2倍并重新散列；將新元素加到鏈表頭部
對(duì)修改HashTable內(nèi)部貢獻(xiàn)數(shù)據(jù)的方法添加了synchronized,保證線程安全

11.HashMap與HashTable區(qū)別

默認(rèn)容量不一樣，擴(kuò)容不同
線程安全性：HashTable安全
效率不同：HashTable要慢，因?yàn)榧渔i

12.可以使用CocurrentHashMap代替HashTable嗎？

HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，因?yàn)樗粌H僅根據(jù)同步級(jí)別對(duì)map的一部分進(jìn)行上鎖
ConcurrentHashMap當(dāng)然可以代替HashTable,但是HashTable提供更強(qiáng)的線程安全性
ConcurrentHashMap和HashTable都可以用于多線程環(huán)境，但是當(dāng)HashTable的大小增加到一定的時(shí)候，性能會(huì)急劇下降，因?yàn)榈鷷r(shí)需要鎖定很長(zhǎng)時(shí)間。由于ConcurrentHashMap引入了分割（segmentation）,不論它變得多么大，僅僅需要鎖定Map的某個(gè)部分，其他的線程不需要等到迭代完成才能訪問Map。簡(jiǎn)而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定Map的某個(gè)部分，而HashTable則會(huì)鎖定整個(gè)Map

13.ConcurrentHashMap(jdk 1.7)

ConcurrentHashMap由Segment數(shù)組和hashEntry數(shù)組和鏈表組成
Segment是基于重入鎖（ReentrantLock）:一個(gè)數(shù)據(jù)段競(jìng)爭(zhēng)鎖。每個(gè)HashEntry一個(gè)鏈表結(jié)構(gòu)的元素，利用Hash算法得到索引確定歸屬的數(shù)據(jù)段，也就是對(duì)應(yīng)到在修改時(shí)需要競(jìng)爭(zhēng)獲取的鎖。ConcurrentHashMap支持CurrencyLevel（segment數(shù)組數(shù)量）的線程并發(fā)。每當(dāng)一個(gè)線程占用鎖訪問一個(gè)segment時(shí)，不會(huì)影響到其他segment
核心數(shù)據(jù)如Value，以及鏈表都是volatile修飾的，保證了獲取時(shí)的可見性
首先是通過key定位到segment，之后對(duì)應(yīng)的segment中進(jìn)行具體的put操作如下：
1. 將當(dāng)前segment中的Table通過可以的HashCode定位到hashEntry
2. 遍歷該hashEntry，如果不為空則判斷傳入的key 和當(dāng)前遍歷的key是否相等，相等則覆蓋舊的Value
3. 不為空則需要新建一個(gè)HashEntry并加入到Segment中，同時(shí)會(huì)先判斷是否需要擴(kuò)容
4. 最后會(huì)接觸在1中所獲取當(dāng)前的Segment的鎖
雖然hashEntry中的Value是用volatile關(guān)鍵詞修飾的，但是并不能保證并發(fā)的原子性，所以put操作時(shí)仍然需要加鎖處理

首先第一步的時(shí)候會(huì)嘗試獲取鎖，如果獲取失敗肯定就會(huì)有其他線程存在競(jìng)爭(zhēng)，則利用scanAndLockForPut()自旋獲取鎖

嘗試自旋獲取鎖
如果重試的次數(shù)達(dá)到了MAX_SCAN_RETRIES則改為阻塞鎖獲取，保證能獲取成功。最后解除當(dāng)前Segment的鎖

13.ConcurrentHashMap(jdk1.8)

ConcurrentHashMap拋棄了Segment分段鎖，采用了CAS + synchronized來保證并發(fā)安全性。其中val next都用了volatile修飾，保證了可見性。
最大特點(diǎn)是引入了CAS
借助Unsafe來實(shí)現(xiàn)native code.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，否則什么都不做，Unsafe借助CPU指令cmpxchg來實(shí)現(xiàn)。
CAS使用實(shí)例
對(duì)sizeCtl的控制都是用CAS來實(shí)現(xiàn)的：

-1代表table正在初始化
N表示有-N-1個(gè)線程正在進(jìn)行擴(kuò)容操作
如果table未初始化，表示table需要初始化的大小
如果table初始化完成，表示table的容量，默認(rèn)是table大小的0.75倍，用這個(gè)公式算0.75（n-(n>>>2))

CAS會(huì)出現(xiàn)的問題：ABA

解決方案：對(duì)變量增加一個(gè)版本號(hào)，每次修改，版本號(hào)加1，比較的時(shí)候比較版本號(hào)

PUT過程

根據(jù)key計(jì)算HashCode
判斷是否需要進(jìn)行初始化
通過key定位出的Node，如果為空表示當(dāng)前位置可以寫入數(shù)據(jù)，利用CAS嘗試寫入，是被則自旋保證成功
如果當(dāng)前位置的HashCode == MOVED == -1,則需要進(jìn)行擴(kuò)容
如果不滿足，則利用synchronized鎖寫入數(shù)據(jù)
如果數(shù)量大于TREEIFY-THRESHOLD則要轉(zhuǎn)換為紅黑樹

GET過程

根據(jù)計(jì)算出來的HashCode尋址，如果就在桶上那么直接返回值
如果是紅黑樹那就按照樹的方式獲取值
就不滿足那就按照鏈表的方式遍歷獲取值

結(jié)尾
ConcurrentHashMap在Java8中存在一個(gè)bug會(huì)進(jìn)入死循環(huán)，原因是遞歸創(chuàng)建ConcurrentHashMap對(duì)象，但是在JDK1.9已經(jīng)修復(fù)了，具體案例如下代碼：

public class ConcurrentHashMapDemo{
    private Map<Integer,Integer> cache = new ConcurrentHashMap<>(15);
    
    public static void main(String[] args){
        ConcurrentHashMapDemo ch = new ConcurrentHashMapDemo();
        System.out.println(ch.fibonaacci(80));
    }
    
    public int fibonaacci(Integer i){
        if(i == 0 || i == 1){
            return i;
        }
        
        return cache.computeIfAbsent(i,(key) ->{System.out.println("fibonaacci : "+ key);
        return fibonaacci(key -1)+fibonaacci(key -2);
        });
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

JAVA面試必選——HashMap全方位剖析

JAVA面試必選——HashMap全方位剖析

HashMap全方位剖析

常見HashMap面試問答

CAS會(huì)出現(xiàn)的問題：ABA

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

JAVA面試必選——HashMap全方位剖析

HashMap全方位剖析

常見HashMap面試問答

CAS會(huì)出現(xiàn)的問題：ABA

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av