HashMap的內(nèi)部實(shí)現(xiàn)-創(chuàng)新互聯(lián)

權(quán)衡時(shí)空

創(chuàng)新互聯(lián)建站專業(yè)提供資陽(yáng)移動(dòng)機(jī)房服務(wù)，為用戶提供五星數(shù)據(jù)中心、電信、雙線接入解決方案，用戶可自行在線購(gòu)買(mǎi)資陽(yáng)移動(dòng)機(jī)房服務(wù)，并享受7*24小時(shí)金牌售后服務(wù)。

---

HashMap是以鍵值對(duì)的方式存儲(chǔ)數(shù)據(jù)的。

如果沒(méi)有內(nèi)存限制，那我直接用哈希Map的鍵作為數(shù)組的索引，取的時(shí)候直接按索引get就行了，可是地價(jià)那么貴，哪里有無(wú)限制的地盤(pán)呢。

如果沒(méi)有時(shí)間限制的話，我可以把數(shù)據(jù)放到一個(gè)無(wú)序數(shù)組中，按順序查找，遲早也能找到?？墒莟ime is money，光陰那么短暫，誰(shuí)又等得起呢。

所以，HashMap做了個(gè)折中的策略，使用適當(dāng)?shù)臅r(shí)間和空間做出了權(quán)衡，具體可以歸結(jié)為“鏈表散列法”，這是一個(gè)hash表處理沖突的經(jīng)典方法。

 　　

鏈表散列

---

那么什么是”鏈表散列法”呢？看下圖：

 

縱向的是一個(gè)數(shù)組，數(shù)組的每一項(xiàng)都是一個(gè)鏈表。你可以把這個(gè)數(shù)組看成是N個(gè)桶，每一個(gè)桶放著一個(gè)鏈子。

數(shù)組是干嘛的？數(shù)組的每一項(xiàng)負(fù)責(zé)放鏈表的。

鏈表是干嘛的？負(fù)責(zé)放Map數(shù)據(jù)的，比如一個(gè)HashMap有兩個(gè)鍵，一個(gè)是key1，一個(gè)是key2。那么該鏈表就會(huì)分出兩個(gè)節(jié)點(diǎn)分別存放這兩個(gè)鍵值對(duì)（每一個(gè)鍵值對(duì)是打包放在Entry對(duì)象中的）。

鏈表是怎么鏈起來(lái)的？Entry包含有key、value、下一個(gè)節(jié)點(diǎn)next、hash值等，這個(gè)next就把各個(gè)節(jié)點(diǎn)串了起來(lái)。

HashMap保存數(shù)據(jù)的過(guò)程為：先計(jì)算當(dāng)前要保存的鍵值對(duì)的哈希值（決定著當(dāng)前鍵值對(duì)要放到哪個(gè)桶中），根據(jù)這個(gè)哈希值找到對(duì)應(yīng)的桶。如果桶中沒(méi)有數(shù)據(jù)，那就直接放進(jìn)去。如果桶中已經(jīng)放了數(shù)據(jù)（也即：桶中的鏈條上放著一個(gè)或者多個(gè)鍵值對(duì)），那就順著桶中的這個(gè)鏈條一個(gè)一個(gè)比對(duì)，看有沒(méi)有key與當(dāng)前要保存的數(shù)據(jù)的key相同。如果有相同，直接覆蓋原來(lái)key的value。如果沒(méi)有相同的，那么將該元素保存在鏈頭（最早保存的元素就會(huì)跑到鏈尾）。

 　　

裝填因子

---

桶的數(shù)量決定了能放多少個(gè)HashMap，而具體用了多少個(gè)桶，則直接關(guān)系著查找的效率。打個(gè)比方，你去隔壁班找小明，班里有10個(gè)人，你很快就會(huì)找到小明，班里坐著100個(gè)人，你可能找半天才能找到。所以你去看HashMap的構(gòu)造函數(shù)是這樣的：

public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }public HashMap() {        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

三個(gè)構(gòu)造函數(shù)都牽動(dòng)著兩個(gè)東西：initialCapacity，loadFactor。前者表示的是桶的初始數(shù)量（即數(shù)組大?。笳弑硎尽把b填因子”，裝填因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度。比如，數(shù)組初始大小為100，如果裝填因子=0.6，表示當(dāng)數(shù)組中存放了60個(gè)Map之后，就要把數(shù)組擴(kuò)容后才能繼續(xù)存放。這就是為了解決上面講到的效率問(wèn)題。

裝填因子定的小了，查找數(shù)據(jù)就快些，但是浪費(fèi)空間。裝填因子大了，空間利用率就高，但是浪費(fèi)時(shí)間。生活就是這樣，顧此失彼在所難免，萬(wàn)事哪有兩全的呢。系統(tǒng)權(quán)衡利弊后，默認(rèn)給的裝填因子是0.75，這個(gè)一般我們是不需要改動(dòng)的。

 　　

除留余數(shù)

---

那么還有個(gè)問(wèn)題。拿到一個(gè)Map的哈希值，怎么決定放到哪個(gè)桶里呢？如果最后數(shù)組中的Map數(shù)據(jù)都擠到一塊兒那可不行，查詢就會(huì)慢。太松了也不行，浪費(fèi)空間。Java用了一招“除留余數(shù)法”，保證數(shù)據(jù)在數(shù)組中分布均勻。

“除留余數(shù)法”，就是取模。比如數(shù)組的長(zhǎng)度是100，Map的哈希值是80，用80%100，余數(shù)是80，就放到80那個(gè)位置。但是Java可不是那樣干算的呦，且看源碼：

void addEntry(int hash, K key, V value, int bucketIndex) {        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
}

上面代碼就是HashMap中的添加Entry數(shù)據(jù)的方法。BucketIndex就是當(dāng)前Map在數(shù)組中的索引。第三行擴(kuò)容且不談，重點(diǎn)在indexFor方法，這個(gè)方法就是”取模”。我們點(diǎn)進(jìn)去看一下：

static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

        return h & (length-1);

}

H是Map的哈希值，length是數(shù)組的長(zhǎng)度。它直接使用了一個(gè)h & (length - 1)。這一句其實(shí)就相當(dāng)于對(duì)數(shù)組取模，但是直接用二進(jìn)制的位操作，比數(shù)學(xué)計(jì)算要快的多。這也給了我們程序員一個(gè)啟發(fā)，能用位運(yùn)算時(shí)盡量用，提高逼格又提高效率。

 　　

均勻分布

---

還有個(gè)有趣的地方，上面代碼的注釋部分：length must be a non-zero power of 2，這句是說(shuō)，數(shù)組的長(zhǎng)度必須是2的n次方。

為啥是2的n次方呢？

如果不是2的n次方，比如length為15，h分別為2,3,4。那么用h & (length -1)有：

h	Length-1	h & (length -1)
0010	1110	0010，即2
0011	1110	0010，即2
0100	1110	0100，即4

你看，隨便測(cè)了三個(gè)數(shù)字，就發(fā)生了碰撞。為什么會(huì)這樣呢？

這是因?yàn)椋喝绻皇?的n次方，那么2^n – 1的最低位必然為0，而0、1分別和0作“與”運(yùn)算，結(jié)果都為0。也就是說(shuō)，不論h為多少，h & (length - 1)的結(jié)果最低位都是0。那么數(shù)組中最低位為1的那些位置就全部空缺著，這就導(dǎo)致數(shù)據(jù)在數(shù)組中分布不均勻了，繼而影響了查詢的效率。

讀取數(shù)據(jù)的時(shí)候就簡(jiǎn)單多了，通過(guò)key的hash值找到在table數(shù)組中的索引處的Entry，然后返回該key對(duì)應(yīng)的value即可。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)頁(yè)名稱：HashMap的內(nèi)部實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文來(lái)源：http://bm7419.com/article6/gejig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司、移動(dòng)網(wǎng)站建設(shè)、云服務(wù)器、電子商務(wù)、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)