什麼是哈希演算法？

01-14

周老闆說他的瀏覽器採用的是哈希演算法，不可逆，只能幫助用戶識別惡意網址，卻無法知道用戶用的是什麼網址？

via:什麼是哈希表和哈希演算法？

比如這裡有一萬首歌，給你一首新的歌X，要求你確認這首歌是否在那一萬首歌之內。

無疑，將一萬首歌一個一個比對非常慢。但如果存在一種方式，能將一萬首歌的每首數據濃縮到一個數字（稱為哈希碼）中，於是得到一萬個數字，那麼用同樣的演算法計算新的歌X的編碼，看看歌X的編碼是否在之前那一萬個數字中，就能知道歌X是否在那一萬首歌中。

作為例子，如果要你組織那一萬首歌，一個簡單的哈希演算法就是讓歌曲所佔硬碟的位元組數作為哈希碼。這樣的話，你可以讓一萬首歌「按照大小排序」，然後遇到一首新的歌，只要看看新的歌的位元組數是否和已有的一萬首歌中的某一首的位元組數相同，就知道新的歌是否在那一萬首歌之內了。

當然這個簡單的哈希演算法很容易出現兩者同樣大小的歌曲，這就是發送了碰撞。而好的哈希演算法發生碰撞的幾率非常小。

真沒有一個內行點的回答嗎？

這個HASH演算法不是大學裡數據結構課里那個HASH表的演算法。這裡的HASH演算法是密碼學的基礎，比較常用的有MD5和SHA，最重要的兩條性質，就是不可逆和無衝突。

所謂不可逆，就是當你知道x的HASH值，無法求出x；

所謂無衝突，就是當你知道x，無法求出一個y，使x與y的HASH值相同。

這兩條性質在數學上都是不成立的。因為一個函數必然可逆，且由於HASH函數的值域有限，理論上會有無窮多個不同的原始值，它們的hash值都相同。MD5和SHA做到的，是求逆和求衝突在計算上不可能，也就是正向計算很容易，而反向計算即使窮盡人類所有的計算資源都做不到。

我覺得密碼學的幾個演算法（HASH、對稱加密、公私鑰）是計算機科學領域最偉大的發明之一，它授予了弱小的個人在強權面前信息的安全（而且是絕對的安全）。舉個例子，只要你一直使用https與國外站點通訊，並注意對方的公鑰沒有被篡改，G**W可以斷開你的連接，但它永遠不可能知道你們的傳輸內容是什麼。

順便說一下，王小雲教授曾經成功製造出MD5的碰撞，即md5(a) = md5(b)。這樣的碰撞只能隨機生成，並不能根據一個已知的a求出b（即並沒有破壞MD5的無衝突特性）。但這已經讓他聲名大噪了。

就是空間映射函數，例如，全體的長整數的取值作為一個取值空間，映射到全部的位元組整數的取值的空間，這個映射函數就是HASH函數。通常這種映射函數是從一個非常大的取值空間映射到一個非常小的取值空間，由於不是一對一的映射，HASH函數轉換後不可逆，即不可能通過逆操作和HASH值還原出原始的值，受到計算能力限制（注意，不是邏輯上不可能，前面的不可能是邏輯上的）而且也無法還原出所有可能的全部原始值。HASH函數運用在字典表等需要快速查找的數據結構中，他的計算複雜度幾乎是O(1)，不會隨著數據量增加而增加。另外一種用途就是文件簽名，文件內容很多，將文件內容通過HASH函數處理後得到一個HASH值，驗證這個文件是否被修改過，只需要把文件內容用同樣的HASH函數處理後得到HASH值再比對和文件一起傳送的HASH值即可，如不公開HASH演算法，那麼信道是無法篡改文件內容的時候篡改文件HASH值，一般應用的時候，HASH演算法是公開的，這時候會用一個非對稱加密演算法加密一下這個HASH值，這樣即便能夠計算HASH值，但沒有加密密鑰依然無法篡改加密後HASH值。這種演算法用途很廣泛，用在電子簽名中。HASH演算法也可進行破解，這種破解不是傳統意義上的解密，而是按照已有的HASH值構造出能夠計算出相同HASH值的其他原文，從而妨礙原文的不可篡改性的驗證，俗稱找碰撞。這種碰撞對現有的電子簽名危害並不嚴重，主要是要能夠構造出有意義的原文才有價值，否則就是構造了一個完全不可識別的原文罷了，接收系統要麼無法處理報錯，要麼人工處理的時候發現完全不可讀。理論上我們終於找到了在可計算時間內發現碰撞的演算法，推算了HASH演算法的逆操作的時間複雜度大概的範圍。

HASH演算法的另外一個很廣泛的用途，就是很多程序員都會使用的在資料庫中保存用戶密碼的演算法，通常不會直接保存用戶密碼（這樣DBA就能看到用戶密碼啦，好危險啊），而是保存密碼的HASH值，驗證的時候，用相同的HASH函數計算用戶輸入的密碼得到計算HASH值然後比對資料庫中存儲的HASH值是否一致，從而完成驗證。由於用戶的密碼的一樣的可能性是很高的，防止DBA猜測用戶密碼，我們還會用一種俗稱「撒鹽」的過程，就是計算密碼的HASH值之前，把密碼和另外一個會比較發散的數據拼接，通常我們會用用戶創建時間的毫秒部分。這樣計算的HASH值不大會都是一樣的，會很發散。最後，作為一個老程序員，我會把用戶的HASH值保存好，然後把我自己密碼的HASH值保存到資料庫裡面，然後用我自己的密碼和其他用戶的用戶名去登錄，然後再改回來解決我看不到用戶密碼而又要「偷窺」用戶的需要。最大的好處是，資料庫泄露後，得到用戶資料庫的黑客看著一大堆HASH值會翻白眼。

把網址A，轉換成數字1。網址B，轉換成數字2。

一個網址X，轉換成數字N，根據數字N作為下標，就可以快速地查找出網址X的信息。

這個轉換的過程就是哈希演算法。

哈希演算法並不是一種特定的演算法，只要能完成這種轉換的演算法都是哈希演算法。但是評定一個演算法是否是好的哈希演算法，要根據演算法的離散度和衝突概率來評定。

這種函數是一種摘要演算法，你給他輸入一個任意長的數據A他給你返回固定長度的數據B，也稱B為「指紋」。

所以理論上來說你拿到一個B你是猜不出來A是什麼的。因為B是固定長度的，它對應了無數個A。

舉個更形象點的例子。

這東西其實就像字典（其實就是）。你給出來的字元串是一個單詞，他在字典裡面所屬的條目是A-Z其中一個字母。不管你給的單詞有多長，他總屬於字典中某一個目錄下（也就是首字母。。）。你現在有兩個單詞，你不知道他們都是什麼，但是你知道一個在「A」裡面一個在「E」裡面。這樣你就知道這倆肯定不是同樣的單詞。不過由於每個條目下都有一大堆的單詞，所以你還是不知道這兩個單詞具體是什麼。

當然也有很大的概率兩個單詞都在E裡面，這種情況叫做一種「碰撞」。兩個不同的東西生成了同樣的結果。拿到360的例子上來說就是，你開了家網站，起了個特別詭異的名字，用奇虎的哈希演算法算出來的結果和某個不良網站一樣。那麼你的網站就被當不良網站屏蔽掉了。

一個好的哈希演算法要保證儘可能的少產生碰撞。還是說你之前查字典的例子。這次你把字典拆了。給裡面每個首字母下面又加了26個條目，分別是A-Z，裡面裝著以這些當結尾的單詞。這樣你隨便挑兩個單詞是一個坑裡出來的概率就小多了。

設計一個哈希演算法要考慮的有很多。比如你不知道一個單詞具體是什麼，但知道首字母是A，但是你也不知道首字母A的單詞都是什麼，你得找一堆單詞挨個試。要是演算法複雜點你得試個幾十年才能找到符合條件的單詞，雖然可能不是你原來找的那個，但是看起來差不多。那麼這演算法就成功了。人家拖了你幾十年。

然後突然你有一天覺醒了。感覺就差倆單詞太費勁了。所以你買了本空字典，把天下單詞挨個試一遍，終於把所有目錄裡面都填滿了。然後你以後找單詞就很方便了。別人給你一個單詞首字母是A，你就隨便從A裡面找個應附上。雖然不知道是不是他說的那個，但至少看起來是一個坑裡出來的就過關了。這字典就叫彩虹表。這東西寫起來比較耗時。沒準你算了二十年發現試過的那些單詞首字母全是XYZ，但是人家每次給的都是ETA，那之前的活都白乾了。

雖然這種方法得到的不是原始記錄，而僅僅是與之具有相同特徵的記錄。而且有這個特徵的記錄可能有一大堆。有的時候你碰巧拿到的就是原來的那個，但大多數拿到的都是垃圾。如果你的表很全的話，那很有可能一堆記錄裡面有個和原來的那條一模一樣的。這時候你可以根據別的什麼信息猜猜找的是什麼。比如你倆正打架，然後找出來他給你的單詞是F開頭的，那基本上就能猜出來了。

這就是哈希演算法。一個好的哈希演算法僅僅知道結果的話是極難反算出原始數據來的，特別是有意義的原始數據。

至於周老闆怎麼用我倒是不知道。不過他既然知道那些網址是非法的，那麼肯定得有個小本，記錄著誰都干過壞事。然後想想之前的彩虹表。你懂的。

諧妖。

通俗點講吧

哈希演算法是用來解決數據和數據之間對應關係的一種演算法。它的初衷是用來加速數據存取。

計算機領域內的大多數查找演算法都與存儲數據的規模呈正相關，用于衡量查找演算法效率的量我們稱為平均查找長度，一般情況下，比較優秀的查找演算法的平均查找長度也不會短於數據規模以2為底的對數（ $log_{2} n$ ）。

哈希演算法中，我們把數據項中的關鍵字用一種特定的對應關係和存儲數據項的地址或地址偏移量對應起來。注意：這種對應一般不是一一對應，因為不可能有足夠多的地址對應近乎無窮多的關鍵字。

這樣一來，當我們知道數據關鍵字的時候，在大多數情況下可以在常數時間（與數據規模無關的常數）內存取這個關鍵字。其他的時候，有可能發生多個關鍵字佔據同一地址的現象，我們稱之為碰撞。這種情況下需要對關鍵字進行二次或更多次的處理（如果發生多次碰撞），所費時間在最差情況下也只與規模成正比。

只要這種函數的對應關係取得足夠好，碰撞就會較少的發生，從而使平均查找長度在數據規模可控的情況下大幅度縮短，從而提高查找效率。

-----------------------------------------------------------------

哈希函數除此以外，也可以用來對廣義上的字元串（例如文本、視頻、圖片、程序等等等等）進行特徵驗證。常見的有CRC32（32位循環冗餘校驗），從MD2、MD3、MD4發展而來的MD5（消息摘要演算法第五版），SHA1（安全哈希演算法）等等。

這類哈希演算法的最初用途僅僅是對這些廣義字元串進行完整性校驗，因為在傳輸中損壞的比特位往往僅僅是極少數，這些少數的錯誤用上述提到的演算法可以得出和原本正確文件截然不同的值，這也就使得文件完整性校驗的開銷得以縮小。

-----------------------------------------------------------------

問題中描述的用途其實並不完全適當，但是在一定程度內可行。

因為訪問的網路地址有無窮多個，但是所有的哈希演算法生成的特徵值都有限，在極端情況下，很有可能會出現兩個不同的網路地址具有相同特徵值的情況。

這不僅使得在得知特徵值時，反向推測網路地址具有了可行性（雖然開銷可能極大，需要大量時間窮舉），而且在網路地址增長速度極快的今天，安全地址可能和危險地址發生碰撞導致誤殺或者錯誤放行的情況（現在雖然可能還沒出現過，但不能排除這種可能性）。

簡單結論：

這種哈希演算法本身雖然在理論上是不可逆的，但是它的思想保證了它也不是絕對可靠的。

哈希演算法，是根據設定的哈希函數H（key）和處理衝突方法將一組關鍵字映象到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。一般用於快速查找和加密演算法。

除了周老闆，比特幣的安全性也依賴哈希加密啊。

比特幣對安全性的要求比周老闆的要精密多了

不明白為什麼前面的很多回答都理解哈希演算法但是卻無法理解哈希演算法是不可逆的。

第一，哈希演算法是有損的，比如MD5可以將幾乎任意大小的文件映射到一串16進位值上面，假如是可逆的話，那麼以後再也不用去買硬碟了，一個U盤走天下。

第二，關於周老闆能不能知道你上的是什麼網站，這幾乎是肯定的。演算法是他們公司設計或者抄的，網站也是他們親自映射到哈希值上面的。即使哈希值不可逆，這個情況也可以通過查資料庫得到，反正我是不信他們會把原始數據刪除只留下來哈希值的。這一點可以參考C++中的std::multimap。

舉個例子，在沒有人工標註的前提下，在一個比較大的圖片集中實現以圖搜圖。

如果直接進行圖片的特徵匹配什麼的，速度比較慢，而且考慮不到圖片所包含的語義信息。

在訓練集上，通過哈希演算法，訓練得到一系列哈希函數。通過這些哈希函數，將每一張圖片都轉換成一串0-1編碼(可能是011011111.....)。這裡有一個要求，編碼串相似的兩張圖片所對應的語義信息也是相似的。這可能有點神奇了，沒有人工的標註，怎麼實現這一點的？這就是哈希演算法所做的事情。這很像機器學習所做的事情，沒錯，現在很多哈希演算法都是從機器學習的演算法中改變而來的。

上面這只是單模態哈希演算法。

還有跨模態的哈希演算法，用文字搜索對應的圖片。

哈希函數一般都是h(x)=sign(WX)，WX算出一個值，再通過sign轉換成0-1編碼。

如果只知道這個圖片的編碼，很難反推得到X的。

不知道，在瀏覽器上用的哈希演算法是不是和我說的一樣，我感覺應該差不多。

哈希(Hash)演算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。哈希函數的這種單向特徵和輸出數據長度固定的特徵使得它可以生成消息或者數據。

原理：

如果我們說一個網址是惡意網址比如 http://huaidan.com

360 將 http://huaidan.com加密得到值為a

瀏覽器將訪問的網址加密得到值為b

通常情況下如果a=b 那麼就能夠說明瀏覽器訪問的是惡意網址，就會有惡意網址的提示（排除重合等例外情況）。

但是：我自己是不相信周老闆這個回答的，這個演算法必定是可逆的，老周需要這個網址。

單調函數；

根據很多自變數和因變數都無法統計出函數長什麼樣；

周老闆如果知道惡意網址的哈希值，自然不就知道訪問的惡意網址了嗎？