爲什麼在使用二級散列時表格大小是優質的？

當談到二次散列時，爲什麼表格的大小是一個素數是有利的？我不太明白這一點。爲什麼在使用二級散列時表格大小是優質的？

2014-09-03 user3274549

在仲（「雙」）的散列，你有兩個哈希函數h1和h2和探針序列是通過評估

探針（X，I）=形成（H1（X）+ I＆middot ; H2（X））MOD tableSize

讓我們假設tableSize 不是一個素數。例如，假設表格大小爲12.假設您有散列h1和h2，因此對於某些輸入x，我們得到h1（x）= 0和h2（x）= 6。在這種情況下，探針序列將會爲0,6,0,6,0,6 ......，這不能保證表格的統一覆蓋（事實上，它只是一次又一次地訪問兩個元素）。更一般地說，如果h2（x）的值是表大小的非平凡除數，那麼探測序列將不會覆蓋表的所有元素。

那麼，你如何確保你永遠不會有h2（x）是表大小的平凡除數？那麼，一個簡單的方法就是讓表格大小成爲主要數據 - 畢竟，根據定義，素數沒有不平凡的因數！如果你確實選擇了一個主表的大小，你可以保證探測序列會訪問表中的每一個元素一次和一次，但證明這需要一些模塊化算術。

希望這會有所幫助！

來源

2014-09-03 21:16:25 templatetypedef

另一種確保h2（x）不會與表大小產生共同因子的方法是具有2的冪次方表格大小和h2（x）爲奇數。 – supercat 2015-03-04 23:51:46

爲什麼在使用二級散列時表格大小是優質的？

回答

相關問題