一、散列函數(shù)

散列函數(shù)的概念

散列函數(shù)常見的幾種構(gòu)造方法

二、哈希沖突

哈希沖突的概念

哈希沖突的常見解決辦法

三、HashMap

HashMap的簡單介紹

HashMap的幾個特點(diǎn)

HashMap的兩個關(guān)鍵因子

HashMap查找的時間復(fù)雜度分析

四、問題小結(jié)

HashMap中哈希函數(shù)的實(shí)現(xiàn)方式是什么？為什么要這樣實(shí)現(xiàn)？

HashMap中哈希表的容量為什么一定要是2的整數(shù)次冪？

HashMap中hashcode()方法和equals()方法有什么用？

一、散列函數(shù)

1.散列函數(shù)的概念

散列函數(shù)，又稱哈希函數(shù)。它是一種映射關(guān)系，根據(jù)數(shù)據(jù)元素的關(guān)鍵字key作為自變量，通過一定的函數(shù)關(guān)系，計(jì)算出該元素存儲地址的值

表示為：address = H[key]

就是把任意長度的輸入值通過哈希（散列）算法轉(zhuǎn)換，得到固定長度的輸出值，即哈希值。

著名的MD5和SHA1算法等等都是目前應(yīng)用最廣泛的hash算法。

2.散列函數(shù)常見的幾種構(gòu)造方法

哈希函數(shù)的構(gòu)造方法有很多，總的一個原則就是要盡可能的減少沖突。

除留余數(shù)法

取關(guān)鍵字key被某一個p值取余而得到的值作為散列地址（散列值），其中p不大于散列表長度n 

即 H(key)=key%p, p<=m

直接尋址法

取關(guān)鍵字key或關(guān)鍵字key的某個線性函數(shù)的值作為散列地址（散列值） 

即 H(key) = key 或者 H(key) = a * key + b，其中 a 和 b 為常數(shù)

數(shù)字分析法

當(dāng)關(guān)鍵字key的位數(shù)大于地址的位數(shù)，對key的各位分布進(jìn)行分析，選出分布均勻的任意幾位作為散列值 

僅適用于所有關(guān)鍵字都已知的情況下，根據(jù)實(shí)際情況應(yīng)用確定要選取的部分，盡量減少沖突的發(fā)生

平方取中法

先計(jì)算出關(guān)鍵字key值的平方，然后取平方值中間任意幾位作為散列地址

折疊法(疊加法)

將關(guān)鍵字key分為位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）作為散列地址 

用于關(guān)鍵字位數(shù)較多，并且關(guān)鍵字中每一位上的數(shù)字分布大致均勻

隨機(jī)數(shù)法

選擇一個隨機(jī)函數(shù)，把關(guān)鍵字key的隨機(jī)函數(shù)值作為它的散列值 

通常當(dāng)關(guān)鍵字的長度不相等時使用這種方法

二、哈希沖突

1.哈希沖突的概念

不同的兩個關(guān)鍵字key，因?yàn)檫x用哈希函數(shù)而計(jì)算出相同的哈希值，被映射到表的同一位置上，稱為沖突或碰撞(collision)

發(fā)生沖突的兩個關(guān)鍵字key稱為該哈希函數(shù)的同義詞(synonym)

2.哈希沖突的常見解決辦法

拉鏈法（鏈接法）

將所有關(guān)鍵字key為同義詞的結(jié)點(diǎn)鏈接在同一個單鏈表中。若選定的散列表長度為 m ，則可將散列表定義為一個由 m 個頭指針組成的指針數(shù)組 T[0 .. m - 1]。凡是散列地址（散列值）為 i 的結(jié)點(diǎn)，均插入到以 T[i] 為頭指針的單鏈表中。指針數(shù)組 T 中各分量的初值均應(yīng)為空指針。

開放定址法

當(dāng)沖突發(fā)生時，使用某種探測技術(shù)在散列表中尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到。 

根據(jù)形成探測序列的方法不同，將開放定址法區(qū)分為線性探查法，二次探查法，雙重散列法等。

這里介紹一下線性探查法：

Hi = ( H(key) + i ) % m, 0 <= i <= m-1 

探測時從地址d開始，首先探查T[d]，然后依次探查T[d+1]…,直到T[m-1]，然后又循環(huán)到T[0]、T[1]，直到探測到有空余地址或者到T[d-1]為止。

三、HashMap

1.HashMap的簡單介紹

HashMap是一個采用Hash表實(shí)現(xiàn)的鍵值對集合，繼承自AbstractMap，實(shí)現(xiàn)了Map接口。

HashMap特殊的存儲結(jié)構(gòu)使得在獲取指定元素時先經(jīng)過哈希運(yùn)算，得到目標(biāo)元素在哈希表中的位置，然后再進(jìn)行少量的比較即可獲取到元素，因此，HashMap的查找效率較高。

在HashMap中，發(fā)生哈希沖突的時候，采用拉鏈法進(jìn)行解決，因此HashMap的底層實(shí)現(xiàn)是數(shù)組+鏈表。

jdk1.8之后，HashMap中如果一個桶(bucket)中的元素個數(shù)超過TREEIFY_THRESHOLD(默認(rèn)為8)時，就會使用紅黑樹來替換鏈表，提高查找速度，稱作桶的樹形化。

2.HashMap的幾個特點(diǎn)

存儲的元素是無序的，順序也會不定時的改變；

底層實(shí)現(xiàn)是鏈表 + 數(shù)組，Java8之后加入了紅黑樹，大大提高了查找效率；

允許有null鍵和null值存在，但空鍵只有一個，且放在第一位，看源碼可知；

插入、查找的時間復(fù)雜度基本為O(1)，(前提是經(jīng)過良好的哈希函數(shù)運(yùn)算，使得元素分布在均勻的位置)；

遍歷整個Map需要的時間與桶(數(shù)組)的長度成正比，因此在初始化HashMap容量 (capacity) 時不宜太大；

key采用Set存放，因此想要做到key不允許重復(fù)，需要在key對應(yīng)的類中重寫 hashcode() 和 equals() 方法；

3.HashMap的兩個關(guān)鍵因子

初始容量 ( DEFAULT_INITIAL_CAPACITY : 1<<4 )：默認(rèn)初始容量為16，且必須是2的整數(shù)次方

加載因子 ( DEFAULT_LOAD_FACTOR : 0.75f )：默認(rèn)加載因子的大小為0.75

加載因子太大，發(fā)生沖突的可能性會加大，導(dǎo)致查找的效率降低；太小的話會頻繁rehash,又會導(dǎo)致性能降低。

這兩個關(guān)鍵因子決定了HashMap應(yīng)該什么時候擴(kuò)容，而HashMap擴(kuò)容又伴隨著相當(dāng)大的開銷(重新創(chuàng)建數(shù)組，重新哈希計(jì)算，重新分配等等)，因此在設(shè)置初始容量時，應(yīng)該根據(jù)實(shí)際情況先考慮Map中有多少對鍵值對，設(shè)置合理的加載因子，盡可能的去避免擴(kuò)容，提高效率。

4.HashMap查找的時間復(fù)雜度分析

在HashMap中，查找的時間復(fù)雜度O一般跟鏈表長度有關(guān)，因此哈希算法越好，元素分布的越均勻，get()方法就越快。

當(dāng)HashMap中有大量的元素都存放到同一個桶中，這時候哈希表中只有一個桶，桶下有一條長長的鏈表，這個時候HashMap與單鏈表無異，遍歷的時間復(fù)雜度又回到了O(n)，完全失去了優(yōu)勢。

所以Java8以后，HashMap新增了紅黑樹 （紅黑樹的結(jié)構(gòu)可以控制時間復(fù)雜度為O(logn)） ，優(yōu)化了這種極端情況下的性能問題。

四、問題小結(jié)

1.HashMap中哈希函數(shù)的實(shí)現(xiàn)方式是什么？為什么要這樣實(shí)現(xiàn)？

在HashMap的jdk1.8源碼中，hash()方法是這樣寫的：

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

這里同樣解釋了為什么HashMap允許有null鍵，因?yàn)楫?dāng)鍵為 null 時，返回了值為0。

通過將傳入鍵的hashcode進(jìn)行無符號右移16位，然后按位異或，得到該鍵的哈希值。(無符號右移，高位總補(bǔ)0)由于哈希表中的容量都是2的整數(shù)次冪，因此key的hashcode在很多情況下低位總是相同的，這大大加大了沖突的可能性，因此在jdk1.8以后進(jìn)行了移位操作，將元素的hashcode和自己右移16位后的結(jié)果做異或運(yùn)算，而int類型長度只有32位，因此無符號右移16位就相當(dāng)于把自己的高位移到低位，然后再與自己的高位做異或運(yùn)算，得到hash值，最后通過取模運(yùn)算(n - 1) & hash得到下標(biāo)值。

這樣做可以避免只靠低位數(shù)據(jù)來計(jì)算hash值時導(dǎo)致的沖突，計(jì)算結(jié)果由高低位共同決定，極大的避免了哈希值分布不均勻，而且，采用位運(yùn)算的效率非常高。

2.HashMap中哈希表的容量為什么一定要是2的整數(shù)次冪？

capacity為2的整數(shù)次冪，在計(jì)算桶的位置hashcode&(length-1)的時候，相當(dāng)于hashcode%length，即對length取模，提高了計(jì)算效率；

capacity為2的整數(shù)次冪，那么capacity-1永遠(yuǎn)為奇數(shù)，則最后一位永遠(yuǎn)為1，這樣就可以保證在進(jìn)行hashcode&(length-1)計(jì)算的時候，得到的hash值的最后一位可能為1也可能為0(取決于hashcode最后一位)，即運(yùn)算完后的hash值既可能為偶數(shù)也可能為奇數(shù)，保證了散列的均勻性，否則，capacity為奇數(shù)的話，capacity-1最后一位永遠(yuǎn)為0，hashcode&(length-1)最后一位也必為0，即只能為偶數(shù)，這樣任意的hashcode值只會被散列到數(shù)組的偶數(shù)下標(biāo)上，浪費(fèi)了近一半的空間，也大大增加了碰撞的幾率。

3.HashMap中hashcode()方法和equals()方法有什么用？

當(dāng)插入、查找時需要通過key的hashcode()的值進(jìn)行hash()計(jì)算得到hash值，然后通過 hash&(length-1) 位運(yùn)算得到下標(biāo)，從而獲得要找的桶的位置。

而當(dāng)發(fā)生沖突時，利用key.equals()方法去鏈表或樹中去找對應(yīng)的節(jié)點(diǎn)。