權(quán)衡時空

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

---

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

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

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

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

 　　

鏈表散列

---

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

 

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

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

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

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

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

 　　

裝填因子

---

桶的數(shù)量決定了能放多少個HashMap，而具體用了多少個桶，則直接關(guān)系著查找的效率。打個比方，你去隔壁班找小明，班里有10個人，你很快就會找到小明，班里坐著100個人，你可能找半天才能找到。所以你去看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òu)造函數(shù)都牽動著兩個東西：initialCapacity，loadFactor。前者表示的是桶的初始數(shù)量（即數(shù)組大?。?，后者表示“裝填因子”，裝填因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。比如，數(shù)組初始大小為100，如果裝填因子=0.6，表示當(dāng)數(shù)組中存放了60個Map之后，就要把數(shù)組擴(kuò)容后才能繼續(xù)存放。這就是為了解決上面講到的效率問題。

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

 　　

除留余數(shù)

---

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

“除留余數(shù)法”，就是取模。比如數(shù)組的長度是100，Map的哈希值是80，用80%100，余數(shù)是80，就放到80那個位置。但是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方法，這個方法就是”取?！?。我們點(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ù)組的長度。它直接使用了一個h & (length - 1)。這一句其實(shí)就相當(dāng)于對數(shù)組取模，但是直接用二進(jìn)制的位操作，比數(shù)學(xué)計(jì)算要快的多。這也給了我們程序員一個啟發(fā)，能用位運(yùn)算時盡量用，提高逼格又提高效率。

 　　

均勻分布

---

還有個有趣的地方，上面代碼的注釋部分：length must be a non-zero power of 2，這句是說，數(shù)組的長度必須是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

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

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

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

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

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

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

廣告

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