哈希表概念

哈希表（散列表），是基于關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。

上面所提到的哈希函數是指：有一個對應關系 f ，使得每個關鍵字和結構中一個唯一的存儲位置相對應，這樣在查找時，我們不需要像傳統的查找算法那樣進行比較，而是根據這個對應關系 f 找到給定值K的像f（K）。

哈希函數與哈希表

• 這個hash函數并沒有什么統一標準，它的核心思想就是就是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。
• 這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數，這個消息可能是字符、數組、字符串等等。
• 再使用哈希表進行查詢的時候，就是再次使用哈希函數將key轉換為對應的數組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數組的定位性能進行數據定位。
• 擁有這樣的hash存儲結構的數據結構稱為散列表，或者叫哈希表。
• 哈希表一般基于數組實現，特定情況下結合鏈表，但是數組是哈希表基礎數據結構。

為什么要有哈希表呢？ 數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數據結構？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現方法，我接下來解釋的是最常用的一種方法

哈希算法

構造哈希函數的方法有很多。首先需要明確什么是“好” 的哈希算法。若對于關鍵字集合中的任一個關鍵字，經哈希函數映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數是均勻的（Uniform）哈希函數。換句話說，就是使關鍵字經過哈希函數得到一個“隨機的地址”，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。

一個hash函數需要滿足

接受一個單一的參數，這個參數可以是任何類型，但是只能是一個。

返回一個整型值(一般情況下)。

輸出的哈希地址均勻分布在整個地址區間中。

對于兩個相同的輸入，輸出必須相同。

對于兩個不同的輸入，輸出相同的概率需要做到非常小。

hash的計算不能過于復雜，時間復雜度盡可能地低。

既然自己想不到比較好的hash算法，我們就來看看別人是怎么做的吧，下面是一些常用的hash算法：

• 直接定址法 取key的線性函數值作為hash值，value = a * key + b,a,b為常數。這一類散列碼的特點是：對輸入為整型數據而言，不會產生下標沖突。不產生沖突當然是最完美的狀態，但是這種方式要求輸入的key遵循一定的線性規律。

例如：有一個01到07的部門人數統計表，其中，部門編號作為關鍵字，哈希函數取關鍵字自身。如下表所示：

地址01020304050607部門01020304050607人數23432465643346

這樣若要詢問01部門有多少人，則只要查表的第01項即可。由于直接定址所得的地址集合和關鍵字集合的大小相同。因此，對于不同的關鍵字不會發生沖突，但是實際中能使用這種哈希函數的情況很少。

• 除留余數法 除留余數法：假設數組的長度為l，value = key % l,這一種散列碼實現簡單，運用比較多，但是如果輸入的元素集合不具有一定的規律，比較容易產生沖突。數組的長度最好是質數，被除數為質數在一定程度上可以緩解數據堆積的問題。

除留余數法此方法為最常用的構造散列函數方法。對于散列表長為m的散列函數公式為： f( key ) = key mod p ( p ≤ m )

mod是取模（求余數）的意思。事實上，這方法不僅可以對關鍵字直接取模，也可在折疊、平方取中后再取模。

顯然在這里選取p的值至為關鍵，那么選取p值多少為合適呢？下面我們來舉個例子看看：有一個關鍵字，它有7個記錄。如果采用除留余數法，那么可以先嘗試將散列函數設計為f(key) = key mod 7的方法。比如12 mod 7= 5，所以它存儲在下標為5的位置。

地址0123456關鍵字722917111248

不過這也是存在沖突的可能的，像7、14、21、28、35.....這些獲得的下標都為零。

如何合理選取p值? 使用除留余數法的一個經驗是，若散列表表長為m，通常p為小于或等于表長（最好接近m)的最小質數或不包含小于20質因子的合數。 舉個例子： 某散列表的長度為100，散列函數H(k)=k%P,則P通常情況下最好選擇哪個作為p呢？答案是97。

• 數字分析法 數字分析法即對關鍵字進行分析，取關鍵字的若干位進行或者組合進行hash計算，這一類散列碼的特點是比較靈活，通常是結合其他hash函數來計算，可根據實際情況來做出調整，具有想當的靈活性。

有學生的生日數據如下：

學生序號012345學生生日1975.10.031975.11.231975.03.021975.07.121975.04.211975.02.15

經分析，第一位，第二位，第三位、第四位重復的可能性大，取這四位造成沖突的機會增加，所以盡量不取前四位，取后四位比較好。

• 隨機數法 選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即H（key）= random（key），其中random為隨機函數。通常，當關鍵字長度不等時采用此法構造哈希函數較恰當。
• 平方取中法 取關鍵字平方后中間幾位作哈希地址。適于關鍵字長度不統一的情況，而且對于元素連續的輸入，可以很好的將其散列均勻，而且相對于除法而言，乘法的執行速度更快，這個由硬件決定。
• 折疊法 將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址，這方法稱為折疊法。

例如：每一種西文圖書都有一個國際標準圖書編號，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10,000時，可采用此法構造一個四位數的哈希函數。

處理哈希沖突的方法

基本原則： 從hash函數的要求可以看到，事實上我們只能定義對于兩個不同的輸入，輸出相同的概率盡可能小。

• 開放地址法
  • 開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）其中，m為哈希表的表長。di是產生沖突的時候的增量序列。

（1）-di值可能為1,2,3,...m-1，稱線性探測再散列。如果di取1，則每次沖突之后，向后移動1個位置. （2）-di取值可能為1,-1,4,-4,9,-9,16,-16,...kk,-kk(k<=m/2）稱二次探測再散列。 （3）-di取值可能為偽隨機數列。稱偽隨機探測再散列。

例如，在長度為7的哈希表中已填有關鍵字分別為9、16的記錄（哈希函數 H(key) = key MOD 7），現有第2個記錄，其關鍵字為16，由哈希函數得到哈希地址為2，產生沖突。若用線性探測再散列方法處理，得到下一個地址為3，仍沖突，繼續算4，不沖突，填入哈希表。若用二次探測再散列，則應填入需要為1的位置。 線性探測再散列

地址0123456關鍵字91716

二次探測再散列

地址0123456關鍵字16917

• 多哈希法 設計多種哈希函數，可以避免沖突，但是沖突幾率還是有的，函數設計的越好或越多都可以將幾率降到最低。
• 拉鏈法 拉出一個動態鏈表代替靜態順序存儲結構，可以避免哈希函數的沖突，不過缺點就是鏈表的設計過于麻煩，增加了編程復雜度。此法可以完全避免哈希函數的沖突。

左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個鏈表的頭，當然這個鏈表可能為空，也可能元素很多。我們根據元素的一些特征把元素分配到不同的鏈表中去，也是根據這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

• 建立一個公共溢出區 這也是處理沖突的一種方法、假設哈希函數的值域為[ 0, m - 1 ]，則設向量HashTable[ 0..m - 1 ]為基本表，每個分量存放一個記錄，另設向量OverTable[0..v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數得到的哈希地址是什么，一旦發生沖突，都填入溢出表。

總結

優點：

• 不論哈希表中有多少數據，查找、插入、刪除（有時包括刪除）只需要接近常量的時間即0(1）的時間級。實際上，這只需要幾條機器指令。
• 哈希表運算得非常快，在計算機程序中，如果需要在一秒種內查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現也相對容易。
• 如果不需要有序遍歷數據，并且可以提前預測數據量的大小。那么哈希表在速度和易用性方面是無與倫比的。

缺點：

• 它是基于數組的，數組創建后難于擴展，某些哈希表被基本填滿時，性能下降得非常嚴重，所以程序員必須要清楚表中將要存儲多少數據（或者準備好定期地把數據轉移到更大的哈希表中，這是個費時的過程）。

總結

以上是生活随笔為你收集整理的ds哈希查找—二次探测再散列_大白话之哈希表和哈希算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。