柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)-哈希表

http://yzkb.51969.com/

一、哈希概念

1.?哈希表

哈希表（Hash Table）：也叫做散列表。是根據(jù)關(guān)鍵碼值（Key Value）直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。

哈希表通過「鍵 key 」和「映射函數(shù) Hash(key) 」計(jì)算出對(duì)應(yīng)的「值 value」，把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做「哈希函數(shù)（散列函數(shù)）」，存放記錄的數(shù)組叫做「哈希表（散列表）」。

1.1 散列表目的與特性

數(shù)組的最大特點(diǎn)：尋址容易，插入和刪除困難；

鏈表的特點(diǎn)正好相反：尋址困難，而插入和刪除操作容易。

哈希表的特點(diǎn)：尋址插入和刪除操作都容易。

那么如果能夠結(jié)合兩者的優(yōu)點(diǎn)，做出一種尋址、插入和刪除操作同樣快速容易的數(shù)據(jù)結(jié)構(gòu)，那該有多好，這就是哈希表創(chuàng)建的基本思想，哈希表就是這樣一個(gè)集查找、插入和刪除操作于一身的數(shù)據(jù)結(jié)構(gòu)。

1.2?哈希表的關(guān)鍵思想

哈希表的關(guān)鍵思想是使用哈希函數(shù)，將鍵 key 映射到對(duì)應(yīng)表的某個(gè)區(qū)塊中。我們可以將算法思想分為兩個(gè)部分：

向哈希表中插入一個(gè)關(guān)鍵碼值：哈希函數(shù)決定該關(guān)鍵字的對(duì)應(yīng)值應(yīng)該存放到表中的哪個(gè)區(qū)塊，并將對(duì)應(yīng)值存放到該區(qū)塊中。在哈希表中搜索一個(gè)關(guān)鍵碼值：使用相同的哈希函數(shù)從哈希表中查找對(duì)應(yīng)的區(qū)塊，并在特定的區(qū)塊搜索該關(guān)鍵字對(duì)應(yīng)的值。

1.3?哈希表的實(shí)現(xiàn)

例如：數(shù)據(jù)集合{1，7，6，4，5，9}；

哈希函數(shù)設(shè)置為：hash(key) = key % capacity

capacity為存儲(chǔ)元素底層空間總的大小。

哈希表在生活中的應(yīng)用也很廣泛，其中一個(gè)常見例子就是「查字典」。

比如為了查找 贊 這個(gè)字的具體意思，我們?cè)谧值渲懈鶕?jù)這個(gè)字的拼音索引 zan，查找到對(duì)應(yīng)的頁碼為 599。然后我們就可以翻到字典的第 599 頁查看贊字相關(guān)的解釋了。

?

在這個(gè)例子中：

存放所有拼音和對(duì)應(yīng)地址的表可以看做是「哈希表」。

贊字的拼音索引zan可以看做是哈希表中的「關(guān)鍵字 key」。

根據(jù)拼音索引zan來確定字對(duì)應(yīng)頁碼的過程可以看做是哈希表中的「哈希函數(shù) Hash(key)」。

查找到的對(duì)應(yīng)頁碼599可以看做是哈希表中的「哈希地址 value」。

1.4 什么是 key?

key ：就是關(guān)鍵值的意思，在哈希表中的 key 值是不允許重復(fù)的，就說明它是唯一的，可以通過唯一的 key 來查找相應(yīng)的 value 值。

key - value：哈希表中的一對(duì)鍵值對(duì)； 一對(duì)鍵值對(duì)通過哈希函數(shù)獲得對(duì)應(yīng)下標(biāo)并映射到表中；

2. 哈希函數(shù)

哈希函數(shù)（Hash Function）：將哈希表中元素的關(guān)鍵鍵值映射為元素存儲(chǔ)位置的函數(shù)。

哈希函數(shù)是哈希表中最重要的部分。一般來說，哈希函數(shù)會(huì)滿足以下幾個(gè)條件：

哈希函數(shù)應(yīng)該易于計(jì)算，并且盡量使計(jì)算出來的索引值均勻分布。哈希函數(shù)計(jì)算得到的哈希值是一個(gè)固定長度的輸出值。

如果Hash(key1)不等于Hash(key2)，那么 key1、key2 一定不相等。

如果Hash(key1)等于Hash(key2)，那么 key1、key2 可能相等，也可能不相等（會(huì)發(fā)生哈希碰撞）。

在哈希表的實(shí)際應(yīng)用中，關(guān)鍵字的類型除了數(shù)字類，還有可能是字符串類型、浮點(diǎn)數(shù)類型、大整數(shù)類型，甚至還有可能是幾種類型的組合。一般我們會(huì)將各種類型的關(guān)鍵字先轉(zhuǎn)換為整數(shù)類型，再通過哈希函數(shù)，將其映射到哈希表中。

而關(guān)于整數(shù)類型的關(guān)鍵字，通常用到的哈希函數(shù)方法有：直接定址法、除留余數(shù)法、平方取中法、基數(shù)轉(zhuǎn)換法、數(shù)字分析法、折疊法、隨機(jī)數(shù)法、乘積法、點(diǎn)積法等。

2.1 直接定址法

直接定址法：取關(guān)鍵字本身 / 關(guān)鍵字的某個(gè)線性函數(shù)值 作為哈希地址。

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

這種方法計(jì)算最簡單，且不會(huì)產(chǎn)生沖突。適合于關(guān)鍵字分布基本連續(xù)的情況，如果關(guān)鍵字分布不連續(xù)，空位較多，則會(huì)造成存儲(chǔ)空間的浪費(fèi)。

舉一個(gè)例子，假設(shè)我們有一個(gè)記錄了從 1 歲到 100 歲的人口數(shù)字統(tǒng)計(jì)表。其中年齡為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身，如下表所示。

比如我們想要查詢 25 歲的人有多少，則只要查詢表中第 25 項(xiàng)即可。

優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突；

缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。

2.2 除留余數(shù)法

除留余數(shù)法：假設(shè)哈希表的表長為 m，取一個(gè)不大于 m 但接近或等于 m 的質(zhì)數(shù) p，利用取模運(yùn)算，將關(guān)鍵字轉(zhuǎn)換為哈希地址。即：Hash(key) = key % p，其中 p 為不大于 m 的質(zhì)數(shù)。

這也是一種簡單且常用的哈希函數(shù)方法。其關(guān)鍵點(diǎn)在于 p 的選擇。根據(jù)經(jīng)驗(yàn)而言，一般 p 取素?cái)?shù)或者 m，這樣可以盡可能的減少?zèng)_突。

比如我們需要將 7 個(gè)數(shù) [ 432, 5, 128, 193, 92, 111, 88 ] 存儲(chǔ)在 11 個(gè)區(qū)塊中（長度為 11 的數(shù)組），通過除留余數(shù)法將這 7 個(gè)數(shù)應(yīng)分別位于如下地址：

特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。

技巧：若設(shè)計(jì)的哈希表長為m，則一般取p≤m且為質(zhì)數(shù) （也可以是不包含小于20質(zhì)因子的合數(shù)）。

eg： 432 % 11 = 3

2.3 平方取中法

平方取中法：先通過求關(guān)鍵字平方值的方式擴(kuò)大相近數(shù)之間的差別，然后根據(jù)表長度，取關(guān)鍵字平方值的中間幾位數(shù)為哈希地址。

理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。

這種方法因?yàn)殛P(guān)鍵字平方值的中間幾位數(shù)和原關(guān)鍵字的每一位數(shù)都相關(guān)，所以產(chǎn)生的哈希地址也比較均勻，有利于減少?zèng)_突的發(fā)生。

3. 哈希沖突

哈希沖突（Hash Collision）：不同的關(guān)鍵字通過同一個(gè)哈希函數(shù)可能得到同一哈希地址，即 key1 ≠ key2，而 Hash(key1) = Hash(key2)，這種現(xiàn)象稱為哈希沖突。

理想狀態(tài)下，我們的哈希函數(shù)是完美的一對(duì)一映射，即一個(gè)關(guān)鍵字（key）對(duì)應(yīng)一個(gè)值（value），不需要處理沖突。但是一般情況下，不同的關(guān)鍵字 key 可能對(duì)應(yīng)了同一個(gè)值 value，這就發(fā)生了哈希沖突。

設(shè)計(jì)再好的哈希函數(shù)也無法完全避免哈希沖突。所以就需要通過一定的方法來解決哈希沖突問題。常用的哈希沖突解決方法主要是兩類：「開放地址法（Open Addressing）」 和 「鏈地址法（Chaining）」。

4. 哈希沖突解決辦法

4.1 開放地址法

開放地址法（Open Addressing）：指的是將哈希表中的「空地址」向處理沖突開放。當(dāng)哈希表未滿時(shí)，處理沖突時(shí)需要嘗試另外的單元，直到找到空的單元為止。

當(dāng)發(fā)生沖突時(shí)，開放地址法按照下面的方法求得后繼哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1)。

H(i) 是在處理沖突中得到的地址序列。即在第 1 次沖突（i = 1）時(shí)經(jīng)過處理得到一個(gè)新地址 H(1)，如果在 H(1) 處仍然發(fā)生沖突（i = 2）時(shí)經(jīng)過處理時(shí)得到另一個(gè)新地址 H(2) …… 如此下去，直到求得的 H(n) 不再發(fā)生沖突。Hash(key) 是哈希函數(shù)，m 是哈希表表長，對(duì)哈希表長取余的目的是為了使得到的下一個(gè)地址一定落在哈希表中。F(i) 是沖突解決方法，取法可以有以下幾種：

????????線性探測(cè)法

????????二次探測(cè)法

????????偽隨機(jī)數(shù)序列

舉個(gè)例子說說明一下如何用以上三種沖突解決方法處理沖突，并得到新地址 H(i)。例如，在長度為 11 的哈希表中已經(jīng)填有關(guān)鍵字分別為 28、49、18 的記錄（哈希函數(shù)為 Hash(key) = key % 11）?，F(xiàn)在將插入關(guān)鍵字為 38 的新紀(jì)錄。根據(jù)哈希函數(shù)得到的哈希地址為 5，產(chǎn)生沖突。接下來分別使用這三種沖突解決方法處理沖突。

4.1.1 使用線性探測(cè)法：得到下一個(gè)地址 H(1) = (5 + 1) % 11 = 6，仍然沖突；繼續(xù)求出 H(2) = (5 + 2) % 11 = 7，仍然沖突；繼續(xù)求出 H(3) = (5 + 3) % 11 = 8，8 對(duì)應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號(hào)為 8 的位置。

4.1.2 使用二次探測(cè)法：得到下一個(gè)地址 H(1) = (5 + 1*1) % 11 = 6，仍然沖突；繼續(xù)求出 H(2) = (5 - 1*1) % 11 = 4，4 對(duì)應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號(hào)為 4 的位置。

4.1.3 使用偽隨機(jī)數(shù)序列：假設(shè)偽隨機(jī)數(shù)為 9，則得到下一個(gè)地址 H(1) = (9 + 5) % 11 = 3，3 對(duì)應(yīng)的地址為空，處理沖突過程結(jié)束，記錄填入哈希表中序號(hào)為 3 的位置。

使用這三種方法處理沖突的結(jié)果如下圖所示：

例子：

例如表長為11的哈希表已經(jīng)填有關(guān)鍵字為17、60、29的記錄，現(xiàn)將一關(guān)鍵字為38的新記錄填入哈希表，利用上述三種方法得到的過程與結(jié)果分別如下：

4.2 鏈地址法

鏈地址法（Chaining）：將具有相同哈希地址的元素（或記錄）存儲(chǔ)在同一個(gè)線性鏈表中。

鏈地址法是一種更加常用的哈希沖突解決方法。相比于開放地址法，鏈地址法更加簡單。

我們假設(shè)哈希函數(shù)產(chǎn)生的哈希地址區(qū)間為 [0, m - 1]，哈希表的表長為 m。則可以將哈希表定義為一個(gè)有 m 個(gè)頭節(jié)點(diǎn)組成的鏈表指針數(shù)組 T。

這樣在插入關(guān)鍵字的時(shí)候，我們只需要通過哈希函數(shù) Hash(key) 計(jì)算出對(duì)應(yīng)的哈希地址 i，然后將其以鏈表節(jié)點(diǎn)的形式插入到以 T[i] 為頭節(jié)點(diǎn)的單鏈表中。在鏈表中插入位置可以在表頭或表尾，也可以在中間。在查詢關(guān)鍵字的時(shí)候，我們只需要通過哈希函數(shù) Hash(key) 計(jì)算出對(duì)應(yīng)的哈希地址 i，然后將對(duì)應(yīng)位置上的鏈表整個(gè)掃描一遍，比較鏈表中每個(gè)鏈節(jié)點(diǎn)的鍵值與查詢的鍵值是否一致

舉個(gè)例子來說明如何使用鏈地址法處理沖突。假設(shè)現(xiàn)在要存入的關(guān)鍵字集合 keys = [ 88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32 ]。再假定哈希函數(shù)為 Hash(key) = key % 13，哈希表的表長 m = 13，哈希地址范圍為 [ 0, m - 1 ]，即[ 0 , 12 ]。將這些關(guān)鍵字使用鏈地址法處理沖突，并按順序加入哈希表中（圖示為插入鏈表表尾位置），最終得到的哈希表如下圖所示：

相對(duì)于開放地址法，采用鏈地址法處理沖突要多占用一些存儲(chǔ)空間（主要是鏈節(jié)點(diǎn)占用空間）。但它可以減少在進(jìn)行插入和查找具有相同哈希地址的關(guān)鍵字的操作過程中的平均查找長度。這是因?yàn)樵阪湹刂贩ㄖ校容^的關(guān)鍵字都是具有相同哈希地址的元素，而在開放地址法中，待比較的關(guān)鍵字不僅包含具有相同哈希地址的元素，而且還包含哈希地址不相同的元素。

4.3 降低沖突率?

沖突率：新放入一個(gè)元素，它的沖突概率

負(fù)載因子：哈希表中已有的元素 / 哈希表的長度 (剛開始的時(shí)候沒有元素，不會(huì)沖突，隨著放入的元素越來越多，只要一直放入，總會(huì)讓沖突率達(dá)到 100%)

所以要把負(fù)載因子控制在一個(gè)閾值之下

負(fù)載因子 size / length ，我們要想將其控制到一個(gè)閾值之內(nèi)，要么減少 size，要么增大 length，但是減少 size 的情況我們一般不去考慮，那么就只有增加 length 這個(gè)方法，那么就要對(duì)哈希表進(jìn)行擴(kuò)容；一般將負(fù)載因子為 3 / 4 作為擴(kuò)容的臨界點(diǎn)；

5. 哈希表總結(jié)

哈希表（Hash Table）：通過鍵 key 和一個(gè)映射函數(shù) Hash(key) 計(jì)算出對(duì)應(yīng)的值 value，把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。

哈希函數(shù)（Hash Function）：將哈希表中元素的關(guān)鍵鍵值映射為元素存儲(chǔ)位置的函數(shù)。

哈希沖突（Hash Collision）：不同的關(guān)鍵字通過同一個(gè)哈希函數(shù)可能得到同一哈希地址。

哈希表的兩個(gè)核心問題是：「哈希函數(shù)的構(gòu)建」 和 「哈希沖突的解決方法」。

常用的哈希函數(shù)方法有：直接定址法、除留余數(shù)法、平方取中法、基數(shù)轉(zhuǎn)換法、數(shù)字分析法、折疊法、隨機(jī)數(shù)法、乘積法、點(diǎn)積法等。

常用的哈希沖突的解決方法有兩種：開放地址法?和?鏈地址法。

6.比較對(duì)象相等時(shí)，hashCode與equals關(guān)系

a.hashCode相同他們的equals一定相同嗎：false

? ? ? 不同的key值可能對(duì)應(yīng)相同的hash值，有哈希沖突，此時(shí)對(duì)象的equals是不相等的。

b.equals相同的對(duì)象，他們的hashCode的值一定相同嗎：true

? ? ? equals同，key值同，所以hash的值肯定相同。

7. 哈希表的結(jié)構(gòu)

JDK1.8以前哈希表是由數(shù)組+鏈表組成

JDK1.8開始哈希表是由數(shù)組+鏈表+紅黑樹組成

加入紅黑樹的好處：

鏈表的特點(diǎn)是增刪快，查詢慢。所以鏈表越長就會(huì)導(dǎo)致查詢?cè)铰t黑樹恰好解決這一問題。

數(shù)組長度：未定義數(shù)組長度會(huì)創(chuàng)建一個(gè)初始化長度為16的數(shù)組。

8. 哈希表的擴(kuò)容

哈希表的底層數(shù)組會(huì)在一下兩種情況下擴(kuò)容：

當(dāng)同一索引值下的元素超過8個(gè)且數(shù)組長度小于64；數(shù)組的索引值占有率超過0.75時(shí)（0.75為加載因子，加載因子是可以自己設(shè)置的，0.75是默認(rèn)值）。

????????????????擴(kuò)容后的新容量就等于舊容量的二倍

可以借助下面的圖來理解：

如圖所示，當(dāng)數(shù)組長度為16，索引值0下面的元素超過8個(gè)，數(shù)組就會(huì)擴(kuò)容，數(shù)組長度變?yōu)?2，而索引值0會(huì)與索引值16平分索引值0下的元素。直到數(shù)組長度達(dá)到64，那么此時(shí)，索引值0會(huì)與索引值32平分，索引自16會(huì)與索引值48平分。

當(dāng)數(shù)組的長度大于64且同一索引值位置下元素超過8

二、哈希表的實(shí)現(xiàn)

1. 哈希表的新增

計(jì)算新增元素的哈希值。

用hash%數(shù)組長度，計(jì)算索引值。

判斷該索引值位置是否為空；

????????如果該索引值為空直接新增；

????????如果不為空，則判斷該索引值位置的元素是否重復(fù)；

????????????????如果不重復(fù)則新增到鏈表的最后。

????????????????如果重復(fù)則不新增；

2. 哈希表主要方法實(shí)現(xiàn)

首先創(chuàng)建Node 類，代表的是鏈表的結(jié)點(diǎn)；

public class Node {

public String key;

public Long value;

public Node next;

public Node(String key, Long value) {

this.key = key;

this.value = value;

}

}

再創(chuàng)建一個(gè) MyHashMap 類，來存放哈希表的屬性以及各種方法的實(shí)現(xiàn)

public class MyHashMap {

private static final double THRESHOLD = 0.75; // 擴(kuò)容的臨界值

// 元素類型是鏈表（以鏈表的頭結(jié)點(diǎn)代表）的數(shù)組

private Node[] array; // 數(shù)組的每個(gè)元素都代表一條獨(dú)立的鏈表

private int size;

public MyHashMap() {

array = new Node[7];

size = 0;

}

get() 方法

get() 方法是用來查找哈希表中的某個(gè)元素；

1.首先獲取 key 的 hashCode 值，將 key 轉(zhuǎn)化成一個(gè)整型，然后通過哈希，變?yōu)橐粋€(gè)合法的數(shù)組下標(biāo) index；

2.根據(jù) index 可以獲得一條鏈表；

3.遍歷鏈表，查找鏈表中的 key 是否和 傳入的 key 相等，若查詢到就返回該 key 的 value 值，否則返回 null；

public Long get(String key) {

int n = key.hashCode(); //獲取 key 的 hashCode 值

//把 n 這個(gè)整型轉(zhuǎn)換成一個(gè)合法的數(shù)組下標(biāo)（假設(shè) n >= 0)

int index = n % array.length;

// 我們已經(jīng)有了 index 這個(gè)下標(biāo)，所以，可以從數(shù)組中得到一條鏈表

// 這個(gè)鏈表的頭結(jié)點(diǎn)就是 array[index];

Node head = array[index];

//遍歷整條鏈表

for (Node cur = head; cur != null; cur = cur.next) {

// 比較 key 和 cur.key 是否相等

if (key.equals(cur.key)) { // 要用 equals 比較

// 查詢到就返回該 key 的 value 值

return cur.value;

}

}

// 說明鏈表都遍歷完了，也沒有找到 key，說明 key 不在哈希表中

// 返回 null，表示沒有找到

return null;

}

put() 方法

put() 方法就是在哈希表中放入或者修改某個(gè)數(shù)據(jù)的操作；

1.首先獲取 key 的 hashCode 值，將 key 轉(zhuǎn)化成一個(gè)整型，然后通過哈希，變?yōu)橐粋€(gè)合法的數(shù)組下標(biāo) index；

2.根據(jù) index 可以獲得一條鏈表；

3.遍歷鏈表，查找鏈表中的 key 與 傳入的 key 是否相等，相等則將原有的 value 值更新為傳入的 value，否則將傳入的 key - value 以頭插方式放入鏈表；

4.放入元素后 size++；

5.判斷是否需要擴(kuò)容；

public Long put(String key, Long value) {

// 放入 or 更新

//要求和 get 必須統(tǒng)一

int n = key.hashCode();

//要求和 get 必須統(tǒng)一

int index = n % array.length;

//得到代表鏈表的頭結(jié)點(diǎn)

Node head = array[index];

//遍歷鏈表，查找 key 是否存在（如果存在，則是更新操作；否則是放入操作）

for (Node cur = head; cur != null; cur = cur.next) {

if (key.equals(cur.key)) {

// 找到了說明存在，進(jìn)行更新操作

Long oldValue = cur.value;

cur.value = value;

return oldValue; // 返回原來的 value ，代表是更新

}

}

// 遍歷完成，沒有找到，則進(jìn)行插入操作

//把 key、value 裝到鏈表的結(jié)點(diǎn)中

Node node = new Node(key, value);

// 使用頭插

node.next = array[index];

array[index] = node;

//增加 size

size++;

//擴(kuò)容

if (1.0 * size / array.length > THRESHOLD) {

growCapacity();

}

//返回 null，代表插入

return null;

}

growCapacity() 擴(kuò)容方法

growCapacity() 方法就是再負(fù)載因子大于 3 / 4 時(shí)對(duì)哈希表進(jìn)行擴(kuò)容來保證沖突率控制在一定范圍以下；

1.考慮到擴(kuò)容以后，數(shù)組 length 變大，使得原來的元素的 index 會(huì)產(chǎn)生變化，所以需要把哈希表中的每一個(gè) key - value 對(duì)重新計(jì)算它的 index；

2.遍歷數(shù)組中的每個(gè)元素(每條鏈表)，再遍歷每個(gè)鏈表中的每個(gè)結(jié)點(diǎn)(每對(duì) key - value)，重新計(jì)算其 index；

3.一個(gè)個(gè)頭插元素，更新它們的 next 屬性；

private void growCapacity() {

//擴(kuò)大 length

Node[] newArray = new Node[array.length * 2];

for (int i = 0; i < array.length; i++) { // 遍歷數(shù)組中的每個(gè)元素（每條鏈表）

Node next;

for (Node cur = array[i]; cur != null; cur = next) { // 遍歷鏈表中的每個(gè)結(jié)點(diǎn)

int n = cur.key.hashCode();

int index = n % newArray.length; //重新計(jì)算 index

// 按照頭插的方式，將結(jié)點(diǎn)，插入到 newArray 的 [index] 位置的新鏈表中

next = cur.next; // 因?yàn)橐呀Y(jié)點(diǎn)插入到新鏈表中，所有 next 會(huì)變化

// 為了能讓老鏈表繼續(xù)遍歷下去，需要提前記錄老的 next

cur.next = newArray[index]; // 頭插

newArray[index] = cur;

}

}

array = newArray;

}

remove() 方法

remove() 方法就是再哈希表中查找某個(gè)元素并將其進(jìn)行刪除；

1.首先獲取 key 的 hashCode 值，將 key 轉(zhuǎn)化成一個(gè)整型，然后通過哈希化，變?yōu)橐粋€(gè)合法的數(shù)組下標(biāo) index；

2.根據(jù) index 可以獲得一條鏈表；

3.遍歷鏈表，若第一個(gè)結(jié)點(diǎn)就是要?jiǎng)h除的 key，那么直接讓頭結(jié)點(diǎn)變?yōu)榈谝粋€(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)；

4.若不是第一個(gè)結(jié)點(diǎn)，證明該結(jié)點(diǎn)有前驅(qū)結(jié)點(diǎn)，讓 pre.next = cur.next，然后返回刪除結(jié)點(diǎn)的 value；

5.若沒找到 key 那么就返回 null；

public Long remove(String key) {

// 刪除

int n = key.hashCode();

int index = n % array.length;

// 如果第一個(gè)結(jié)點(diǎn)的 key 就是要?jiǎng)h除的 key，沒有前驅(qū)結(jié)點(diǎn)

if (array[index] != null && key.equals(array[index].key)) {

Node head = array[index];

array[index] = array[index].next;

return head.value;

}

Node prev = null; //記錄前驅(qū)結(jié)點(diǎn)

Node cur = array[index];

while (cur != null) {

if (key.equals(cur.key)) {

// 刪除鏈表中的結(jié)點(diǎn)，需要前驅(qū)結(jié)點(diǎn)

prev.next = cur.next; // 刪除 cur 結(jié)點(diǎn)

return cur.value;

}

prev = cur;

cur = cur.next;

}

return null;

}

size() 方法

size() 方法就是獲取哈希表中元素個(gè)數(shù)的操作；

直接返回 size 即可

public int size() {

return size;

}

isEmpty() 方法

isEmpty() 方法是判斷哈希表是否為空；

直接判斷 size() 是否為 0

public boolean isEmpty() {

return size() == 0;

}

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)-哈希表

http://yzkb.51969.com/

推薦文章