？優勢:
哈希表可以提供快速操作。
缺點:
哈希表通常基於數組，創建後很難擴展。
也沒有簡單的方法以任何順序遍歷表中的數據項(例如，從小到大)。
綜上所述，如果不需要按順序遍歷數據，可以提前預測數據的大小。那麽哈希表在速度和易用性上是無與倫比的。
1.？使用哈希函數將搜索到的關鍵字轉換為數組的索引。
2.？處理哈希沖突。
如果關鍵字是k，它的值存儲在f(k)的存儲位置。所以不需要對比就可以直接得到搜索到的記錄。把這種對應F稱為哈希函數，按照這種思路建立的表就是哈希表。
如果關鍵字集合中的任意壹個關鍵字映射到地址集合中的任意壹個地址的概率相等，那麽這種哈希函數就叫做均勻哈希函數，也就是說關鍵字可以通過哈希函數得到壹個“隨機地址”，從而減少碰撞。
哈希函數可以使訪問數據序列的過程更快、更有效，通過哈希函數可以更快地定位數據元素。
壹個好的哈希函數通常應該考慮以下因素:
1.計算簡單，提高了轉換速度。
2.關鍵字對應的地址空間均勻分布，盡量減少沖突。
1.？直接尋址方法
取關鍵字或關鍵字的壹個線性函數值作為哈希地址，即H(Key)=Key或H(Key) = a * key+b(其中a和b為整數)。這個散列函數也稱為自函數。如果h (key)的hash地址已經有值了，那麽就在下壹個位置尋找，直到找到H(Key)的位置沒有值為止，把元素放進去。
2.？數字分析方法
數字分析就是找出數字的規律，盡可能利用這些數據構造沖突概率低的哈希地址。
3.？中間平方方法
取關鍵字平方後的中間數字作為哈希地址。這種方法的原理是通過取平方來擴大差值，平方值的中間位數與這個數的每壹位相關，所以不同關鍵字得到的hash函數值不容易沖突，得到的hash地址也比較統壹。這種方法適用於關鍵字中每壹位都有壹些數字重復頻率很高的現象。
4.？折疊法
折疊的方法是將關鍵字分成若幹個位數相同的部分，最後壹部分可以有不同的位數，然後取這些部分的疊加和(註意:加和時去掉進位)作為哈希地址。
數字疊加可分為移位疊加和邊界疊加。移位疊加是將每個被除部分的最低位對齊，然後相加；邊界疊加就是從壹端到另壹端沿著分割線來回折疊，然後對齊相加。
這種方法適用於關鍵字較多的情況。
5.？隨機數方法
選擇壹個隨機數作為哈希地址，通常在關鍵字長度不同時使用。
6.？除法和余數法
把關鍵字除以壹個不大於哈希表長度m的數p得到的余數作為哈希地址，即h (key) = key mod p，p
不同的關鍵字可能得到相同的哈希地址，即k1≠k2，而f(k1)=f(k2)。這種現象叫做碰撞。對於這個哈希函數，具有相同函數值的關鍵字稱為同義詞。
通過構造壹個性能良好的哈希函數，可以減少沖突，但壹般不可能完全避免沖突，所以解決沖突是哈希方法的另壹個關鍵問題。創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法要壹致。
這裏以創建哈希表為例，說明解決沖突的方法。
1.開放式尋址方法
這種方法也叫再散列法。其基本思想是:當關鍵字key的hash地址p=H(key)沖突時，基於P生成另壹個hash地址p1，如果p1仍然沖突，則基於P生成另壹個hash地址p2，直到找到壹個不沖突的hash地址pi，並在其中存儲相應的元素。這個方法有壹個rehash函數的壹般形式:Hi=(H(key)+di)%m？I = 1，2，…，m-1，其中H(key)是哈希函數，m是表長，di是增量序列，I是碰撞次數。增量序列的值不同，對應的重散列方法也不同。增量序列主要包括以下內容:
(1)?線性檢測再散列
di=1，2，3，…，m-1
這種方法的特點是:當發生沖突時，按順序查找表中的下壹個單元格，直到找到壹個空單元格或搜索到整個表。
(2)二次檢測和重散列
di=12，-12，22，-22，…，k2，-k2(k & lt；=m/2)
這種方法的特點是:當發生沖突時，通過跳轉來檢測表格的左右更加靈活。
(3)偽隨機檢測和再散列
Di=偽隨機數序列。
線性探針重散列的優點是，只要哈希表不滿足，就可以找到不沖突的哈希地址，而第二次探針重散列和偽隨機探針重散列則不壹定。線性探針重散列容易產生“二次聚合”，即在處理同義詞沖突時導致非同義詞的沖突。
事實上，除了上述方法之外，開放尋址方法還有許多變體，但它們都有不同的di表示法。(例如雙哈希檢測方法:di=i*h2(k))
2.重新散列
這種方法是同時構造幾個不同的哈希函數:Hi=RHi(key)，i=1，2，3，…，n。
當哈希地址H1=RH1(鍵)沖突時，計算H2 = rh2(鍵)...直到沖突不再發生。這種方法不易產生聚合，但增加了計算時間。
？3.鏈地址法(拉鏈法)
這種方法的基本思想是所有哈希地址相同的元素組成壹個叫做同義詞鏈的單鏈表，單鏈表的頭指針存放在壹個哈希表(數組)中，所以查找、插入和刪除主要在同義詞鏈中進行。如果所選哈希表的長度為m，則該哈希表可被定義為指針數組T [0...m-1]由m個頭和指針組成。散列地址為I的所有節點都被插入到以T[i]為頭指針的單鏈表中。t中每個分量的初始值應該是壹個空指針。鏈地址法適用於頻繁插入和刪除。
拉鏈法的優點
與開放式尋址方法相比，拉鏈式方法具有以下優點:
(1) Zipper方法處理沖突簡單，不存在堆積現象，即非同義詞永遠不會沖突，所以平均搜索長度短；
(2)由於zipper方法中每個鏈表的節點空間都是動態應用的，所以更適用於在做表之前無法確定表長的情況；
(3)為了減少沖突，開放式尋址方式要求填充因子α很小，所以在節點規模較大時會浪費大量空間。在zipper方法中，理論上可以選擇α≥1，當節點較大時，可以忽略zipper方法中添加的指針字段，從而節省空間；(哈希表的填充因子定義為:α =表中填充的元素數/哈希表的長度)
註意:HashMap的默認填充因子是0.75。
(4)在用zipper方法構造的哈希表中，刪除節點的操作容易實現。只需刪除鏈表上相應的節點。但是對於開放地址法構造的哈希表，刪除節點不能簡單的清空被刪除節點的空間，否則填充哈希表的同義詞節點在它之後的搜索路徑會被截斷。這是因為在各種開放式尋址方法中，空地址單元被理解為不查找元素。所以在刪除使用開放尋址方式處理沖突的哈希表時，只能標記刪除的節點，不能真正刪除。
拉鏈法的缺點
zipper方法的缺點是指針需要額外的空間，所以當節點尺寸較小時，開放式尋址方法節省空間。此時，節省下來的指針空間用於擴大哈希表的規模，可以減少填充因子，進而減少開放式尋址方式中的沖突，從而提高平均搜索速度。
4、設立公共溢出區。
這種方法的基本思想是將哈希表分為基本表和溢出表兩部分，所有與基本表沖突的元素都填充到溢出表中(這種方法中，元素分別存儲在兩個表中)。
哈希表的查找過程和造表過程基本相同。有的鍵碼可以直接通過哈希函數轉換的地址找到，有的鍵碼在哈希函數得到的地址中有沖突，需要按照處理沖突的方法找到。在介紹的三種處理沖突的方法中，尋找沖突仍然是壹個給定值與鍵碼比較的過程。因此，哈希表搜索效率的衡量標準仍然是平均搜索長度。
在搜索的過程中，關鍵代碼比較的次數取決於沖突的次數。沖突少，搜索效率就高，沖突多，搜索效率就低。所以影響沖突數量的因素，也就是影響搜索效率的因素。
有三個因素會影響沖突的數量:
1.哈希函數是否統壹；
2.處理沖突的方法；
3.哈希表的填充因子。
哈希表的填充因子
定義為:α =表中填充的元素數/哈希表的長度。
α是哈希表填充度的符號因子。因為表的長度是壹個常數值，α與表中填充的元素數成正比，所以α越大，表中填充的元素越多，沖突的可能性越大；α越小，表中填入的元素越少，沖突的可能性越小。
其實哈希表的平均搜索長度是填充因子α的函數，只是處理沖突的方法不同，作用也不同。
這個哈希算法不是大學裏數據結構課上的哈希表的算法。這裏的哈希算法是密碼學的基礎。知道了哈希的基本定義，就不能不提到壹些著名的哈希算法。MD5和SHA-1可以說是目前應用最廣泛的哈希算法，都是基於MD4設計的。
哈希算法在信息安全中的應用主要體現在以下三個方面:
⑴?文件檢查
我們熟悉奇偶校驗和CRC校驗。這兩種檢查都沒有抵抗數據篡改的能力。它們可以在壹定程度上檢測數據傳輸中的信道錯誤，但無法防止對數據的惡意破壞。
md5哈希算法的“數字指紋”特性使其成為目前應用最廣泛的文件完整性校驗和算法，許多Unix系統都提供了計算MD5校驗和的命令。
⑵?數字簽名
哈希算法也是現代密碼學的重要組成部分。由於非對稱算法運算速度慢，單向哈希函數在數字簽名協議中占有重要地位。對哈希值進行數字簽名，也稱為“數字摘要”，可以被認為等同於對文件本身進行數字簽名。這樣的協議還有其他好處。
？(3)認證協議
以下認證協議也稱為挑戰認證模式:當傳輸信道可以被截獲但不能被篡改時，這是壹種簡單而安全的方法。
DHT主要用於分布式緩存，可以用來解決分布式存儲結構下動態添加和刪除節點帶來的問題。比如在分布式存儲系統中，要將數據存儲在特定的節點上，如果用普通的hash方法將數據映射到特定的節點上，比如key%N(key是數據的key，N是機器節點數)，如果壹臺機器加入或者退出集群，所有的數據映射都將無效，如果是持久存儲，就需要進行數據遷移，如果是分布式緩存，其他緩存都將無效。
判斷哈希算法好壞的四個定義:
1，平衡:平衡是指哈希結果盡可能地分布到所有緩沖區，使所有緩沖區空間都得到利用。
2.單調性:單調性是指如果壹些內容已經通過哈希分配到了相應的緩沖區，那麽系統中就會增加新的緩沖區。哈希結果應確保原始分配的內容可以映射到原始或新的緩沖區，而不會映射到舊緩沖區集中的其他緩沖區。
3.傳播:在分布式環境中，終端可能看不到所有的緩沖區，而只能看到其中的壹部分。當終端想通過哈希過程將內容映射到緩沖區時，由於不同的終端可能看到不同的緩沖區範圍，哈希的結果是不壹致的，最終的結果是相同的內容被不同的終端映射到不同的緩沖區。這種情況顯然應該避免，因為它導致相同的內容存儲在不同的緩沖區中，降低了系統存儲的效率。離差的定義就是上述情況的嚴重程度。壹個好的哈希算法應該能夠盡可能的避免不壹致，也就是最小化離散度。
4.負荷:負荷的問題其實就是換個角度看離散的問題。由於不同的終端可以將相同的內容映射到不同的緩沖器，所以不同的用戶也可以將特定的緩沖器映射到不同的內容。和分散壹樣，應該避免這種情況，所以壹個好的哈希算法應該能夠盡可能地減少緩沖區負載。
在分布式集群中，添加或刪除機器或機器故障後自動離開集群是分布式集群管理的最基本功能。如果采用常用的哈希模算法，在添加或刪除機器後，很多原始數據都找不到了，嚴重違背了單調性原則。接下來主要說明壹致性哈希算法是如何設計的。
對於SpyMemcached的ketama算法，思路如下:
用哈希函數把數據映射到大空間，如圖。存儲數據時，先獲取壹個hash值，對應這個環中的每壹個位置，比如k1對應圖中所示的位置，然後順時針找壹個機器node B，將k1存儲在這個node B中。
如果節點B宕機，節點B上的數據會落到節點C上，如下圖所示:
這樣，只有節點C會受到影響，其他節點A和D的數據不會受到影響。但這樣會造成“雪崩”的情況，即由於節點C承接了節點B的數據，節點C的負載會變高，節點C容易下去，以此類推，導致整個集群掛起。
為此，引入了“虛節點”的概念:即想象這個環上有很多“虛節點”。數據的存儲是沿著環的順時針方向找壹個虛擬節點，每個虛擬節點都會關聯壹個真實節點，如下圖所示:
圖中，A1、A2、B1、B2、C1、C2、D1和D2都是虛擬節點，A機存儲A1和A2的數據，B機存儲B1和B2的數據，C機存儲數據。因為這些虛擬節點數量眾多且分布均勻，所以不會出現“雪崩”現象。