成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

深入理解HashMap(二): 關(guān)鍵源碼逐行分析之hash算法

chunquedong / 2282人閱讀

摘要：散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個叫做散列值，，，或的指紋。

前言

系列文章目錄

前面我們討論了HashMap的結(jié)構(gòu), 接下來幾篇我們從源碼角度來看HashMap的實現(xiàn)細(xì)節(jié).

本篇我們就來聊聊HashMap的hash算法

本文的源碼基于 jdk8 版本.

hash算法

上一篇文章我們提到, 為了利用數(shù)組索引進(jìn)行快速查找, 我們需要先將 key值映射成數(shù)組下標(biāo). 因為數(shù)組的下標(biāo)是有限的集合, 所以我們可以先通過hash算法將key映射成整數(shù), 再將整數(shù)映射成有限的數(shù)組下標(biāo):

Object -> int -> index

對于 Object -> int 部分, 使用的就是hash function, 而對于 int -> index 部分, 我們可以簡單的使用對數(shù)組大小取模來實現(xiàn).

下面我們就來看看HashMap使用了什么hash算法.

首先我們來看維基百科對于hash function的定義:

散列函數(shù)（英語：Hash function）又稱散列算法、哈希函數(shù)，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。

在java中, hash函數(shù)是一個native方法, 這個定義在Object類中, 所以所有的對象都會繼承.

public native int hashCode();

因為這是一個本地方法, 所以我們無法看到它的具體實現(xiàn), 但是從函數(shù)簽名上可以看出, 該方法將任意對象映射成一個整型值.調(diào)用該方法, 我們就完成了 Object -> int的映射

所以將 key映射成index 的方式可以是

key.hashCode() % table.length

那么HashMap是這樣做的嗎? 事實上, HashMap定義了自己的散列方法:

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

我們知道, int類型是32位的, h ^ h >>> 16 其實就是將hashCode的高16位和低16位進(jìn)行異或, 這充分利用了高半位和低半位的信息, 對低位進(jìn)行了擾動, 目的是為了使該hashCode映射成數(shù)組下標(biāo)時可以更均勻, 詳細(xì)的解釋可以參考這里.

另外, 從這個函數(shù)中, 我們還可以得到一個意外收獲:

HashMap中key值可以為null, 且null值一定存儲在數(shù)組的第一個位置.
性能提升

前面我們提到, 將hash值轉(zhuǎn)換成數(shù)組下標(biāo)我們可以采用取模運(yùn)算, 但是取模運(yùn)算是十分耗時的.

另一方面, 我們知道, 當(dāng)一個數(shù)是 2^n 時, 任意整數(shù)對2^n取模等效于:

h % 2^n = h & (2^n -1)

這樣我們就將取模操作轉(zhuǎn)換成了位操作, 而位操作的速度遠(yuǎn)遠(yuǎn)快于取模操作.

為此, HashMap中, table的大小都是2的n次方, 即使你在構(gòu)造函數(shù)中指定了table的大小, HashMap也會將該值擴(kuò)大為距離它最近的2的整數(shù)次冪的值. 這在我們下面分析構(gòu)造函數(shù)的時候就能看到了.

(完)

下一篇 : 深入理解HashMap(三): 關(guān)鍵源碼逐行分析之構(gòu)造函數(shù)

查看更多系列文章：系列文章目錄

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76538.html

相關(guān)文章

  • 系列文章目錄

    摘要：為了避免一篇文章的篇幅過長，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會持續(xù)更新，以給大家一個查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因為寫作的時候發(fā)現(xiàn)，為了弄懂一個知識，不得不先去了解另外一些知識，這樣以來，為了說明一個問題，就要把一系列知識都了解一遍，寫出來的文章就特別長。 為了避免一篇...

    lijy91 評論0 收藏0

  • 系列文章目錄

    摘要：為了避免一篇文章的篇幅過長，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會持續(xù)更新，以給大家一個查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因為寫作的時候發(fā)現(xiàn)，為了弄懂一個知識，不得不先去了解另外一些知識，這樣以來，為了說明一個問題，就要把一系列知識都了解一遍，寫出來的文章就特別長。 為了避免一篇...

    Yumenokanata 評論0 收藏0

  • 深入理解HashMap(三): 關(guān)鍵源碼逐行分析之構(gòu)造函數(shù)

    摘要：前言系列文章目錄上一篇我們說明了的算法說到在構(gòu)造時會自動將設(shè)為的整數(shù)次冪本篇我們就來聊聊的構(gòu)造函數(shù)本文的源碼基于版本構(gòu)造函數(shù)共有四個構(gòu)造函數(shù)默認(rèn)初始大小默認(rèn)負(fù)載因子沒有指定時使用默認(rèn)值即默認(rèn)初始大小默認(rèn)負(fù)載因子指定初始大小但使用默認(rèn)負(fù)載因子 前言 系列文章目錄 上一篇我們說明了HashMap的hash算法, 說到HashMap在構(gòu)造時會自動將table設(shè)為2的整數(shù)次冪. 本篇我們就來聊...

    QiuyueZhong 評論0 收藏0

  • 深入理解HashMap(五): 關(guān)鍵源碼逐行分析之put

    摘要：當(dāng)鏈表長度超過默認(rèn)是個時，會將鏈表轉(zhuǎn)換成紅黑樹以提升查找性能。 前言 系列文章目錄 上一篇我們討論了HashMap的擴(kuò)容操作, 提到擴(kuò)容操作發(fā)生在table的初始化或者table大小超過threshold后，而這兩個條件的觸發(fā)基本上就發(fā)生在put操作中。 本篇我們就來聊聊HashMap的put操作。 本文的源碼基于 jdk8 版本. put方法 HashMap 實現(xiàn)了Map接口, 因此...

    APICloud 評論0 收藏0

  • 深入理解HashMap(四): 關(guān)鍵源碼逐行分析之resize擴(kuò)容

    摘要：前言系列文章目錄上一篇我們說明了的構(gòu)造函數(shù)談到構(gòu)造函數(shù)中并不會初始化變量變量是在過程中初始化的本篇我們就來聊聊的擴(kuò)容本文的源碼基于版本用于以下兩種情況之一初始化在大小超過之后進(jìn)行擴(kuò)容下面我們直接來對照源碼分析原中已經(jīng)有值已經(jīng)超過最大限制不再 前言 系列文章目錄 上一篇我們說明了HashMap的構(gòu)造函數(shù), 談到構(gòu)造函數(shù)中并不會初始化table 變量, table 變量是在 resize過...

    aristark 評論0 收藏0

發(fā)表評論

0條評論

chunquedong

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<