差的Hash函數

Question

有東西在課堂上沿行提到的「最壞的情況下哈希函數，H（X）= 1」

（我的教練是出城的幾個星期，我明明只想問他是否可以）。

我的問題：「最糟糕的散列函數」究竟意味着什麼？它是這樣每個元素被賦予相同的值1（或1％的tableSize），或者這樣elementOne被賦予散列值1，elementTwo 2，elementThree 3，等等？

可能是一個noob問題，但我想我會問它。

Answer 1

最糟糕的哈希函數是一個返回一個常數值的函數。即該類型的所有對象具有相同的散列值，導致大量的衝突。

雖然通常不能完全避免碰撞，但最小化它們對於使用哈希的任何性能都很重要。

應該指出，雖然它是一個可怕的散列函數，但它在技術上是正確的，因爲對散列函數的要求只是爲被認爲相等的對象返回相同的值（這很平常，因爲它返回一切都相同）。

Answer 2

散列函數的質量由與多個不同對象發生衝突的概率決定。一個完美的散列函數將所有對象映射到沒有碰撞的數字上，從而保證了桶之間物品的均勻分佈。

相比之下，無論您傳遞什麼對象，最糟糕的散列函數都可以通過爲所有對象返回相同的值來確保衝突。這將基於散列的查找轉換爲衝突解析查找，從而消除了首先使用基於散列容器的任何優勢。

Answer 3

在最壞的情況下，每個對象都有相同的散列（例如1）。這與equals相等，只要兩個相等的對象總是具有相同的散列值，所以它可以工作;但它不會給你任何好的散列提供的查找好處，因爲每次嘗試查找對象時，都必須查看集合中的每個對象（因爲它們都具有相同的散列）。

Answer 4

最差的哈希函數是一個返回一個常數值的函數。 在基於散列的集合中，根據對象的散列值存儲對象。
因此，如果對於任何對象，您將獲得相同的散列值，這意味着所有對象最終都存儲在相同的位置。
所以，收集需要迭代總是和總是相同的桶/槽與這個哈希值相關聯來檢索對象。

您失去了使用散列函數的興趣。

Answer 5

無論x是什麼，您定義的散列函數h(x)=1都會生成相同的值。一個理想的散列函數會爲x的每個值生成一個唯一的鍵。常量散列函數最終會爲x的每個值生成相同的散列值。因此，如果你使用散列表的情況下，它將是一個單一的元素表與一個巨大的鏈表