散列表（hash）是什么？

散列技術(shù)實(shí)在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系f缀磕，是的每個(gè)關(guān)鍵字key對應(yīng)一個(gè)存儲(chǔ)位置f(key)。

我們把這種對應(yīng)關(guān)系f稱為散列函數(shù)，又稱為哈希函數(shù)。按這個(gè)思路器净，采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱為散列表或者哈希表当凡。那么關(guān)鍵字對應(yīng)的記錄存儲(chǔ)位置我們稱為散列地址掌动。

散列技術(shù)最適合的求解問題是查找與給定值相等的記錄。對于查找來說宁玫，簡化了比較過程，效率就會(huì)大大提高柑晒。

我們時(shí)常會(huì)碰到兩個(gè)關(guān)鍵字key1欧瘪，key2，但是f(key1)!=f(key2)匙赞，這種現(xiàn)象我們稱之為沖突佛掖，并把key1和key2稱為散列函數(shù)的同義詞。

如何構(gòu)造散列表涌庭？

• 直接定址法
  我們?nèi)リP(guān)鍵字的某個(gè)線性函數(shù)值為散列地址芥被。即：f(key)=a*key+b(a、b為常數(shù))坐榆。

這樣的散列函數(shù)優(yōu)點(diǎn)就是簡單拴魄、均勻，也不會(huì)產(chǎn)生沖突席镀。但問題是這需要事先知道關(guān)鍵字的分布取情況匹中，適合查找表較小且連續(xù)的情況。由于這樣的限制豪诲，在現(xiàn)實(shí)應(yīng)用中顶捷，此方法雖然簡單，但卻不常用屎篱。

• 數(shù)字分析法
  抽取部分關(guān)鍵字服赎，如手機(jī)號后4位作為hash值葵蒂。這種方法適用于事先知道關(guān)鍵字分布的若干位比較均勻的情況。

• 平方取中法·
  這方法相對簡單重虑，只是把key值做平方后取中間某幾位践付。

• 折疊法
  將關(guān)鍵字從左到右分成幾部分，將這幾部分相加后取其中幾位數(shù)作為散列地址嚎尤。

• 除留余數(shù)法
  這種方法最常用荔仁。公式為f(key)=key mod p(p<=m)，mod是取模（求余數(shù)）的意思芽死。實(shí)際上乏梁，這方法不僅可以對關(guān)鍵字直接取模，也可以折疊关贵、平方后取中再取模遇骑。

顯然，本方法關(guān)鍵就在于選取核實(shí)的p揖曾，p如果選的不好落萎，就容易產(chǎn)生同義詞。

根據(jù)經(jīng)驗(yàn)炭剪，若散列表長為m练链，通常p為小于或等于表長的最小指數(shù)或不包含小于20質(zhì)因子的合數(shù)。

如何處理散列表沖突奴拦？

• 開放定址法
  一旦發(fā)生沖突媒鼓，就去找下一個(gè)空的散列地址。只要散列表足夠大错妖，空的散列地址總能找到绿鸣，并將記錄存入到該地址下。

• 再散列函數(shù)法
  對于我們的散列表來說暂氯，我們準(zhǔn)備多個(gè)散列函數(shù)潮模，f(key)=RH(key)，這里RH就是不同的散列函數(shù)痴施，可以把之前說的除留余數(shù)擎厢、折疊、平方取中全部用上晾剖，每當(dāng)發(fā)生沖突時(shí)锉矢，就換一個(gè)散列函數(shù)計(jì)算，相信總有一個(gè)散列函數(shù)能把沖突解決掉齿尽。這種方法能夠是關(guān)鍵字不聚集沽损，但也相應(yīng)的增加了計(jì)算的時(shí)間。

• 鏈地址法
  在散列表中增加單鏈表循头，產(chǎn)生沖突即在當(dāng)前位置給單鏈表增加節(jié)點(diǎn)绵估，這樣保證了絕對不會(huì)出現(xiàn)找不到地址的情況出現(xiàn)炎疆，但是也帶來了查找時(shí)需要遍歷單鏈表的性能損耗。

• 公共區(qū)溢出法
  為所有沖突的關(guān)鍵字簡歷一個(gè)公共溢出區(qū)存放国裳。在查找時(shí)形入，咸魚基本表相應(yīng)位置進(jìn)行對比，如果相等則查找成功缝左，如果不相等則到溢出表去進(jìn)行順序查找亿遂，相對基本表而言，有沖突的數(shù)據(jù)很少的情況下渺杉，公共溢出區(qū)的結(jié)構(gòu)對查找性能來說還是非常高的蛇数。

散列表查找如何實(shí)現(xiàn)？

1.定義散列表結(jié)構(gòu)并初始化散列表
2.定義散列函數(shù)
3.插入散列表：插入關(guān)鍵字時(shí)是越，先算出散列地址耳舅，如果當(dāng)前地址部位空關(guān)鍵字，則說明有沖突倚评，此時(shí)使用適當(dāng)方法解決沖突
4.通過散列表查找

什么是哈希算法浦徊？

就是以較短的信息來保證文件唯一性的標(biāo)志，這種標(biāo)志與文件的每一個(gè)字節(jié)相關(guān)天梧，而且難以找到逆向規(guī)律盔性。

哈希算法的應(yīng)用場景？

• 版本控制
  網(wǎng)絡(luò)部署和版本控制工具使用hash算法呢岗，保證文件的可靠性（當(dāng)原有文件發(fā)生改變時(shí)纯出，其標(biāo)志值也會(huì)發(fā)生改變，從而告訴文件使用者當(dāng)前的文件已經(jīng)不是所需的文件）

• 安全加密
  給證書敷燎、文檔密碼登高安全系數(shù)的內(nèi)容添加加密保護(hù)（不可逆性）

哈希算法的特點(diǎn)？

• 正向快速
  給定銘文和hash算法箩言，有限時(shí)間和有限資源內(nèi)能計(jì)算出hash值

• 逆向困難
  給定若干hash值硬贯，有限時(shí)間內(nèi)很難逆推明文

• 輸入敏感
  原始輸入有一點(diǎn)裱花，輸出差異會(huì)非常大

• 沖突避免
  很難找到兩端內(nèi)容不同明文陨收，使它們hash值一致（發(fā)生沖突）

哈希算法在密碼學(xué)中如何應(yīng)用饭豹？

登錄要輸入密碼，如果明文保存密碼务漩，很容易被破解拄衰，那么就是用hash算法，生成一個(gè)密碼的簽名饵骨，后臺(tái)保存這個(gè)簽名翘悉。由于hash算法不可逆，黑客拿到這個(gè)簽名也沒有用處居触，在你輸入密碼后妖混，后臺(tái)重新計(jì)算一下hash值老赤，與后臺(tái)保存的hash值對比，相同則允許登