圖片哈希演算法

❶ 相似圖片搜索的原理是怎樣的

2011年，Google把「相似圖片搜索」正式放上了首頁。你可以用一張圖片，搜索互聯網上所有與它相似的圖片。點擊搜索框中照相機的圖標。

有了50×50像素的黑白縮略圖，就等於有了一個50×50的0-1矩陣。矩陣的每個值對應原圖的一個像素，0表示黑色，1表示白色。這個矩陣就是一張圖片的特徵矩陣。

兩個特徵矩陣的不同之處越少，就代表兩張圖片越相似。這可以用」異或運算」實現（即兩個值之中只有一個為1，則運算結果為1，否則運算結果為0）。對不同圖片的特徵矩陣進行」異或運算」，結果中的1越少，就是越相似的圖片。

❷ 相似圖片檢測：感知哈希演算法之dHash的python實現

某些情況下，我們需要檢測圖片之間的相似性，進行我們需要的處理：刪除同一張圖片、標記盜版等。
如何判斷是同一張圖片呢？最簡單的方法是使用加密哈希（例如MD5, SHA-1）判斷。但是局限性非常大。例如一個txt文檔，其MD5值是根據這個txt的二進制數據計算的，如果是這個txt文檔的完全復製版，那他們的MD5值是完全相同的。但是，一旦改變副本的內容，哪怕只是副本的縮進格式，其MD5也會天差地別。因此加密哈希只能用於判斷兩個完全一致、未經修改的文件，如果是一張經過調色或者縮放的圖片，根本無法判斷其與另一張圖片是否為同一張圖片。
那麼如何判斷一張被PS過的圖片是否與另一張圖片本質上相同呢？比較簡單、易用的解決方案是採用感知哈希演算法（Perceptual Hash Algorithm)。

感知哈希演算法是一類演算法的總稱，包括aHash、pHash、dHash。顧名思義，感知哈希不是以嚴格的方式計算Hash值，而是以更加相對的方式計算哈希值，因為「相似」與否，就是一種相對的判定。

如果我們要計算上圖的dHash值，第一步是把它 縮放到足夠小 。為什麼需要縮放呢？因為原圖的解析度一般都非常高。一張 200*200 的圖片，就有整整4萬個像素點，每一個像素點都保存著一個RGB值，4萬個RGB，是相當龐大的信息量，非常多的細節需要處理。因此，我們需要把圖片縮放到非常小，隱藏它的細節部分，只見森林，不見樹木。建議縮放為9*8，雖然可以縮放為任意大小，但是這個值是相對合理的。而且寬度為9，有利於我們轉換為hash值，往下面看，你就明白了。

(感謝評論區 隔壁萬能的小黑 同學，建議在 image.resize 中加上Image.ANTIALIAS參數，加上此參數將會對所有可以影響輸出像素的輸入像素進行高質量的重采樣濾波)

dHash全名為差異值hash，通過計算相鄰像素之間的顏色強度差異得出。我們縮放後的圖片，細節已經被隱藏，信息量已經變少。但是還不夠，因為它是彩色的，由RGB值組成。白色表示為（255,255,255）,黑色表示為（0,0,0），值越大顏色越亮，越小則越暗。每種顏色都由3個數值組成，也就是紅、綠、藍的值 。如果直接使用RGB值對比顏色強度差異，相當復雜，因此我們轉化為灰度值——只由一個0到255的整數表示灰度。這樣的話就將三維的比較簡化為了一維比較。

差異值是通過計算每行相鄰像素的強度對比得出的。我們的圖片為9*8的解析度，那麼就有8行，每行9個像素。差異值是每行分別計算的，也就是第二行的第一個像素不會與第一行的任何像素比較。每一行有9個像素，那麼就會產生8個差異值，這也是為何我們選擇9作為寬度，因為8bit剛好可以組成一個byte，方便轉換為16進制值。
如果前一個像素的顏色強度大於第二個像素，那麼差異值就設置為True（也就是1），如果不大於第二個像素，就設置為False（也就是0）。

我們將差異值數組中每一個值看做一個bit，每8個bit組成為一個16進制值，將16進制值連接起來轉換為字元串，就得出了最後的dHash值。

漢明距離這個概念不止運用於圖片對比領域，也被使用於眾多領域，具體的介紹可以參見Wikipedia。
漢明距離表示將A修改成為B，需要多少個步驟。比如字元串「abc」與「ab3」，漢明距離為1，因為只需要修改「c」為「3」即可。
dHash中的漢明距離是通過計算差異值的修改位數。我們的差異值是用0、1表示的，可以看做二進制。二進制0110與1111的漢明距離為2。
我們將兩張圖片的dHash值轉換為二進制difference，並取異或。計算異或結果的「1」的位數，也就是不相同的位數，這就是漢明距離。

如果傳入的參數不是兩張圖的dHash值，而是直接比較兩張圖片，那麼不需要生成dHash值，直接用Step3中的difference數組，統計不相同的位數，就是漢明距離。

一般來說，漢明距離小於5，基本就是同一張圖片。大家可以根據自己的實際情況，判斷漢明距離臨界值為多少。

https://github.com/hjaurum/DHash

❸ PHP 如何獲取圖片的哈希值啊。。

你好，哈希演算法很多，自帶有，sha1函數跟md5函數，獲取圖片的哈希值要讀取內容去運算，
如$file=file_get_contents("圖片路徑"); echo sha1($file);//哈希值，echo md5($file);//md5值，這兩個都是摘要。謝謝

❹ 關於哈希值

通俗來講，哈希值就是文件的身份證，不過比身份證還嚴格。他是根據文件大小，時間，類型，創作者，機器等計算出來的，很容易就會發生變化，誰也不能預料下一個號碼是多少，也沒有更改他的軟體。哈希演算法將任意長度的二進制值映射為固定長度的較小二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨後的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的。

有這樣一種情境，有三萬張圖片我們要均勻放置於三個緩存伺服器上
簡單的做法是對緩存的key進行哈希計算，得到的值進行取模計算，所得到的余數，便是緩存的伺服器編號

hash % 機器數 = 余數
當機器數為3時無論值為多少，其餘數永遠只有0，1，2三種情況
那麼根據余數，我們給伺服器進行編號s0,s1,s2,余數為0的放置於s0伺服器上，1，2同理。

這樣我們就將三萬張圖片的緩存均分成三份存放與三台緩存伺服器中
因為對同一張圖片進行哈希計算時，所得到的哈希值是不變的，所以當需要訪問圖片時，只要再次進行哈希計算和取模計算，就能獲取到圖片存放於哪台伺服器，便可以去該伺服器中查找滿足了我們的需求。而這種演算法也稱之為哈希演算法

這其中有一個問題，那便是如果我增加一台伺服器呢
可以預見的是，當增加一台伺服器伺服器數變成了4.而余數也出現了4種情況

這時向s2的伺服器查詢時，無法讀取到圖片，這導致了程序無法從緩存伺服器中讀取數據，這時程序就會向後端伺服器請求，而大量的緩存同時失效，會導致所有請求都指向後端伺服器，這會引起後端伺服器的崩潰。
這是就要引入一致性哈希演算法

還是同樣的三個緩存伺服器，這次我們將哈希值對2 ^{32取模，所得到的數一定是1到2} 32之間的一個整數
然後我們想像一個圓環，其上的每一個點都代表1到2^32之間的一個整數，而這個圓環也被稱為hash環
之後我們對伺服器A進行取模計算，這樣算出來的整數肯定在1到2^32之間，將這個整數代表為伺服器A,並且我們可以將這個整數映射到哈希環上，同樣的道理我們處理另外兩個伺服器，這時三個伺服器都被映射到了哈希環上，對於圖片我們也將他映射到哈希環上
那麼我們只要從圖片的哈希值開始，沿順時針在哈希環上查找，遇到的第一個伺服器便是圖片緩存所在的伺服器
這時哪怕新添加一個伺服器在哈希環上，我門所丟失的緩存數據也只是新添加的伺服器到逆時針方向遇到的第一個伺服器這部分數據，而這樣仍然有大部分緩存在緩存伺服器中可以被查找到，這樣可以幫助後端伺服器分擔大部分壓力，不會使伺服器崩潰，而這部分丟失的緩存數據，之後重新在後端載入便可以了

這又引入了另一個問題，哈希偏斜
我們無法確保三個伺服器在哈希環上為均分的狀態，很有可能其中一台伺服器分到了很大部分而另兩台分到了很少的部分，這樣同樣會有後端伺服器崩潰的隱患
我們可以添加很多虛擬結點同一個伺服器我們分出許多虛擬節點，映射在哈希環上，哈希環上的節點越多，緩存被均分的概率便越大，這樣可以盡可能的保證緩存在伺服器上是接近理想均分的狀態，避免了哈希偏斜的問題

❺ 圖片相似度判斷

1. https://zhuanlan.hu.com/p/68215900
為了得到兩張相似的圖片，在這里通過以下幾種簡單的計算方式來計算圖片的相似度：
直方圖計算圖片的相似度
通過哈希值，漢明距離計算
通過圖片的餘弦距離計算
通過圖片結構度量計算

二、哈希演算法計算圖片的相似度
圖像指紋：

圖像指紋和人的指紋一樣，是身份的象徵，而圖像指紋簡單點來講，就是將圖像按照一定的哈希演算法，經過運算後得出的一組二進制數字。

漢明距離：

假如一組二進制數據為101，另外一組為111，那麼顯然把第一組的第二位數據0改成1就可以變成第二組數據111，所以兩組數據的漢明距離就為1。簡單點說，漢明距離就是一組二進制數據變成另一組數據所需的步驟數，顯然，這個數值可以衡量兩張圖片的差異，漢明距離越小，則代表相似度越高。漢明距離為0，即代表兩張圖片完全一樣。

感知哈希演算法是一類演算法的總稱，包括aHash、pHash、dHash。顧名思義，感知哈希不是以嚴格的方式計算Hash值，而是以更加相對的方式計算哈希值，因為「相似」與否，就是一種相對的判定。

幾種hash值的比較：

aHash：平均值哈希。速度比較快，但是常常不太精確。
pHash：感知哈希。精確度比較高，但是速度方面較差一些。
dHash：差異值哈希。精確度較高，且速度也非常快

該演算法是基於比較灰度圖每個像素與平均值來實現。

aHash的hanming距離步驟：

先將圖片壓縮成8*8的小圖
將圖片轉化為灰度圖
計算圖片的Hash值，這里的hash值是64位，或者是32位01字元串
將上面的hash值轉換為16位的
通過hash值來計算漢明距離

def ahash(image):
# 將圖片縮放為8*8的
image = cv2.resize(image, (8, 8), interpolation=cv2.INTER_CUBIC)
# 將圖片轉化為灰度圖
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
# s為像素和初始灰度值，hash_str為哈希值初始值
s = 0
# 遍歷像素累加和
for i in range(8):
for j in range(8):
s = s + gray[i, j]
# 計算像素平均值
avg = s / 64
# 灰度大於平均值為1相反為0，得到圖片的平均哈希值，此時得到的hash值為64位的01字元串
ahash_str = ''
for i in range(8):
for j in range(8):
if gray[i, j] > avg:
ahash_str = ahash_str + '1'
else:
ahash_str = ahash_str + '0'
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(ahash_str[i: i + 4], 2))
# print("ahash值：",result)
return result
2.感知哈希演算法（pHash）：

均值哈希雖然簡單，但是受均值影響大。如果對圖像進行伽馬校正或者進行直方圖均值化都會影響均值，從而影響哈希值的計算。所以就有人提出更健壯的方法，通過離散餘弦（DCT）進行低頻提取。

離散餘弦變換（DCT）是種圖像壓縮演算法，它將圖像從像素域變換到頻率域。然後一般圖像都存在很多冗餘和相關性的，所以轉換到頻率域之後，只有很少的一部分頻率分量的系數才不為0，大部分系數都為0（或者說接近於0）。Phash哈希演算法過於嚴格，不夠精確，更適合搜索縮略圖，為了獲得更精確的結果可以選擇感知哈希演算法，它採用的是DCT（離散餘弦變換）來降低頻率的方法。

pHash的hanming距離步驟：

縮小圖片：32 * 32是一個較好的大小，這樣方便DCT計算轉化為灰度圖
計算DCT：利用Opencv中提供的dct()方法，注意輸入的圖像必須是32位浮點型，所以先利用numpy中的float32進行轉換
縮小DCT：DCT計算後的矩陣是32 * 32，保留左上角的8 * 8，這些代表的圖片的最低頻率
計算平均值：計算縮小DCT後的所有像素點的平均值。
進一步減小DCT：大於平均值記錄為1，反之記錄為0.
得到信息指紋：組合64個信息位，順序隨意保持一致性。
最後比對兩張圖片的指紋，獲得漢明距離即可。

def phash(path):
# 載入並調整圖片為32*32的灰度圖片
img = cv2.imread(path)
img1 = cv2.resize(img, (32, 32),cv2.COLOR_RGB2GRAY)
​
# 創建二維列表
h, w = img.shape[:2]
vis0 = np.zeros((h, w), np.float32)
vis0[:h, :w] = img1
​
# DCT二維變換
# 離散餘弦變換，得到dct系數矩陣
img_dct = cv2.dct(cv2.dct(vis0))
img_dct.resize(8,8)
# 把list變成一維list
img_list = np.array().flatten(img_dct.tolist())
# 計算均值
img_mean = cv2.mean(img_list)
avg_list = ['0' if i<img_mean else '1' for i in img_list]
return ''.join(['%x' % int(''.join(avg_list[x:x+4]),2) for x in range(0,64,4)])

相比pHash，dHash的速度要快的多，相比aHash，dHash在效率幾乎相同的情況下的效果要更好，它是基於漸變實現的。

dHash的hanming距離步驟：

先將圖片壓縮成9*8的小圖，有72個像素點
將圖片轉化為灰度圖
計算差異值：dHash演算法工作在相鄰像素之間，這樣每行9個像素之間產生了8個不同的差異，一共8行，則產生了64個差異值，或者是32位01字元串。
獲得指紋：如果左邊的像素比右邊的更亮，則記錄為1，否則為0.
通過hash值來計算漢明距離

def dhash(image):
# 將圖片轉化為8*8
image = cv2.resize(image, (9, 8), interpolation=cv2.INTER_CUBIC)
# 將圖片轉化為灰度圖
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
dhash_str = ''
for i in range(8):
for j in range(8):
if gray[i, j] > gray[i, j + 1]:
dhash_str = dhash_str + '1'
else:
dhash_str = dhash_str + '0'
result = ''
for i in range(0, 64, 4):
result += ''.join('%x' % int(dhash_str[i: i + 4], 2))
# print("dhash值",result)
return result

def campHash(hash1, hash2):
n = 0
# hash長度不同返回-1,此時不能比較
if len(hash1) != len(hash2):
return -1
# 如果hash長度相同遍歷長度
for i in range(len(hash1)):
if hash1[i] != hash2[i]:
n = n + 1
return n

❻ 哈希（hash） - 哈希演算法的應用

通過之前的學習，我們已經了解了哈希函數在散列表中的應用，哈希函數就是哈希演算法的一個應用。那麼在這里給出哈希的定義： 將任意長度的二進制值串映射為固定長度的二進制值串，這個映射規則就是哈希演算法，得到的二進制值串就是哈希值 。
要設計一個好的哈希演算法並不容易，它應該滿足以下幾點要求：

哈希演算法的應用非常廣泛，在這里就介紹七點應用：

有很多著名的哈希加密演算法：MD5、SHA、DES...它們都是通過哈希進行加密的演算法。
對於加密的哈希演算法來說，有兩點十分重要：一是很難根據哈希值反推導出原始數據；二是散列沖突的概率要很小。
當然，哈希演算法不可能排除散列沖突的可能，這用數學中的 鴿巢原理 就可以很好解釋。以MD5演算法來說，得到的哈希值為一個 128 位的二進制數，它的數據容量最多為 2 ¹²⁸ bit，如果超過這個數據量，必然會出現散列沖突。
在加密解密領域沒有絕對安全的演算法，一般來說，只要解密的計算量極其龐大，我們就可以認為這種加密方法是較為安全的。

假設我們有100萬個圖片，如果我們在圖片中尋找某一個圖片是非常耗時的，這是我們就可以使用哈希演算法的原理為圖片設置唯一標識。比如，我們可以從圖片的二進制碼串開頭取100個位元組，從中間取100個位元組，從結尾取100個位元組，然後將它們合並，並使用哈希演算法計算得到一個哈希值，將其作為圖片的唯一標識。
使用這個唯一標識判斷圖片是否在圖庫中，這可以減少甚多工作量。

在傳輸消息的過程中，我們擔心通信數據被人篡改，這時就可以使用哈希函數進行數據校驗。比如BT協議中就使用哈希栓發進行數據校驗。

在散列表那一篇中我們就講過散列函數的應用，相比於其它應用，散列函數對於散列演算法沖突的要求低很多（我們可以通過開放定址法或鏈表法解決沖突），同時散列函數對於散列演算法是否能逆向解密也並不關心。
散列函數比較在意函數的執行效率，至於其它要求，在之前的我們已經講過，就不再贅述了。

接下來的三個應用主要是在分布式系統中的應用

復雜均衡的演算法很多，如何實現一個會話粘滯的負載均衡演算法呢？也就是說，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個伺服器上。

最簡單的辦法是我們根據客戶端的 IP 地址或會話 ID 創建一個映射關系。但是這樣很浪費內存，客戶端上線下線，伺服器擴容等都會導致映射失效，維護成本很大。

藉助哈希演算法，我們可以很輕松的解決這些問題：對客戶端的 IP 地址或會話 ID 計算哈希值，將取得的哈希值域伺服器的列表的大小進行取模運算，最後得到的值就是被路由到的伺服器的編號。

假設有一個非常大的日誌文件，裡面記錄了用戶的搜索關鍵詞，我們想要快速統計出每個關鍵詞被搜索的次數，該怎麼做呢？

分析一下，這個問題有兩個難點：一是搜索日誌很大，沒辦法放到一台機器的內存中；二是如果用一台機器處理這么大的數據，處理時間會很長。

針對這兩個難點，我們可以先對數據進行分片，然後使用多台機器處理，提高處理速度。具體思路：使用 n 台機器並行處理，從日誌文件中讀出每個搜索關鍵詞，通過哈希函數計算哈希值，然後用 n 取模，最終得到的值就是被分配的機器編號。
這樣，相同的關鍵詞被分配到了相同的機器上，不同機器只要記錄屬於自己那部分的關鍵詞的出現次數，最終合並不同機器上的結果即可。

針對這種海量數據的處理問題，我們都可以採用多機分布式處理。藉助這種分片思路，可以突破單機內存、CPU等資源的限制。

處理思路和上面出現的思路類似：對數據進行哈希運算，對機器數取模，最終將存儲數據（可能是硬碟存儲，或者是緩存分配）分配到不同的機器上。

你可以看一下上圖，你會發現之前存儲的數據在新的存儲規則下全部失效，這種情況是災難性的。面對這種情況，我們就需要使用一致性哈希演算法。

哈希演算法是應用非常廣泛的演算法，你可以回顧上面的七個應用感受一下。

其實在這里我想說的是一個思想： 用優勢彌補不足 。
例如，在計算機中，數據的計算主要依賴 CPU ，數據的存儲交換主要依賴內存。兩者一起配合才能實現各種功能，而兩者在性能上依然無法匹配，這種差距主要是： CPU運算性能對內存的要求遠高於現在的內存能提供的性能。
也就是說，CPU運算很快，內存相對較慢，為了抹平這種差距，工程師們想了很多方法。在我看來，散列表的使用就是利用電腦的高計算性能（優勢）去彌補內存速度（不足）的不足，你仔細思考散列表的執行過程，就會明白我的意思。

以上就是哈希的全部內容

❼ 哈希演算法從原理到實戰

引言 

       將任意長度的二進制字元串映射為定長二進制字元串的映射規則我們稱為散列（hash）演算法，又叫哈希（hash）演算法，而通過原始數據映射之後得到的二進制值稱為哈希值。哈希表（hash表）結構是哈希演算法的一種應用，也叫散列表。用的是數組支持按照下標隨機訪問數據的特性擴展、演化而來。可以說沒有數組就沒有散列表。

哈希演算法主要特點

        從哈希值不能反向推導原始數據，也叫單向哈希。

        對輸入數據敏感，哪怕只改了一個Bit，最後得到的哈希值也大不相同。

        散列沖突的概率要小。

        哈希演算法執行效率要高，散列結果要盡量均衡。

哈希演算法的核心應用

         安全加密 ：對於敏感數據比如密碼欄位進行MD5或SHA加密傳輸。

         唯一標識 ：比如圖片識別，可針對圖像二進制流進行摘要後MD5，得到的哈希值作為圖片唯一標識。

         散列函數 :是構造散列表的關鍵。它直接決定了散列沖突的概率和散列表的性質。不過相對哈希演算法的其他方面應用，散列函數對散列沖突要求較低，出現沖突時可以通過開放定址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高。反而更加關注的是散列的均勻性，即是否散列值均勻落入槽中以及散列函數執行的快慢也會影響散列表性能。所以散列函數一般比較簡單，追求均勻和高效。

        *負載均衡 ：常用的負載均衡演算法有很多，比如輪詢、隨機、加權輪詢。如何實現一個會話粘滯的負載均衡演算法呢？可以通過哈希演算法，對客戶端IP地址或會話SessionID計算哈希值，將取得的哈希值與伺服器列表大小進行取模運算，最終得到應該被路由到的伺服器編號。這樣就可以把同一IP的客戶端請求發到同一個後端伺服器上。

        *數據分片 ：比如統計1T的日誌文件中「搜索關鍵詞」出現次數該如何解決？我們可以先對日誌進行分片，然後採用多機處理，來提高處理速度。從搜索的日誌中依次讀取搜索關鍵詞，並通過哈希函數計算哈希值，然後再跟n(機器數)取模，最終得到的值就是應該被分到的機器編號。這樣相同哈希值的關鍵詞就被分到同一台機器進行處理。每台機器分別計算關鍵詞出現的次數，再進行合並就是最終結果。這也是MapRece的基本思想。再比如圖片識別應用中給每個圖片的摘要信息取唯一標識然後構建散列表，如果圖庫中有大量圖片，單機的hash表會過大，超過單機內存容量。這時也可以使用分片思想，准備n台機器，每台機器負責散列表的一部分數據。每次從圖庫取一個圖片，計算唯一標識，然後與機器個數n求余取模，得到的值就是被分配到的機器編號，然後將這個唯一標識和圖片路徑發往對應機器構建散列表。當進行圖片查找時，使用相同的哈希函數對圖片摘要信息取唯一標識並對n求余取模操作後，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。實際上海量數據的處理問題，都可以藉助這種數據分片思想，突破單機內存、CPU等資源限制。

        *分布式存儲 ：一致性哈希演算法解決緩存等分布式系統的擴容、縮容導致大量數據搬移難題。

         JDK集合工具實現 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map實現類源碼分析，詳見  https://www.jianshu.com/p/602324fa59ac

總結

        本文從哈希演算法的原理及特點，總結了哈希演算法的常見應用場景。

        其中基於余數思想和同餘定理實現的哈希演算法（除留取余法），廣泛應用在分布式場景中（散列函數、數據分片、負載均衡）。由於組合數學中的「鴿巢」原理，理論上不存在完全沒有沖突的哈希演算法。（PS:「鴿巢」原理是指有限的槽位，放多於槽位數的鴿子時，勢必有不同的鴿子落在同一槽內，即沖突發生。同餘定理：如果a和b對x取余數操作時a%x = b%x，則a和b同餘）

        構造哈希函數的常規方法有：數據分析法、直接定址法、除留取余法、折疊法、隨機法、平方取中法等  。

        常規的解決哈希沖突方法有開放定址法（線性探測、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是採用鏈表法解決哈希沖突的。鏈表法適合大數據量的哈希沖突解決，可以使用動態數據結構（比如：跳錶、紅黑樹等）代替鏈表，防止鏈表時間復雜度過度退化導致性能下降；反之開放定址法適合少量數據的哈希沖突解決。

❽ 感知哈希演算法

感知哈希演算法是一類哈希演算法的總稱，其作用在於生成每張圖像的「指紋」(fingerprint)字元串，比較不同圖像的指紋信息來判斷圖像的相似性。結果越接近圖像越相似。感知哈希演算法包括均值哈希（aHash）、感知哈希（pHash）和dHash（差異值哈希）。
aHash速度較快，但精確度較低；pHash則反其道而行之，精確度較高但速度較慢；dHash兼顧二者，精確度較高且速度較快。
在得到64位hash值後，使用漢明距離量化兩張圖像的相似性。漢明距離越大，圖像的相似度越小，漢明距離越小，圖像的相似度越大。

a) 縮放圖片：為了保留圖像的結構，降低圖像的信息量，需要去掉細節、大小和橫縱比的差異，建議把圖片統一縮放到8*8，共64個像素的圖片；
b) 轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖；

c) 計算平均值： 計算進行灰度處理後圖片的所有像素點的平均值；
d) 比較像素灰度值：遍歷灰度圖片每一個像素，如果大於平均值記錄為1，否則為0；
e) 構造hash值：組合64個bit位生成hash值，順序隨意但前後保持一致性即可；
f) 對比指紋：計算兩幅圖片的指紋，計算漢明距離。

感知哈希演算法可以獲得更精確的結果，它採用的是DCT（離散餘弦變換）來降低頻率。
a) 縮小尺寸
為了簡化了DCT的計算，pHash以小圖片開始（建議圖片大於8x8，32x32）。
b) 簡化色彩
與aHash相同，需要將圖片轉化成灰度圖像，進一步簡化計算量（具體演算法見aHash演算法步驟）。
c) 計算DCT
DCT是把圖片分解頻率聚集和梯狀形。這里以32x32的圖片為例。

d) 縮小DCT
DCT的結果為32x32大小的矩陣，但只需保留左上角的8x8的矩陣，這部分呈現了圖片中的最低頻率。
e) 計算平均值
如同均值哈希一樣，計算DCT的均值
f) 進一步減小DCT
根據8x8的DCT矩陣進行比較，大於等於DCT均值的設為」1」，小於DCT均值的設為「0」。圖片的整體結構保持不變的情況下，hash結果值不變。
g) 構造hash值
組合64個bit位生成hash值，順序隨意但前後保持一致性即可。
h）對比指紋：計算兩幅圖片的指紋，計算漢明距離。

相比pHash，dHash的速度更快，相比aHash，dHash在效率幾乎相同的情況下的效果要更好，它是基於漸變實現的。
a) 縮小圖片：收縮至9*8的大小，它有72的像素點；
b) 轉化為灰度圖：把縮放後的圖片轉化為256階的灰度圖。（具體演算法見aHash演算法步驟）；
c) 計算差異值：計算相鄰像素間的差異值，這樣每行9個像素之間產生了8個不同的差異，一共8行，則產生了64個差異值；
d) 比較差異值：如果前一個像素的顏色強度大於第二個像素，那麼差異值就設置為「1」，如果不大於第二個像素，就設置「0」。
e) 構造hash值：組合64個bit位生成hash值，順序隨意但前後保持一致性即可。
f) 對比指紋：計算兩幅圖片的指紋，計算漢明距離。

❾ 均值哈希演算法和感知哈希演算法

1.離散餘弦變換

離散餘弦變換由於為數據與餘弦函數乘積累計，將無規律數列改為規則排列，如圖像數據原數據為無規則二維矩陣，離散餘弦變換後矩陣左上角包含圖像數據的低頻信息部分，右下角為高頻信息部分，低頻信息為圖像主體框架，高頻信息記錄圖像細節，去掉50%高頻信息存儲部分，圖像信息量損失不超過5%(未驗證此數據)，常用於圖像壓縮(如jpeg圖像)

2.漢明距離

兩個字碼中不同位值的數目叫漢明距離，即a^b後驗證結果的非0個數即為漢明距離

3.均值哈希演算法和感知哈希演算法

均值哈希演算法和感知哈希演算法常用於相似圖像識別，將基準圖縮小為較小尺寸圖片，均值哈希演算法計算圖像平均像素值(未驗證添加權值，理論可使圖像部分區域具有更大權重)，然後將每個元素點與平均像素值比較，大於或等於均值，記為位1，小於均值記為位0，得到一串哈希值；感知哈希演算法先進行離散餘弦變換，取矩陣左上角區域數據(圖像低頻信息區域)，計算均值並將每個數值與均值比較，得到一串哈希值。在原圖片中取相同大小圖片，計算出另一串哈希值，得到兩串哈希值漢明距離，值越小兩張圖片相似度越高

❿ 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的特點。