用哈希縮短長網址？

Question

我有一個文件緩存，文件從不同的URL下載。我想通過他們的url的名稱保存每個文件。這些名字可能會很長，但我使用的是FAT32文件系統的設備 - 所以在我耗盡實際磁盤空間之前，長名字已經耗盡了資源。

我正在尋找一種縮短文件名的方法，得到了對字符串進行散列的建議。但我不確定哈希是否保證對於兩個不同的字符串是唯一的。如果兩個散列網址具有相同的散列值，那麼如果我無意中獲取了錯誤的圖像，那將會很糟糕。

感謝

Answer 1

有沒有（縮短）散列可以保證不同的散列每個輸入。這根本不可能。

我通常這樣做的方式是在緩存文件的開始處（例如第一行）保存原始名稱。因此，要找到你做這樣的緩存文件：

• 哈希的URL
• 找到對應於散列
• 檢查第一行的文件。如果是一樣的完整URL：
• 文件的其餘部分是由兩個線和前鋒

您也可以考慮保存在數據庫中URL->文件映射。

Answer 2

目前推薦使用SHA-1算法。沒有已知的方法有意挑起這種算法的碰撞，所以你應該是安全的。用兩個具有共同結構的數據（例如前綴http://）激發碰撞更加困難。如果在獲得HTTP 200響應後保存這些內容，那麼該URL顯然會獲取某些內容，因此使用相同的SHA-1哈希獲得兩個截然不同的有效URL實際上不應該成爲問題。

如果有任何再保證Git使用它來標識源代碼庫中的所有對象，提交和文件夾。我還沒有聽說有人在對象商店發生碰撞。

Answer 3

看看我的評論。
一個可能的解決方案（有很多）是創建一個本地文件（SQLite？XML？TXT？），其中存儲一對（file_id - file_name），以便您可以使用它們的唯一ID將文件保存爲文件名。
只是一個想法，沒有最好...

Answer 4

hash並不是保證是唯一的，但碰撞的機率是微乎其微。

如果你的散列值是128位，那麼任何一對條目的衝突的概率是2^128中的1。通過生日悖論，如果你的桌子上有10^18個條目，那麼碰撞的可能性只有1％，所以你不必擔心它。如果你是偏執狂，那麼通過使用SHA256或SHA512增加哈希的大小。

很明顯，您需要確保散列表示實際佔用的空間比原始文件名更少。 Base-64編碼的字符串表示每個字符6位，因此您可以通過數學計算來確定它是否值得首先執行哈希。

如果您的文件系統barfs由於名稱太長，您可以爲實際存儲創建前綴子目錄。例如，如果文件映射哈希ABCDE，則可以將其存儲爲/path/to/A/B/CDE或/path/to/ABC/DE，具體取決於對您的文件系統最有效的方式。

Git是這種技術在實踐中的一個很好的例子。

Answer 5

你可以做什麼是由索引保存文件，並使用一個索引文件，以找到實際文件的位置

目錄

您有：

index.txt 
file1 
file2 
... 
etc. 

和index.txt你使用一些數據結構來有效地查找文件名（或用一個數據庫替換）

Answer 6

但我不確定散列是否保證對於兩個不同的字符串是唯一的。

他們非常不（也不能，因爲pigeonhole principle）。但是，如果散列足夠長（至少64位）並且分佈良好（理想情況下是密碼散列），那麼碰撞的可能性變得非常小以至於不值得擔心。

作爲粗略指導，一旦文件數量接近可能的不同散列數（birthday paradox）的平方根，就會發生衝突。因此，對於64位散列（10個字符文件名），如果您有40億個文件，則一次衝突的可能性大約爲50％。

您必須決定這是否是可接受的風險。你可以通過使哈希長度更長來減少碰撞的機會，但是當然在某些時候，這意味着與你想要的相反。

Answer 7

您可以爲每個URL生成UUID並將其用作文件名。

UUID是唯一的（或「實際上唯一的」），長度爲36個字符，所以我猜文件名不會是一個問題。

從版本5開始，JDK附帶一個類來生成UUID（java.util.UUID）。如果有方法將它們與URL相關聯，則可以使用隨機生成的UUID，也可以使用基於名稱的UUID。基於名稱的UUID的總是相同的，所以下面的始終是真實的：

String url = ... 
UUID urlUuid = UUID.nameUUIDFromBytes(url.getBytes); 
assertTrue(urlUuid.equals(UUID.nameUUIDFromBytes(url.getBytes)));