我正在學習斯坦福演算法課程，他們在其中提到了素數。作為一種“快速而骯臟”的散列方法。所以我試圖實作我自己的哈希表類，但我一直堅持尋找最接近 n 的素數（“桶”的數量）的最佳方法。埃拉托色尼篩法是有效的，但需要 O(nloglogn) 時間復雜度。
有沒有更好的方法來解決這個問題？
uj5u.com熱心網友回復：
您的問題說您正在嘗試選擇一個最接近桶數的素數。大概你這樣做是為了避免浪費水桶......
這不是你的做法。
當您將質數模數應用于哈希時，您會選擇質數的桶。模數就是桶的數量。
您選擇的存盤桶數通常取決于表中的專案數。通常當做出這個選擇時，目標表大小在 2n 左右，其中 n 是專案數。
然而，沒有必要精確。如果您有 256 個素數的硬編碼串列，按對數分布，因此第 i 個素數約為 2^(i/4)，那么您只需找到最接近 2n 的素數并使用它。它將在目標值的 10% 以內，這已經足夠接近了。
uj5u.com熱心網友回復：
您可以使用像米勒拉賓素數測驗這樣的素數測驗，帶有一點隨機性來選擇存盤桶的數量。雖然對于單個 std::size_t 測驗在恒定時間內運行，但您可能需要嘗試一些數字。但是調整哈希表的大小很少見。
或者，您可以預先計算一個適合用作哈希表大小的素數串列，例如最接近 2^n 的素數。您仍然可以使用(key ^ seed) % prime.
uj5u.com熱心網友回復：
GCC 只使用預先計算的 LUT。當您可以存盤一個陣列并使用時，沒有理由重新計算素數std::lower_bound
事實上，他們使用了兩個 LUT。主要是一個質數陣列，最多為 2^64。另一種是包含最后一個素數 <= 索引 i 的小型行內，這在建構式和小型字典的常見情況中很有用。
你不需要所有的素數。存盤更少只會限制您可以使用的存盤桶數量，因此您的負載因子可能會不太精確。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/485806.html