從HashMap說起

散列表（Hash table，也叫哈希表）虹钮，是依據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)翼雀。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問記錄炊邦，以加快查找的速度编矾。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表馁害。

比方我們存儲(chǔ)70個(gè)元素洽沟，但我們可能為這70個(gè)元素申請(qǐng)了100個(gè)元素的空間。70/100=0.7蜗细，這個(gè)數(shù)字稱為負(fù)載因子裆操。我們之所以這樣做怒详，也是為了“高速存取”的目的。我們基于一種結(jié)果盡可能隨機(jī)平均分布的固定函數(shù)H為每一個(gè)元素安排存儲(chǔ)位置踪区，這樣就能夠避免遍歷性質(zhì)的線性搜索昆烁，以達(dá)到高速存取《懈冢可是因?yàn)榇穗S機(jī)性静尼，也必定導(dǎo)致一個(gè)問題就是沖突。所謂沖突传泊，即兩個(gè)元素通過散列函數(shù)H得到的地址同樣鼠渺，那么這兩個(gè)元素稱為“同義詞”。這類似于70個(gè)人去一個(gè)有100個(gè)椅子的飯店吃飯眷细。散列函數(shù)的計(jì)算結(jié)果是一個(gè)存儲(chǔ)單位地址拦盹，每一個(gè)存儲(chǔ)單位稱為“桶”。設(shè)一個(gè)散列表有m個(gè)桶溪椎，則散列函數(shù)的值域應(yīng)為[0,m-1]普舆。

解決沖突是一個(gè)復(fù)雜問題。沖突主要取決于：

• 散列函數(shù)校读，一個(gè)好的散列函數(shù)的值應(yīng)盡可能平均分布沼侣。
• 處理沖突方法。
• 負(fù)載因子的大小歉秫。太大不一定就好蛾洛，并且浪費(fèi)空間嚴(yán)重，負(fù)載因子和散列函數(shù)是聯(lián)動(dòng)的雁芙。

解決沖突的辦法：

• 線性探查法：沖突后轧膘，線性向前試探，找到近期的一個(gè)空位置却特。缺點(diǎn)是會(huì)出現(xiàn)堆積現(xiàn)象扶供。存取時(shí)，可能不是同義詞的詞也位于探查序列裂明，影響效率椿浓。
• 鏈地址法：
• 溢出區(qū)法：
• 再散列函數(shù)法：在位置d沖突后，再次使用還有一個(gè)散列函數(shù)產(chǎn)生一個(gè)與散列表桶容量m互質(zhì)的數(shù)c闽晦，依次試探(d+n*c)%m扳碍，使探查序列跳躍式分布。

構(gòu)造散列函數(shù)的方法

1. 直接尋址法：取keyword或keyword的某個(gè)線性函數(shù)值為散列地址仙蛉。即H(key)=key或H(key) = a?key + b笋敞，當(dāng)中a和b為常數(shù)（這樣的散列函數(shù)叫做自身函數(shù)）

2. 數(shù)字分析法：分析一組數(shù)據(jù)，比方一組員工的出生年月日荠瘪，這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體同樣夯巷，這種話赛惩，出現(xiàn)沖突的幾率就會(huì)非常大，可是我們發(fā)現(xiàn)年月日的后幾位表示月份和詳細(xì)日期的數(shù)字區(qū)別非常大趁餐，假設(shè)用后面的數(shù)字來(lái)構(gòu)成散列地址喷兼，則沖突的幾率會(huì)明顯減少。因此數(shù)字分析法就是找出數(shù)字的規(guī)律后雷，盡可能利用這些數(shù)據(jù)來(lái)構(gòu)造沖突幾率較低的散列地址季惯。

3. 平方取中法：取keyword平方后的中間幾位作為散列地址。

4. 折疊法：將keyword切割成位數(shù)同樣的幾部分臀突，最后一部分位數(shù)能夠不同勉抓，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。

5. 隨機(jī)數(shù)法：選擇一隨機(jī)函數(shù)候学，取keyword的隨機(jī)值作為散列地址藕筋，通經(jīng)常使用于keyword長(zhǎng)度不同的場(chǎng)合。

6. 除留余數(shù)法：取keyword被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址盒齿。即 H(key) = key MOD p, p<=m念逞。不僅能夠?qū)eyword直接取模困食，也可在折疊边翁、平方取中等運(yùn)算之后取模。對(duì)p的選擇非常重要硕盹，一般取素?cái)?shù)或m符匾，若p選的不好，easy產(chǎn)生同義詞瘩例。

著名的hash算法

• MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的啊胶，MD 是 Message Digest 的縮寫。它適用在32位字長(zhǎng)的處理器上用快速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作來(lái)實(shí)現(xiàn)的垛贤。

• MD5(RFC 1321)是 Rivest 于1991年對(duì)MD4的改進(jìn)版本號(hào)焰坪。它對(duì)輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)聘惦，與 MD4 同樣某饰。MD5比MD4來(lái)得復(fù)雜，而且速度較之要慢一點(diǎn)善绎，但更安全黔漂，在抗分析和抗差分方面表現(xiàn)更好

• SHA-1：SHA1是由NIST NSA設(shè)計(jì)為同DSA一起使用的，它對(duì)長(zhǎng)度小于264的輸入禀酱，產(chǎn)生長(zhǎng)度為160bit的散列值炬守，因此抗窮舉(brute-force)性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4同樣原理,而且模仿了該算法剂跟。

Hash算法在信息安全方面的應(yīng)用主要體如今下面的3個(gè)方面：

• 文件校驗(yàn)
• 數(shù)字簽名
• 鑒權(quán)協(xié)議

分類

Hash函數(shù)應(yīng)用的主要對(duì)象是數(shù)組（比方减途，字符串）酣藻，而其目標(biāo)通常是一個(gè)int類型。
一般的說鳍置，Hash函數(shù)能夠簡(jiǎn)單的劃分為例如以下幾類：

1. 加法Hash臊恋；
2. 位運(yùn)算Hash；
3. 乘法Hash墓捻；
4. 除法Hash抖仅；
5. 查表Hash；
6. 混合Hash砖第；
   以下具體的介紹以上各種方式在實(shí)際中的運(yùn)用撤卢。

一 加法Hash

所謂的加法Hash就是把輸入元素一個(gè)一個(gè)的加起來(lái)構(gòu)成最后的結(jié)果。標(biāo)準(zhǔn)的加法Hash的構(gòu)造例如以下：

static int additiveHash(String key, int prime)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
這里的prime是隨意的質(zhì)數(shù)梧兼，看得出放吩，結(jié)果的值域?yàn)閇0,prime-1]。

二 位運(yùn)算Hash

這類型Hash函數(shù)通過利用各種位運(yùn)算（常見的是移位和異或）來(lái)充分的混合輸入元素羽杰。比方渡紫，標(biāo)準(zhǔn)的旋轉(zhuǎn)Hash的構(gòu)造例如以下：

static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i < key.length(); i++)
hash = (hash<<4>>28)^key.charAt(i);
return (hash % prime);
}
先移位，然后再進(jìn)行各種位運(yùn)算是這樣的類型Hash函數(shù)的主要特點(diǎn)考赛。比方惕澎，以上的那段計(jì)算hash的代碼還能夠有例如以下幾種變形：

hash = (hash<<5>>27)^key.charAt(i);
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
if((i&1) == 0)
{
hash ^= (hash<<7>>3);
}
else
{
hash ^= ~((hash<<11>>5));
}
hash += (hash<<5>
hash = key.charAt(i) + (hash<<6>>16) ? hash;
hash ^= ((hash<<5>>2));

三 乘法Hash

這樣的類型的Hash函數(shù)利用了乘法的不相關(guān)性（乘法的這樣的性質(zhì)，最有名的莫過于平方取頭尾的隨機(jī)數(shù)生成算法颜骤，盡管這樣的算法效果并不好）唧喉。
使用這樣的方式的著名Hash函數(shù)還有：

// 32位FNV算法
int M_SHIFT = 0;
public int FNVHash(byte[] data)
{
int hash = (int)2166136261L;
for(byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
以及改進(jìn)的FNV算法：

public static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
除了乘以一個(gè)固定的數(shù)，常見的還有乘以一個(gè)不斷改變的數(shù)忍抽，比方：

static int RSHash(String str)
{
int b = 378551;
int a = 63689;
int hash = 0;

 for(int i = 0; i < str.length(); i++)
 {
    hash = hash * a + str.charAt(i);
    a    = a * b;
 }
 return (hash & 0x7FFFFFFF);

}

查表Hash

查表Hash最有名的樣例莫過于CRC系列算法八孝。盡管CRC系列算法本身并非查表，可是鸠项，查表是它的一種最快的實(shí)現(xiàn)方式干跛。

混合Hash

混合Hash算法利用了以上各種方式。各種常見的Hash算法祟绊，比方MD5楼入、Tiger都屬于這個(gè)范圍。它們一般非常少在面向查找的Hash函數(shù)里面使用久免。

快速的String Hash

paper：https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Ref：
http://www.cnblogs.com/mengfanrong/p/4034950.html