What is the best method to implement prime number hashing?

Question

I was going through the Stanford algorithms course in which they had mentioned prime no. as a 'quick and dirty' method of hashing. So I was attempting to implement my own hash table class, but I am stuck at finding the best way to get the closest prime number to n (number of 'buckets'). Sieve of Eratosthenes is valid, but will take O(nloglogn) time complexity.

Is there any better way to go about this?

Answer 1

Your question says that you are trying to pick a prime number that is closest to the number of buckets. Presumably you are doing this to avoid wasting buckets...

That's not how you do it.

When you apply a prime number modulus to your hash, then you pick a prime number of buckets. The modulus is exactly the number of buckets.

The number of buckets you choose typically depends on the number of items in the table. Usually when this choice is made, the target table size is somewhere around 2n, where n is the number of items.

There is no need to be precise, however. If you have a hard-coded list of 256 primes, logarithmically distributed so that the ith one is about 2^(i/4), then you can just find the one that is closest to 2n and use that. It will be within 10% of the target value, and that is close enough.

Answer 2

You can use a prime number test like Miller Rabin primality test with a bit of randomness to pick the number of buckets. While the test runs in constant time for a single std::size_t you might have to try a few numbers. But resizing a hashtable is rare.

Alternatively you can just pre-compute a list of suitable primes for use as hashtable size, e.g. the closest prime to 2^n. You can still add randomness to the hash by using (key ^ seed) % prime.

Answer 3

GCC just uses a precomputed LUT. No reason to recompute primes when you can just store an array and use std::lower_bound

In fact, they use two LUTs. The primary one is an array of prime numbers up to 2^64. The other is a small inline one that contains the last prime number <= index i which is useful in constructors and common cases of small dictionaries.

You don't need all prime numbers. Storing fewer just limits the number of buckets you may use, so your load factor may be approximated less precisely.

Answer 4

Here's a very small amendment to Will Ness' answer's test code. It's in JavaScript, which has C-like syntax:

// 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);
})();