介紹

本文詳細(xì)介紹了散列表的概念、散列函數(shù)的選擇、散列沖突的解決辦法，并且最后提供了一種散列表的Java代碼實(shí)現(xiàn)。

數(shù)組的特點(diǎn)是尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是尋址困難，插入和刪除容易。而對(duì)于tree結(jié)構(gòu)，它們的查找都是先從根節(jié)點(diǎn)進(jìn)行查找，從節(jié)點(diǎn)取出數(shù)據(jù)或索引與查找值進(jìn)行比較，雖然查找和增刪的綜合效率較好，但是最終還是需要進(jìn)行多次查找。為此引入了散列表來(lái)嘗試進(jìn)一步提升查找效率和增刪的綜合效率。

1 散列表概述

1.1 散列表概述

之前所掌握的查找算法，最簡(jiǎn)單的順序表結(jié)構(gòu)查找包括簡(jiǎn)單的順序查找、二分查找、插值查找、斐波那契查找，以及后來(lái)的樹(shù)結(jié)構(gòu)查找包括二叉排序樹(shù)、平衡二叉樹(shù)、多路查找樹(shù)、紅黑樹(shù)等。它們有一個(gè)功能特點(diǎn)就是，要查找的元素始終要與已經(jīng)存在的元素進(jìn)行多次比較，才能最終的出要該的元素是否存在或者不存在的結(jié)果。

我們知道，這些比較用于逐漸的定位某一個(gè)確切的位置，上面的大部分查找算法要求數(shù)據(jù)必須是有序存儲(chǔ)的，算法就是通過(guò)比較兩個(gè)數(shù)據(jù)的大小來(lái)縮小查找的范圍，最終找到一個(gè)大小相等的數(shù)據(jù)，或說(shuō)明該元素存在，或者最終也沒(méi)有找到一個(gè)大小相等的數(shù)據(jù)，說(shuō)明不存在。

為什么一定要“比較”？能否直接通過(guò)關(guān)鍵字key得到要查找的記錄內(nèi)存存儲(chǔ)位置呢？當(dāng)然有，這就是散列表。

事先在數(shù)據(jù)(這里可以是key-value鍵值對(duì)形式的數(shù)據(jù)，也可以是單個(gè)key形式的數(shù)據(jù))的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系f，使得每個(gè)關(guān)鍵字k對(duì)應(yīng)一個(gè)存儲(chǔ)位置f（key）。即：存儲(chǔ)位置=f(key)，該映射被稱(chēng)為散列函數(shù)，利用散列函數(shù)來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)被稱(chēng)為散列表。通過(guò)f(key)計(jì)算出存儲(chǔ)位置的過(guò)程被稱(chēng)為散列，所得的存儲(chǔ)位置稱(chēng)散列地址。

散列表通?；跀?shù)組來(lái)實(shí)現(xiàn)。存放數(shù)據(jù)的時(shí)候，散列函數(shù)f(key)根據(jù)key計(jì)算出數(shù)據(jù)應(yīng)該存儲(chǔ)的位置-數(shù)組下標(biāo)，從而將不同的數(shù)據(jù)分散在不同的存儲(chǔ)位置，這也是“散列”的由來(lái)；查找的時(shí)候，通過(guò)散列函數(shù)f(key)對(duì)應(yīng)的key可以直接確定查找值所在位置-數(shù)組下標(biāo)，而不需要一個(gè)個(gè)比較。這樣就“預(yù)先知道”key所在的位置，直接找到數(shù)據(jù)，提升效率。散列表存放元素的數(shù)組位置也被稱(chēng)為“槽（slot）”。

散列表與線性表、樹(shù)、圖等結(jié)構(gòu)不同的是，后幾種結(jié)構(gòu)數(shù)據(jù)元素之間都存在某種邏輯關(guān)系，而使用散列技術(shù)的散列表的數(shù)據(jù)元素之間不存在什么邏輯關(guān)系，元素的位置只與關(guān)鍵字key和散列函數(shù)f(key)有關(guān)聯(lián)。

對(duì)于查找來(lái)說(shuō)，散列技術(shù)簡(jiǎn)化了比較過(guò)程，效率就會(huì)大大提高，但萬(wàn)事有利就有弊，由于數(shù)據(jù)元素之間并沒(méi)有確切的關(guān)系，散列技術(shù)不具備很多常規(guī)數(shù)據(jù)結(jié)構(gòu)的能力。相對(duì)于其他查找結(jié)構(gòu)，它只支持部分操作（查找、增刪……），另一部分操作不能實(shí)現(xiàn)（排序、索引操作、范圍查找、順序輸出、查找最大/小值……）。因此，散列表主要是面向查找的存儲(chǔ)結(jié)構(gòu)。

散列表的英文名稱(chēng)為 hash table，因此散列表又被稱(chēng)為哈希表，散列函數(shù)又被稱(chēng)為哈希函數(shù)，函數(shù)的實(shí)現(xiàn)步驟被稱(chēng)為散列算法/哈希算法。

1.2 散列沖突（hash collision）

我們還能看出來(lái)，散列算法實(shí)際上是將任意長(zhǎng)度的key變換成固定范圍長(zhǎng)度的值。這種轉(zhuǎn)換是一種壓縮映射，簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。也就是，散列值的范圍大小通常遠(yuǎn)小于輸入的key的范圍。

例如，輸入的key為5,28,19,15,20,33,12,17,10，共9個(gè)，此時(shí)肯定不能將哈希表（內(nèi)部數(shù)組）的長(zhǎng)度初始化為33，那樣的話就太浪費(fèi)空間了。理想的結(jié)果是，將這9個(gè)key通過(guò)某個(gè)散列函數(shù)f(key)將它們放入長(zhǎng)度為10的哈希表（數(shù)組）中，并且然而由于散列算法是一種壓縮映射算法，散列表的長(zhǎng)度單元是有限的，關(guān)鍵字key是無(wú)限的，對(duì)于某個(gè)散列算法，如果key樣本如果大，那么兩個(gè)不同的key映射到相同的單元，即f(key)的值相等的情況幾乎是一種必然，這種現(xiàn)象也被稱(chēng)為散列沖突/哈希沖突。

例如對(duì)上面的key個(gè)數(shù)采用的散列函數(shù)是f(key)=key mod 9，f(5)=5，所以數(shù)據(jù)5應(yīng)該放在散列表的第5個(gè)槽里；f(28)=1，所以數(shù)據(jù)28應(yīng)該放在散列表的第1個(gè)槽里；f(19)=1，也就是說(shuō)，數(shù)據(jù)19也應(yīng)該放在散列表表的第1個(gè)槽里——于是就造成了碰撞。

盡管我們可以通過(guò)精心設(shè)計(jì)的散列函數(shù)讓沖突盡可能的少，但是不能完全避免。因此散列表必須具備處理散列沖突的能力。

2 散列函數(shù)的選擇

2.1 散列函數(shù)的要求

從上面的散列表的概述可以看出來(lái)，要實(shí)現(xiàn)散列表，最關(guān)鍵的就是散列函數(shù)f(key)的選擇和處理散列沖突的能力，我們先來(lái)看散列函數(shù)的選擇。

良好的散列函數(shù)應(yīng)該滿(mǎn)足下面兩個(gè)原則：

• 計(jì)算簡(jiǎn)單：如果散列算法需要很復(fù)雜的計(jì)算，會(huì)耗費(fèi)很多時(shí)間，這對(duì)于需要頻繁地查找來(lái)說(shuō)，就會(huì)大大降低查找的效率了。因此散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過(guò)其他查找技術(shù)與關(guān)鍵字比較的時(shí)間。
• 散列地址分布均勻：我們剛才也提到?jīng)_突帶來(lái)的問(wèn)題，雖然不能完全避免沖突，但是可能設(shè)計(jì)好的散列函數(shù)盡量讓散列地址均勻地分布在存儲(chǔ)空間中，這樣可以保證存儲(chǔ)空間的有效利用，并減少?zèng)_突的發(fā)生和為處理沖突而耗費(fèi)的時(shí)間。 下面介紹幾種常用的散列函數(shù)構(gòu)造方法！

2.2 散列函數(shù)構(gòu)造方法

直接定址法

取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址（這種散列函數(shù)也叫自身函數(shù)）。f(key)=a×key+b（a、b為常數(shù)）。

比如對(duì)0-100歲人口數(shù)統(tǒng)計(jì)，直接采用年齡作為關(guān)鍵字。

比如統(tǒng)計(jì)1980年忠厚每年出生的人口數(shù)目，我們可以對(duì)出生年份關(guān)鍵字減去1980來(lái)作為地址。

這樣的散列函數(shù)優(yōu)點(diǎn)就是簡(jiǎn)單、均勻，也不會(huì)產(chǎn)生沖突，但問(wèn)題是這需要事先知道關(guān)鍵字的分布情況，適合查找表較小且連續(xù)的情況。由于這樣的限制，在現(xiàn)實(shí)應(yīng)用中，此方法雖然簡(jiǎn)單，但卻并不常用。

數(shù)字分析法

假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。

比如對(duì)于手機(jī)號(hào)碼的key，用手機(jī)號(hào)碼后四位參與計(jì)算。

數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻，就可以考慮用這個(gè)方法。

折疊法

將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時(shí)可以短些），然后將這幾部分疊加求和，并按散列表表長(zhǎng)，取后幾位作為散列地址。 比如我們的關(guān)鍵字是9876543210，散列表表長(zhǎng)為三位，我們將它分為四組，987|654|321|0，然后將它們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962。

有時(shí)可能這還不能夠保證分布均勻，不妨從一端向另一端來(lái)回折疊后對(duì)齊相加。比如我們將987和321反轉(zhuǎn)，再與654和0相加，變成789+654+123+0=1566，此時(shí)散列地址為566。

折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況。

平方取中法

取關(guān)鍵字平方后的中間幾位為哈希地址。通過(guò)平方擴(kuò)大差別，另外中間幾位與乘數(shù)的每一位相關(guān)，由此產(chǎn)生的散列地址較為均勻。

假設(shè)關(guān)鍵字是1234，那么它的平方就是1522756，再抽取中間的3位就是227，用做散列地址。再比如關(guān)鍵字是4321，那么它的平方就是18671041，抽取中間的3位就可以是671，也可以是710，用做散列地址。

平方取中法比較適合于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。

除留余數(shù)法

此方法為最常用的構(gòu)造散列函數(shù)方法。對(duì)于散列表長(zhǎng)為m的散列函數(shù)公式為：f(key)=key mod p(p≤m)

mod是取模（求余數(shù)）的意思。事實(shí)上，這方法不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中后再取模。很顯然，本方法的關(guān)鍵就在于選擇合適的p，p如果選得不好，就可能會(huì)容易產(chǎn)生沖突。HashMap就采用了這種方法（利用位運(yùn)算代替取模運(yùn)算，提高程序的計(jì)算效率）。需要注意的是，只有在特定情況下，位運(yùn)算才可以轉(zhuǎn)換成取模運(yùn)算（當(dāng) b = 2^n 時(shí)，a % b = a & (b - 1) ）。

因此根據(jù)前輩們的經(jīng)驗(yàn)，若散列表表長(zhǎng)為m，通常p為小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。

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

選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。也就是：f(key)=random(key)

這里random是隨機(jī)函數(shù)。當(dāng)關(guān)鍵字的長(zhǎng)度不等時(shí)，采用這個(gè)方法構(gòu)造散列函數(shù)是比較合適的。

總之，現(xiàn)實(shí)中，應(yīng)該視不同的情況采用不同的散列函數(shù)。我們只能給出一些考慮的因素來(lái)提供參考：

1.計(jì)算散列地址所需的時(shí)間。

2.關(guān)鍵字的長(zhǎng)度。

3.散列表的大小。

4.關(guān)鍵字的分布情況。

5.記錄查找的頻率。

綜合這些因素，才能決策選擇哪種散列函數(shù)更合適。

3 散列沖突的解決

設(shè)計(jì)得再好的散列函數(shù)也不可能完全避免沖突。對(duì)無(wú)論以何種散列函數(shù)構(gòu)建的散列表，還必須考慮如何處理散列沖突。常見(jiàn)方法有以下幾種：

• 使用輔助數(shù)據(jù)結(jié)構(gòu)：分離鏈接法/鏈地址法/拉鏈法
• 不使用輔助數(shù)據(jù)結(jié)構(gòu)：開(kāi)放定址法（線性探測(cè)、平方探測(cè)、雙散列）
• 再散列

3.1 分離鏈接法

在存儲(chǔ)數(shù)據(jù)的過(guò)程中，如果發(fā)生沖突，可以利用單鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù)，訪問(wèn)的數(shù)組下標(biāo)元素作為鏈表的頭部。這種解決沖突的方法被稱(chēng)為“分離鏈接法”，又被稱(chēng)為分離鏈接法、拉鏈法?？梢韵胂?，除了鏈表之外，其他輔助結(jié)構(gòu)都能解決沖突現(xiàn)象：二叉樹(shù)或者另一張散列表，如果采用鏈表來(lái)輔助解決散列沖突，并且散列函數(shù)設(shè)計(jì)的很好，那么鏈表應(yīng)該是比較短的，此時(shí)其他復(fù)雜的輔助結(jié)構(gòu)便不值得嘗試了。

如下圖，使用鏈地址法的散列表：

JDK1.8之前的HashMap就是使用的鏈表來(lái)處理散列沖突，為了降低鏈表過(guò)長(zhǎng)造成的遍歷性能損耗，在JDK1.8中采用鏈表+紅黑樹(shù)的方法來(lái)處理散列沖突，當(dāng)鏈表長(zhǎng)度大于8個(gè)時(shí)，轉(zhuǎn)換為紅黑樹(shù)，紅黑樹(shù)的查找效率明顯高于單鏈表的。而小于等于8個(gè)時(shí)，采用鏈表則完全可以接受，避免紅黑樹(shù)的復(fù)雜結(jié)構(gòu)。

3.2 開(kāi)放定址法

開(kāi)放定址法的基本思路就是出現(xiàn)沖突時(shí)，通過(guò)另外的算法尋找其他空余的位置，因此不需要額外的輔助數(shù)據(jù)結(jié)構(gòu)，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。

開(kāi)放定址法法又可以分為線性探測(cè)法、平方探測(cè)法、雙散列法。

3.2.1 線性探測(cè)法(Linear Probing)

線性探測(cè)公式為：（H（key）+di）％ m；其中H（key）為哈希函數(shù)，m 為表長(zhǎng)-1，di為一個(gè)增量序列（di=0,1,2,3...,m-1）。

線性探測(cè)法的主要思想是：當(dāng)發(fā)生碰撞時(shí)（一個(gè)鍵被散列到一個(gè)已經(jīng)有鍵值對(duì)的數(shù)組位置），我們會(huì)檢查數(shù)組的下一個(gè)位置，這個(gè)過(guò)程被稱(chēng)作線性探測(cè)。線性探測(cè)可能會(huì)產(chǎn)生三種結(jié)果：

• 命中：該位置的鍵與要查找的鍵相同；
• 未命中：該位置為空；
• 該位置的鍵和被查找的鍵不同。

當(dāng)我們查找某個(gè)鍵時(shí)，首先通過(guò)散列函數(shù)得到一個(gè)數(shù)組索引后，之后我們就開(kāi)始檢查相應(yīng)位置的鍵是否與給定鍵相同，若不同則繼續(xù)查找（若到數(shù)組末尾也沒(méi)找到就折回?cái)?shù)組開(kāi)頭），直到找到該鍵或遇到一個(gè)空位置。由線性探測(cè)的過(guò)程我們可以知道，若數(shù)組已滿(mǎn)的時(shí)候我們?cè)傧蚱渲胁迦胄骆I，會(huì)陷入無(wú)限循環(huán)之中。

3.2.2 平方探測(cè)法

如果散列函數(shù)選的不是那么的好，可能導(dǎo)致沖突不斷出現(xiàn)。如果先存入key1，能夠找到某個(gè)空余位置存入，存入key2時(shí)與key1沖突，此時(shí)被存入到key1的下一個(gè)位置，后來(lái)key3又與它們發(fā)生散列沖突……這樣就出現(xiàn)了關(guān)鍵字聚集在某一區(qū)域的情況，即出現(xiàn)了數(shù)據(jù)聚集的現(xiàn)象。

一種解決方法是，增大di的增量：（H（key）+di²）％ m（di=0,1,2,3...,m/2）

增加平方運(yùn)算的目的是為了不讓關(guān)鍵字都聚集在某一塊區(qū)域。我們稱(chēng)這種方法為平方探測(cè)法。

如果m—表長(zhǎng)-1不為素?cái)?shù)，那么備選單元的數(shù)量將會(huì)減少，造成散列沖突的可能性就會(huì)大大增加。

3.2.3 雙散列法

準(zhǔn)備兩個(gè)散列函數(shù)。雙散列一般公式為：F(i)= i * hash2(x)，意思是用第二個(gè)散列函數(shù)算出x的散列值，然后在距離hash2(x)，2hash2(x)的地方探測(cè)。

3.3 再散列法

前面的鏈地址法和開(kāi)放定址法都是為了讓散列表中的元素分布的更加合理，但是散列表空間總有用完的時(shí)候，甚至當(dāng)它們的散列表填充元素過(guò)多時(shí)，都會(huì)增大發(fā)生散列沖突的概率。這里的再散列法就是計(jì)算出什么時(shí)候讓散列表進(jìn)行擴(kuò)展以及在散列表擴(kuò)展的時(shí)候，如何讓原來(lái)的元素在新的空間中合理的分布。

一般方法是：當(dāng)散列表的元素足夠的多時(shí)，建立另外一個(gè)大約兩倍大的表，再用一個(gè)新的散列函數(shù)，掃描整個(gè)原始表然后按照新的映射插入到新的表里，這就是再散列。其開(kāi)銷(xiāo)非常大，因?yàn)樯婕暗剿性氐囊苿?dòng)。

再散列的觸發(fā)條件通常有：只要表有一半滿(mǎn)了就做、只有當(dāng)插入失敗時(shí)才做（這種比較極端）、當(dāng)表到達(dá)某個(gè)擴(kuò)容因子時(shí)再做。第三種是較好的方法，HashMap就是用的這種方法。

散列表的擴(kuò)容因子： 所謂的擴(kuò)容因子α=填入表中的記錄個(gè)數(shù)/散列表長(zhǎng)度，α標(biāo)志著散列表的裝滿(mǎn)的程度。一般來(lái)說(shuō)，當(dāng)元素?cái)?shù)量達(dá)到設(shè)定的擴(kuò)容因子的數(shù)量時(shí)，就表示可以進(jìn)行再散列擴(kuò)容了，也叫裝填因子。因此一個(gè)合理的擴(kuò)容因子非常重要。α越大，產(chǎn)生沖突的可能性就越大；α越小，產(chǎn)生沖突的可能性就越小，但是造成了空間浪費(fèi)。JDK1.8的HasmMap裝填因子默認(rèn)為0.75。

4 散列表的簡(jiǎn)單實(shí)現(xiàn)

JDK已經(jīng)提供了現(xiàn)成的散列表實(shí)現(xiàn)，比如著名的HashMap。JDK1.8的HashMap是采用數(shù)組+鏈表+紅黑樹(shù)來(lái)實(shí)現(xiàn)的。散列函數(shù)采用基于hashcode()的去除留余法，并且采用分離鏈接法和再散列法的散列沖突解決辦法。

這里提供另一種采用線性探測(cè)的散列表的Java簡(jiǎn)單實(shí)現(xiàn)，從下面的實(shí)現(xiàn)上可以看出來(lái)，實(shí)際上線性探測(cè)的散列表效率并不高，并且產(chǎn)生了數(shù)據(jù)聚集，但是JDK中也有使用線性探測(cè)實(shí)現(xiàn)的散列表類(lèi)，比如ThreadLocal中的ThreadLocalMap，因?yàn)榫€性探測(cè)的實(shí)現(xiàn)比較簡(jiǎn)單。

/**
 * 基于線性探測(cè)法的散列表簡(jiǎn)單實(shí)現(xiàn)
 *
 * @param <K> key類(lèi)型
 * @param <V> value類(lèi)型
 */
public class LinearProbingHashMap<K, V> {

    /**
     * 存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)的數(shù)組
     */
    transient Entry<K, V>[] table;

    /**
     * 存儲(chǔ)的節(jié)點(diǎn)對(duì)象
     *
     * @param <K>
     * @param <V>
     */
    private static class Entry<K, V> implements Map.Entry<K, V> {
        /**
         * 保存hash值,避免重復(fù)計(jì)算
         */
        final int hash;
        /**
         * key值
         */
        final K key;
        /**
         * value值
         */
        V value;

        /**
         * 構(gòu)造器
         *
         * @param hash
         * @param key
         * @param value
         */
        private Entry(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        /*@Override
        public final String toString() {

            return hash + "=" + key + "=" + value;
        }*/
        @Override
        public final String toString() {

            return key + "=" + value;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        @Override
        public int hashCode() {
            return hash;
        }
    }

    /**
     * 散列表的容量,初始為16
     */
    private int capacity = 16;
    /**
     * 散列表節(jié)點(diǎn)數(shù)量
     */
    private int size;

    /**
     * 空構(gòu)造器,并不會(huì)初始化內(nèi)部數(shù)組
     */
    public LinearProbingHashMap() {
    }

    /**
     * 插入
     *
     * @param key   k
     * @param value v
     */
    public V put(K key, V value) {
        //初始化
        if (table == null) {
            table = new Entry[capacity];
        }
        //擴(kuò)容,這里判斷元素?cái)?shù)量大于等于0.75*capacity
        if (size >= capacity * 0.75) {
            resize(2 * capacity);
        }
        int hash = hash(key);
        //計(jì)算應(yīng)該插入的數(shù)組元素下標(biāo)
        int position = hash & (capacity - 1);
        //插入邏輯,總會(huì)成功
        while (true) {
            if (table[position] == null) {
                table[position] = new Entry<>(hash, key, value);
                size++;
                break;
                //判斷是否是重復(fù)的key,這里使用hash值和==判斷
            } else if (hash == table[position].hashCode() && table[position].getKey() == key) {
                return table[position].setValue(value);
            }
            position = nextIndex(position, capacity);
        }
        return null;
    }

    /**
     * 查找
     *
     * @param key 要查找的key
     * @return 查找到的value
     */
    public V get(K key) {
        if (table == null) {
            return null;
        }
        //計(jì)算出key對(duì)應(yīng)的數(shù)組位置
        int position = hash(key) & (capacity - 1);
        //如果該位置不為null,則開(kāi)始查找連續(xù)的元素
        if (table[position] != null) {
            do {
                if (table[position].getKey() == key) {
                    return table[position].getValue();
                }
                position = nextIndex(position, capacity);
            } while (table[position] != null);
        }
        return null;
    }


    /**
     * 刪除元素
     *
     * @param key 查找的元素
     * @return 被刪除的元素value;null不代表不是被刪除的value
     */
    public V delete(K key) {
        if (table == null) {
            return null;
        }
        //計(jì)算出key對(duì)應(yīng)的數(shù)組位置
        int position = hash(key) & (capacity - 1);
        V value;
        //如果該位置不為null,則開(kāi)始查找連續(xù)的元素
        if (table[position] != null) {
            do {
                if (table[position].getKey() == key) {
                    //刪除元素
                    value = table[position].getValue();
                    table[position] = null;
                    size--;
                    //將后面的連續(xù)的元素全部重新插入
                    position = nextIndex(position, capacity);
                    Entry<K, V> positionEntry;
                    while ((positionEntry = table[position]) != null) {
                        table[position] = null;
                        size--;
                        put(positionEntry.getKey(), positionEntry.getValue());
                        position = nextIndex(position, capacity);
                    }
                    return value;
                }
                position = nextIndex(position, capacity);
            } while (table[position] != null);
        }
        return null;
    }

    public int size() {
        return size;
    }

    /**
     * 獲取hash值,不是直接取hash值,而是借鑒了HashMap的擾動(dòng)算法,這樣可以讓元素分布更加均勻
     *
     * @param key k
     * @return hash值
     */
    private int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 擴(kuò)容
     *
     * @param newCapacity 新容量
     */
    private void resize(int newCapacity) {
        if (newCapacity <= 0) {
            throw new StackOverflowError("容量超出最大容量");
        }
        this.capacity = newCapacity;
        Entry<K, V>[] oldTab = table;
        table = new Entry[capacity];
        for (Entry<K, V> e : oldTab) {
            if (e != null) {
                int position = e.hashCode() & (capacity - 1);
                while (table[position] != null) {
                    position = nextIndex(position, capacity);
                }
                table[position] = e;
            }
        }
    }

    /**
     * 下一個(gè)位置
     *
     * @param i   當(dāng)前位置
     * @param len 數(shù)組長(zhǎng)度
     * @return 下一個(gè)位置, 此處包含循環(huán)的邏輯循環(huán)
     */
    private static int nextIndex(int i, int len) {
        return ((i + 1 < len) ? i + 1 : 0);
    }


    @Override
    public String toString() {
        return "LinearProbingHashST{" +
                "table=" + Arrays.toString(table) +
                '}';
    }
}

4.1 測(cè)試

public class LinearProbingHashMapTest {
    public static void main(String[] args) {
        System.out.println("==========>插入一批元素");
        LinearProbingHashMap<Object, Object> objectObjectLinearProbingHashMap = new LinearProbingHashMap<>();
        objectObjectLinearProbingHashMap.put(49, 16);
        objectObjectLinearProbingHashMap.put("Aa", 1);
        objectObjectLinearProbingHashMap.put(34, 78);
        objectObjectLinearProbingHashMap.put(17, 85);
        //Aa與BB的hash值是一樣的
        objectObjectLinearProbingHashMap.put("BB", 2);
        objectObjectLinearProbingHashMap.put(36, 36);
        objectObjectLinearProbingHashMap.put(21, 37);
        objectObjectLinearProbingHashMap.put(9, 87);
        objectObjectLinearProbingHashMap.put("兓", 62);
        objectObjectLinearProbingHashMap.put(46, 43);
        objectObjectLinearProbingHashMap.put("呵呵", 3);
        objectObjectLinearProbingHashMap.put("嘻嘻", 4);
        System.out.println(objectObjectLinearProbingHashMap);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>刪除 BB");
        Object delete = objectObjectLinearProbingHashMap.delete("BB");
        System.out.println(delete);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>插入(46,44) 重復(fù)添加46,將會(huì)替換value");
        Object put = objectObjectLinearProbingHashMap.put(46, 44);
        System.out.println(put);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>插入null 將會(huì)嘗試添加到第一個(gè)元素");
        Object putNull = objectObjectLinearProbingHashMap.put(null, "nullnull");
        System.out.println(putNull);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>獲取null 對(duì)應(yīng)的value");
        Object o = objectObjectLinearProbingHashMap.get(null);
        System.out.println(o);

        System.out.println("==========>擴(kuò)容");
        objectObjectLinearProbingHashMap.put("BB", 5);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);

        System.out.println("==========>獲取BB 對(duì)應(yīng)的value");
        Object bb = objectObjectLinearProbingHashMap.get("BB");
        System.out.println(bb);

        System.out.println("==========>刪除 34");
        Object delete34 = objectObjectLinearProbingHashMap.delete(34);
        System.out.println(delete34);
        System.out.println("size:" + objectObjectLinearProbingHashMap.size());
        System.out.println(objectObjectLinearProbingHashMap);
    }
}

以上就是Java數(shù)據(jù)結(jié)構(gòu)之散列表詳解的詳細(xì)內(nèi)容，更多關(guān)于Java 散列表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論