0
$\begingroup$

I have been looking at How to create minimal perfect hash functions, and come across resources such as these:

  • Finding Succinct Ordered Minimal Perfect Hash Functions $$h(x) = \Bigg[\sum_{j=0}^{m-1}g(h_j(x))\Bigg] \mod p$$
  • Generating Perfect Hash Functions
  • Universal and Perfect Hashing

    In this method, we will instead view the key $x$ as a vector of integers $[x_1,x_2,\cdots ,x_k]$ with the only requirement being that each $x_i$ is in the range $\{0, 1,... ,M−1\}$. For example, if we are hashing strings of length $k$, then $x_i$ could be the $i^{th}$ character (assuming our table size is at least 256) or the ith pair of characters (assuming our table size is at least 65536). Furthermore, we will require our table size $M$ to be a prime number. To select a hash function $h$ we choose $k$ random numbers $r_1,r_2,\cdots,r_k$ from $\{0, 1,\cdots ,M-1\}$ and define:

    $$h(x) = r_1x_1 + r_2x_2 + \dots + r_kx_k \mod M.$$

  • jsw_tut_hashing

Other resources are similar.

What I don't understand is where this idea of using $\mod x$ came from, and how they know how to use the components of the hash function equations. That is, I don't see how they knew to use $r_1x_1$ or $\sum_{j=0}^{m-1}g(h_j(x))$ or other things. It seems like it just came from thin air. Wondering if one could explain generally how you go about constructing a minimal perfect hash function (not one like this).

I'm wondering generally what the process is for coming up with a hash function, how they knew what tricks to use to figure it out.

So like there is this Bernstein Hash function:

unsigned djb_hash(void *key, int len)
{
    unsigned char *p = key;
    unsigned h = 0;
    int i;

    for (i = 0; i < len; i++)
    {
        h = 33 * h + p[i];
    }

    return h;
}

It seems so arbitrary, I don't see how it got decided.

Same with the FNV hash:

unsigned fnv_hash(void *key, int len)
{
    unsigned char *p = key;
    unsigned h = 2166136261;
    int i;

    for (i = 0; i < len; i++)
    {
        h = (h * 16777619) ^ p[i];
    }

    return h;
}

Designing a hash function is more trial and error with a touch of theory than any well defined procedure. For example, beyond making the connection between random numbers and the desirable random distribution of hash values, the better part of the design for my JSW hash involved playing around with constants to see what would work best.

...

The key here is that a hash function should never be used blindly without testing it, no matter how good the author says it is. Often, hash tests are designed around a hash function, and that introduces a bias in favor of that function.

The main thing I wonder about is how they know they aren't going to get any collisions in a minimal perfect hash when designing it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.