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

chunquedong 發布于2019-08-19 10:50 / 2275人閱讀

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

前言

系列文章目錄

前面我們討論了HashMap的結構, 接下來幾篇我們從源碼角度來看HashMap的實現細節.

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

本文的源碼基于 jdk8 版本.

hash算法

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

Object -> int -> index

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

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

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

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

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

public native int hashCode();

因為這是一個本地方法, 所以我們無法看到它的具體實現, 但是從函數簽名上可以看出, 該方法將任意對象映射成一個整型值.調用該方法, 我們就完成了 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位進行異或, 這充分利用了高半位和低半位的信息, 對低位進行了擾動, 目的是為了使該hashCode映射成數組下標時可以更均勻, 詳細的解釋可以參考這里.

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

HashMap中key值可以為null, 且null值一定存儲在數組的第一個位置.

性能提升

前面我們提到, 將hash值轉換成數組下標我們可以采用取模運算, 但是取模運算是十分耗時的.

另一方面, 我們知道, 當一個數是 2^n 時, 任意整數對2^n取模等效于:

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

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

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

(完)

下一篇 : 深入理解HashMap(三): 關鍵源碼逐行分析之構造函數

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

云服務器 GPU云服務器深入理解webrtc之aec 深入理解系列深入理解linux 深入理解webrtc

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76538.html

系列文章目錄

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

lijy91 2019-06-28 16:36 評論0 收藏0
系列文章目錄

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

Yumenokanata 2019-08-19 10:58 評論0 收藏0
深入理解HashMap(三): 關鍵源碼逐行分析之構造函數

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

QiuyueZhong 2019-08-19 10:50 評論0 收藏0
深入理解HashMap(五): 關鍵源碼逐行分析之put

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

APICloud 2019-08-19 10:51 評論0 收藏0
深入理解HashMap(四): 關鍵源碼逐行分析之resize擴容

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

aristark 2019-08-19 10:50 評論0 收藏0