Python中用於命名緩存文件的最短哈希

Question

python中可用的最短哈希（可用於文件名形式，如十六進制摘要）是什麼？我的應用程序想爲某些對象保存緩存文件。這些對象必須具有唯一的repr（），以便它們用於「種子」文件名。我想爲每個對象生成一個可能唯一的文件名（不是那麼多）。它們不應該相互碰撞，但是如果它們做了我的應用程序，那麼這個對象就會缺少緩存（並且必須重新索引該對象的數據，這對應用程序來說是一個小的代價）。

因此，如果發生一次衝突，我們會丟失一個緩存文件，但這是緩存所收集的所有對象的節省，使得應用程序啓動速度更快，所以沒關係。

現在我實際上使用abs（hash（repr（obj）））;沒錯，字符串hash！還沒有發現任何碰撞，但我想有一個更好的散列函數。 hashlib.md5在Python庫中可用，但如果放入文件名中，十六進制文件非常長。替代方案，具有合理的碰撞阻力？

編輯： 用例如下： 數據加載器獲取數據攜帶對象的新實例。獨特的類型有獨特的repr。因此如果存在hash(repr(obj))的緩存文件，則取消該緩存文件的替換，並將未替代對象替換爲obj。如果發生衝突並且緩存是錯誤匹配，我會注意到。因此，如果我們沒有緩存或者有錯誤匹配，我會改爲初始化obj（重新加載它的數據）。

結論（？）

的str散列蟒蛇可能是不夠好，我只是擔心它的抗碰撞性。但是如果我可以用它來散列2**16對象，它將會不夠好。

我發現瞭如何把一個十六進制哈希（從任何散列源）和使用Base64壓縮存儲它：

# 'h' is a string of hex digits 
bytes = "".join(chr(int(h[i:i+2], 16)) for i in xrange(0, len(h), 2)) 
hashstr = base64.urlsafe_b64encode(bytes).rstrip("=") 

Answer 1

的birthday paradox適用：給出了良好的散列函數，在碰撞發生前散列的預期數量爲約SQRT（N），其中N是不同值的數目，該散列函數可以採取。 （我指出的維基百科條目給出了確切的公式）。因此，例如，如果您要使用不超過32位的值，那麼對於大約64K個對象（即2**16對象 - 散列函數可以使用的不同值的平方根），您的碰撞擔心是嚴重的。你期望有多少物體，數量級？

既然你提到碰撞是一個小麻煩，我建議你的目標是哈希長度大約是你將擁有的對象數量的平方，或者少一點，但不會少得多。

你想要創建一個文件名 - 是在Unix上典型的區分大小寫的文件系統嗎？還是你也不得不滿足不區分大小寫的系統呢？這很重要，因爲你的目標是短文件名，但是你可以使用每個字符的位數來表示你的散列作爲文件名，在大小寫敏感或不敏感的系統上會發生顯着變化。

在區分大小寫的系統，可以使用標準庫的base64模塊（我建議編碼的「urlsafe」版本，即this功能，避免了「/」字符，可能出現在平原Base64是重要的在Unix文件名中）。這給你每個字符6個可用位，比16位的4位/字符好得多。

即使在不區分大小寫的系統上，仍然可以比hex更好 - 使用base64.b32encode並獲得每個字符5位。

這些函數獲取並返回字符串;如果您選擇的散列函數生成數字，請使用struct模塊將數字轉換爲字符串。

如果你確實有幾萬個對象，我認爲你可以使用內建散列（32位，所以6-7個字符，取決於你選擇的編碼）。對於一百萬個物體，你需要40位左右（7或8個字符） - 你可以將sha256摺疊（xor，不要截斷;-)一個合理的位數，比如說128位左右，並在編碼之前使用%運算符將其進一步剪切至所需的長度。

Answer 2

我敢肯定，有Python中的CRC32實現，但可能是太短（8位數字）。好的，這很快。

發現，binascii.crc32

Answer 3

如果你有一個碰撞，你怎麼告訴它實際上發生了什麼？

如果我是你，我會使用hashlib到sha1()repr()，然後只是得到一個有限的子串（例如前16個字符）。

除非你在談論大量的這些對象，否則我會建議你只使用完整散列。那麼碰撞的機會是如此，所以，如此之小，以至於你永遠不會看到它發生（可能）。

此外，如果你正在處理那很多文件，我猜你應該調整你的緩存技術來適應它。

Answer 4

字符串的內置散列函數相當無衝突，也相當短。它有2**32值，所以碰到碰撞的可能性很小（如果使用它的abs值，它將只有2**31的值）。

您一直在尋求最短的散列函數。這肯定是

def hash(s): 
    return 0 

，但我想你沒有真正的本意......

Answer 5

短哈希意味着你可以有兩個不同的文件相同的哈希。大哈希也可能發生，但其方式更爲罕見。 也許這些文件名應根據其他參考文件而有所不同，例如microtime（除非這些文件可能創建得太快）。

Answer 6

你可以通過簡單的截斷來縮短你喜歡的任何哈希。 md5始終是32位十六進制數字，但它的任意子字符串（或任何其他散列）具有散列的適當品質：相等的值產生相等的散列值，並且值散佈在一堆中。

Answer 7

對於緩存對象，我們使用hashlib.sha1.hexdigest（），它會產生更長的字符串，並取得很好的成功。無論如何，沒有人真的在看緩存文件。

Answer 8

考慮到您的使用案例，如果您沒有將自己的心設置爲使用單獨的緩存文件並且您的開發路徑不太遠，則可以考慮使用shelve模塊。

這將爲您提供一個持久性字典（存儲在單個dbm文件中），用於存儲對象。酸洗/取出是透明地執行的，你不必擔心哈希，碰撞，文件I/O等。

對於擱置字典鍵，你只需使用repr（obj）並讓shelve處理爲你藏着你的物品。一個簡單的例子：

import shelve 
cache = shelve.open('cache') 
t = (1,2,3) 
i = 10 
cache[repr(t)] = t 
cache[repr(i)] = i 
print cache 
# {'(1, 2, 3)': (1, 2, 3), '10': 10} 
cache.close() 

cache = shelve.open('cache') 
print cache 
#>>> {'(1, 2, 3)': (1, 2, 3), '10': 10} 
print cache[repr(10)] 
#>>> 10