一棒口、什么是哈希算法芥被？
- 定義
將任意長(zhǎng)度的二進(jìn)制值串映射成固定長(zhǎng)度的二進(jìn)制值串，這個(gè)映射的規(guī)則就是哈希算法屹逛，而通過(guò)原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值。 - 如何設(shè)計(jì)一個(gè)優(yōu)秀的哈希算法汛骂？
- 單向哈希：
從哈希值不能反向推導(dǎo)出哈希值（所以哈希算法也叫單向哈希算法）罕模。 - 篡改無(wú)效：
對(duì)輸入敏感，哪怕原始數(shù)據(jù)只修改一個(gè)Bit帘瞭，最后得到的哈希值也大不相同淑掌。 - 散列沖突：
散列沖突的概率要很小，對(duì)于不同的原始數(shù)據(jù)蝶念，哈希值相同的概率非常小抛腕。 - 執(zhí)行效率：
哈希算法的執(zhí)行效率要盡量高效芋绸，針對(duì)較長(zhǎng)的文本，也能快速計(jì)算哈希值担敌。
二摔敛、哈希算法的常見應(yīng)用有哪些？
7個(gè)常見應(yīng)用：安全加密全封、唯一標(biāo)識(shí)马昙、數(shù)據(jù)校驗(yàn)、散列函數(shù)刹悴、負(fù)載均衡行楞、數(shù)據(jù)分片、分布式存儲(chǔ)
- 安全加密
- 常用于加密的哈希算法：
MD5：MD5 Message-Digest Algorithm颂跨，MD5消息摘要算法
SHA：Secure Hash Algorithm敢伸，安全散列算法
DES：Data Encryption Standard，數(shù)據(jù)加密標(biāo)準(zhǔn)
AES：Advanced Encryption Standard恒削，高級(jí)加密標(biāo)準(zhǔn) - 對(duì)用于加密的哈希算法池颈，有兩點(diǎn)格外重要，第一點(diǎn)是很難根據(jù)哈希值反向推導(dǎo)出原始數(shù)據(jù)钓丰，第二點(diǎn)是散列沖突的概率要小躯砰。
- 在實(shí)際開發(fā)中要權(quán)衡破解難度和計(jì)算時(shí)間來(lái)決定究竟使用哪種加密算法。
唯一標(biāo)識(shí)
通過(guò)哈希算法計(jì)算出數(shù)據(jù)的唯一標(biāo)識(shí)携丁，從而用于高效檢索數(shù)據(jù)琢歇。數(shù)據(jù)校驗(yàn)
利用哈希算法對(duì)輸入數(shù)據(jù)敏感的特點(diǎn)，可以對(duì)數(shù)據(jù)取哈希值梦鉴，從而高效校驗(yàn)數(shù)據(jù)是否被篡改過(guò)李茫。散列函數(shù)
散列函數(shù)中用到的哈希算法更加關(guān)注散列后的值能不能平均分布，以及散列函數(shù)的執(zhí)行快慢肥橙。負(fù)載均衡
- 如何實(shí)現(xiàn)一個(gè)會(huì)話粘滯（session sticky）的負(fù)載均衡算法魄宏？也就是說(shuō)，在一次會(huì)話中的所有請(qǐng)求都路由到同一個(gè)服務(wù)器上存筏？
- 通過(guò)哈希算法對(duì)客戶端IP或會(huì)話ID計(jì)算哈希值宠互，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號(hào)椭坚。這樣予跌，就可以把同一個(gè)IP過(guò)來(lái)的請(qǐng)求都路由到同一個(gè)后端服務(wù)器上。
- 數(shù)據(jù)分片
- 如何統(tǒng)計(jì)“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)善茎？
- 需求描述
假如我們有1T的日志文件券册，這里面記錄了用戶的搜索關(guān)鍵詞，我們想要快速統(tǒng)計(jì)出每個(gè)關(guān)鍵詞被搜索的次數(shù)，該怎么做呢汁掠？ - 問(wèn)題分析
這個(gè)問(wèn)題有兩個(gè)難點(diǎn)略吨，第一個(gè)是搜索的日子很大，沒辦法放到一臺(tái)機(jī)器的內(nèi)存中考阱。第二個(gè)是只用一臺(tái)機(jī)器來(lái)處理這么巨大的數(shù)據(jù)，處理時(shí)間會(huì)很長(zhǎng)鞠苟。 - 解決方案
先對(duì)數(shù)據(jù)進(jìn)行分片乞榨，然后采用多臺(tái)（比如n臺(tái)）機(jī)器進(jìn)行處理。具體做法：從搜索記錄的日志文件中依次讀取每個(gè)關(guān)鍵詞当娱，并通過(guò)哈希函數(shù)計(jì)算該關(guān)鍵詞的哈希值吃既，然后跟機(jī)器的臺(tái)數(shù)n取模，最終得到值就是該關(guān)鍵詞應(yīng)該被分到的機(jī)器編號(hào)跨细，這樣相同的關(guān)鍵詞一定會(huì)被分配到同一臺(tái)機(jī)器上鹦倚，數(shù)據(jù)分配完成后，由多臺(tái)機(jī)器并行進(jìn)行統(tǒng)計(jì)冀惭，最后合并起來(lái)就是最終結(jié)果震叙。
實(shí)際上，這里的處理過(guò)程也是 MapReduce 的基本設(shè)計(jì)思想散休。
- 如何快速判斷圖片是否存在圖庫(kù)中媒楼？
需求描述
假設(shè)現(xiàn)在我們的圖庫(kù)中有1億張圖片，如何快速判斷圖片是否在圖庫(kù)中戚丸？基本方式是給每個(gè)圖片去唯一表示（或者信息摘要）划址，然后構(gòu)建散列表。問(wèn)題分析
很顯然限府，在單臺(tái)機(jī)器上構(gòu)建散列表示行不通的夺颤，因?yàn)閱闻_(tái)機(jī)器的內(nèi)存有限，而1億張圖片構(gòu)建散列表遠(yuǎn)遠(yuǎn)超過(guò)了單臺(tái)機(jī)器的內(nèi)存上限胁勺。解決方案
準(zhǔn)備n臺(tái)機(jī)器世澜，讓每臺(tái)機(jī)器只維護(hù)一部分圖片對(duì)應(yīng)的散列表。我們每次從圖庫(kù)中讀取一個(gè)圖片姻几，計(jì)算唯一標(biāo)識(shí)宜狐，然后與機(jī)器個(gè)數(shù)n求余取模，得到的值就對(duì)應(yīng)要分配的機(jī)器編號(hào)蛇捌，然后將這個(gè)圖片的唯一表示和圖片路徑發(fā)往對(duì)應(yīng)的機(jī)器構(gòu)建散列表抚恒。當(dāng)我們要判斷一個(gè)圖片是否在圖庫(kù)中時(shí)，我們通過(guò)同樣的哈希算法络拌，計(jì)算這個(gè)圖片的唯一表示俭驮，然后與機(jī)器個(gè)數(shù)n求余取模。假設(shè)得到的值是k，那就去編號(hào)為k的機(jī)器構(gòu)建的散列表中查找混萝。
如何估算給1億張圖片構(gòu)建散列表大約需要多少臺(tái)機(jī)器遗遵？
散列表中每個(gè)數(shù)據(jù)單元包含兩個(gè)信息，哈希值和圖片文件的路徑逸嘀。假設(shè)我們通過(guò) MD5 來(lái)計(jì)算哈希值车要，那長(zhǎng)度就是 128 比特，也就是 16 字節(jié)崭倘。文件路徑長(zhǎng)度的上限是 256 字節(jié)翼岁，我們可以假設(shè)平均長(zhǎng)度是 128 字節(jié)。如果我們用鏈表法來(lái)解決沖突司光，那還需要存儲(chǔ)指針琅坡，指針只占用 8 字節(jié)。所以残家，散列表中每個(gè)數(shù)據(jù)單元就占用 152 字節(jié)（這里只是估算榆俺，并不準(zhǔn)確）。
假設(shè)一臺(tái)機(jī)器的內(nèi)存大小為 2GB坞淮，散列表的裝載因子為 0.75茴晋，那一臺(tái)機(jī)器可以給大約 1000 萬(wàn)（2GB*0.75/152）張圖片構(gòu)建散列表。所以碾盐，如果要對(duì) 1 億張圖片構(gòu)建索引晃跺，需要大約十幾臺(tái)機(jī)器。在工程中毫玖，這種估算還是很重要的掀虎，能讓我們事先對(duì)需要投入的資源、資金有個(gè)大概的了解付枫，能更好地評(píng)估解決方案的可行性烹玉。
實(shí)際上，針對(duì)這種海量數(shù)據(jù)的處理問(wèn)題阐滩，我們都可以采用多機(jī)分布式處理二打。借助這種分片的思路，可以突破單機(jī)內(nèi)存掂榔、CPU 等資源的限制
- 分布式存儲(chǔ)
- 什么是分布式存儲(chǔ)继效？
- 分布式存儲(chǔ)就是將數(shù)據(jù)存儲(chǔ)在多臺(tái)機(jī)器上并提供高效的讀取、寫入支持装获。那如何決定將哪個(gè)數(shù)據(jù)放到哪個(gè)機(jī)器上呢瑞信？可以利用數(shù)據(jù)分片的思想，即通過(guò)哈希算法對(duì)數(shù)據(jù)取哈希值穴豫，然后對(duì)機(jī)器個(gè)數(shù)取模凡简，這個(gè)最終值就是應(yīng)該存儲(chǔ)的緩存機(jī)器編號(hào)逼友。
- 遇到的問(wèn)題是什么？
- 如果數(shù)據(jù)持續(xù)增多秤涩，原來(lái)的機(jī)器數(shù)量已經(jīng)不能滿足需求帜乞，就需要增加機(jī)器，這時(shí)就麻煩了筐眷，因?yàn)樗械臄?shù)據(jù)都需要重新哈希值進(jìn)行再次分配黎烈。這就相當(dāng)于，緩存中的數(shù)據(jù)一下子都失效了浊竟，所有的數(shù)據(jù)請(qǐng)求都會(huì)穿透緩存怨喘，直接去請(qǐng)求數(shù)據(jù)庫(kù)。這樣就可能發(fā)生雪崩效應(yīng)振定，壓垮數(shù)據(jù)庫(kù)。
- 解決方案是什么肉拓？
- 這時(shí)后频，需要一種方法，使得新加入一個(gè)機(jī)器后暖途，并不需要做大量的數(shù)據(jù)搬移卑惜。那就是在分布式系統(tǒng)中應(yīng)用非常廣泛的一致性哈希算法。
- 一致性哈希算法的基本思想是什么呢驻售？為了說(shuō)清楚這個(gè)問(wèn)題露久，我們假設(shè)有k個(gè)機(jī)器，數(shù)據(jù)的哈希值范圍是[0-MAX]欺栗，我們將整個(gè)范圍劃分成m個(gè)小區(qū)間（m遠(yuǎn)大于k）毫痕，每個(gè)機(jī)器復(fù)雜m/k個(gè)小區(qū)間。當(dāng)有新機(jī)器加入的時(shí)候迟几，我們就將某幾個(gè)小區(qū)間的數(shù)據(jù)消请，從原來(lái)的機(jī)器中搬移到新的機(jī)器中。這樣类腮，既不用全部重新哈希臊泰、搬移數(shù)據(jù)，也保持了各個(gè)機(jī)器上數(shù)據(jù)量的均衡蚜枢。
三缸逃、思考
- 如何防止數(shù)據(jù)庫(kù)中的用戶信息被脫庫(kù)？你會(huì)如何存儲(chǔ)用戶密碼這么重要的數(shù)據(jù)嗎厂抽？
- 使用MD5進(jìn)行加密
- 字典攻擊：如果用戶信息被“脫庫(kù)”需频，黑客雖然拿到的是加密之后的密文，但可以通過(guò)“猜”的方式來(lái)破解密碼修肠，這是因?yàn)楹爻剑行┯脩舻拿艽a太簡(jiǎn)單。
- 針對(duì)字典攻擊，我們可以引入一個(gè)鹽（salt）饲化，跟用戶密碼組合在一起莽鸭，增加密碼的復(fù)雜度。
- 現(xiàn)在吃靠，區(qū)塊鏈?zhǔn)且粋€(gè)很火的領(lǐng)域硫眨，它被很多人神秘化，不過(guò)其底層的實(shí)現(xiàn)原理并不復(fù)雜巢块。其中礁阁，哈希算法就是它的一個(gè)非常重要的理論基礎(chǔ)。你能講一講區(qū)塊鏈?zhǔn)褂玫氖悄姆N哈希算法嗎族奢？是為了解決什么問(wèn)題而使用的呢姥闭？
- 如果要在海量的圖庫(kù)中，搜索一張圖是否存在越走，我們不能單純地用圖片的元信息（比如圖片名稱）來(lái)比對(duì)棚品，因?yàn)橛锌赡艽嬖诿Q相同但圖片內(nèi)容不同，或者名稱不同圖片內(nèi)容相同的情況廊敌。那我們?cè)撊绾嗡阉髂兀?/li>
- BT協(xié)議校驗(yàn)
