完美的散列函數是否保證沒有碰撞？

我一直在閱讀和學習哈希和哈希表，並與一些代碼一起訓練（我對這個還是很新的，所以我可能會說我錯過了一些錯誤的東西）。我對這個問題提出了完美的散列函數。只要我有，不知怎的，具有完美的哈希函數我自己的自定義類型：完美的散列函數是否保證沒有碰撞？

class Foo 
{ 
    private int data; 

    override int GetHashCode() 
    { 
     return data.GetHashCode(); 
    } 
}

的一個int哈希碼是int本身，所以我有一個完美的哈希函數，對不對？但是，當我們使用散列函數由簡單的公式對象以一個哈希表映射：

index = foo.GetHashCode() % hashtable.Length

，我們得到的是取決於我們也多少元素在哈希表中的變量指標。如果散列表的大小是int.MaxValue，那麼我們將有一個完美的散列函數。例如，假設我們有一個大小爲2的哈希表。如果我們散列例如數字1和3我們得到

1 % 2 = 1 
3 % 2 = 1

碰撞！我瞭解哈希和哈希表有什麼問題嗎？它表明完美的散列函數並不完美。

來源

2013-05-11 Bosak

如果你可以寫一個完美的散列函數，我想有一百萬美元在等着你。 – ChiefTwoPencils 2013-05-11 20:41:23

@ C.Lang一個完美的散列函數在限制可散列數據集時很容易編寫。 – 2013-05-11 20:54:03

@SethCarnegie：謝謝。我通過非限制性的實現瞭解到。根據他在朱利安的回答中的評論，這是OP所指的。無論如何，只是另一件事纏繞我的頭：）\ – ChiefTwoPencils 2013-05-11 21:15:35

是的，一個完美的散列函數可以保證不會發生衝突。

這就是它的定義！

維基百科（http://en.wikipedia.org/wiki/Perfect_hash_function）

用於一組S A完美散列函數是散列函數映射S中不同元件的一組整數，沒有碰撞。一個完美的哈希函數有很多相同的應用程序中的其他散列函數，但沒有衝突解決必須實施

來源

2013-05-11 20:44:40

是的，但它實際上有碰撞見我做的例子。這是一個給出一對一關係的函數。問題不在散列函數中，而是以計算索引的方式（'i = hash（obj）％length'） – Bosak 2013-05-11 20:48:08

然後你做的例子不是一個完美的散列函數。然而，你的問題的答案是「一個完美的哈希函數保證沒有碰撞？」必須是「是」，因爲正如我所指出的那樣，這是完美散列函數的定義。 – 2013-05-11 22:34:40

優勢你擁有一切權利，直到這一點

index = foo.GetHashCode() % hashtable.Length

你的哈希函數是完美的，但是當你計算模數時，你實際上使用了不同的散列函數。在這種情況下，你的散列函數int.GetHashCode是的完美，但是你的數據結構使用的是foo.GetHashCode() % hashtable.Length不是。也就是說，有一件事是你的對象的哈希值，而另一件事是持有這些對象的結構使用的哈希值。

爲了讓您的數據結構更完美，它的最大尺寸也必須是整數。我們爲什麼不碰撞Dictionary？其實，我們做到了。如果兩個對象A和B在字典中具有相同的散列，我們就會發生衝突。會發生什麼是該字典運行A.Equals(B)作爲最終檢查，看看這兩個對象實際上是否相同。如果他們是，你會得到重複的例外。如果他們不這樣做，他們都被保存在相同的字典哈希中。

來源

2013-05-11 20:48:47

是的，我想了解它，但不是如何實施哈希表？例如在C＃中的字典。而不是一個長度爲int.MaxValue的數組太大而不能有效，並且大量內存將被浪費？ – Bosak 2013-05-11 20:52:14

是的，但字典確實有碰撞。會發生的是，無論何時發生碰撞，字典都會檢查兩個碰撞對象的「Equals」方法。那一個是最後的檢查 – 2013-05-11 20:53:56

是的，我知道他們有碰撞，我知道有很多碰撞求解算法存在，但事實並非如此。所以你知道一個完美的散列函數是否可以存在（使用模數），以便它適用於任何大小的數組。 – Bosak 2013-05-11 20:59:56

是的！（如所述，根據定義）
從哪裏獲得p.h.f從一開始？你想散列一個固定，即常數將S的不同（即無多集）值設爲集合1 .. | S |，雙射。顯然那時，p.h.f取決於集合S
此外，刪除從S上單個元素，並添加一個又一個，你幾乎肯定會得到一個碰撞（新元素的與舊的）。
所以，你實際上想要「爲這樣一個明確定義/描述的集合設置p.h.f.」。然後我們可以嘗試找到一個。

來源

2013-12-07 14:33:53 Michael

完美的散列函數是否保證沒有碰撞？

回答

相關問題