HashMap的作用是什么

今天就跟大家聊聊有關(guān)HashMap的作用是什么，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

創(chuàng)新互聯(lián)成立與2013年，我們提供高端網(wǎng)站建設(shè)、微信平臺小程序開發(fā)、電商視覺設(shè)計、APP應(yīng)用開發(fā)及網(wǎng)絡(luò)營銷搜索優(yōu)化服務(wù)，在傳統(tǒng)互聯(lián)網(wǎng)與移動互聯(lián)網(wǎng)發(fā)展的背景下，我們堅守著用標準的設(shè)計方案與技術(shù)開發(fā)實力作基礎(chǔ)，以企業(yè)及品牌的互聯(lián)網(wǎng)商業(yè)目標為核心，為客戶打造具商業(yè)價值與用戶體驗的互聯(lián)網(wǎng)+產(chǎn)品。

工作原理

結(jié)構(gòu)組成

put

• 首先是或者對插入對象的key的hash指進行擾動得到新的hash值，簡單來講是為了更好的散列

• 根據(jù)hash值找到需要插入值的下標，然后對鏈表進行相應(yīng)的操作，在末尾插入，hash沖突，轉(zhuǎn)化成紅黑樹

• 如果有需要，則進行擴容

get

獲取值的時候就比較簡單了，直接根據(jù)key的hash找到桶的下標，再遍歷鏈表找到值就好了。

注意：key對象本身有個hash值，但是put和get的時候是經(jīng)過了hash算法進行了擾動生成了新的hash值，但是對象本身的hash值不變。

成員變量

肯定是挑重點的說先，其它的有了基礎(chǔ)后可以自行去源碼中查找學(xué)習(xí)，這樣更有成就感。

內(nèi)部類-Node

通過一開始也知道，HashMap 是由數(shù)組加鏈表組成的，其實本質(zhì)就是多個下面Node<K,V>組成的數(shù)組 。

<img src="/upload/otherpic50/node-hashmap.png" alt="node-hashmap"  />

其實好像也沒啥好講的，知道有這么一個類，類里面有那些成員變量就好了。

成員變量

可能有小伙伴會發(fā)現(xiàn)了，怎么沒有capcity 容量這個成員變量呀。需要注意的是jdk1.8之后，桶數(shù)組的初始化不是在構(gòu)造函數(shù)內(nèi)完成的，而是在第一次put的時候完成的，所以不設(shè)capcity這個變量完全沒問題。

構(gòu)造函數(shù)

構(gòu)造函數(shù)大體來說有兩種，一種是給成員變量賦值，一種是復(fù)制一個新的map

上面有兩個函數(shù)tableSizeFor() 和putMapEntries() 有興趣的小伙伴可以去看下源碼，實現(xiàn)比較簡單，這里就不再贅述。

Put

hash()

讓我們來看下put的源碼

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

首先運行的是一個hash() 的函數(shù)

static final int hash(Object key) {//hash算法
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先int h = key.hashCode() h是一個4字節(jié)32位的數(shù)，接著是異或上h >>> 16 最后得到了新的hash值。

h是個32位的數(shù)，那么它右移16位后，高位（前16位）位0，而x ^ 0 = x。所以整個上面一句話的作用就是保留高位，低位和高位異或，這樣子能達到的目標就是擾亂了低位，且低位具有高位的一部分屬性。

接下來的重點就到了putVal() ，需要分位第一次put和其它put來講。

第一次put

第一次put時候的putVal()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //.....

}

當(dāng)?shù)谝淮蝡ut的時候，table肯定是為空的，也就是if ((tab = table) == null || (n = tab.length) == 0) 判斷返回為true，走到resize() 流程。

來看看第一次put的時候resize是怎么運作的

通過源碼可以看到真正的table數(shù)組是在第一次put中的putVal() 中的resize() 時才初始化。

正常put

看源碼，首先會有一個根據(jù)hash計算該key應(yīng)該放在哪個桶下面，n是桶數(shù)組的長度，永遠是2的冪。反映在二進制就是只有某一位是1，其它全是0。這樣的情況下，n - 1就是尾部全是1，其它全是0。（n - 1） & hash就是保留hash值中數(shù)組長度低位的數(shù)，高位的數(shù)置0。

假設(shè)n = 16，那么n - 1 = 15 = 00001111，這樣與上hash相當(dāng)于只保留了hash的后4位。

擴容

可以發(fā)現(xiàn)上述源碼中在最后還有一個resize() ，可見resize() 除了初始化的時候有用，更多時候是用在擴容這方面。

上面源碼注釋中也有寫到是當(dāng)k-v個數(shù) > 擴容閾值 = table數(shù)組容量 * 負載因子（默認是0.75）的時候開始擴容，table數(shù)組變成原來的2倍，舊k-v重新散列在新數(shù)組中。

我把后面的拆開來說，因為其一是因為其巧妙，其二是因為太長了看著疲憊

可以提前說下，jdk的思想是把鏈表拆分成兩部分進行散列。想拆成2部分必須用hash經(jīng)過某種運算得到兩種結(jié)果，計算機里面自然就想到了0，1。一個數(shù)和另一個數(shù)得到0和1，所以可以想到&運算，且其中一個數(shù)只有1位是1，其它都是0。

所以算法就是那hash（注意，是擾動前的hash）& newCap 這樣得到的結(jié)果就只有0和1了。

Get

相比之前的插入和擴容函數(shù)，get() 相對來說就簡單了

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看到最終是到了getNode() 函數(shù)

看完上述內(nèi)容，你們對HashMap的作用是什么有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

標題名稱：HashMap的作用是什么
網(wǎng)站網(wǎng)址：http://muchs.cn/article46/gdcieg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)站設(shè)計、網(wǎng)站導(dǎo)航、網(wǎng)站設(shè)計公司、面包屑導(dǎo)航、企業(yè)建站

廣告

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