MAD方法壓縮功能

我在舊的考試中遇到了以下問題。我的答案只是感覺有點短而不足。我可以看到的任何額外想法或我忽略的原因都很好。 ThanxMAD方法壓縮功能

考慮MAD方法壓縮函數，將哈希碼i的對象映射到6000元素桶陣列的元素[（3i + 7）mod9027] mod6000。解釋爲什麼這是壓縮功能的一個糟糕的選擇，以及如何改進。

我基本上只是說通過將p（或9027）的值更改爲素數併爲（或3）選擇其他常數也可以提高此功能。

2010-06-10 htdIO

是的，我認爲3和9027需要互反。我不認爲+7很重要，可能會被淘汰。如果你確實使它們互斥，那麼第一部分將在9027中均勻地傳播元素，然後將它摺疊成6000，這樣頂部3027總是會與6000的前3027重疊，也就是說一般會有兩倍的元素分佈進入第一批3027桶。如果你可以選擇p接近6000，例如6001，那可能會更好？或者，也許你甚至可以使用6000與不同的？但我不記得這裏的理論。 – Rup 2010-06-10 18:10:28

Rup的評論基本上是正確的答案。 3和9027都可以被3整除，所以3i + 7只能映射到0-9026範圍的1/3。然後映射模塊6000將2/3的值映射到下半部分。因此，第1桶將包含大約1/1500的值[如果我已經完成了數學計算]，而不是您想要的1/6000。存儲桶0將是空的。

來源

2010-06-10 18:36:53 bmm6o

謝謝，所有的答案給了我一點額外的信息和洞察力，我尋求:) – htdIO 2010-06-10 19:14:17

如果i均勻分佈在一個足夠大的範圍內，那麼(3i + 7)mod9027將均勻分佈在0-9026之間，但是然後取模6000意味着三分之二的散列將在範圍的前半部分（0到3026和6000至9026），以及在後半部分（3037至5999）的三分之一。

來源

2010-06-10 18:18:09

MAD方法壓縮功能

回答

相關問題