用於路徑緩存的快速，無碰撞散列算法？

我正在使用php轉換網站。我的部分過程是驗證圖像路徑不指向不存在的圖像（即沒有損壞的圖像）。由於許多頁面共享某些圖像，因此我設置了一個緩存陣列，以查看是否已檢查某個給定路徑的圖像文件是否存在。用於路徑緩存的快速，無碰撞散列算法？

使用原始路徑字符串作爲數組索引無法正常工作，所以我使用了md5()，這就是訣竅。然而，轉換腳本需要很長時間，似乎很清楚，這是因爲md5的計算（我在過去幾天頻繁地運行轉換，並且我馬上注意到，只要我的緩存開始工作，腳本花了很長時間才能運行。）

所以我想知道是否有更快的哈希算法，我可以在我的緩存中使用，當然我需要一個不會產生衝突。由於這是一次性腳本，因此我不需要超級安全的不可破解的算法，只需要一個讓作業更快完成的算法。

This comment顯然是php提供給它的所有散列函數的列表。

編輯我沒有畫了很多關注這在我的評論，但是當我使用的路徑作爲緩存數組索引的普通字符串，它沒有工作。只要我將其更改爲md5散列，它就可以工作。如果我有更多的時間，我會解決這個問題，但這是一個一次性的項目，我不能花更多的時間，而不是我絕對需要的時間。

帖子編輯好吧，顯然我在做我的緩存方式有問題;當我將索引更改爲散列而導致緩存開始工作時，我必須改變某些內容，而不管哈希如何。人們說我的散列應該和文件路徑字符串一樣好，而且md5s也不需要那麼長。所以，我不知道我做錯了什麼，我沒有時間在這個項目中弄清楚。我會刪除這個問題，但它已經有答案。

2011-09-07 user151841

沒有碰撞散列這樣的事情。散列基本上涉及獲取無限數量的輸入，並將它們映射到有限數量的輸出。即使在有限的數據集（當然，大小大於1），也無法保證任何散列算法都不會實際散列所有散列並檢查衝突，從而避免衝突。 –

如果MD5速度太慢，那麼你正在做一些非常錯誤的事情。過去5年內構建的任何機器都應該能夠每秒處理數百萬條路徑。關於你管理數組的方式很可能很慢;這個問題根本不可能是MD5。 – meagar

@Michael Madsen它只是無碰撞*足夠*。 – user151841

如果這些散列僅在PHP中使用，並且在此腳本工作時動態構建，爲何不簡單使用數組？

if (isset($path_cache['/some/weird/ugly/long/path'])) { 
    ... 
}

在沒有MD5計算開銷的情況下也能正常工作。

2011-09-07 21:20:07

我會仔細檢查是否有更多的時間，但無論什麼原因，使用原始路徑字符串作爲數組索引不起作用（我在我的問題中說過）。當我使用散列字符串作爲索引時它工作。 – user151841

它怎麼不起作用？如果用作鍵的字符串是路徑或者是md5哈希值，PHP並不在乎，它們都只是字符串。 –

下面是它不工作的方式：當它從緩存陣列中提取一個值時，它設置爲拋出一條消息。在過去的一週裏，我沒有看到這個消息，儘管緩存中充滿了路徑。我將索引更改爲哈希值，突然間，幾乎所有內容都從緩存中提取出來。不幸的是，我沒有時間弄清楚我做錯了什麼：P – user151841

我建議你使用普通路徑 - 無需散列它。然而，crc32似乎是一個快速的。請記住 - 你正在犧牲衝突率來加速。

2011-09-07 21:24:10 gilden

最快的哈希函數似乎是

hash('adler32', $string);

不過只是md5()作品幾乎一樣快，上面的功能。

在PHP中有所有哈希的benchamrk。
http://l.garygolden.me/fastest-hash-php

2012-11-07 16:48:18

foreach (hash_algos() as $value) { 
    print hash($value, 'some random') . ' - ' . $value . '<br />'; 
}

它會在打印PHP支持所有哈希算法散列的字符串。

2014-05-10 09:21:28 azuneca

回答