什么是Hash？什么是Hash表？什么是Hash沖突？
HASH
??哈希（散列）是指：任意長度的輸入經(jīng)過hash算法轉(zhuǎn)化為固定長度的輸出。
public static String strToHashKey(String k) {
String tmpKey;
try {
final MessageDigest mDigest = MessageDigest.getInstance("MD5");
mDigest.update(k.getBytes());
tmpKey = bytesToHexString(mDigest.digest());
} catch (NoSuchAlgorithmException e) {
tmpKey = String.valueOf(k.hashCode());
}
return tmpKey;
}
private static String bytesToHexString(byte[] b) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < b.length; i++) {
String hex = Integer.toHexString(0xFF & b[i]);
if (hex.length() == 1) {
sb.append('0');
}
sb.append(hex);
}
return sb.toString();
}
public static void main(String[] args) {
String str = "TEST_HASH_01_STR";
String str2 = "TEST_HASH_02_STR";
String str3 = "TEST_HASH_03_STR";
String str4 = "TEST_HASH_04_STR";
System.out.println(str + "的hash值= " + strToHashKey(str));
System.out.println(str2 + "的hash值= " + strToHashKey(str2));
System.out.println(str3 + "的hash值= " + strToHashKey(str3));
System.out.println(str4 + "的hash值= " + strToHashKey(str4));
}
控制臺輸出
--------------------------------------------------------
TEST_HASH_01_STR的hash值= 488ffb5451eca9a66e5841f2d33127c7
TEST_HASH_02_STR的hash值= 4f637e42de1540f7f51687a1e776a5aa
TEST_HASH_03_STR的hash值= 2008b46e01406eb4a44d3176a23cdec2
TEST_HASH_04_STR的hash值= 3e8eb32d529479a488201c53232e79df
哈希的使用
Hash取模 (hash(輸入) % n)
??現(xiàn)在有3個服務(wù)器生棍，要做負載均衡，就可以對請求的ip地址或者用戶的id等使用Hash函數(shù)媳谁，然后將計算得出的Hash值對機器數(shù)取模涂滴，余數(shù)為幾，就把請求分配到相應(yīng)的服務(wù)器上韩脑。
??缺點：新增服務(wù)器或者服務(wù)器宕機的時候氢妈，絕大多數(shù)請求基本上都需要重新映射到另一個節(jié)點。這種變動有時候是不能接受的段多。比如在Web負載均衡的場景下，session會保存在每個節(jié)點里壮吩。當然进苍，如果你是“無狀態(tài)”的服務(wù)，那不會存在這個問題鸭叙。因為如果增加或者刪除了一個節(jié)點觉啊，就會導(dǎo)致幾乎所有的數(shù)據(jù)都需要重新遷移。
一致性Hash
??盡可能降低分布式環(huán)境下沈贝，通過哈希定位運算確認元素位置的集群服務(wù)受機器數(shù)的影響杠人，避免使用固定值取模，改為范圍定位的方式宋下。
上面的取模運算的除數(shù)是機器數(shù)嗡善，而一致性Hash的除數(shù)是2^32（int類型的最大值）。從0到232 - 1,首尾相連構(gòu)成了一個環(huán)学歧。
我們先對服務(wù)器節(jié)點的IP進行Hash罩引，然后除以2^32
得到服務(wù)器節(jié)點在這個Hash環(huán)中的位置。如果有請求進來了枝笨，同樣進行Hash然后處于2^32求余袁铐。如果落在Hash環(huán)上，然后順時針找到第一個節(jié)點横浑，這個節(jié)點就負責處理這個請求剔桨。
優(yōu)點：解決因為橫向伸縮導(dǎo)致的大規(guī)模數(shù)據(jù)變動。
缺點：一致性Hash算法在節(jié)點數(shù)量較少的時候徙融，會出現(xiàn)分布不均勻的問題洒缀。
解決方案就是在Hash環(huán)上增加虛擬節(jié)點。
哈希的應(yīng)用
??1.密碼學和數(shù)字簽名张咳。
??2.文件的完整性檢查帝洪。
??3.基于HASH的數(shù)據(jù)結(jié)構(gòu)似舵。
哈希算法的特點
??1.不可逆：不可以根據(jù)hash值計算出原值。
??2.效率高葱峡，HASH運算能快速計算出結(jié)果砚哗。
??3.沖突少，優(yōu)秀的哈希算法具備的特點砰奕。
哈希算法
（1）MD4
??MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年設(shè)計的蛛芥，MD 是 Message Digest（消息摘要） 的縮寫。它適用在32位字長的處理器上用高速軟件實現(xiàn)——它是基于 32位操作數(shù)的位操作來實現(xiàn)的军援。
（2）MD5
??MD5（RFC 1321）是 Rivest 于1991年對MD4的改進版本仅淑。它對輸入仍以512位分組，其輸出是4個32位字的級聯(lián)胸哥，與 MD4 相同涯竟。MD5比MD4來得復(fù)雜，并且速度較之要慢一點空厌，但更安全庐船，在抗分析和抗差分方面表現(xiàn)更好。
（3）SHA-1及其他
??SHA1是由NIST NSA設(shè)計為同DSA一起使用的嘲更，它對長度小于264的輸入筐钟，產(chǎn)生長度為160bit的散列值，因此抗窮舉（brute-force）性更好赋朦。SHA-1 設(shè)計時基于和MD4相同原理篓冲，并且模仿了該算法。
什么是Hash表宠哄？什么又是Hash沖突壹将？
HASH表
??哈希表是基于數(shù)組的一種存儲方式，它主要由哈希函數(shù)和數(shù)組構(gòu)成琳拨。當要存儲一個數(shù)據(jù)的時候瞭恰，首先用一個函數(shù)計算數(shù)據(jù)的地址，然后再將數(shù)據(jù)存進指定地址位置的數(shù)組里面狱庇。這個函數(shù)就是哈希函數(shù)惊畏，而這個數(shù)組就是哈希表。
哈希沖突
??哈希是通過對數(shù)據(jù)進行再壓縮密任，轉(zhuǎn)為為固定長度的輸出颜启。但由于通過哈希函數(shù)產(chǎn)生的哈希值是有限的，而數(shù)據(jù)可能比較多浪讳，導(dǎo)致經(jīng)過哈希函數(shù)處理后仍然有不同的數(shù)據(jù)對應(yīng)相同的值缰盏。
哈希沖突的影響因素
裝填因子（裝填因子=數(shù)據(jù)總數(shù) / 哈希表長）、哈希函數(shù)、處理沖突的方法
HASH沖突的解決方案
1.開放地址方法
（1）線性探測
??按順序決定值時口猜，如果某數(shù)據(jù)的值已經(jīng)存在负溪，則在原來值的基礎(chǔ)上往后加一個單位，直至不發(fā)生哈希沖突济炎。
（2）再平方探測
??按順序決定值時川抡，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來值的基礎(chǔ)上先加1的平方個單位须尚，若仍然存在則減1的平方個單位崖堤。隨之是2的平方，3的平方等等耐床。直至不發(fā)生哈希沖突密幔。
（3）偽隨機探測
??按順序決定值時，如果某數(shù)據(jù)已經(jīng)存在撩轰，通過隨機函數(shù)隨機生成一個數(shù)胯甩，在原來值的基礎(chǔ)上加上隨機數(shù)，直至不發(fā)生哈希沖突钧敞。
2.鏈式地址法（HashMap的哈希沖突解決方法）
對于相同的值蜡豹，使用鏈表進行連接。使用數(shù)組存儲每一個鏈表溉苛。
優(yōu)點：
（1）拉鏈法處理沖突簡單，且無堆積現(xiàn)象弄诲，即非同義詞決不會發(fā)生沖突愚战，因此平均查找長度較短；
（2）由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的齐遵，故它更適合于造表前無法確定表長的情況寂玲；
（3）開放定址法為減少沖突，要求裝填因子α較小梗摇，故當結(jié)點規(guī)模較大時會浪費很多空間拓哟。而拉鏈法中可取α≥1，且結(jié)點較大時伶授，拉鏈法中增加的指針域可忽略不計断序，因此節(jié)省空間；
（4）在用拉鏈法構(gòu)造的散列表中糜烹，刪除結(jié)點的操作易于實現(xiàn)违诗。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。
缺點：
??指針占用較大空間時疮蹦，會造成空間浪費诸迟，若空間用于增大散列表規(guī)模進而提高開放地址法的效率。
3.建立公共溢出區(qū)
??建立公共溢出區(qū)存儲所有哈希沖突的數(shù)據(jù)。
4.再哈希法
??對于沖突的哈希值再次進行哈希處理阵苇，直至沒有哈希沖突壁公。
