哈希表大總結

哈希表總結

目錄

• ​​哈希表總結​​

• ​​哈希表​​
• ​​哈希表不可避免沖突（collision）現象：​​

• ​​散清單查找步驟​​

• ​​哈希函數的特殊性:​​
• ​​散列函數構造方法​​

• ​​直接定址法:​​
• ​​數字分析法​​
• ​​折疊法​​
• ​​除法散列法​​
• ​​乘法散列法​​
• ​​平方取中法​​
• ​​随機數法​​

• ​​處理散列沖突的方法​​

• ​​開放位址法​​

• ​​線性探測法​​
• ​​二次探測法​​
• ​​随機探測法​​

• ​​再哈希法​​
• ​​鍊位址法​​
• ​​公共溢出區法​​

• ​​散清單查找算法(線性探測法)​​
• ​​散清單性能分析​​

• ​​實際應用​​
• ​​總結:​​

哈希表

記錄的存儲位置和它的關鍵字之間建立一确定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。

因而查找時，隻需根據這個對應關系f找到給定值K的像f(K）。

若結構中存在關鍵字和K相等的記錄，則必定在f(K）的存儲位置上，由此不需要進行比較便可直接取得所查記錄。

在此，稱這個對應關系f為哈希函數，按這個思想建立的表為哈希表（又稱為雜湊法或散清單。

哈希表不可避免沖突（collision）現象：

• 對不同的關鍵字可能得到同一哈希位址 即key1≠key2，而hash(key1)=hash(key2）。
• 具有相同函數值的關鍵字對該哈希函數來說稱為同義詞（synonym）。
• 是以，在建造哈希表時不僅要設定一個好的哈希函數，而且要設定一種處理沖突的方法。
• 可如下描述哈希表：根據設定的哈希函數H(key）和所選中的處理沖突的方法，
• 将一組關鍵字映象到一個有限的、位址連續的位址集（區間）上并以關鍵字在位址集中的“象”作為相應記錄在表中的存儲位置，這種表被稱為哈希表。

散清單查找步驟

散清單(也叫哈希表,Hash table) ,是根據關鍵碼的值進行通路的資料結構.散清單的實作常常叫做散列（hasing）,散列是一種用于以常數平均時間執行插入,删除和查找的技術

整個散列過程分為兩步

1. 通過散列函數計算記錄的散列位址,并按照散列位址儲存該記錄

   無論什麼記錄我們都需要用同一個散列函數計算位址，然後再存儲。

2. 查找通過同樣的散列函數計算記錄的散列位址,按此散列位址通路該記錄.因為我們存和取的時候用的都是一個散列函數，是以結果肯定相同。

散列函數是什麼呢？

• 假設某個函數為f，使得存儲位置 = f (key)那樣我們就能通過查找關鍵字不需要比較就可獲得需要的記錄的存儲位置。這種存儲技術被稱為散列技術。散列技術是在通過記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系 f ,使得每個關鍵字 key 都對應一個存儲位置 f(key)

這裡的f就是我們所描述的哈希函數(散列函數),我們利用散列技術将記錄儲存在一塊連續的儲存空間中,這塊連續的儲存空間就是----(哈希)散列

對不同的關鍵字可能得到同一散列位址，即k1≠k2，而f(k1)=f(k2)，這種現象稱為沖（英語：Collision）。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。對于這種情況我們能找到有效的方法解決

哈希函數的特殊性:

建立哈希函數是必須遵循一下原則:

1. 必須一緻性

   無論什麼記錄我們都需要用同一個散列函數計算位址

2. 計算簡單

   在保證不哈希沖突的情況下,使得計算簡單,如果這個算法計算複雜，會耗費很多時間.散列函數的計算時間不應該超過其他查找技術與關鍵字的比較時間，不然的話我們幹嘛使用哈希技術了

3. 散列位址分布均勻

   讓散列位址盡量均勻分布在儲存空間中,這樣既保證了空間的有效性,有減少了處理沖突而消耗的時間

散列函數構造方法

直接定址法:

1. 取關鍵字或關鍵字的某個線性函數值為散列位址。
2. 即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函數叫做自身函數）。
3. 若其中H(key）中已經有值了，就往下一個找，直到H(key）中沒有值了，就放進去。

優點:

• 簡單,均勻,無沖突

應用場景：

• 需要事先知道關鍵字的分布情況，适合查找表較小且連續的情況

數字分析法

1. 該方法也是十分簡單的方法，就是分析我們的關鍵字，取其中一段，或對其位移，疊加，用作位址
2. 比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差别很大，如果用後面的數字來構成散列位址，則沖突的幾率會明顯降低。
3. 是以數字分析法就是找出數字的規律，盡可能利用這些資料來構造沖突幾率較低的散列位址。

優點：

• 簡單、均勻、适用于關鍵字位數較大的情況

應用場景：

• 關鍵字位數較大，知道關鍵字分布情況且關鍵字的若幹位較均勻

折疊法

1. 将關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列位址。
2. 比如我們的關鍵字是123456789，則我們分為三部分 123 ，456 ，789 然後将其相加得 1368 然後我們再取其後三位 368 作為我們的散列位址。

優點：

• 事先不需要知道關鍵字情況

應用場景：

• 适合關鍵字位數較多的情況

除法散列法

1. 在用來設計散列函數的除法散列法中,通過取key除p的餘數,将關鍵字映射到某一個上,對于散清單長度為 m 的散列函數公式為
2. f(k) = k mod p (p <= m)

如

如果散清單長度為 12，即 m = 12 ，我們的參數 p 也設為12，那 k = 100時 f(k) = 100 % 12 = 4

我們隻需要做一次除法操作,是以除法散列法非常快

由上面的公式可以看出，該方法的重點在于 p 的取值，如果 p 值選的不好，就可能會容易産生同義詞(哈希沖突)。見下面這種情況。我們哈希表長度為6，我們選擇6為p值，則有可能産生這種情況，所有關鍵字都得到了0這個位址數。

那我們在選用除法散列法時選取 p 值時應該遵循怎樣的規則呢？

1. m 不應為 2 的幂，因為如果 m = 2^p ，則 f(k) 就是 k 的 p 個最低位數字。例 12 % 8 = 4 ，12的二進制表示位1100，後三位為100。
2. 若散清單的長度為m,通常p為小于或者等于表長(接近)的最小質數或者包含不小于20質因子的合數

合數：合數是指在大于1的整數中除了能被1和本身整除外，還能被其他數（0除外）整除的數。

質因子：質因子（或質因數）在數論裡是指能整除給定正整數的質數。      

注：這裡的2，3，5為質因子

根據規則選擇 5 為 p 值，我們再來看。這時我們發現隻有 6 和 36 沖突，相對來說就好了很多。

優點:

• 計算效率高,靈活

應用場景:

• 不知道關鍵字分布情況

乘法散列法

構造散列函數的乘法散列法主要包含兩個步驟

• 用關鍵字 k 乘上常數 A(0 < A < 1)，并提取 k A 的小數部分
• 用 m 乘以這個值，再向下取整

散列函數為:

f (k) = ⌊ m(kA mod 1) ⌋

這裡的 kA mod 1 的含義是取 keyA 的小數部分，即 kA - ⌊kA⌋ 。

優點：對 m 的選擇不是特别關鍵一般選擇它為 2 的某個幂次（m = 2 ^ p ,p為某個整數）

應用場景：不知道關鍵字情況

平方取中法

• 這個方法就比較簡單了，假設關鍵字是 321，那麼他的平方就是 103041，再抽取中間的 3 位就是 030 或 304 用作散列位址。
• 再比如關鍵字是 1234 那麼它的平方就是 1522756 ，抽取中間 3 位就是 227 用作散列位址.

優點：

靈活，适用範圍廣泛

适用場景：

不知道關鍵字分布，而位數又不是很大的情況

随機數法

選擇一随機函數，取關鍵字的随機值作為散列位址，即H(key)=random(key)其中random為随機函數,通常用于關鍵字長度不等的場合。

處理散列沖突的方法

hash 函數之後發現關鍵字 key1 不等于 key2 ，但是 f(key1) = f(key2)，即有沖突，

開放位址法

一旦發生沖突,就會尋找下一個空的散列位址,隻要清單足夠大,空的散列位址總能找到,并将記錄存入,為了使用開放尋址法插入一個元素,需要連續檢查散清單,稱為探查,我們常用的有線性探測，二次探測，随機探測。

線性探測法

我們來看一個例子，我們的關鍵字集合為{12，67，56，16，25，37，22，29，15，47，48，21}，表長為12，我們再用散列函數 f(key) = key mod 12。

我們求出每個 key 的 f(key)見下表

我們檢視上表發現，前五位的 f(key) 都不相同，即沒有沖突，可以直接存入，但是到了第六位 f(37) = f(25) = 1,那我們就需要利用上面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2，這其實就是我們的訂包廂的做法。下面我們看一下将上面的所有數存入哈希表是什麼情況吧。

注：藍色為計算哈希值，紅色為存入哈希表

他第一次會落在下标為 10 的位置，那麼如果繼續使用線性探測的話，則需要通過不斷取餘後得到結果，資料量小還好，要是很大的話那也太慢了吧，但是明明他的前面就有一個空房間呀，如果向前移動隻需移動一次即可。

二次探測法

其實了解了我們的上個例子之後，這個一下就能整明白了，根本不用費腦子，這個方法就是更改了一下di的取值

注：這裡的是 -1^2 為負值 而不是 （-1)^2

是以對于我們的34來說，當di = -1時，就可以找到空位置了。

二次探測法的目的就是為了不讓關鍵字聚集在某一塊區域。另外還有一種有趣的方法，位移量采用随機函數計算得到，接着往下看吧.

随機探測法

大家看到這是不又有新問題了，剛才我們在散列函數構造規則的第一條中說

（1）必須是一緻的

我們 di 是随機生成的呀，這裡的随機其實是僞随機數，僞随機數含義為，我們設定随機種子相同，則不斷調用随機函數可以生成不會重複的數列，我們在查找時，用同樣的随機種子，它每次得到的數列是相同的，那麼相同的 di 就能得到相同的散列位址。

随機種子（Random Seed）是計算機專業術語，一種以随機數作為對象的以真随機數（種子）為初始條件的随機數。一般計算機的随機數都是僞随機數，以一個真随機數（種子）作為初始條件，然後用一定的算法不停疊代産生随機數      

再哈希法

這個方法其實也特别簡單，利用不同的哈希函數再求得一個哈希位址，直到不出現沖突為止。

f,(key) = RH,( key ) (i = 1,2,3,4……k)

這裡的RH就是不同的散列函數,可以把我們之前說的那些散列函數都用上,每當發生哈希沖突時就換一個散列函數，相信總有一個能夠解決沖突的。這樣的代價就是增加了計算時間

鍊位址法

1. key 不同 f(key) 相同的情況,我們将這些同義詞儲存在一個單連結清單,這種表叫做同義詞子表.散清單中隻儲存同義詞表的頭指針…
2. 關鍵字集合為{12，67，56，16，25，37，22，29，15，47，48，21}，表長為12，
3. 我們再用散列函數f(key) = key mod 12
4. 用了鍊位址法之後就在也不沖突,無論有多少沖突，我們隻需在同義詞子表中添加結點即可。下面我們看下鍊位址法的存儲情況。

鍊位址法雖然不能夠産生沖突,但是查找時需要周遊單連結清單的性能.

公共溢出區法

将有沖突的,放入到别的地方(溢出表),這樣你就有地方住了。我們為所有沖突的關鍵字建立了一個公共的溢出區來存放。

怎樣查找: 通過散列函數計算出散列位址後,先于基本表對比,如果不相等就到溢出表中順序查找.,對于沖突很少的情況性能還是非常高的

散清單查找算法(線性探測法)

首先需要定義散列清單的結構以及一些相關常數，

• elem代表散清單資料存儲數組
• count代表的是目前插入元素個數
• size代表哈希表容量
• NULLKEY散清單初始值
• 然後我們如果查找成功就傳回索引，如果不存在該元素就傳回元素不存在。
• 我們将哈希表初始化，為數組元素賦初值。

插入操作的具體步驟

1. 通過哈希函數(除法散列法),将key轉化為數組下标
2. 如果該下标中沒有元素,則插入,否則說明沖突,則利用線性探測法處理沖突

查找

1. 通過哈希函數(同輸入時一樣),将key轉化成為數組下标
2. 通過數組下标找到key值,如果key一緻,則查找成功,否則利用線性探測法繼續查找

blog.csdnimg.cn/img_convert/1684f4dd64d5c14d42e6cc624f68c6d2.png)

完整代碼

散清單性能分析

如果沒有沖突的話,散清單查找是效率最高的,時間複雜度為O(1),

散列查找的平均查找長度取決于哪些方面呢

1. 散列函數是否均勻

2. 處理沖突的方法

   比如我們線性探測有時會堆積，則不如二次探測法好，因為鍊位址法處理沖突時不會産生任何堆積，因而具有最佳的平均查找性能

3. 散清單的填裝因子

   裝填因子 α = 填入表中的記錄數 / 散清單長度

實際應用

什麼是檔案的hash值呢?

MD5-Hash-檔案的數字文摘通過Hash函數計算得到。不管檔案長度如何，它的Hash函數計算結果是一個固定長度的數字。與​​加密算法​​不同，這一個Hash算法是一個不可逆的單向函數。采用安全性高的Hash算法，如MD5、SHA時，兩個不同的檔案幾乎不可能得到相同的Hash結果。是以，一旦檔案被修改，就可檢測出來。

總結:

• 一般的線性表、樹中，記錄在結構中的相對位置是随機的即和記錄的關鍵字之間不存在确定的關系，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較”的基礎上，查找的效率與比較次數密切相關。理想的情況是能直接找到需要的記錄，是以必須在記錄的存儲位置和它的關鍵字之間建立一确定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。因而查找時，隻需根據這個對應關系f找到給定值K的像f(K）。若結構中存在關鍵字和K相等的記錄，則必定在f(K）的存儲位置上，由此不需要進行比較便可直接取得所查記錄。在此，稱這個對應關系f為​​哈希函數​​​，按這個思想建立的表為哈希表（又稱為雜湊法或​​散清單​​）。
• 哈希表不可避免沖突（collision）現象：對不同的關鍵字可能得到同一哈希位址 即key1≠key2，而hash(key1)=hash(key2）。具有相同函數值的關鍵字對該​​哈希函數​​​來說稱為同義詞（synonym）。是以，在建造哈希表時不僅要設定一個好的​​哈希函數​​​，而且要設定一種處理沖突的方法。可如下描述哈希表：根據設定的​​哈希函數​​​H(key）和所選中的處理沖突的方法，将一組​​關鍵字​​映象到一個有限的、位址連續的位址集（區間）上并以關鍵字在位址集中的“象”作為相應記錄在表中的存儲位置，這種表被稱為哈希表。
• 對于動态​​查找表​​​而言，1) 表長不确定；2）在設計查找表時，隻知道關鍵字所屬範圍，而不知道确切的關鍵字。是以，一般情況需建立一個函數關系，以f(key）作為關鍵字為key的錄在表中的位置，通常稱這個函數f(key）為​​哈希函數​​。（注意：這個函數并不一定是數學函數）
• ​​哈希函數​​是一個映象，即：将關鍵字的集合映射到某個位址集合上，它的設定很靈活，隻要這個位址集合的大小不超出允許範圍即可。
• 現實中​​哈希函數​​是需要構造的，并且構造的好才能使用的好。
• 用途：加密，解決沖突問題。