哈希
Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。
這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間。
沖突/碰撞：不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。
特點/優(yōu)勢：
- 很難找到逆向規(guī)律
- 提高存儲空間的利用
- 提高數(shù)據(jù)的查詢效率
- 保障數(shù)據(jù)傳遞的安全性
常用哈希函數(shù)
- 直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)
- 數(shù)字分析法：找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。比如，生日的后幾位。
- 平方取中法：取關(guān)鍵字平方后的中間幾位作為散列地址。
- 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址。
- 隨機數(shù)法：選擇一隨機函數(shù)，取關(guān)鍵字作為隨機函數(shù)的種子生成隨機值作為散列地址，通常用于關(guān)鍵字長度不同的場合。
- 除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生碰撞。
處理沖突的方法：
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)元素存入其中。
線性探測再散列/二次探測再散列/偽隨機探測再散列
2． 再哈希法
這種方法是同時構(gòu)造多個不同的哈希函數(shù)：
Hi=RH1（key） i=1，2，…，k
當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間
3． 鏈地址法(拉鏈法)：這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。
4． 建立一個公共溢出區(qū)：這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。
hash算法：
MD4、MD5、SHA-1及其他
散列表
（Hash table，也叫哈希表）是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表
