哈希碰撞演算法

『壹』 hash演算法是什麼呢

hash演算法是：一種特殊的函數，不論輸入多長的一串字元，只要通過這個函數都可以得到一個固定長度的輸出值，這就好像身份證號碼一樣，永遠都是十八位而且全國唯一。

哈希演算法的輸出值就叫做哈希值。哈希演算法也被稱為「散列」，是區塊鏈的四大核心技術之一。是能計算出一個數字消息所對應的、長度固定的字元串。

原理：

Hash演算法的原理是把輸入空間的值映射到Hash空間內，由於Hash值的空間遠小於輸入的空間，而且藉助抽屜原理 ，可以得出一定會存在不同的輸入被映射成相同輸出的情況，如果一個Hash演算法足夠好，那麼他就一定會有更小的發生沖突的概率，也就是說，一個好的Hash演算法應該具有優秀的 抗碰撞能力。

『貳』 hash演算法是什麼

Hash，就是把任意長度的輸入（又叫做預此模映射，pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。

這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

使用哈希查找有兩個步驟：

1、使用哈希函數將被查找的鍵轉換為數組的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下乎扒腔我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理沖突。

2、處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文後面會介歲衫紹拉鏈法和線性探測法。

『叄』 什麼是哈希演算法

舉個更形象點的例子。 這東西其實就像字典（其實就是）。你給出來的字元串是一個單詞，他在字典裡面所屬的條目是A-Z其中一個字母。不管你給的單詞有多長，他總屬於字典中某一個目錄下（也就是首字母。。）。你現在有兩個單詞，你不知道他們都是什麼，但是你知道一個在「A」裡面一個在「E」裡面。這樣你就知道這倆肯定不是同樣的單詞。不過由於每個條目下都有一大堆的單詞，所以你還是不知道這兩個單詞具體是什麼。 當然也有很大的概率兩個單詞都在E裡面，這種情況叫做一種「碰撞」。兩個不同的東西生成了同樣的結果。拿到360的例子上來說就是，你開了家網站，起了個特別詭異的名字，用奇虎的哈希演算法算出來的結果和某個不良網站一樣。那麼你的網站就被當不良網站屏蔽掉了。 一個好的哈希演算法要保證盡可能的少產生碰撞。還是說你之前查字典的例子。這次你把字典拆了。給裡面每個首字母下面又加了26個條目，分別是A-Z，裡面裝著以這些當結尾的單詞。這樣你隨便挑兩個單詞是一個坑裡出來的概率就小多了。 然後突然你有一天覺醒了。感覺就差倆單詞太費勁了。所以你買了本空字典，把天下單詞挨個試一遍，終於把所有目錄裡面都填滿了。然後你以後找單詞就很方便了。別人給你一個單詞首字母是A，你就隨便從A裡面找個應附上。雖然不知道是不是他說的那個，但至少看起來是一個坑裡出來的就過關了。這字典就叫彩虹表。這東西寫起來比較耗時。沒准你算了二十年發現試過的那些單詞首字母全是XYZ，但是人家每次給的都是ETA，那之前的活都白幹了。 雖然這種方法得到的不是原始記錄，而僅僅是與之具有相同特徵的記錄。而且有這個特徵的記錄可能有一大堆。有的時候你碰巧拿到的就是原來的那個，但大多數拿到的都是垃圾。如果你的表很全的話，那很有可能一堆記錄裡面有個和原來的那條一模一樣的。這時候你可以根據別的什麼信息猜猜找的是什麼。比如你倆正打架，然後找出來他給你的單詞是F開頭的，那基本上就能猜出來了。 這就是哈希演算法。一個好的哈希演算法僅僅知道結果的話是極難反算出原始數據來的，特別是有意義的原始數據。

『肆』 python之哈希演算法

哈希(Hash)演算法：`hash（object）`

哈希演算法將一個不定長的輸入，通過散列函數變換成一個定長的輸出，即散列值。是一種信息摘要演算法。對象的hash值比原對象擁有更低的內存復雜度。

它不同於加密。哈希（hash）是將目標文本轉換成具有相同長度的，不可逆的雜湊字元串，而加密則是將文本轉換為具有相同長度的，可逆的密文。

哈希（hash）演算法是不可逆的，只能由輸入產生輸出，不能由輸出產生輸入。而加密則是可逆的。即可以從輸入產生輸出，也可以反過來從輸出推出輸入。

對於hash演算法，不同的數據應該生成不同的哈希值。如果兩個不同的數據經過Hash函數計算得到的Hash值一樣。就稱為哈希碰撞（collision）。哈希碰撞無法被完全避免。只能降低發生概率。

好的hash函數會導致最少的hash碰撞。

*

可哈希性（hashable）：

可哈希的數據類型為不可變的數據結構（如字元串srt，元組tuple，對象集objects等）。這種數據被稱為可哈希性。

不可哈希性：

不可哈希的數據類型，為可變的數據結構（如字典dict，列表list和集合set等）。

如果對可變的對象進行哈希處理，則每次對象更新時，都需要更新哈希表。這樣我們則需要將對象移至不同的數據集，這種操作會使花費過大。

因此設定不能對可變的對象進行hash處理。

**

**

Python3.x添加了hash演算法的隨機性，以提高安全性，因此對於每個新的python調用，同樣的數據源生成的結果都將不同。

哈希方法有（MD5, SHA1, SHA256與SHA512等）。常用的有SH256與SHA512。MD5與SHA1不再常用。

- MDH5 (不常用)

- SHA1 (不常用)

- SHA256 (常用)

- SHA512 (常用)

一種局部敏感的hash演算法，它產生的簽名在一定程度上可以表徵原內容的相似度。

> 可以被用來比較文本的相似度。

安裝simhash：

Pip3 install simhash

感知哈希演算法（perceptual Hash Algorithm）。用於檢測圖像和視頻的差異。

安裝Imagehash:

pip3 install Imagehash

比較下面兩張圖片的Imagehash值

可以看到兩張圖片的hash值非常相似。相似的圖片可以生成相似的哈希值是Imagehash的特點。

『伍』 什麼是哈希演算法

就是空間映射函數，例如，全體的長整數的取值作為一個取值空間，映射到全部的位元組整數的取值的空間，這個映射函數就是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值會翻白眼。

『陸』 哈希演算法是什麼呢

哈希演算法就是一種特殊的函數，不論輸入多長的一串字元，只要通過這個函數都可以得到一個固定長度的輸出值，這就好像身份證號碼一樣，永遠都是十八位而且全國唯一。哈希演算法的輸出值就叫做哈希值。

原理：

哈希演算法有三個特點，它們賦予了區塊鏈不可篡改、匿名等特性，並保證了整個區塊鏈體系的完整。

第一個特點是具有單向性。比如輸入一串數據，通過哈希演算法可以獲得一個哈希值，但是通過這個哈希值是沒有辦法反推回來得到輸入的那串數據的。這就是單向性，也正是基於這一點，區塊鏈才有效保護了我們信息的安全性。

哈希演算法的第二個特點是抗篡改能力，對於任意一個輸入，哪怕是很小的改動，其哈希值的變化也會非常大。

它的這個特性，在區塊與區塊的連接中就起到了關鍵性的作用。區塊鏈的每個區塊都會以上一個區塊的哈希值作為標示，除非有人能夠破解整條鏈上的所有哈希值，否則數據一旦記錄在鏈上，就不可能進行篡改。

哈希演算法的第三個特點就是抗碰撞能力。所謂碰撞，就是輸入兩個不同的數據，最後得到了一個相同的輸入。

就跟我們逛街時撞衫一樣，而坑碰撞就是大部分的輸入都能得到一個獨一無二的輸出。在區塊鏈的世界中，任何一筆交易或者賬戶的地址都是完全依託於哈希演算法生產的。這也就保證了交易或者賬戶地址在區塊鏈網路中的唯一性。

無論這筆轉賬轉了多少錢，轉給了多少個人，在區塊鏈這個大賬本中都是唯一的存在。它就像人體體內的白細胞，不僅區塊鏈的每個部分都離不開它，而且它還賦予了區塊鏈種種特點，保護著整個區塊鏈體系的安全。

『柒』 哈希演算法的原理

什麼是哈希演算法？哈希是一種加密演算法，也稱為散列函數或雜湊函數。哈希函數是一個公開函數，可以將任意長度的消息M映射成為一個長度較短且長度固定的值H（M），稱H（M）為哈希值、散列值（Hash Value）、雜湊值或者消息摘要。它是一種單向密碼體制，即一個從明文到密文的不可逆映射，只有加密過程，沒有解密過程。

Hash的特點

易壓縮：對於任意大小的輸入x，Hash值的長度很小，在實際應用中，函數H產生的Hash值其長度是固定的。

易計算：對於任意給定的消息，計算其Hash值比較容易。

單向性：對於給定的Hash值，要找到使得在計算上是不可行的，即求Hash的逆很困難。在給定某個哈希函數H和哈希值H（M）的情況下，得出M在計算上是不可行的。即從哈希輸出無法倒推輸入的原始數值。這是哈希函數安全性的基礎。

抗碰撞性：理想的Hash函數是無碰撞的，但在實際演算法的設計中很難做到這一點。

有兩種抗碰撞性：一種是弱抗碰撞性，即對於給定的消息，要發現另一個消息，滿足在計算上是不可行的；另一種是強抗碰撞性，即對於任意一對不同的消息，使得在計算上也是不可行的。

高靈敏性：這是從比特位角度出發的，指的是1比特位的輸入變化會造成1/2的比特位發生變化。消息M的任何改變都會導致哈希值H（M）發生改變。即如果輸入有微小不同，哈希運算後的輸出一定不同。