实现素数哈希的最佳方法是什么?

Question

我正在上斯坦福大学的算法课，课上他们提到了素数。作为一种"快速而肮脏"的哈希方法。所以我试图实现我自己的哈希表类，但我一直在寻找最接近n的素数("桶"的数量)的最佳方法。埃拉托色尼的筛是有效的，但将花费O(nloglogn)的时间复杂度。

有更好的方法来做这件事吗?

Answer 1

你的问题说你正试图选择一个质数最接近桶的数量。大概你这样做是为了避免浪费桶…

你不是这样做的。

当你应用一个素数模数到你的哈希，那么你选择一个素数桶。模数就是桶的数目。

您选择的桶的数量通常取决于表中项目的数量。通常在做出此选择时，目标表大小大约在2n左右，其中n是项的数量。

但是，不需要精确。如果你有一个256个素数的硬编码列表，它们是对数分布的，所以第i个素数大约是2^(i/4)，那么你可以找到最接近2n的那个，然后使用它。它将在目标值的10%以内，这已经足够接近了。

Answer 2

您可以使用像Miller Rabin素数测试这样的素数测试，带有一点随机性来选择桶的数量。虽然测试在常量时间内运行一个std::size_t，但您可能需要尝试几个数字。但是调整哈希表的大小是很少见的。

或者你可以预先计算一个合适的素数列表作为哈希表的大小，例如最接近2^n的素数。您仍然可以通过使用(key ^ seed) % prime向哈希中添加随机性。

Answer 3

GCC只使用预先计算的LUT。当你可以存储一个数组并使用std::lower_bound

时，没有理由重新计算质数实际上，它们使用两个lut。第一种是一个最大为2^64的质数数组。另一个是一个小的内联字典，它包含最后一个素数<= index i，这在构造函数和小字典的常见情况下很有用。

你不需要所有质数。存储更少只是限制了您可以使用的桶的数量，因此您的负载因子可能不太精确。

Answer 4

这是对Will Ness回答的测试代码的一个很小的修改。它在JavaScript中，有类似c的语法:

// stackoverflow.com/a/69345662/849891
//   by stackoverflow.com/users/849891/will-ness
function *primesFrom(start) {
//console.log("Starting....");
if (start <= 2) { yield 2; }
if (start <= 3) { yield 3; }
if (start <= 5) { yield 5; }
if (start <= 7) { yield 7; }
const sieve = new Map();
const ps = primesFrom(2);
ps.next();                 // skip the 2
let p = ps.next().value;   // p==3
let psqr = p * p;          // 9
let c = psqr;              // first candidate, 9
let s = 6;                 // step
let m = 9;                 // multiple
while( psqr < start )
{
// must adjust initial state
s = 2 * p;
m = p + s * Math. ceil( (start-p)/s );
while (sieve.has(m)) m += s;
sieve.set(m, s);
p = ps.next().value;
psqr = p * p;
}
if ( start > c) { c = start; }
if ( c%2 === 0 ) { c += 1; }

// main loop
for ( ;  true ;  c += 2 ) 
{
s = sieve.get(c);
if (s !== undefined) {
sieve.delete(c);
} else if (c < psqr) {
yield c;
continue;
} else {          // c == psqr
s = 2 * p;
p = ps.next().value;
psqr = p * p;
}
m = c + s;
while (sieve.has(m)) m += s;
sieve.set(m, s);
}
}

(function test() {
maxItems = 50;
target = Math.floor(Math.random() * Math.pow(2, 40));
console.log("Target: " + target);
from = Math.floor(target - 5*Math.log(target));

const ps = primesFrom( from );
let left;
let right;
for(i = 0; i < maxItems; i=i+1)
{
p = ps.next().value;
if (p <= target) {
left = p;
} else {
right = p;
break;
}
}
console.log(left + ", " + right);
})();