資訊專欄INFORMATION COLUMN
摘要：散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值，，，或的指紋。
前言
系列文章目錄
前面我們討論了HashMap的結(jié)構(gòu), 接下來幾篇我們從源碼角度來看HashMap的實(shí)現(xiàn)細(xì)節(jié).
本篇我們就來聊聊HashMap的hash算法
本文的源碼基于 jdk8 版本.
hash算法上一篇文章我們提到, 為了利用數(shù)組索引進(jìn)行快速查找, 我們需要先將 key值映射成數(shù)組下標(biāo). 因?yàn)閿?shù)組的下標(biāo)是有限的集合, 所以我們可以先通過hash算法將key映射成整數(shù), 再將整數(shù)映射成有限的數(shù)組下標(biāo):
Object -> int -> index
對(duì)于 Object -> int 部分, 使用的就是hash function, 而對(duì)于 int -> index 部分, 我們可以簡(jiǎn)單的使用對(duì)數(shù)組大小取模來實(shí)現(xiàn).
下面我們就來看看HashMap使用了什么hash算法.
首先我們來看維基百科對(duì)于hash function的定義:
散列函數(shù)（英語：Hash function）又稱散列算法、哈希函數(shù)，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。
在java中, hash函數(shù)是一個(gè)native方法, 這個(gè)定義在Object類中, 所以所有的對(duì)象都會(huì)繼承.
public native int hashCode();
因?yàn)檫@是一個(gè)本地方法, 所以我們無法看到它的具體實(shí)現(xiàn), 但是從函數(shù)簽名上可以看出, 該方法將任意對(duì)象映射成一個(gè)整型值.調(diào)用該方法, 我們就完成了 Object -> int的映射
所以將 key映射成index 的方式可以是
key.hashCode() % table.length
那么HashMap是這樣做的嗎? 事實(shí)上, HashMap定義了自己的散列方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我們知道, int類型是32位的, h ^ h >>> 16 其實(shí)就是將hashCode的高16位和低16位進(jìn)行異或, 這充分利用了高半位和低半位的信息, 對(duì)低位進(jìn)行了擾動(dòng), 目的是為了使該hashCode映射成數(shù)組下標(biāo)時(shí)可以更均勻, 詳細(xì)的解釋可以參考這里.
另外, 從這個(gè)函數(shù)中, 我們還可以得到一個(gè)意外收獲:
HashMap中key值可以為null, 且null值一定存儲(chǔ)在數(shù)組的第一個(gè)位置.性能提升
前面我們提到, 將hash值轉(zhuǎn)換成數(shù)組下標(biāo)我們可以采用取模運(yùn)算, 但是取模運(yùn)算是十分耗時(shí)的.
另一方面, 我們知道, 當(dāng)一個(gè)數(shù)是 2^n 時(shí), 任意整數(shù)對(duì)2^n取模等效于:
h % 2^n = h & (2^n -1)
這樣我們就將取模操作轉(zhuǎn)換成了位操作, 而位操作的速度遠(yuǎn)遠(yuǎn)快于取模操作.
為此, HashMap中, table的大小都是2的n次方, 即使你在構(gòu)造函數(shù)中指定了table的大小, HashMap也會(huì)將該值擴(kuò)大為距離它最近的2的整數(shù)次冪的值. 這在我們下面分析構(gòu)造函數(shù)的時(shí)候就能看到了.
(完)
下一篇 : 深入理解HashMap(三): 關(guān)鍵源碼逐行分析之構(gòu)造函數(shù)
查看更多系列文章：系列文章目錄
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/76538.html
摘要：為了避免一篇文章的篇幅過長(zhǎng)，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會(huì)持續(xù)更新，以給大家一個(gè)查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因?yàn)閷懽鞯臅r(shí)候發(fā)現(xiàn)，為了弄懂一個(gè)知識(shí)，不得不先去了解另外一些知識(shí)，這樣以來，為了說明一個(gè)問題，就要把一系列知識(shí)都了解一遍，寫出來的文章就特別長(zhǎng)。 為了避免一篇...
摘要：為了避免一篇文章的篇幅過長(zhǎng)，于是一些比較大的主題就都分成幾篇來講了，這篇文章是筆者所有文章的目錄，將會(huì)持續(xù)更新，以給大家一個(gè)查看系列文章的入口。 前言 大家好，筆者是今年才開始寫博客的，寫作的初衷主要是想記錄和分享自己的學(xué)習(xí)經(jīng)歷。因?yàn)閷懽鞯臅r(shí)候發(fā)現(xiàn)，為了弄懂一個(gè)知識(shí)，不得不先去了解另外一些知識(shí)，這樣以來，為了說明一個(gè)問題，就要把一系列知識(shí)都了解一遍，寫出來的文章就特別長(zhǎng)。 為了避免一篇...
摘要：前言系列文章目錄上一篇我們說明了的算法說到在構(gòu)造時(shí)會(huì)自動(dòng)將設(shè)為的整數(shù)次冪本篇我們就來聊聊的構(gòu)造函數(shù)本文的源碼基于版本構(gòu)造函數(shù)共有四個(gè)構(gòu)造函數(shù)默認(rèn)初始大小默認(rèn)負(fù)載因子沒有指定時(shí)使用默認(rèn)值即默認(rèn)初始大小默認(rèn)負(fù)載因子指定初始大小但使用默認(rèn)負(fù)載因子 前言 系列文章目錄 上一篇我們說明了HashMap的hash算法, 說到HashMap在構(gòu)造時(shí)會(huì)自動(dòng)將table設(shè)為2的整數(shù)次冪. 本篇我們就來聊...
摘要：當(dāng)鏈表長(zhǎng)度超過默認(rèn)是個(gè)時(shí)，會(huì)將鏈表轉(zhuǎn)換成紅黑樹以提升查找性能。 前言 系列文章目錄 上一篇我們討論了HashMap的擴(kuò)容操作, 提到擴(kuò)容操作發(fā)生在table的初始化或者table大小超過threshold后，而這兩個(gè)條件的觸發(fā)基本上就發(fā)生在put操作中。 本篇我們就來聊聊HashMap的put操作。 本文的源碼基于 jdk8 版本. put方法 HashMap 實(shí)現(xiàn)了Map接口, 因此...
摘要：前言系列文章目錄上一篇我們說明了的構(gòu)造函數(shù)談到構(gòu)造函數(shù)中并不會(huì)初始化變量變量是在過程中初始化的本篇我們就來聊聊的擴(kuò)容本文的源碼基于版本用于以下兩種情況之一初始化在大小超過之后進(jìn)行擴(kuò)容下面我們直接來對(duì)照源碼分析原中已經(jīng)有值已經(jīng)超過最大限制不再 前言 系列文章目錄 上一篇我們說明了HashMap的構(gòu)造函數(shù), 談到構(gòu)造函數(shù)中并不會(huì)初始化table 變量, table 變量是在 resize過...
閱讀 2412·2023-04-26 02:14
閱讀 2988·2021-09-30 09:46
閱讀 2196·2021-09-24 09:48
閱讀 1092·2021-09-24 09:47
閱讀 3315·2019-08-30 15:44
閱讀 1938·2019-08-30 15:44
閱讀 3346·2019-08-30 14:18
閱讀 2028·2019-08-30 12:58
