預(yù)測未來的最好方法就是創(chuàng)造它💦

目錄

一、什么是Hash表

二、Hash沖突

三、Hash函數(shù)的構(gòu)造方法

? 1. 直接定址法
? 2. 除余法
? 3. 基數(shù)轉(zhuǎn)換法
? 4. 平方取中法
? 5. 折疊法
? 6. 移位法
? 7. 隨機(jī)數(shù)法

四、處理沖突方法

? 1. 開放地址法
?? ? 線性探測法
?? ? 雙散列函數(shù)法
? 2. 拉鏈法

---

一、什么是Hash表

??哈希表（Hash Table），也叫散列表，是一種根據(jù)關(guān)鍵字直接訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。它通過把關(guān)鍵字映射到哈希表中一個(gè)位置來訪問記錄，以加快查找的速度。

??哈希表是由哈希函數(shù)和數(shù)組組成的，通過哈希函數(shù)將關(guān)鍵字轉(zhuǎn)換成數(shù)組的下標(biāo)，然后把該關(guān)鍵字存儲在這個(gè)下標(biāo)所對應(yīng)的數(shù)組元素中，從而實(shí)現(xiàn)快速的查找、插入和刪除操作。

二、Hash沖突

??當(dāng)不同的關(guān)鍵字被映射到同一個(gè)數(shù)組下標(biāo)時(shí)，就發(fā)生了哈希沖突（Collision）。哈希表解決沖突的方式有多種，常見的方式是使用鏈?zhǔn)椒?#xff08;Chaining）和開放地址法（Open Addressing）。

三、Hash函數(shù)的構(gòu)造方法

??對于Hash函數(shù)的構(gòu)造，沒有特定的要求，所以方法很多，只是我們需要了解，什么樣的哈希函數(shù)，才叫好的Hash函數(shù)，這樣就便于我們根據(jù)實(shí)際情況來構(gòu)造合理的Hash函數(shù)。
??衡量一個(gè)哈希函數(shù)是否合理，是否是一個(gè)好的哈希函數(shù)，就看哈希函數(shù)對一組關(guān)鍵字所產(chǎn)生的沖突的頻率有多高，如果一個(gè)哈希函數(shù)能夠盡量的避免掉這些沖突，那么這個(gè)哈希函數(shù)就是一個(gè)好的哈希函數(shù)。

1. 直接定址法

??取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。即：
????H(key) = key 或 H(key) = a*key +b

2. 除余法

??以關(guān)鍵碼除以表元素總數(shù)后得到的余數(shù)為存儲地址

例:

對21，30，11三個(gè)數(shù)，利用k MOD 3的方式，求他們的哈希地址有:
21 MOD 3=0
30 MOD 3=0
11 MOD 3= 2

3. 基數(shù)轉(zhuǎn)換法

??將關(guān)鍵碼看作是某個(gè)基數(shù)制上的整數(shù)，然后將其轉(zhuǎn)換為另一基數(shù)制上的數(shù)，轉(zhuǎn)換后得到的數(shù)據(jù)就是存儲地址

例：
對21、30、11進(jìn)行基數(shù)轉(zhuǎn)換法求哈希地址。

假設(shè)這三個(gè)數(shù)看成是八進(jìn)制數(shù)(不一定是八進(jìn)制數(shù)，只是假設(shè))，轉(zhuǎn)成十進(jìn)制有:17、24、9

4. 平方取中法

??先通過求關(guān)鍵字的平方值擴(kuò)大相近數(shù)的差別，然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值。又因?yàn)橐粋€(gè)乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻。

例：
對:21、30、11進(jìn)行平方取中法求哈希地址(取中間的一位)。

21x21 = 441 ??4
30x30 = 900 ??0
11x11 = 121 ??2

5. 折疊法

??折疊法是一種常見的哈希函數(shù)構(gòu)造方法，其基本思想是將關(guān)鍵字分組后，每組相加、相乘或進(jìn)行異或運(yùn)算，然后得到一個(gè)總和值。最后，按照需求截取其中一段作為哈希值。

折疊法的具體實(shí)現(xiàn)方式如下：

1. 將關(guān)鍵字分成若干段，每段固定長度（通常為哈希表大小），不足時(shí)可以補(bǔ)0或者隨機(jī)數(shù)。

2. 對每段進(jìn)行相加、相乘或進(jìn)行異或運(yùn)算，得到一個(gè)中間值。

3. 所有中間值相加或相乘得到一個(gè)總和值。

4. 按照需求截取其中一段作為哈希值。

---

??假設(shè)我們要將數(shù)字 12345678 轉(zhuǎn)換成哈希值。為了方便起見，我們將其分成兩段，每段四個(gè)數(shù)字。由于 1234 和 5678 長度相同，可以直接采用加法或者乘法的方式計(jì)算中間值。

以下是一種可能的折疊法實(shí)現(xiàn)方法：

1. 將數(shù)字 12345678 分成兩段：1234 和 5678。

2. 將每段數(shù)字逆序排列得到 4321 和 8765。

3. 將每段數(shù)字相加或相乘得到中間值。

?例如，我們選擇將每段數(shù)字相加：

• 中間值 1：4+8=12；

• 中間值 2：3+7=10；

• 中間值 3：2+6=8；

• 中間值 4：1+5=6；

4. 將所有中間值相加得到總和值：12+10+8+6=36。

5. 按照需求截取其中一段作為哈希值。假設(shè)哈希表大小為 10，因此選擇取總和值的最后一位 6 作為哈希值。

因此，使用折疊法將數(shù)字 12345678 轉(zhuǎn)換成哈希值為 6。

6. 移位法

??將關(guān)鍵碼分為多段，左邊的段右移，右邊的段左移，然后將它們疊加。和折疊法相似。

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

??隨機(jī)數(shù)法是一種基于隨機(jī)數(shù)的哈希函數(shù)構(gòu)造方法，它主要通過將關(guān)鍵字和一個(gè)在某個(gè)范圍內(nèi)隨機(jī)生成的常數(shù)進(jìn)行運(yùn)算，從而得到一個(gè)哈希值。這種方法的優(yōu)勢在于對大部分?jǐn)?shù)據(jù)集都能夠提供比較均勻的哈希分布。

??假設(shè)我們有一個(gè)數(shù)字 666，現(xiàn)在我們想要將它映射為某個(gè)哈希表中的桶號，我們可以按照以下步驟進(jìn)行：

1. 選取一個(gè)隨機(jī)數(shù)，假設(shè)為 x；

2. 對于 666這個(gè)數(shù)字，將它與 x 相乘得到一個(gè)新的數(shù)字；

3. 將這個(gè)新的數(shù)字除以桶的數(shù)量，然后將余數(shù)作為桶號返回即可。

例如，我們選取 x = 9876，并且哈希表中總共有 100 個(gè)桶。那么，使用隨機(jī)數(shù)法將 666映射到相應(yīng)的桶號的過程如下：

1. x = 9876

2. new_key = 666* 9876 = 6577416

3. bucket_id = new_key % 100 = 16

因此，在桶數(shù)量為 100 ，隨機(jī)數(shù)為 9876 的情況下，數(shù)字 666的哈希值為 16。

需要注意的是，如果隨機(jī)數(shù)選擇不當(dāng)，也有可能會導(dǎo)致哈希沖突，因此在實(shí)際應(yīng)用中需要根據(jù)具體情況選擇合適的隨機(jī)數(shù)，并且根據(jù)哈希鍵值的特征做出相應(yīng)的調(diào)整。

四、處理沖突方法

??哈希函數(shù)在將關(guān)鍵字映射到桶中時(shí)，由于桶數(shù)量的限制和哈希函數(shù)本身的不可避免性質(zhì)，可能會出現(xiàn)多個(gè)關(guān)鍵字映射到同一個(gè)桶中的情況，即產(chǎn)生了哈希沖突。為了解決這種問題，常用的處理方法有以下幾種：

1. 開放地址法

??開放地址法是一種簡單有效的哈希沖突處理方法。當(dāng)發(fā)生哈希沖突時(shí)，就嘗試在哈希表中另外尋找空桶來存儲該關(guān)鍵字，通常包括線性探測法、雙散列函數(shù)法等方式，直到遇到空桶或達(dá)到最大探測次數(shù)為止。這種方法具有簡單、高效的特點(diǎn)，但是會導(dǎo)致集群化、二次聚集等問題。

1. 線性探測法
   ??線性探測法是一種應(yīng)用較為廣泛的哈希沖突解決方法。當(dāng)出現(xiàn)哈希沖突時(shí)，線性探測法會從當(dāng)前索引值往后順序查找下一個(gè)可以使用的空桶，并將新元素插入該空桶中。
   ??具體而言，當(dāng)哈希函數(shù)計(jì)算得到的桶已經(jīng)被占用（即存在沖突）時(shí)，線性探測法通過沿著連續(xù)下一位置的方式來尋找空閑的桶。假設(shè)當(dāng)前我們要插入的元素的哈希值為 h，則線性探測法的插入流程大致如下：

   1. 如果桶 h 為空，則將元素直接存儲到桶 h 中；

   2. 如果桶 h 不為空，則從桶 h 的下一項(xiàng)開始，依次檢查其后面所有的相鄰?fù)?#xff0c;直到找到一個(gè)空桶 k，然后將元素存儲在空桶 k 中；

   3. 如果從桶 h 開始，依次檢查完了哈希表中所有的桶，但是沒有找到空桶，則認(rèn)為哈希表已滿，此時(shí)需要進(jìn)行哈希表擴(kuò)容等操作才能繼續(xù)向其中添加元素。
      
      同時(shí)，在哈希表中查詢某個(gè)元素時(shí)，也需要采用類似的方式來進(jìn)行查找。具體而言，查詢時(shí)從哈希函數(shù)計(jì)算得到的初始桶 h 開始，逐個(gè)檢查當(dāng)前桶、其下一項(xiàng)、再下去的下一項(xiàng)等等直到查詢到的元素或者一個(gè)空桶為止。
      

需要注意，線性探測法雖然簡單，但是容易出現(xiàn)堆積和聚集的問題，導(dǎo)致哈希表的效率急劇降低。因此，在實(shí)際應(yīng)用中，如果采用了線性探測法作為哈希表存儲沖突處理的方法，就需要根據(jù)具體情況進(jìn)行調(diào)整，以避免這種問題的發(fā)生。

2. 雙散列函數(shù)法
   ??雙散列函數(shù)法也是一種常見的開放地址哈希表沖突解決方法，它通過構(gòu)造兩個(gè)不同的哈希函數(shù)，分別計(jì)算出可能的插入位置，以此來避免沖突，并且添加新元素時(shí)按照一個(gè)固定的步長，在空桶之間線性查找下一個(gè)可以使用的位置。
   ??具體來說，對于雙散列函數(shù)法，假設(shè)我們有兩個(gè)哈希函數(shù) h1、h2，在哈希表中查找第 i 個(gè)關(guān)鍵字時(shí)，計(jì)算其哈希值有兩種方式：

   1. 計(jì)算第一層哈希：h1(key)=ih1?(key)=i
      如果第 h1(i) 個(gè)桶為空，則將關(guān)鍵字存儲在該桶中。否則執(zhí)行第二步；

   2. 計(jì)算第二層哈希：h2(key)=1+(imod??m?1)h2?(key)=1+(imodm?1)
      從第 h2(i) 個(gè)桶開始向后順序查找空桶，直到找到空桶并將新元素存儲在該處。

其中，步驟 2 中的 「1」可理解為步長，這里常常選擇m - 1作為其值，m 表示哈希表的桶數(shù)。這樣計(jì)算出的 h2(i) 內(nèi)部等于 i+1i+1 在模mm下的余數(shù)，使得整個(gè)哈希表能夠被覆蓋到，不會出現(xiàn)漏掉某些桶的情況。

2. 拉鏈法

??拉鏈法使用了鏈表數(shù)據(jù)結(jié)構(gòu)來解決哈希沖突。具體而言，對于哈希表中的每個(gè)桶，我們不再將其存儲單個(gè)元素，而是維護(hù)一個(gè)指向鏈表頭部的指針，這個(gè)鏈表包含了所有映射到該桶上的關(guān)鍵字。

例如：

對于關(guān)鍵字集合{4, 11, 16, 54}和桶數(shù) m=5，我們需要確定每一個(gè)關(guān)鍵字在哈希表中的存儲位置。

首先可以使用某個(gè)常見的哈希函數(shù)如：h(key)=key mod p，其中 p 是一個(gè)比 m 小的素?cái)?shù)，在這里 p=5。根據(jù)該哈希函數(shù)，我們可以求得各個(gè)關(guān)鍵字的哈希值：

h(4)=4 mod 5 = 4

h(11)=11 ?mod? 5 = 1

h(16)=16 ?mod ?5 = 1

h(54)=54 ?mod ?5 = 4

因?yàn)?11 和 16 的哈希值相同，它們屬于同一個(gè)桶，因此需要將它們分別插入到同一個(gè)鏈表中。最終，我們可以得到下面這張包含所有關(guān)鍵字的哈希表表示：

0	1	2	3	4
	11 -> 16			4 -> 54

其中，表格的每一列表示一個(gè)桶，在第 i 列中的元素都是哈希值為 i 的關(guān)鍵字列表。

在實(shí)際情況中哈希函數(shù)和桶數(shù)的選擇都需要經(jīng)過合理設(shè)計(jì)和評估，我們通常需要考慮許多因素如質(zhì)數(shù)選取、哈希函數(shù)效率、動態(tài)擴(kuò)容、負(fù)載因子等等以保證哈希表的正常運(yùn)行。