[TOC]
本文轉(zhuǎn)自其他人的博客。簡化了一下，方便備忘浦徊。
概述
Hash一般翻譯作散列也有直接音譯作“哈希”天梧。就是把任意長度的輸入通過散列算法變換成固定長度的輸出盔性，該輸出就是散列值。
散列值的空間通常遠(yuǎn)小于輸入的空間腿倚，不同的輸入可能會散列成相同的輸出纯出，所以不可能從散列值來確定唯一的輸入值蚯妇。
哈希函數(shù)的應(yīng)用非常廣泛，各種校驗暂筝、簽名箩言、密碼，都是哈希函數(shù)應(yīng)用的重要場景焕襟。
性質(zhì)
- 確定性：哈希的散列值不同陨收，那么哈希的原始輸入也就不同。
- 不確定性：同一個散列值很有可能對應(yīng)多個不同的原始輸入鸵赖。稱為“哈希碰撞”务漩。
實現(xiàn)
哈希函數(shù)的實現(xiàn)分為兩部分：構(gòu)造和解決沖突。
構(gòu)造
哈希函數(shù)的構(gòu)造應(yīng)該滿足以下準(zhǔn)則：
- 散列函數(shù)的計算簡單它褪，快速饵骨。
- 散列函數(shù)能將關(guān)鍵字集合K均勻地分布在地址集{0,1，…茫打，m-1}上居触，使沖突最小。
直接定址法
H(key) = key 或 H(key) = a·key + b
直接定址法老赤，不會有哈希沖突轮洋。但實際這樣使用的情況較少。
相乘取整法
H(key) = (int) ( m * ( key*A - (int)(key*A) ) ) 其中 0 < A < 1
注意：該方法最大的優(yōu)點是m的選取比除余法要求更低抬旺。比如弊予，完全可選擇它是2的整數(shù)次冪。雖然該方法對任何A的值都適用开财，但對某些值效果會更好汉柒。Knuth建議選取 0.61803……。
平方取中法
取關(guān)鍵字平方后的中間幾位為哈希地址床未。
F(a) = a的中間三位竭翠。
H(key) = F(key^2)
除留余數(shù)法
H(key) = key MOD p (p ≤ m)
隨機數(shù)法
H(key) = random (key)
jdk中HashMap的hash構(gòu)造
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
哈希沖突的解決
開放地址法
就是在發(fā)生沖突后振坚，通過某種探測技術(shù)薇搁，去依次探查其他單元，直到探查到不沖突為止渡八，將元素添加進(jìn)去啃洋。
假如是在index的位置發(fā)生哈希沖突，那么通常有一下幾種探測方式：
線性探測法（線性探測再散列）
向后依次探測index+1屎鳍，index+2…位置宏娄，看是否沖突，直到不沖突為止逮壁，將元素添加進(jìn)去孵坚。
平方探測法
不探測index的后一個位置，而是探測2i位置，比如探測20位置上時發(fā)生沖突卖宠，接著探測2^1位置巍杈，依此類推，直至沖突解決扛伍。
再哈希法：（雙散列法）
在發(fā)生哈希沖突后筷畦，使用另外一個哈希算法產(chǎn)生一個新的地址，直到不發(fā)生沖突為止刺洒。這個應(yīng)該很好理解鳖宾。
再哈希法可以有效的避免堆積現(xiàn)象，但是缺點是不能增加了計算時間和哈希算法的數(shù)量逆航，而且不能保證在哈希表未滿的情況下鼎文，總能找到不沖突的地址。
鏈地址法（開散列法）
基本思想：
鏈表法就是在發(fā)生沖突的地址處因俐，掛一個單向鏈表漂问，然后所有在該位置沖突的數(shù)據(jù)，都插入這個鏈表中女揭。插入數(shù)據(jù)的方式有多種蚤假，可以從鏈表的尾部向頭部依次插入數(shù)據(jù)，也可以從頭部向尾部依次插入數(shù)據(jù)吧兔，也可以依據(jù)某種規(guī)則在鏈表的中間插入數(shù)據(jù)磷仰，總之保證鏈表中的數(shù)據(jù)的有序性。Java的HashMap類就是采取鏈表法的處理方案境蔼。
結(jié)語
哈希表一旦發(fā)生沖突灶平，其性能就會顯著下降。因此建立哈希表時必須規(guī)避哈希沖突的產(chǎn)生箍土，大多數(shù)哈希表的實現(xiàn)都是：第一步逢享，是通過哈希算法將key值轉(zhuǎn)換一個整數(shù)以確定數(shù)據(jù)的存儲位置；第二步吴藻，檢查是否發(fā)生哈希沖突瞒爬，以及確定發(fā)生沖突后的處理方案。
