哈希表定義
????散列表（Hash table望伦，也叫哈希表）林说，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把關(guān)鍵碼映射到表中一個位置來訪問記錄屯伞，以加快查找的速度腿箩。這個映射函數(shù)叫做散列函數(shù)（哈希函數(shù)），存放記錄的數(shù)組叫做散列表愕掏。
哈希表優(yōu)缺點(diǎn)
? 優(yōu)點(diǎn)：
??????哈希表可以提供快速的操作度秘。
缺點(diǎn)：
? ????? 哈希表通常是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展。
????????也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數(shù)據(jù)項剑梳。
????綜上唆貌，如果不需要有序遍歷數(shù)據(jù)，井且可以提前預(yù)測數(shù)據(jù)量的大小垢乙。那么哈希表在速度和易用性方面是無與倫比的锨咙。
哈希查找
????????1.?使用哈希函數(shù)將被查找的鍵轉(zhuǎn)換為數(shù)組的索引。
????????2.?處理哈希碰撞沖突追逮。
散列函數(shù)
????若關(guān)鍵字為k酪刀，則其值存放在f(k)的存儲位置上。由此钮孵，不需比較便可直接取得所查記錄骂倘。稱這個對應(yīng)關(guān)系f為散列函數(shù)，按這個思想建立的表為散列表巴席。
????若對于關(guān)鍵字集合中的任一個關(guān)鍵字历涝，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function)漾唉，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個"隨機(jī)的地址"荧库，從而減少碰撞。
散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效赵刑，通過散列函數(shù)分衫，數(shù)據(jù)元素將被更快地定位。
一個好的散列函數(shù)一般應(yīng)該考慮下列因素：
????1.計算簡單般此，以便提高轉(zhuǎn)換速度蚪战。
????2.關(guān)鍵詞對應(yīng)的地址空間分布均勻，以盡量減少沖突恤煞。
常見的 散列函數(shù) ：
1.?? 直接尋址法
????取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數(shù)),這種散列函數(shù)也叫做自身函數(shù).如果H(Key)的哈希地址上已經(jīng)有值了,那么就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進(jìn)去屎勘。
2.?? 數(shù)字分析法
????數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址居扒。
3.?? 平方取中法
????取關(guān)鍵字平方后的中間幾位作為散列地址概漱。這種方法的原理是通過取平方擴(kuò)大差別，平方值的中間幾位和這個數(shù)的每一位都相關(guān)喜喂，則對不同的關(guān)鍵字得到的哈希函數(shù)值不易產(chǎn)生沖突瓤摧，由此產(chǎn)生的哈希地址也較為均勻。該方法適用于關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象玉吁。
4.?? 折疊法
????折疊法是將關(guān)鍵字分割成位數(shù)相同的幾部分,最后一部分位數(shù)可以不同,然后取這幾部分的疊加和(注意:疊加和時去除進(jìn)位)作為散列地址照弥。
????數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊,然后相加;間界疊加是從一端向另一端沿分割界來回折疊,然后對齊相加进副。
????該方法適用于關(guān)鍵字特別多的情況这揣。
5.?? 隨機(jī)數(shù)法
????選擇一個隨機(jī)數(shù),作為散列地址,通常用于關(guān)鍵字長度不同的場合悔常。
6.?? 除留余數(shù)法
????取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關(guān)鍵字直接取模,也可在折疊、平方取中等運(yùn)算之后取模给赞。對p的選擇很重要机打，一般取素數(shù)或m，若p選得不好片迅，則很容易產(chǎn)生沖突残邀。
處理沖突
????對不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2柑蛇，而f(k1)=f(k2)芥挣，這種現(xiàn)象稱為碰撞(英語:Collision)。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞耻台。
????通過構(gòu)造性能良好的散列函數(shù)空免，可以減少沖突，但一般不可能完全避免沖突粘我，因此解決沖突是哈希法的另一個關(guān)鍵問題鼓蜒。創(chuàng)建哈希表和查找哈希表都會遇到?jīng)_突，兩種情況下解決沖突的方法應(yīng)該一致征字。
下面以創(chuàng)建哈希表為例，說明解決沖突的方法娇豫。
1.開放定址法
????這種方法也稱再散列法匙姜，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H(key)出現(xiàn)沖突時，以p為基礎(chǔ)冯痢，產(chǎn)生另一個哈希地址p1氮昧，如果p1仍然沖突，再以p為基礎(chǔ)浦楣，產(chǎn)生另一個哈希地址p2袖肥，…，直到找出一個不沖突的哈希地址pi 振劳，將相應(yīng)元素存入其中椎组。這種方法有一個通用的再散列函數(shù)形式：Hi=(H(key)+di)%m?? i=1，2历恐，…寸癌，m-1,其中H（key）為哈希函數(shù)，m 為表長弱贼，di稱為增量序列蒸苇，i為碰撞次數(shù)。增量序列的取值方式不同吮旅，相應(yīng)的再散列方式也不同溪烤。增量序列主要有以下幾種：
????(1)?線性探測再散列
????????di=1，2，3檬嘀，…莺葫，m-1
????????這種方法的特點(diǎn)是：沖突發(fā)生時，順序查看表中下一單元枪眉，直到找出一個空單元或查遍全表捺檬。
????(2)二次探測再散列
????????di=12，-12贸铜，22堡纬，-22，…蒿秦，k2烤镐，-k2( k<=m/2 )
????????這種方法的特點(diǎn)是：沖突發(fā)生時，在表的左右進(jìn)行跳躍式探測棍鳖，比較靈活炮叶。
????(3)偽隨機(jī)探測再散列
????????di=偽隨機(jī)數(shù)序列。
????線性探測再散列的優(yōu)點(diǎn)是：只要哈希表不滿渡处，就一定能找到一個不沖突的哈希地址镜悉，而二次探測再散列和偽隨機(jī)探測再散列則不一定。線性探測再散列容易產(chǎn)生“二次聚集”医瘫，即在處理同義詞的沖突時又導(dǎo)致非同義詞的沖突侣肄。
????其實除了上面的幾種方法，開放定址法還有很多變種醇份，不過都是對di有不同的表示方法稼锅。（如雙散列探測法：di=i*h2(k)）
2.再哈希法
????這種方法是同時構(gòu)造多個不同的哈希函數(shù)：Hi=RHi（key），i=1僚纷，2,3矩距，…,n。
????當(dāng)哈希地址H1=RH1（key）發(fā)生沖突時怖竭，再計算H2=RH2（key）……锥债，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集侵状，但增加了計算時間赞弥。
?3.鏈地址法(拉鏈法)
????這種方法的基本思想是將所有哈希地址相同的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表（數(shù)組）中趣兄，因而查找绽左、插入和刪除主要在同義詞鏈中進(jìn)行。若選定的散列表長度為m艇潭，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組T[0..m-1]拼窥。凡是散列地址為i的結(jié)點(diǎn)戏蔑，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應(yīng)為空指針鲁纠。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況总棵。
? ??拉鏈法的優(yōu)點(diǎn)
????????與開放定址法相比，拉鏈法有如下幾個優(yōu)點(diǎn)：
????????????(1)拉鏈法處理沖突簡單改含，且無堆積現(xiàn)象情龄，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短捍壤；
????????????(2)由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動態(tài)申請的骤视，故它更適合于造表前無法確定表長的情況；
????????????(3)開放定址法為減少沖突鹃觉，要求裝填因子α較小专酗，故當(dāng)結(jié)點(diǎn)規(guī)模較大時會浪費(fèi)很多空間。而拉鏈法中理論上可取α≥1盗扇，且結(jié)點(diǎn)較大時祷肯，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間疗隶；（散列表的裝填因子定義為：α= 填入表中的元素個數(shù) / 散列表的長度）
注：HashMap默認(rèn)裝填因子是0.75佑笋。
????????????(4)在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實現(xiàn)抽减。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可允青。而對開放定址法構(gòu)造的散列表，刪除結(jié)點(diǎn)不能簡單地將被刪結(jié)點(diǎn)的空間置為空卵沉，否則將截斷在它之后填入散列表的同義詞結(jié)點(diǎn)的查找路徑。這是因為各種開放定址法中法牲，空地址單元都被理解沒有查找到元素史汗。 因此在用開放定址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記拒垃，而不能真正刪除結(jié)點(diǎn)停撞。
? ??拉鏈法的缺點(diǎn)
????????拉鏈法的缺點(diǎn)是：指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時悼瓮，開放定址法較為節(jié)省空間戈毒，此時將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小横堡，這又減少了開放定址法中的沖突埋市，從而提高平均查找速度。
4命贴、建立公共溢出區(qū)
????這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分道宅，凡是和基本表發(fā)生沖突的元素食听，一律填入溢出表(在這個方法里面是把元素分開兩個表來存儲)。
查找性能
????散列表的查找過程基本上和造表過程相同污茵。一些關(guān)鍵碼可通過散列函數(shù)轉(zhuǎn)換的地址直接找到樱报，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找泞当。在介紹的三種處理沖突的方法中迹蛤，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過程。所以襟士，對散列表查找效率的量度盗飒，依然用平均查找長度來衡量。
????查找過程中敌蜂，關(guān)鍵碼的比較次數(shù)箩兽，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少章喉，查找效率就高汗贫，產(chǎn)生的沖突多，查找效率就低秸脱。因此落包，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素摊唇。
影響產(chǎn)生沖突多少有以下三個因素:
????1. 散列函數(shù)是否均勻;
????2. 處理沖突的方法;
????3. 散列表的裝填因子咐蝇。
????散列表的裝填因子
????????定義為:α= 填入表中的元素個數(shù) / 散列表的長度
????????α是散列表裝滿程度的標(biāo)志因子。由于表長是定值巷查，α與"填入表中的元素個數(shù)"成正比有序，所以，α越大岛请，填入表中的元素較多旭寿，產(chǎn)生沖突的可能性就越大;α越小，填入表中的元素較少崇败，產(chǎn)生沖突的可能性就越小盅称。
????????實際上，散列表的平均查找長度是裝填因子α的函數(shù)后室，只是不同處理沖突的方法有不同的函數(shù)缩膝。
哈希算法
????這個HASH算法不是大學(xué)里數(shù)據(jù)結(jié)構(gòu)課里那個HASH表的算法。這里的HASH算法是密碼學(xué)的基礎(chǔ)岸霹，了解了hash基本定義疾层，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以說是目前應(yīng)用最廣泛的Hash算法松申，而它們都是以 MD4 為基礎(chǔ)設(shè)計的云芦。
Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個方面:
? ??⑴?文件校驗
????????我們比較熟悉的校驗算法有奇偶校驗和CRC校驗俯逾，這2種校驗并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測出數(shù)據(jù)傳輸中的信道誤碼舅逸，但卻不能防止對數(shù)據(jù)的惡意破壞桌肴。
????????MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗和(Checksum)算法琉历，不少Unix系統(tǒng)有提供計算md5 checksum的命令坠七。
? ??⑵?數(shù)字簽名
????????Hash 算法也是現(xiàn)代密碼體系中的一個重要組成部分。由于非對稱算法的運(yùn)算速度較慢旗笔，所以在數(shù)字簽名協(xié)議中彪置，單向散列函數(shù)扮演了一個重要的角色。對 Hash 值蝇恶，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名拳魁，在統(tǒng)計上可以認(rèn)為與對文件本身進(jìn)行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)撮弧。
? ??⑶ 鑒權(quán)協(xié)議
????????如下的鑒權(quán)協(xié)議又被稱作挑戰(zhàn)--認(rèn)證模式:在傳輸信道是可被偵聽潘懊，但不可被篡改的情況下，這是一種簡單而安全的方法贿衍。
一致性哈希表
????一致性哈希表簡稱DHT授舟，主要應(yīng)用于分布式緩存中，可以用來解決分布式存儲結(jié)構(gòu)下動態(tài)增加和刪除節(jié)點(diǎn)所帶來的問題贸辈。比如释树，一個分布式的存儲系統(tǒng)，要將數(shù)據(jù)存儲到具體的節(jié)點(diǎn)上擎淤，如果采用普通的hash方法，將數(shù)據(jù)映射到具體的節(jié)點(diǎn)上嘴拢，如key%N（key是數(shù)據(jù)的key，N是機(jī)器節(jié)點(diǎn)數(shù)）抢腐，如果有一個機(jī)器加入或退出這個集群迈倍，則所有的數(shù)據(jù)映射都無效了啼染，如果是持久化存儲則要做數(shù)據(jù)遷移迹鹅，如果是分布式緩存斜棚，則其他緩存就失效了弟蚀。
判定哈希算法好壞的四個定義：
????1、平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去昧绣，這樣可以使得所有的緩沖空間都得到利用。
????2斩启、單調(diào)性(Monotonicity)：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中兔簇，又有新的緩沖加入到系統(tǒng)中垄琐。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去狸窘，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)翻擒。
????3、分散性(Spread)：在分布式環(huán)境中巩趁，終端有可能看不到所有的緩沖议慰，而是只能看到其中的一部分别凹。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時番川，由于不同終端所見的緩沖范圍有可能不同颁督，從而導(dǎo)致哈希的結(jié)果不一致沉御，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中吠裆。這種情況顯然是應(yīng)該避免的试疙，因為它導(dǎo)致相同內(nèi)容被存儲到不同緩沖中去祝旷，降低了系統(tǒng)存儲的效率距贷。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度忠蝗。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生阁最，也就是盡量降低分散性闽撤。
????4、負(fù)載(Load)：負(fù)載問題實際上是從另一個角度看待分散性問題闸餐。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中舍沙，那么對于一個特定的緩沖區(qū)而言拂铡，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣失球，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷黔牵。
????在分布式集群中，對機(jī)器的添加刪除跃巡，或者機(jī)器故障后自動脫離集群這些操作是分布式集群管理最基本的功能素邪。如果采用常用的hash取模算法，那么在有機(jī)器添加或者刪除后沽甥，很多原有的數(shù)據(jù)就無法找到了，這樣嚴(yán)重的違反了單調(diào)性原則媳瞪。接下來主要說明一下一致性哈希算法是如何設(shè)計的蛇受。
以SpyMemcached的ketama算法來說，思路是這樣的：
把數(shù)據(jù)用hash函數(shù)把将，映射到一個很大的空間里，如圖所示。數(shù)據(jù)的存儲時绞铃，先得到一個hash值，對應(yīng)到這個環(huán)中的每個位置，如k1對應(yīng)到了圖中所示的位置懒鉴，然后沿順時針找到一個機(jī)器節(jié)點(diǎn)B奴璃，將k1存儲到B這個節(jié)點(diǎn)中苟穆。
如果B節(jié)點(diǎn)宕機(jī)了魏颓，則B上的數(shù)據(jù)就會落到C節(jié)點(diǎn)上沦童，如下圖所示：
這樣，只會影響C節(jié)點(diǎn)，對其他的節(jié)點(diǎn)A泪电，D的數(shù)據(jù)不會造成影響鲜锚。然而旺隙，這又會造成一個“雪崩”的情況伏社，即C節(jié)點(diǎn)由于承擔(dān)了B節(jié)點(diǎn)的數(shù)據(jù)速妖，所以C節(jié)點(diǎn)的負(fù)載會變高，C節(jié)點(diǎn)很容易也宕機(jī)，這樣依次下去，這樣造成整個集群都掛了。
為此川蒙，引入了“虛擬節(jié)點(diǎn)”的概念：即把想象在這個環(huán)上有很多“虛擬節(jié)點(diǎn)”，數(shù)據(jù)的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點(diǎn)长已，每個虛擬節(jié)點(diǎn)都會關(guān)聯(lián)到一個真實節(jié)點(diǎn)畜眨，如下圖所使用：
圖中的A1、A2术瓮、B1康聂、B2、C1斤斧、C2早抠、D1、D2都是虛擬節(jié)點(diǎn)撬讽，機(jī)器A負(fù)載存儲A1蕊连、A2的數(shù)據(jù)，機(jī)器B負(fù)載存儲B1游昼、B2的數(shù)據(jù)甘苍，機(jī)器C負(fù)載存儲C1、C2的數(shù)據(jù)烘豌。由于這些虛擬節(jié)點(diǎn)數(shù)量很多载庭，均勻分布，因此不會造成“雪崩”現(xiàn)象廊佩。
