完善哈希

Question

大廈

爲什麼我們不使用SHA-1，MD5SUM和哈希等標準加密哈希值。它們非常聰明，可以避免碰撞，也不可恢復。所以寧可拿出一套新的散列函數，可能會有衝突，爲什麼我們不使用它們。 我能夠想到的唯一原因是他們需要說大的關鍵說32bit.But仍然避免碰撞，所以仰視肯定是O（1）。

Answer 1

1. 因爲他們是非常緩慢的，原因有二：
   1. 他們的目標是成爲crytographically安全，一般不僅耐碰撞
   2. 他們生產的不是你真正需要一個更大的哈希值哈希表
2. 因爲他們處理非結構化數據（字節/字節流），但你需要哈希往往結構，並且需要線性第一對象

Answer 2

爲什麼我們不使用SHA-1，MD5SUM和哈希等標準加密哈希值。他們有足夠的智慧避免衝突...

錯誤的，因爲：

• 兩個輸入凸輪還是碰巧具有相同的哈希值。假設哈希值是32位，一個很好的通用哈希例程（即，不利用對實際密鑰集合的洞察）仍然有至少1/2^32的機會爲任何2返回相同的哈希值鍵，然後2分之2^ 32機會與那些作爲第三密鑰被散列的一個碰撞，3/2^32爲第四等。
• 具有不同的散列值是一個非常不同的東西從具有散列值映射到散列表中的不同散列桶。添加元素時一個哈希表＃預先存在的元素/表尺寸的碰撞的機會 - 散列值通常改裝成到表大小來選擇一個水桶，所以充其量 - 並再次用於通用散列。

因此而不是想出一套新的哈希函數，這可能有衝突，我們爲什麼不使用它們。

因爲速度往往是程序員的目標，當選擇使用哈希表來說二叉樹。如果散列值在計算上數學上很複雜，那麼它們可能需要比使用更多（但仍然不是特別）容易碰撞但更快計算散列函數更長的時間。這就是說，有些時候對哈希更多的努力可以還清 - 例如，當磁盤並尋求&閱讀記錄的I/O成本上存在哈希表相形見絀哈希計算工作量。

antti對數據也提出了一個有趣的觀點...通用哈希例程通常在具有特定起始地址和多個字節的二進制數據塊上工作（它們甚至可能需要字節數爲2或4）。在許多應用中，需要被散列將與必須不包含在散列數據被混合在一起的數據 - 諸如高速緩存的值，文件句柄，指針/向其它數據或虛擬分派表等的引用。一個常見的解決方案是分別散列所需的字段並組合散列鍵 - 也許使用exclusive或or。由於可能有位字段應與其他不應該散列的數據在相同的內存字節中進行散列，因此您有時需要自定義代碼來提取這些值。儘管如此，即使事先需要一些複製和填充，每個單獨的字段最終都可以使用md5，SHA-1或其他任何形式進行散列，並且這些散列值可以進行類似的組合，因此，這種複雜性並沒有真正明確地排除您的方法，重新感興趣。

唯一的原因我能想到的是他們需要說大的關鍵說32位。

其他所有的東西都相同，關鍵越大越好，但如果散列函數在數學上是理想的，那麼它的任何N位（其中2^N> =＃散列桶）將產生最小的碰撞。

但仍然避免碰撞，所以仰視肯定是O（1）。

再次，錯誤如上所述。

（順便說一句...我在上面幾個地方強調通用目的，這是因爲有些微不足道的情況，您可能會對密鑰有一些瞭解，例如，如果你知道密鑰是數字1000,2000,3000等等高達100000，並且你有至少100個散列桶，你可以簡單地定義你的散列函數爲x/1000，並知道你如果知道你所有的鍵映射到不同的哈希表桶，這種情況稱爲「完美哈希」 - 根據你的問題標題 - 一個好的通用哈希像md5不是一個完美的哈希，在沒有了解完整的可能密鑰的情況下討論完美的哈希是沒有意義的）。