快速和（實際上）無衝突散列

-2

我有一個計算（長）路徑的對象。如果計算相同的路徑，則兩個對象相等。我以前測試過，如果兩個對象是由剛纔做類似等於：快速和（實際上）無衝突散列

obj1.calculatePath() == obj2.calculatePath()

不過，現在這已經成爲一個性能瓶頸。我試圖在對象內部存儲路徑，但因爲我有很多對象，所以這變成了內存問題。

我估計64位散列應該足以避免衝突 - 假設散列很好（雙射）。因此，由於通常的快速哈希（Murmur等）確實有碰撞，所以我想避免它們，因爲當你可以使用像SHA-2這樣的哈希函數時，聽起來像是頭疼的事情。（如果我可以信任散列而不是在兩個對象的散列相匹配的情況下執行額外檢查，那就更好了）

然而，與舊的散列函數（如MD系列）相比，SHA也「慢」用MD5甚至MD4這樣的東西會更好嗎？

所以我的問題是：假設沒有一個邪惡的黑客動機與特製的輸入產生衝突 - 但只有良性（隨機）輸入。我應該選擇哪一個散列函數作爲我的代碼中性能關鍵的部分，我希望避免使用像Murmur這樣的「不安全」散列的複雜性。

來源

2014-11-04 Markus

我不確定你的問題是否合理。 *根據定義，所有*哈希函數都有碰撞。你說「這已經成爲一個性能瓶頸」，但是計算一個散列並比較，根據定義，它將比原始值慢。你說過你有足夠的對象，路徑列表成爲內存問題 - 什麼構成內存問題？你是在256MB內存的機器上運行，還是真的擁有數百萬個具有1000個字符路徑的對象？ – 2014-11-04 10:10:51

@DanPuzey謝謝你的時間。我知道所有哈希都有碰撞，這是我的標題說「（實際上）」。也許該帖子的其餘部分不清楚。然而，Murmur在英語中甚至有文字碰撞。在MD5碰撞中非常罕見，只有找到一個獎勵。我認爲是有區別的。我沒有幾百萬的路徑，但可能有一百萬，我不知道它們的長度。但是，我在自定義速度和內存限制環境中運行。 – Markus 2014-11-04 15:24:11

因此，如果您的環境有限，您應該分享這些限制。事實上，你的問題很難回答。同樣值得注意的是，當你在散列文件路徑時，「Murmur甚至在英文中的文字內碰撞」是無關緊要的。您是否嘗試過散列大量數據以查看是否存在衝突？ – 2014-11-04 15:27:15

沒有更多信息很難幫助。所有人都可以推薦的是一個通用的散列函數。有一些要點！

FNV-1A（http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function）

通常是不太寒酸的起點。（a）容易實現，（b）通常不「不好」，（c）計算便宜，適用於你的「長期」路徑問題。

但是我想知道的是：

這些路徑在哪些空間中？ In（x，y，z，t）是「真實」的時空（即軌跡）嗎？通過某些圖形的路徑？他們是文件路徑嗎？還有別的嗎？

沒有更多的上下文很難說更多。

來源

2014-11-04 16:57:49 Persixty

快速和（實際上）無衝突散列

回答

相關問題