哈希演算法數據結構
① 有關數據結構哈希表的問題
Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
hashing定義了一種將字元組成的字元串轉換為固定長度(一般是更短長度)的數值或索引值的方法，稱為散列法，也叫哈希法。由於通過更短的哈希值比用原始值進行資料庫搜索更快，這種方法一般用來在資料庫中建立索引並進行搜索，同時還用在各種解密演算法中。
設所有可能出現的關鍵字集合記為u(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為k（|k|比|u|小得多）。|k|是集合k中元素的個數。
散列方法是使用函數hash將u映射到表t[0..m-1]的下標上（m=o(|u|)）。這樣以u中關鍵字為自變數，以h為函數的運算結果就是相應結點的存儲地址。從而達到在o(1)時間內就可完成查找。
其中：
① hash：u→{0，1，2，…，m-1} ，通常稱h為散列函數(hash function)。散列函數h的作用是壓縮待處理的下標范圍，使待處理的|u|個值減少到m個值，從而降低空間開銷。
② t為散列表(hash table)。
③ hash(ki)(ki∈u)是關鍵字為ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的散列地址存儲到散列表中的過程稱為散列(hashing).
比如：有一組數據包括用戶名字、電話、住址等，為了快速的檢索，我們可以利用名字作為關鍵碼，hash規則就是把名字中每一個字的拼音的第一個字母拿出來，把該字母在26個字母中的順序值取出來加在一塊作為改記錄的地址。比如張三，就是z+s＝26+19＝45。就是把張三存在地址為45處。
但是這樣存在一個問題，比如假如有個用戶名字叫做：周四，那麼計算它的地址時也是z+s＝45，這樣它與張三就有相同的地址，這就是沖突，也叫作碰撞！
沖突：兩個不同的關鍵字，由於散列函數值相同，因而被映射到同一表位置上。該現象稱為沖突(collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(synonym)。
沖突基本上不可避免的，除非數據很少，我們只能採取措施盡量避免沖突，或者尋找解決沖突的辦法。影響沖突的因素
沖突的頻繁程度除了與h相關外，還與表的填滿程度相關。
設m和n分別表示表長和表中填人的結點數，則將α=n/m定義為散列表的裝填因子(load factor)。α越大，表越滿，沖突的機會也越大。通常取α≤1。
散列函數的構造方法：
1、散列函數的選擇有兩條標准：簡單和均勻。
簡單指散列函數的計算簡單快速；
均勻指對於關鍵字集合中的任一關鍵字，散列函數能以等概率將其映射到表空間的任何一個位置上。也就是說，散列函數能將子集k隨機均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。
2、常用散列函數
（1）直接定址法：比如在一個0～100歲的年齡統計表，我們就可以把年齡作為地址。
（2）平方取中法
具體方法：先通過求關鍵字的平方值擴大相近數的差別，然後根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，所以由此產生的散列地址較為均勻。
（3）除留余數法
取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數（4）隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即
h(key)=random(key)
其中random為偽隨機函數，但要保證函數值是在0到m-1之間。
處理沖突的方法：
1、開放定址法
hi=(h(key)+di) mod m i=1,2,...,k(k<=m-1)
其中m為表長，di為增量序列
如果di值可能為1,2,3,...m-1，稱線性探測再散列。
如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測再散列。
如果di取值可能為偽隨機數列。稱偽隨機探測再散列。開放地址法堆裝填因子的要求
開放定址法要求散列表的裝填因子α≤l，實用中取α為0.5到0.9之間的某個值為宜。
②二次探查法(quadratic probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2
即探查序列為d=h(key)，d+12，d+22，…，等。
該方法的缺陷是不易探查到整個散列空間。
③雙重散列法(double hashing)
該方法是開放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列為：
d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
該方法使用了兩個散列函數h(key)和h1(key)，故也稱為雙散列函數探查法。
2、拉鏈法
拉鏈法解決沖突的方法
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組t[0..m-1]。凡是散列地址為i的結點，均插入到以t為頭指針的單鏈表中。t中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大於1，但一般均取α≤1。
3、建立一個公共溢出區
假設哈希函數的值域為[0,m-1],則設向量hashtable[0..m-1]為基本表，另外設立存儲空間向量overtable[0..v]用以存儲發生沖突的記錄。
性能分析
插入和刪除的時間均取決於查找，故下面只分析查找操作的時間性能。
雖然散列表在關鍵字和存儲位置之間建立了對應關系，理想情況是無須關鍵字的比較就可找到待查關鍵字。但是由於沖突的存在，散列表的查找過程仍是一個和關鍵字比較的過程，不過散列表的平均查找長度比順序查找、二分查找等完全依賴於關鍵字比較的查找要小得多。
（1）查找成功的asl
散列表上的查找優於順序查找和二分查找。
（2） 查找不成功的asl
對於不成功的查找，順序查找和二分查找所需進行的關鍵字比較次數僅取決於表長，而散列查找所需進行的關鍵字比較次數和待查結點有關。因此，在等概率情況下，也可將散列表在查找不成功時的平均查找長度，定義為查找不成功時對關鍵字需要執行的平均比較次數。
注意：
①由同一個散列函數、不同的解決沖突方法構造的散列表，其平均查找長度是不相同的。
②散列表的平均查找長度不是結點個數n的函數，而是裝填因子α的函數。因此在設計散列表時可選擇α以控制散列表的平均查找長度。
③ α的取值
α越小，產生沖突的機會就小，但α過小，空間的浪費就過多。只要α選擇合適，散列表上的平均查找長度就是一個常數，即散列表上查找的平均時間為o(1)。
④ 散列法與其他查找方法的區別
除散列法外，其他查找方法有共同特徵為：均是建立在比較關鍵字的基礎上。其中順序查找是對無序集合的查找，每次關鍵字的比較結果為"="或"!="兩種可能，其平均時間為o(n)；其餘的查找均是對有序集合的查找，每次關鍵字的比較有"="、"<"和">"三種可能，且每次比較後均能縮小下次的查找范圍，故查找速度更快，其平均時間為o(lgn)。而散列法是根據關鍵字直接求出地址的查找方法，其查找的期望時間為o(1)。
例子：例子：選取哈希函數h(k)=(3k)%11,用線性探測再散列法處理沖突。
試在0～10的散列地址空間中，對關鍵序列22,41,53,46,30,13,01,67構造哈希表，並求等概率情況下查找不成功的平均查找長度asl。
② 簡要回答哈希表這種數據結構應用在查找操作中的優勢
優勢：
從時間和空間的角度分析：
時間高效：利用哈希可使插入、查找、刪除、修改、替換操作的時間復雜度達到O(1)，這是其他查找方式無法達到的（比如樹形查找O(logn)、二分查找O(logn)、順序查找O(n)等）。即使出現碰撞，整體理論值也可以接近O(1)。
空間可接受：哈希的比較合適的空間消耗以O(2n)最佳，對於其他同類演算法（主要是樹形查找方式），要分為兩類。第一種是以葉子存放有效值的樹(如b+樹、線段樹)，其空間消耗可認為是O(4n)；第二種是所有節點均存放有效值，空間消耗可認為O(n)。
③ 數據結構哈希演算法
1，直接定址法：
函數公式：f(key)=a*key+b (a,b為常數)
這種方法的優點是：簡單，均勻，不會產生沖突。但是需要事先知道關鍵字的分布情況，適合查找表較小並且連續的情況。
2，數字分析法：
比如我們的11位手機號碼「136XXXX7887」，其中前三位是接入號，一般對應不同運營公司的子品牌，如130是聯通如意通，136是移動神州行，153是電信等。中間四們是HLR識別號，表示用戶歸屬地。最後四們才是真正的用戶號。
若我們現在要存儲某家公司員工登記表，如果用手機號碼作為關鍵字，那麼極有可能前7位都是相同的，所以我們選擇後面的四們作為哈希地址就是不錯的選擇。
3，平方取中法：
故名思義，比如關鍵字是1234，那麼它的平方就是1522756，再抽取中間的3位就是227作為哈希地址。
4，折疊法：
折疊法是將關鍵字從左到右分割成位數相等的幾個部分(最後一部分位數不夠可以短些)，然後將這幾部分疊加求和，並按哈希表表長，取後幾位作為哈希地址。
比如我們的關鍵字是9876543210，哈希表表長三位，我們將它分為四組，987|654|321|0 ，然後將它們疊加求和987+654+321+0=1962，再求後3位即得到哈希地址為962，哈哈，是不是很有意思。
5，除留余數法：
函數公式：f(key)=key mod p (p<=m)m為哈希表表長。
這種方法是最常用的哈希函數構造方法。
6，隨機數法：
函數公式：f(key)= random(key)。
這里random是隨機函數，當關鍵字的長度不等是，採用這種方法比較合適。
兩種哈希函數沖突解決方法：
我們設計得最好的哈希函數也不可能完全避免沖突，當我們在使用哈希函數後發現兩個關鍵字key1!=key2，但是卻有f(key1)=f(key2)，即發生沖突。
④ 數據結構哈希表
1. 計算出字元串的三個哈希值 （一個用來確定位置，另外兩個用來校驗)
2. 察看哈希表中的這個位置
3. 哈希表中這個位置為空嗎？假如為空，則肯定該字元串不存在，返回
4. 假如存在，則檢查其他兩個哈希值是否也匹配，假如匹配，則表示找到了該字元串，返回
5. 移到下一個位置，假如已經越界，則表示沒有找到，返回
6. 看看是不是又回到了原來的位置，假如是，則返回沒找到
7. 回到3
怎麼樣，很簡單的演算法吧，但確實是天才的idea, 其實最優秀的演算法往往是簡單有效的演算法。
⑤ 什麼叫HASH演算法要求例題（PASCAL）
哈希表（Hash Table）的應用近兩年才在NOI中出現，作為一種高效的數據結構，它正在競賽中發揮著越來越重要的作用。
哈希表最大的優點，就是把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。
哈希表又叫做散列表，分為"開散列" 和"閉散列"。考慮到競賽時多數人通常避免使用動態存儲結構，本文中的"哈希表"僅指"閉散列"，關於其他方面讀者可參閱其他書籍。
⑥ C語言版數據結構哈希演算法題：設m=16,HASH函數為H（key）=key mod 13,現採用再哈希法Hi=RHi(key）處理沖突
應該是這個意思：
第一次沖突就是散列的位置+1，這次發生沖突了就繼續第二次
第二次用的是平方取中，55^2= 3025，當然第二次沖突的RH2就是02了，答案(2)
⑦ 哈希表是一種演算法還是一種數據結構呢
對於動態查找表而言，1) 表長不確定；2)在設計查找表時，只知道關鍵字所屬范圍，而不知道確切的關鍵字。因此，一般情況需建立一個函數關系，以f(key)作為關鍵字為key的錄在表中的位置，通常稱這個函數f(key)為哈希函數。(注意：這個函數並不一定是數學函數)
哈希函數是一個映象，即：將關鍵字的集合映射到某個地址集合上，它的設置很靈活，只要這個地址集合的大小不超出允許范圍即可。
現實中哈希函數是需要構造的，並且構造的好才能使用的好。
用途：加密，解決沖突問題。。。。
用途很廣，比特精靈中就使用了哈希函數，你可 以自己看看。
具體可以學習一下數據結構和演算法的書。
⑧ 數據結構問題：哈希表的存儲結構是什麼
哈希表
是
散列
存儲
，它的哈希值是通過哈希演算法得到的。哈希值就類似於數組中的下標值，但是哈希表中的對象存放位置不是連續的。通過找到哈希值
很容易找到相應位置的對象。一般散列度在0.75最佳(查詢效率和內存使用率的均衡點吧)！！！
⑨ 數據結構-哈希演算法
H(22)=(3*22)mod 11=0;
H(41)=2;
H(53)=5;
H(46)=6;
H(30)=2;沖突；H1=(H(key)+d1)MOD m = (2+1((7*30)MOD 10+1)) MOD 11=3;
H(13)=6;沖突；H1=(6+1(1+1))=8;
H(01)=3;沖突；H1=(3+1(7+1))mod 11=0;H2=(3+2(7+1))mod 11=8;
H3=(3+3*8)mod 11=5; H4=(3+4*8)mod 11=2;
H5=(3+5*8)mod 11=10;
H(67)=3;沖突；H1=(3+1*(7*67mod10+1))mod 11=2; H2=(3+2*10)mod 11=1；
⑩ 數據結構與演算法，求哈希函數
1、
2、裝填因子=9/13
3、查找成功的平均查找長度ASL= 11/13