（點擊上方公眾號，可快速關注）
來源：mengfanrong
連結：www.cnblogs.com/mengfanrong/p/4034950.html
散列表，它是基於高速存取的角度設計的，也是一種典型的「空間換時間」的做法。顧名思義，該數據結構能夠理解為一個線性表，可是當中的元素不是緊密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是依據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
比方我們存儲70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0.7，這個數字稱為負載因子。我們之所以這樣做，也是為了「高速存取」的目的。我們基於一種結果儘可能隨機平均分布的固定函數H為每一個元素安排存儲位置，這樣就能夠避免遍歷性質的線性搜索，以達到高速存取。可是因為此隨機性，也必定導致一個問題就是衝突。
所謂衝突，即兩個元素通過散列函數H得到的地址同樣，那麼這兩個元素稱為「同義詞」。這類似於70個人去一個有100個椅子的飯店吃飯。散列函數的計算結果是一個存儲單位地址，每一個存儲單位稱為「桶」。設一個散列表有m個桶，則散列函數的值域應為[0,m-1]。
解決衝突是一個複雜問題。衝突主要取決於：
（1）散列函數，一個好的散列函數的值應儘可能平均分布。
（2）處理衝突方法。
（3）負載因子的大小。太大不一定就好，並且浪費空間嚴重，負載因子和散列函數是聯動的。
解決衝突的辦法：
（1）線性探查法：衝突後，線性向前試探，找到近期的一個空位置。缺點是會出現堆積現象。存取時，可能不是同義詞的詞也位於探查序列，影響效率。
（2）雙散列函數法：在位置d衝突後，再次使用還有一個散列函數產生一個與散列表桶容量m互質的數c，依次試探(d+n*c)%m，使探查序列跳躍式分布。
經常使用的構造散列函數的方法
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位：
1. 直接尋址法：取keyword或keyword的某個線性函數值為散列地址。即H(key)=key或H(key) = a•key + b，當中a和b為常數（這樣的散列函數叫做自身函數）
2. 數字分析法：分析一組數據，比方一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體同樣，這種話，出現衝突的機率就會非常大，可是我們發現年月日的後幾位表示月份和詳細日期的數字區別非常大，假設用後面的數字來構成散列地址，則衝突的機率會明顯減少。因此數字分析法就是找出數字的規律，儘可能利用這些數據來構造衝突機率較低的散列地址。
3. 平方取中法：取keyword平方後的中間幾位作為散列地址。
4. 摺疊法：將keyword切割成位數同樣的幾部分，最後一部分位數能夠不同，然後取這幾部分的疊加和（去除進位）作為散列地址。
5. 隨機數法：選擇一隨機函數，取keyword的隨機值作為散列地址，通經常使用於keyword長度不同的場合。
6. 除留餘數法：取keyword被某個不大於散列表表長m的數p除後所得的餘數為散列地址。即 H(key) = key MOD p, p<=m。不僅能夠對keyword直接取模，也可在摺疊、平方取中等運算之後取模。對p的選擇非常重要，一般取素數或m，若p選的不好，easy產生同義詞。
查找的性能分析
散列表的查找過程基本上和造表過程同樣。一些關鍵碼可通過散列函數轉換的地址直接找到，還有一些關鍵碼在散列函數得到的地址上產生了衝突，須要按處理衝突的方法進行查找。在介紹的三種處理衝突的方法中，產生衝突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依舊用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生衝突的多少，產生的衝突少，查找效率就高，產生的衝突多，查找效率就低。因此，影響產生衝突多少的因素，也就是影響查找效率的因素。影響產生衝突多少有下面三個因素：
1. 散列函數是否均勻；
2. 處理衝突的方法；
3. 散列表的裝填因子。
散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度
α是散列表裝滿程度的標誌因子。因為表長是定值，α與「填入表中的元素個數」成正比，所以，α越大，填入表中的元素較多，產生衝突的可能性就越大；α越小，填入表中的元素較少，產生衝突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函數，僅僅是不同處理衝突的方法有不同的函數。
了解了hash基本定義，就不能不提到一些著名的hash算法，MD5 和 SHA-1 能夠說是眼下應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的。那麼他們都是什麼意思呢?
這裡簡單說一下：
（1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用快速軟體實現–它是基於 32 位操作數的位操作來實現的。
（2) MD5
MD5(RFC 1321)是 Rivest 於1991年對MD4的改進版本號。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 同樣。MD5比MD4來得複雜，而且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好
（3) SHA-1 及其它
SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小於264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基於和MD4同樣原理,而且模仿了該算法。
哈希表不可避免衝突(collision)現象：對不同的keyword可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2)。因此，在建造哈希表時不僅要設定一個好的哈希函數，並且要設定一種處理衝突的方法。可例如以下描寫敘述哈希表：依據設定的哈希函數H(key)和所選中的處理衝突的方法，將一組keyword映象到一個有限的、地址連續的地址集(區間)上並以keyword在地址集中的「象」作為對應記錄在表中的存儲位置，這樣的表被稱為哈希表。
對於動態查找表而言，1) 表長不確定；2)在設計查找表時，僅僅知道keyword所屬範圍，而不知道確切的keyword。因此，普通情況需建立一個函數關係，以f(key)作為keyword為key的錄在表中的位置，通常稱這個函數f(key)為哈希函數。(注意：這個函數並不一定是數學函數)
哈希函數是一個映象，即：將keyword的集合映射到某個地址集合上，它的設置非常靈活，僅僅要這個地址集合的大小不超出同意範圍就可以。
現實中哈希函數是須要構造的，而且構造的好才幹使用的好。
那麼這些Hash算法究竟有什麼用呢?
Hash算法在信息安全方面的應用主要體如今下面的3個方面：
（1) 文件校驗
我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗數據篡改的能力，它們一定程度上能檢測並糾正傳輸數據中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash算法的」數字指紋」特性，使它成為眼下應用最廣泛的一種文件完整性校驗和(Checksum)算法，不少Unix系統有提供計算md5 checksum的命令。
（2) 數字籤名
Hash 算法也是現代password體系中的一個重要組成部分。因為非對稱算法的運算速度較慢，所以在數字籤名協議中，單向散列函數扮演了一個重要的角色。 對 Hash 值，又稱」數字摘要」進行數字籤名，在統計上能夠覺得與對文件本身進行數字籤名是等效的。並且這種協議還有其它的長處。
（3) 鑑權協議
例如以下的鑑權協議又被稱作挑戰–認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
文件hash值
MD5-Hash-文件的數字文摘通過Hash函數計算得到。無論文件長度怎樣，它的Hash函數計算結果是一個固定長度的數字。與加密算法不同，這一個Hash算法是一個不可逆的單向函數。採用安全性高的Hash算法，如MD5、SHA時，兩個不同的文件差點兒不可能得到同樣的Hash結果。因此，一旦文件被改動，就可檢測出來。
Hash函數還有另外的含義。實際中的Hash函數是指把一個大範圍映射到一個小範圍。把大範圍映射到一個小範圍的目的往往是為了節省空間，使得數據easy保存。除此以外，Hash函數往往應用於查找上。所以，在考慮使用Hash函數之前，須要明確它的幾個限制：
1. Hash的主要原理就是把大範圍映射到小範圍；所以，你輸入的實際值的個數必須和小範圍相當或者比它更小。不然衝突就會非常多。
2. 因為Hash逼近單向函數；所以，你能夠用它來對數據進行加密。
3. 不同的應用對Hash函數有著不同的要求；比方，用於加密的Hash函數主要考慮它和單項函數的差距，而用於查找的Hash函數主要考慮它映射到小範圍的衝突率。
應用於加密的Hash函數已經探討過太多了，在作者的博客裡面有更具體的介紹。所以，本文僅僅探討用於查找的Hash函數。
Hash函數應用的主要對象是數組（比方，字符串），而其目標通常是一個int類型。下面我們都依照這樣的方式來說明。
一般的說，Hash函數能夠簡單的劃分為例如以下幾類：
1. 加法Hash；
2. 位運算Hash；
3. 乘法Hash；
4. 除法Hash；
5. 查表Hash；
6. 混合Hash；
以下具體的介紹以上各種方式在實際中的運用。
一 加法Hash
所謂的加法Hash就是把輸入元素一個一個的加起來構成最後的結果。標準的加法Hash的構造例如以下：
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是隨意的質數，看得出，結果的值域為[0,prime-1]。
二 位運算Hash
這類型Hash函數通過利用各種位運算（常見的是移位和異或）來充分的混合輸入元素。比方，標準的旋轉Hash的構造例如以下：
static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i
hash = (hash<>28)^key.charAt(i);
return (hash % prime);
}
先移位，然後再進行各種位運算是這樣的類型Hash函數的主要特點。比方，以上的那段計算hash的代碼還能夠有例如以下幾種變形：
hash = (hash<>27)^key.charAt(i);
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
if((i&1) == 0)
{
hash ^= (hash<>3);
}
else
{
hash ^= ~((hash<>5));
}
hash += (hash<
hash = key.charAt(i) + (hash<>16) ? hash;
hash ^= ((hash<>2));
三 乘法Hash
這樣的類型的Hash函數利用了乘法的不相關性（乘法的這樣的性質，最有名的莫過於平方取頭尾的隨機數生成算法，儘管這樣的算法效果並不好）。比方，
static int bernstein(String key)
{
int hash = 0;
int i;
for (i=0; i
return hash;
}
jdk5.0裡面的String類的hashCode()方法也使用乘法Hash。只是，它使用的乘數是31。推薦的乘數還有：131, 1313, 13131, 131313等等。
使用這樣的方式的著名Hash函數還有：
// 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;
}
以及改進的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;
}
除了乘以一個固定的數，常見的還有乘以一個不斷改變的數，比方：
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);
}
儘管Adler32算法的應用沒有CRC32廣泛，只是，它可能是乘法Hash裡面最有名的一個了。關於它的介紹，大家能夠去看RFC 1950規範。
四 除法Hash
除法和乘法一樣，相同具有表面上看起來的不相關性。只是，由於除法太慢，這樣的方式差點兒找不到真正的應用。須要注意的是，我們在前面看到的hash的 結果除以一個prime的目的僅僅是為了保證結果的範圍。假設你不須要它限制一個範圍的話，能夠使用例如以下的代碼替代」hash%prime」： hash = hash ^ (hash>>10) ^ (hash>>20)。
五 查表Hash
查表Hash最有名的樣例莫過於CRC系列算法。儘管CRC系列算法本身並非查表，可是，查表是它的一種最快的實現方式。以下是CRC32的實現：
static int crctab[256] = {
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,0xjobbole
0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};
int crc32(String key, int hash)
{
int i;
for (hash=key.length(), i=0; i
hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k.charAt(i)];
return hash;
}
查表Hash中有名的樣例有：Universal Hashing和Zobrist Hashing。他們的表格都是隨機生成的。
六 混合Hash
混合Hash算法利用了以上各種方式。各種常見的Hash算法，比方MD5、Tiger都屬於這個範圍。它們一般非常少在面向查找的Hash函數裡面使用。
七 對Hash算法的評價
http://www.burtleburtle.net/bob/hash/doobs.html 這個頁面提供了對幾種流行Hash算法的評價。我們對Hash函數的建議例如以下：
1. 字符串的Hash。最簡單能夠使用主要的乘法Hash，當乘數為33時，對於英文單詞有非常好的散列效果（小於6個的小寫形式能夠保證沒有衝突）。複雜一點能夠使用FNV算法（及其改進形式），它對於比較長的字符串，在速度和效果上都不錯。
public override unsafe int GetHashCode()
{//微軟System.String 字符串哈希算法
fixed (char* str= ((char*) this))
{
char* chPtr = str;
intnum = 0x15051505;
intnum2 = num;
int* numPtr = (int*) chPtr;
for (inti = this.Length; i > 0; i -= 4)
{
num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
if (i <= 2)
{
break;
}
num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
numPtr += 2;
}
return (num + (num2 * 0x5d588b65));
}
}
2. 長數組的Hash。能夠使用http://burtleburtle.net/bob/c/lookup3.c這樣的算法，它一次運算多個字節，速度還算不錯。
關注「算法愛好者」
看更多精選算法技術文章
↓↓↓