『壹』 哈希查找演算法
散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函數，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散列表。
通過某種轉換關系，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以後查找的時間復雜度越小，空間復雜度越高。
Hash是一種典型以空間換時間的演算法，比如原來一個長度為100的數組，對其查找，只需要遍歷且匹配相應記錄即可，從空間復雜度上來看，假如數組存儲的是byte類型數據，那麼該數組佔用100byte空間。現在我們採用Hash演算法，我們前面說的Hash必須有一個規則，約束鍵與存儲位置的關系，那麼就需要一個固定長度的hash表，此時，仍然是100byte的數組，假設我們需要的100byte用來記錄鍵與位置的關系，那麼總的空間為200byte，而且用於記錄規則的表大小會根據規則，大小可能是不定的。
通過哈希函數，我們可以將鍵轉換為數組的索引(0-M-1)，但是對於兩個或者多個鍵具有相同索引值的情況，我們需要有一種方法來處理這種沖突。
一種比較直接的辦法就是，將大小為M 的數組的每一個元素指向一個鏈表，鏈表中的每一個節點都存儲散列值為該索引的鍵值對，這就是拉鏈法。下圖很清楚的描述了什麼是拉鏈法。
「John Smith」和「Sandra Dee」 通過哈希函數都指向了152 這個索引，該索引又指向了一個鏈表， 在鏈表中依次存儲了這兩個字元串。
單獨鏈表法：將散列到同一個存儲位置的所有元素保存在一個鏈表中（聚集），該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都盡可能的短小，以保證查找的效率。當鏈表過長、大量的鍵都會映射到相同的索引上，哈希表的順序查找會轉變為鏈表的查找，查找時間將會變大。對於開放定址會造成性能的災難性損失。
實現基於拉鏈表的散列表，目標是選擇適當的數組大小M，使得既不會因為空鏈表而浪費內存空間，也不會因為鏈表太而在查找上浪費太多時間。拉鏈表的優點在於，這種數組大小M的選擇不是關鍵性的，如果存入的鍵多於預期，那麼查找的時間只會比選擇更大的數組稍長。另外，我們也可以使用更高效的結構來代替鏈表存儲。如果存入的鍵少於預期，索然有些浪費空間，但是查找速度就會很快。所以當內存不緊張時，我們可以選擇足夠大的M，可以使得查找時間變為常數，如果內存緊張時，選擇盡量大的M仍能夠將性能提高M倍。
線性探測法是開放定址法解決哈希沖突的一種方法，基本原理為，使用大小為M的數組來保存N個鍵值對，其中M>N，我們需要使用數組中的空位解決碰撞沖突。如下圖所示：
對照前面的拉鏈法，在該圖中，「Ted Baker」 是有唯一的哈希值153的，但是由於153被「Sandra Dee」佔用了。而原先「Snadra Dee」和「John Smith」的哈希值都是152的，但是在對「Sandra Dee」進行哈希的時候發現152已經被佔用了，所以往下找發現153沒有被佔用，所以索引加1 把「Sandra Dee」存放在沒有被佔用的153上，然後想把「Ted Baker」哈希到153上，發現已經被佔用了，所以往下找，發現154沒有被佔用，所以值存到了154上。
單純論查找復雜度：對於無沖突的Hash表而言，查找復雜度為O(1)。
原文： 哈希查找 - 賣賈筆的小男孩 - 博客園 (cnblogs.com)
『貳』 什麼是哈希查找
哈希查找是為了快速查找記錄的一種演算法，它利用的數據結構是哈希表，即以空間換取時間的演算法，例如：在圖書館中，根據每個人的名字來查找個人信息（借書時間，名字等），這些信息存放於資料庫中，即物理存儲系統中，比如xiaozhang,哈希演算法可以是：把他的信息存放於把名字的每個字母之和的物理地址上，當然這是理想化的，肯定會比這個復雜的
『叄』 哈希表詳解
哈希表：即散列存儲結構。
散列法存儲的基本思想：建立記錄關鍵碼字與其存儲位置的對應關系，或者說，由關鍵碼的值決定數據的存儲地址。
這樣，不經過比較，一次存取就能得到所查元素的查找方法
優點：查找速度極快（O(1)）,查找效率與元素個數n無關！
哈希方法(雜湊法)
選取某個函數，依該函數按關鍵字計算元素的存儲位置並按此存放；查找時也由同一個函數對給定值k計算地址，將k與地址中內容進行比較，確定查找是否成功。
哈希函數(雜湊函數)
哈希方法中使用的轉換函數稱為哈希函數(雜湊函數).在記錄的關鍵碼與記錄的存儲地址之間建立的一種對應關系
有數據元素序列(14，23，39，9，25，11)，若規定每個元素k的存儲地址H（k）＝k ， H(k)稱為散列函數,畫出存儲結構圖。
根據散列函數H（k）＝k ，可知元素14應當存入地址為14的單元，元素23應當存入地址為23的單元，……，
根據存儲時用到的散列函數H(k)表達式，迅即可查到結果！
例如，查找key=9,則訪問H(9)=9號地址，若內容為9則成功；
若查不到，應當設法返回一個特殊值，例如空指針或空記錄。
很顯然這種搜索方式空間效率過低。
哈希函數可寫成：addr(ai)=H(ki)
選取某個函數，依該函數按關鍵字計算元素的存儲位置並按此存放；查找時也由同一個函數對給定值k計算地址，將k與地址中內容進行比較，確定查找是否成功。哈希方法中使用的轉換函數稱為哈希函數(雜湊函數).在記錄的關鍵碼與記錄的存儲地址之間建立的一種對應關系。
通常關鍵碼的集合比哈希地址集合大得多，因而經過哈希函數變換後，可能將不同的關鍵碼映射到同一個哈希地址上，這種現象稱為沖突。
有6個元素的關鍵碼分別為：（14，23，39，9，25，11）。
選取關鍵碼與元素位置間的函數為H(k)=k mod 7
根據哈希函數算出來發現同一個地址放了多個關鍵碼，也就是沖突了。
在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。
所以，哈希方法必須解決以下兩個問題：
1）構造好的哈希函數
（a）所選函數盡可能簡單，以便提高轉換速度；
（b）所選函數對關鍵碼計算出的地址，應在哈希地址內集中並大致均勻分布，以減少空間浪費。
2）制定一個好的解決沖突的方案
查找時，如果從哈希函數計算出的地址中查不到關鍵碼，則應當依據解決沖突的規則，有規律地查詢其它相關單元。
從上面兩個例子可以得出如下結論：
哈希函數只是一種映象，所以哈希函數的設定很靈活，只要使任何關鍵碼的哈希函數值都落在表長允許的范圍之內即可
沖突：key1≠key2，但H(key1)=H(key2)
同義詞：具有相同函數值的兩個關鍵碼
哈希函數沖突不可避免，只能盡量減少。所以，哈希方法解決兩個問題：
構造好的哈希函數；
制定解決沖突基本要求：
要求一：n個數據原僅佔用n個地址，雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。
要求二：無論用什麼方法存儲，目的都是盡量均勻地存放元素，以避免沖突。
Hash(key) = a·key + b (a、b為常數)
優點：以關鍵碼key的某個線性函數值為哈希地址，不會產生沖突.
缺點：要佔用連續地址空間，空間效率低。
例.關鍵碼集合為{100，300，500，700，800，900}，
選取哈希函數為Hash(key)=key/100，
則存儲結構（哈希表）如下：
Hash(key)=key mod p (p是一個整數)
特點：以關鍵碼除以p的余數作為哈希地址。
關鍵：如何選取合適的p？p選的不好，容易產生同義詞
技巧：若設計的哈希表長為m，則一般取p≤m且為質數
（也可以是合數，但不能包含小於20的質因子）。
Hash(key)= ⎣ B ( A key mod 1 ) ⎦
(A、B均為常數，且0<A<1，B為整數)
特點：以關鍵碼key乘以A，取其小數部分，然後再放大B倍並取整，作為哈希地址。
例：欲以學號最後兩位作為地址，則哈希函數應為：
H(k)=100 (0.01 k % 1 )
其實也可以用法2實現： H(k)=k % 100
特點：選用關鍵字的某幾位組合成哈希地址。選用原則應當是：各種符號在該位上出現的頻率大致相同。
例：有一組（例如80個）關鍵碼，其樣式如下：
討論：
① 第1、2位均是「3和4」，第3位也只有「 7、8、9」，因此，這幾位不能用，餘下四位分布較均勻，可作為哈希地址選用。
② 若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和後，取低兩位作哈希地址。
特點：對關鍵碼平方後，按哈希表大小，取中間的若干位作為哈希地址。(適於不知道全部關鍵碼情況)
理由：因為中間幾位與數據的每一位都相關。
例：2589的平方值為6702921，可以取中間的029為地址。
特點：將關鍵碼自左到右分成位數相等的幾部分（最後一部分位數可以短些），然後將這幾部分疊加求和，並按哈希表表長，取後幾位作為哈希地址。
適用於：關鍵碼位數很多,且每一位上各符號出現概率大致相同的情況。
法1：移位法 ── 將各部分的最後一位對齊相加。
法2：間界疊加法──從一端向另一端沿分割界來回折疊後，最後一位對齊相加。
例：元素42751896,
用法1： 427＋518＋96=1041
用法2： 427 518 96—> 724+518+69 =1311
7、隨機數法
Hash(key) = random ( key ) (random為偽隨機函數)
適用於：關鍵字長度不等的情況。造表和查找都很方便。
小結：構造哈希函數的原則：
① 執行速度（即計算哈希函數所需時間）；
② 關鍵字的長度；
③ 哈希表的大小；
④ 關鍵字的分布情況；
⑤ 查找頻率。
設計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，並將數據元素存入。
1）線性探測法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：
Hash(key)為哈希函數
m為哈希表長度
di 為增量序列 1，2，…m-1，且di=i
關鍵碼集為 {47，7，29，11，16，92，22，8，3}，
設：哈希表表長為m=11；
哈希函數為Hash(key)=key mod 11；
擬用線性探測法處理沖突。建哈希表如下：
解釋：
① 47、7是由哈希函數得到的沒有沖突的哈希地址；
② Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8為空，因此將29存入。
③ 另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。
其中3 還連續移動了（二次聚集）
線性探測法的優點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；
線性探測法的缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，……，
因此，可能出現很多元素在相鄰的哈希地址上「堆積」起來，大大降低了查找效率。
解決方案：可採用二次探測法或偽隨機探測法，以改善「堆積」問題。
2） 二次探測法
仍舉上例，改用二次探測法處理沖突，建表如下：
Hi=(Hash(key)±di) mod m
其中：Hash(key)為哈希函數
m為哈希表長度，m要求是某個4k+3的質數；
di為增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2
註：只有3這個關鍵碼的沖突處理與上例不同，
Hash(3)=3，哈希地址上沖突，由
H1=(Hash(3)+1 ^2) mod 11=4，仍然沖突；
H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希地址，存入。
3） 若di＝偽隨機序列，就稱為偽隨機探測法
基本思想：將具有相同哈希地址的記錄(所有關鍵碼為同義詞)鏈成一個單鏈表，m個哈希地址就設m個單鏈表，然後用一個數組將m個單鏈表的表頭指針存儲起來，形成一個動態的結構。
設{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函數為：
Hash(key)=key mod 11，
用拉鏈法處理沖突，則建表如圖所示。
Hi=RHi(key) i=1, 2, …，k
RHi均是不同的哈希函數，當產生沖突時就計算另一個哈希函數，直到沖突不再發生。
優點：不易產生聚集；
缺點：增加了計算時間。
思路：除設立哈希基本表外，另設立一個溢出向量表。
所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數得到的地址是什麼，一旦發生沖突，都填入溢出表。
明確：散列函數沒有「萬能」通式（雜湊法），要根據元素集合的特性而分別構造。
討論：哈希查找的速度是否為真正的O（1）？
不是。由於沖突的產生，使得哈希表的查找過程仍然要進行比較，仍然要以平均查找長度ASL來衡量。
一般地，ASL依賴於哈希表的裝填因子α,它標志著哈希表的裝滿程度。
0≤α≤1
α 越大，表中記錄數越多，說明表裝得越滿，發生沖突的可能性就越大，查找時比較次數就越多。
例 已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函數為：H(key)=key MOD 13, 哈希表長為m=16，
設每個記錄的查找概率相等
(1) 用線性探測再散列處理沖突，即Hi=(H(key)+di) MOD m
(2) 用二次探測再散列處理沖突，即Hi=(H(key)+di) MOD m
(3) 用鏈地址法處理沖突
1） 散列存儲的查找效率到底是多少？
答：ASL與裝填因子α有關！既不是嚴格的O(1)，也不是O(n)
2）「沖突」是不是特別討厭？
答：不一定！正因為有沖突，使得文件加密後無法破譯！（單向散列函數不可逆，常用於數字簽名和間接加密）。
利用了哈希表性質：源文件稍稍改動，會導致哈希表變動很大。
『肆』 哈希表如何存儲字元串
LZ 哈希表 貌似是一種查找方式吧
然後你弄個數組 鏈表什麼的存儲任何你想要存儲的數據
比如說 你可以將 jan 存儲在 array[j+a+n]中
要查找jan 時 就可以直接找到了了
輸入 jan 然後 查找那個存儲單元就好
『伍』 hash演算法原理詳解
散列方法的主要思想是根據結點的關鍵碼值來確定其存儲地址：以關鍵碼值K為自變數，通過一定的函數關系h(K)(稱為散列函數)，計算出對應的函數值來，把這個值解釋為結點的存儲地址，將結點存入到此存儲單元中。檢索時，用同樣的方法計算地址，然後到相應的單元里去取要找的結點。通過散列方法可以對結點進行快速檢索。散列（hash，也稱「哈希」）是一種重要的存儲方式，也是一種常見的檢索方法。
按散列存儲方式構造的存儲結構稱為散列表（hash table）。散列表中的一個位置稱為槽(slot)。散列技術的核心是散列函數(hash function)。 對任意給定的動態查找表DL，如果選定了某個「理想的」散列函數h及相應的散列表HT，則對DL中的每個數據元素X。函數值h（X.key）就是X在散列表HT中的存儲位置。插入（或建表）時數據元素X將被安置在該位置上，並且檢索X時也到該位置上去查找。由散列函數決定的存儲位置稱為散列地址。 因此，散列的核心就是：由散列函數決定關鍵碼值(X.key)與散列地址h(X.key)之間的對應關系，通過這種關系來實現組織存儲並進行檢索。
一般情況下，散列表的存儲空間是一個一維數組HT[M]，散列地址是數組的下標。設計散列方法的目標，就是設計某個散列函數h，0<=h( K ) < M；對於關鍵碼值K，得到HT[i] = K。 在一般情況下，散列表的空間必須比結點的集合大，此時雖然浪費了一定的空間，但換取的是檢索效率。設散列表的空間大小為M，填入表中的結點數為N，則稱為散列表的負載因子（load factor，也有人翻譯為「裝填因子」）。建立散列表時，若關鍵碼與散列地址是一對一的關系，則在檢索時只需根據散列函數對給定值進行某種運算，即可得到待查結點的存儲位置。但是，散列函數可能對於不相等的關鍵碼計算出相同的散列地址，我們稱該現象為沖突（collision），發生沖突的兩個關鍵碼稱為該散列函數的同義詞。在實際應用中，很少存在不產生沖突的散列函數，我們必須考慮在沖突發生時的處理辦法。
在以下的討論中，我們假設處理的是值為整型的關鍵碼，否則我們總可以建立一種關鍵碼與正整數之間的一一對應關系，從而把該關鍵碼的檢索轉化為對與其對應的正整數的檢索；同時，進一步假定散列函數的值落在0到M－1之間。散列函數的選取原則是：運算盡可能簡單；函數的值域必須在散列表的范圍內；盡可能使得結點均勻分布，也就是盡量讓不同的關鍵碼具有不同的散列函數值。需要考慮各種因素：關鍵碼長度、散列表大小、關鍵碼分布情況、記錄的檢索頻率等等。下面我們介紹幾種常用的散列函數。
顧名思義，除余法就是用關鍵碼x除以M（往往取散列表長度），並取余數作為散列地址。除余法幾乎是最簡單的散列方法，散列函數為： h(x) ＝ x mod M。
使用此方法時，先讓關鍵碼key乘上一個常數A (0< A < 1)，提取乘積的小數部分。然後，再用整數n乘以這個值，對結果向下取整，把它做為散列的地址。散列函數為： hash ( key ) = _LOW( n × ( A × key % 1 ) )。 其中，「A × key % 1」表示取 A × key 小數部分，即： A × key % 1 = A × key - _LOW(A × key), 而_LOW(X)是表示對X取下整
由於整數相除的運行速度通常比相乘要慢，所以有意識地避免使用除余法運算可以提高散列演算法的運行時間。平方取中法的具體實現是：先通過求關鍵碼的平方值，從而擴大相近數的差別，然後根據表長度取中間的幾位數（往往取二進制的比特位）作為散列函數值。因為一個乘積的中間幾位數與乘數的每一數位都相關，所以由此產生的散列地址較為均勻。
假設關鍵字集合中的每個關鍵字都是由 s 位數字組成 (u1, u2, …, us)，分析關鍵字集中的全體，並從中提取分布均勻的若干位或它們的組合作為地址。數字分析法是取數據元素關鍵字中某些取值較均勻的數字位作為哈希地址的方法。即當關鍵字的位數很多時，可以通過對關鍵字的各位進行分析，丟掉分布不均勻的位，作為哈希值。它只適合於所有關鍵字值已知的情況。通過分析分布情況把關鍵字取值區間轉化為一個較小的關鍵字取值區間。
舉個例子：要構造一個數據元素個數n=80,哈希長度m=100的哈希表。不失一般性，我們這里只給出其中8個關鍵字進行分析，8個關鍵字如下所示：
K1=61317602 K2=61326875 K3=62739628 K4=61343634
K5=62706815 K6=62774638 K7=61381262 K8=61394220
分析上述8個關鍵字可知，關鍵字從左到右的第1、2、3、6位取值比較集中，不宜作為哈希地址，剩餘的第4、5、7、8位取值較均勻，可選取其中的兩位作為哈希地址。設選取最後兩位作為哈希地址，則這8個關鍵字的哈希地址分別為：2，75，28，34，15，38，62，20。
此法適於:能預先估計出全體關鍵字的每一位上各種數字出現的頻度。
將關鍵碼值看成另一種進制的數再轉換成原來進制的數，然後選其中幾位作為散列地址。
例Hash(80127429)=(80127429)13=8 137+0 136+1 135+2 134+7 133+4 132+2*131+9=(502432641)10如果取中間三位作為哈希值，得Hash（80127429）=432
為了獲得良好的哈希函數，可以將幾種方法聯合起來使用，比如先變基，再折疊或平方取中等等，只要散列均勻，就可以隨意拼湊。
有時關鍵碼所含的位數很多，採用平方取中法計算太復雜，則可將關鍵碼分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為散列地址，這方法稱為折疊法。
分為：
盡管散列函數的目標是使得沖突最少，但實際上沖突是無法避免的。因此，我們必須研究沖突解決策略。沖突解決技術可以分為兩類：開散列方法( open hashing，也稱為拉鏈法，separate chaining )和閉散列方法( closed hashing，也稱為開地址方法，open addressing )。這兩種方法的不同之處在於：開散列法把發生沖突的關鍵碼存儲在散列表主表之外，而閉散列法把發生沖突的關鍵碼存儲在表中另一個槽內。
(1)拉鏈法
開散列方法的一種簡單形式是把散列表中的每個槽定義為一個鏈表的表頭。散列到一個特定槽的所有記錄都放到這個槽的鏈表中。圖9-5說明了一個開散列的散列表，這個表中每一個槽存儲一個記錄和一個指向鏈表其餘部分的指針。這7個數存儲在有11個槽的散列表中，使用的散列函數是h(K) = K mod 11。數的插入順序是77、7、110、95、14、75和62。有2個值散列到第0個槽，1個值散列到第3個槽，3個值散列到第7個槽，1個值散列到第9個槽。
閉散列方法把所有記錄直接存儲在散列表中。每個記錄關鍵碼key有一個由散列函數計算出來的基位置，即h(key)。如果要插入一個關鍵碼，而另一個記錄已經占據了R的基位置(發生碰撞)，那麼就把R存儲在表中的其它地址內，由沖突解決策略確定是哪個地址。
閉散列表解決沖突的基本思想是：當沖突發生時，使用某種方法為關鍵碼K生成一個散列地址序列d0，d1，d2，... di ，...dm-1。其中d0=h（K）稱為K的基地址地置( home position )；所有di(0< i< m)是後繼散列地址。當插入K時，若基地址上的結點已被別的數據元素佔用，則按上述地址序列依次探查，將找到的第一個開放的空閑位置di作為K的存儲位置；若所有後繼散列地址都不空閑，說明該閉散列表已滿，報告溢出。相應地，檢索K時，將按同值的後繼地址序列依次查找，檢索成功時返回該位置di ；如果沿著探查序列檢索時，遇到了開放的空閑地址，則說明表中沒有待查的關鍵碼。刪除K時，也按同值的後繼地址序列依次查找，查找到某個位置di具有該K值，則刪除該位置di上的數據元素（刪除操作實際上只是對該結點加以刪除標記）；如果遇到了開放的空閑地址，則說明表中沒有待刪除的關鍵碼。因此，對於閉散列表來說，構造後繼散列地址序列的方法，也就是處理沖突的方法。
形成探查的方法不同，所得到的解決沖突的方法也不同。下面是幾種常見的構造方法。
(1)線性探測法
將散列表看成是一個環形表，若在基地址d（即h(K)=d）發生沖突，則依次探查下述地址單元：d+1，d+2，......，M-1，0，1，......，d-1直到找到一個空閑地址或查找到關鍵碼為key的結點為止。當然，若沿著該探查序列檢索一遍之後，又回到了地址d，則無論是做插入操作還是做檢索操作，都意味著失敗。 用於簡單線性探查的探查函數是： p(K，i) = i
例9.7 已知一組關鍵碼為（26，36，41，38，44，15，68，12，06，51，25），散列表長度M= 15，用線性探查法解決沖突構造這組關鍵碼的散列表。 因為n=11，利用除余法構造散列函數，選取小於M的最大質數P=13，則散列函數為：h(key) = key%13。按順序插入各個結點： 26: h(26) = 0，36: h(36) = 10， 41: h(41) = 2，38: h(38) = 12， 44: h(44) = 5。 插入15時，其散列地址為2，由於2已被關鍵碼為41的元素佔用，故需進行探查。按順序探查法，顯然3為開放的空閑地址，故可將其放在3單元。類似地，68和12可分別放在4和13單元中.
(2)二次探查法
二次探查法的基本思想是：生成的後繼散列地址不是連續的，而是跳躍式的，以便為後續數據元素留下空間從而減少聚集。二次探查法的探查序列依次為：12，-12，22 ，-22，...等，也就是說，發生沖突時，將同義詞來回散列在第一個地址的兩端。求下一個開放地址的公式為：
(3)隨機探查法
理想的探查函數應當在探查序列中隨機地從未訪問過的槽中選擇下一個位置，即探查序列應當是散列表位置的一個隨機排列。但是，我們實際上不能隨機地從探查序列中選擇一個位置，因為在檢索關鍵碼的時候不能建立起同樣的探查序列。然而，我們可以做一些類似於偽隨機探查( pseudo-random probing )的事情。在偽隨機探查中，探查序列中的第i個槽是(h(K) + ri) mod M，其中ri是1到M - 1之間數的「隨機」數序列。所有插入和檢索都使用相同的「隨機」數。探查函數將是 p(K，i) = perm[i - 1]， 這里perm是一個長度為M - 1的數組，它包含值從1到M – 1的隨機序列。
例子：
例如，已知哈希表長度m=11，哈希函數為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元，參圖8.26 (a)。如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元，參圖8.26 (b)。如果用偽隨機探測再散列處理沖突，且偽隨機數序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元，參圖8.26 (c)。
(4)雙散列探查法
偽隨機探查和二次探查都能消除基本聚集——即基地址不同的關鍵碼，其探查序列的某些段重疊在一起——的問題。然而，如果兩個關鍵碼散列到同一個基地址，那麼採用這兩種方法還是得到同樣的探查序列，仍然會產生聚集。這是因為偽隨機探查和二次探查產生的探查序列只是基地址的函數，而不是原來關鍵碼值的函數。這個問題稱為二級聚集( secondary clustering )。
為了避免二級聚集，我們需要使得探查序列是原來關鍵碼值的函數，而不是基位置的函數。雙散列探查法利用第二個散列函數作為常數，每次跳過常數項，做線性探查。
『陸』 hash查找演算法 數據量在10萬左右 資料庫中存儲
可以用，但是最好加入緩存機制。
『柒』 什麼是哈希函數，怎麼應用於資料庫
哈希函數是數據結構的一種專業術語，這個用於資料庫就邊現在其數據的存儲方式上，你可以去參考數據結構。
『捌』 數據結構問題：哈希表的存儲結構是什麼
哈希表的存儲結構為散列函數。
散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。
這里把這種對應關系f稱為散列函數，又稱為哈希（Hash）函數。按這個思想，採用散列技術將記錄存在在一塊連續的存儲空間中，這塊連續存儲空間稱為散列表或哈希表。那麼，關鍵字對應的記錄存儲位置稱為散列地址。
散列技術最適合的求解問題是查找與給定值相等的記錄。對於查找來說，簡化了比較過程，效率會大大 提高。但是，散列技術部具備很多常規數據結構的能力，如比較同樣的關鍵字，對應很多記錄的情況，不適合用散列技術；散列表也不適合范圍查找等等。
在理想的情況下，每一個關鍵字，通過散列函數計算出來的地址都是不一樣的，可現實中，這只是一個理想。市場會碰到兩個關鍵字key1 != key2，但是卻有f(key1) = f(key2)，這種現象稱為沖突。出現沖突將會造成查找錯誤，因此可以通過精心設計散列函數讓沖突盡可能的少，但是不能完全避免。
『玖』 哈希表是如何存取數據的原理是什麼
設要存的數據如下格式：
姓名 學號 成績
劉三 2322232 89
創建空的哈希表。
例：以姓名為key，用哈希函數得出key的哈希值作為該key所在數據存儲的地址。
然後將該數據存到該地址。如果該地址已經存有數據（即：不同的key得出了相同的哈希值），則用特定的沖突解決方法再計算出新的哈希值，以此類推。
查找時，輸入要查詢數據的key值，例：王七。程序將計算出key王七的哈希值，直接調出王七哈希值所在地址的數據。節省查詢時間。