一致性hash參考：[一致性哈希](http://blog.csdn.net/u013074465/article/details/46939275) Hash函數也稱為散列表，是一種常用的數據結構。哈希表優點：可以提供快速插入和查找操作，無論有多少數據項，插入與查找只需接近常量的時間：O(1)時間級。而且編程很容易實現。哈希表的缺點：它是基于數組的，數組一旦被創建，就難以拓展；某些哈希表的填充因子（填入的元素個數/哈希表長度)過大，性能會急劇下降。 Hash函數在多個領域均有應用，而在數字簽名和數據庫實現時又用的最多，比如基于hash的索引，是最好的單值查找索引；同時，在當前數據爆炸的場景下，執行相似item的查找時，在內存受限時，均可以采取LSH（local sensitive hash）進行分段處理。具體用途很多，不贅述，下面介紹一些常用的知識：hash函數本質；簡單的hash函數生成法；hash的沖突消解； 一個國外牛人的個人網站，有非常全面的hash算法列表：[http://burtleburtle.net/bob/hash/](http://burtleburtle.net/bob/hash/) # 1 hash的本質 還可以參考這里[http://blog.csdn.net/u013074465/article/details/40504975](http://blog.csdn.net/u013074465/article/details/40504975) Hash函數是指把一個大范圍映射到一個小范圍。把大范圍映射到一個小范圍的目的往往是為了節省空間。在考慮使用Hash函數之前，需要明白它的幾個限制： ????? （1）Hash的主要原理就是把大范圍映射到小范圍；所以，你輸入的實際值的個數必須與小范圍相當或者比它更小。不然沖突就會很多。 　　（2） 由于Hash逼近單向函數；所以，你可以用它來對數據進行加密。 　　（3）不同的應用對Hash函數有著不同的要求；比如，用于加密的Hash函數主要考慮它和單項函數的差距，而用于查找的Hash函數主要考慮它映射到小范圍的沖突率。 Hash函數好壞非評判標準：簡單和均勻。 ?? 　簡單指散列函數的計算簡單快速； ?? 　均勻指對于關鍵字集合中的任一關鍵字，散列函數能以等概率將其映射到表空間的任何一個位置上。也就是說，散列函數能將子集K隨機均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。 # 2 常用hash生成方法 ????常用的散列函數構造有7種方法，1，直接定址法； 2，數字分析法； 3 ，平方取中法；4，除留余數法；5，相乘取整法；6，偽隨機數法；7，折疊法 ### （1）直接尋址法 取關鍵字或關鍵字的某個線性函數值為散列地址。 即Hash(key) = key 或Hash(key) = a * key + b，其中a,b為常數。 ### （2）數字分析法 分析一組數據，比如某班學生的出生年月日發現出生年月日的前幾位數字大體相同，這樣的話，沖突的幾率會很大，但是發現年月日的后幾位表示月份和具體日期的數字差別較大，如果用后幾位構成散列地址，則沖突的幾率會明顯降低。因此數字分析法是找出數字的規律，盡可能利用這些數字構造沖突幾率低的散列地址。 ### （3）平方取中法 ?? 　具體方法：先通過求關鍵字的平方值擴大相近數的差別，然后根據表長度取中間的幾位數作為散列函數值。又因為一個乘積的中間幾位數和乘數的每一位都相關，所以由此產生的散列地址較為均勻。 　【例】將一組關鍵字(0100，0110，1010，1001，0111)平方后得 ?? (0010000，0012100，1020100，1002001，0012321) 　若取表長為1000，則可取中間的三位數作為散列地址集： ?? (100，121，201，020，123)。 相應的散列函數用C實現很簡單： ~~~ int Hash(int key){ //假設key是4位整數 key *= key; ?key /= 100; //先求平方值，后去掉末尾的兩位數 return key ％ 1000; //取中間三位數作為散列地址返回 } ~~~ ### （4）除余法 ?? 　該方法是最為簡單常用的一種方法。它是以表長m來除關鍵字，取其余數作為散列地址，即 h(key)=key％m ?? 　該方法的關鍵是選取m。選取的m應使得散列函數值盡可能與關鍵字的各位相關。m最好為素數。 　【例】若選m是關鍵字的基數的冪次，則就等于是選擇關鍵字的最后若干位數字作為地址，而與高位無關。于是高位不同而低位相同的關鍵字均互為同義詞。 　【例】若關鍵字是十進制整數，其基為10，則當m=100時，159，259，359，…，等均互為同義詞。 ### （5）相乘取整法 ?? 　該方法包括兩個步驟：首先用關鍵字key乘上某個常數A(0<A<1)，并抽取出key.A的小數部分；然后用m乘以該小數后取整。即：?? ?? 　該方法最大的優點是選取m不再像除余法那樣關鍵。比如，完全可選擇它是2的整數次冪。雖然該方法對任何A的值都適用，但對某些值效果會更好。??????????? ?? 　該函數的C代碼為： ~~~ int Hash(int key){ double d=key *A; //不妨設A和m已有定義 return (int)(m*(d-(int)d));//(int)表示強制轉換后面的表達式為整數 } ~~~ ### （6）隨機數法 ?? 　選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即 ??????? h(key) = random(key) 　其中random為偽隨機函數，但要保證函數值是在0到m-1之間。 ### （7） 折疊法 將關鍵字分割成位數相同的幾個部分（最后一部分位數可以不同），然后取這幾個部分的疊加和（舍棄進位）作為哈希地址。 關鍵字位數很多，而且關鍵字中每一位數字分布大致均勻時，可以采用折疊法。 # 3 處理hash沖突 ### 1)沖突是如何產生的？ ???? 上文中談到，哈希函數是指如何對關鍵字進行編址的，這里的關鍵字的范圍很廣，可視為無限集，如何保證無限集的原數據在編址的時候不會出現重復呢？規則本身無法實現這個目的。 舉一個例子，仍然用班級同學做比喻，現有如下同學數據：張三，李四，王五，趙剛，吳露..... 假如我們編址規則為取姓氏中姓的開頭字母在字母表的相對位置作為地址，則會產生如下的哈希表 <table rules="all" border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="35"><span style="font-size:12px">位置</span></td><td width="35"><span style="font-size:12px">字母</span></td><td width="35"><span style="font-size:12px">姓名</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr><tr><td width="35"><span style="font-size:12px">0</span></td><td width="35"><span style="font-size:12px">a</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr><tr><td><span style="font-size:12px">1</span></td><td><span style="font-size:12px">b</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr><tr><td><span style="font-size:12px">2</span></td><td><span style="font-size:12px">c</span></td><td><span style="font-size:12px"><br/></span></td><td><span style="font-size:12px"><br/></span></td></tr></tbody></table> ... <table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="35"><span style="font-size:12px">10???</span></td><td width="35"><span style="font-size:12px">L????</span></td><td width="35"><span style="font-size:12px">李四</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr></tbody></table> ... <table border="1" cellpadding="3" cellspacing="0" style="background-color:#c0c0c0"><tbody><tr><td width="35"><span style="font-size:12px">22</span></td><td width="35"><span style="font-size:12px">W</span></td><td width="100"><span style="font-size:12px">王五，吳露</span></td><td width="35"><span style="font-size:12px"><br/></span></td></tr></tbody></table> .. <table border="1" cellpadding="3" cellspacing="0" style="background-color:#c0c0c0"><tbody><tr><td width="35"><span style="font-size:12px">25?</span></td><td width="35"><span style="font-size:12px">Z?</span></td><td width="100"><span style="font-size:12px">張三，趙剛</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table> 我們注意到，灰色背景標示的兩行里面，關鍵字王五，吳露被編到了同一個位置，關鍵字張三，趙剛也被編到了同一個位置。老師再拿號來找張三，座位上有兩個人，"你們倆誰是張三？" ### 2)如何解決沖突問題 既然不能避免沖突，那么如何解決沖突呢，顯然需要附加的步驟。通過這些步驟，以制定更多的規則來管理關鍵字集合，通常的辦法有: ### a)開放地址法 開放地執法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1) 其中，m為哈希表的表長。di 是產生沖突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。 會出現的問題：一次聚集，即使表相對較空，這樣占據的單元也會開始形成一些區塊，散列到區塊中的任何關鍵字都要經過多次探測才能解決沖突，然后該關鍵字又加入到相應塊區中。 如果di取1，則每次沖突之后，向后移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)? 稱二次探測再散列。 二次探測可以解決線性探測的一次聚集問題，但是會出現二次聚集：散列到同一位置上的那些元素將探測相同的備選單元。 為了解決上述的二次聚集，另一個解決沖突的方法是：雙散列 比如選擇di = i * Hash2(key)，即發生沖突時，我們將第二個散列函數應用到key并在距離Hash2(key)、 2Hash2(key)、……進行探測。 如果di取值可能為偽隨機數列。稱偽隨機探測再散列。仍然以學生排號作為例子， 現有兩名同學，李四，吳用。李四與吳用事先已排好序，現新來一名同學，名字叫王五，對它進行編制 | 10.. | .... | 22 | .. | .. | 25 | |-----|-----|-----|-----|-----|-----| | 李四.. | .... | 吳用 | .. | .. | 25 | ??趙剛未來之前 <table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">10..</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">23</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">吳用</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">王五</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table> (a)線性探測再散列對趙剛進行編址，且di=1 <table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">10...</span></td><td width="60"><span style="font-size:12px">20</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">王五</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px">吳用</span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td width="35" style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table> (b)二次探測再散列，且di=-2 <table border="1" cellpadding="3" cellspacing="0"><tbody><tr><td width="60"><span style="font-size:12px">1...</span></td><td width="60"><span style="font-size:12px">10...</span></td><td width="60"><span style="font-size:12px">22</span></td><td width="60"><span style="font-size:12px">..</span></td><td width="60"><span style="font-size:12px">25</span></td></tr><tr><td style="background-color:#c0c0c0"><span style="font-size:12px">王五..</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px">李四..</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px">吳用</span></td><td style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td><td style="background-color:#c0c0c0"><span style="font-size:12px"><br/></span></td></tr></tbody></table> (c)偽隨機探測再散列,偽隨機序列為:5,3,2 ### b)再哈希法 當散列表較滿時，沖突增加，插入可能失敗。于是建立另外一個大約兩倍大的散列表（而且使用新的散列函數），掃描原來散列表，計算每個未刪除元素的新的散列值，并將其插入到新表中。 缺點：這是非常昂貴的操作，運行時間O(N)，不過再散列不是經常發生，實際效果沒那么差 ### c)鏈地址法 將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。如下：  ### d.建立一個公共溢出區（比較常見于實際操作中） ????? 假設哈希函數的值域為[0,m-1],則設向量HashTable[0..m-1]為基本表，另外設立存儲空間向量OverTable[0..v]用以存儲發生沖突的記錄。 經過以上方法，基本可以解決掉hash算法沖突的問題。 ?? 還有許多用于散列表的方法，比如散列函數不好或裝填因子過大，都會使堆積現象加劇。為了減少堆積的發生，不能像線性探查法那樣探查一個順序的地址序列(相當于順序查找)，而應使探查序列跳躍式地散列在整個散列表中。衍生出二次探查法，雙重散列表法。 參考資料： http://hunteagle.iteye.com/blog/118551 數據結構（C語言版） 嚴蔚敏