Hash function for a key of type structure

Question

I need to implement a hash function for a key of type structure. This structure is as follows:

typedef struct hash_key_s {
    void *k1;
    char *k2;
    char *k3;
} hash_key_t;

My proposed hash function is as follows:

unsigned long hash_func (void *key)
{
    hash_key_t  *k = (hash_key_t *) key;
    unsigned long h = 0;
    char c = 0;
    char *p = k->k2;

    if (p != NULL) {
        for (c=0; c=*p; p++) {
            h = h*31 + c;
        }
    }
    p = k->k3;
    if (p != NULL) {
        for (c=0; c=*p; p++) {
            h = h*31 + c;
        }
    }

    h = h*31 + (((unsigned long) k->k1) >> 2);
    return h*110351524UL;
}

I just want to know if it is a good hash or if I can improve it further.

Answer 1

"Is this a good hash function?" is not a question that can be answered in isolation. It depends greatly on the expected distribution of the inputs and on the desired distribution of its output. Do you want each bit of the output to be equally likely to be 0 or 1, for example?

Here, I'm going to assume that you want the minimal requirements for a hash function - maximum likelihood of different outputs for different inputs, and no requirements for cryptographic-strength collision resistance.

---

It's interesting that you're combining the content pointed to by k2 and k3 but that value of the pointer k1 - a comment is needed to explain why this is what you want.

---

I assume that you are constrained to the signature unsigned long (*)(void*) by some library. A pointer to const void would be better as the argument, as your hash function really mustn't modify its argument. Failing that, you can declare k as pointer-to-const:

    hash_key_t const *const k = key;

(It's C, so void* will promote to any other pointer).

---

The repeated code to hash the two strings can be extracted into a function:

static unsigned long hash_string(const char *s, unsigned long h)
{
    if (!s) return h;
    while (*s)
        h = h * 31 + *s++;
    return h;
}

unsigned long hash_func (void *key)
{
    const hash_key_t *const k = key;
    unsigned long h = 0;

    h = hash_string(k->k2, h);
    h = hash_string(k->k3, h);

    h = h*31 + (unsigned long)k->k1;
    return h*110351524UL;
}

I removed the right-shift of k1 in the above - that doesn't add any extra entropy to the hash, and may (on some platforms) reduce it. But I have left your magic constant untouched - see next section.

---

An aspect of your algorithm that's a little suspect is the final constant. It is an even number - worse, it's a multiple of 4; this is throwing away two bits from your result. I'm not convinced there's a good reason to multiply the final result - you'll need to justify it given the expected inputs and desired distribution of result.

Because you effectively concatenate the two strings, you'll get collisions between "ab", "c" and "a", "bc". That may or may not be a problem for your inputs, but it's worth noting in a comment in case you want to repurpose this in future. If it's undesirable, you could either perform another multiplication between the strings or you could provide a different per-character constant to each invocation.

---

Rather than reinventing the wheel, you may be able to re-use (or at least copy) an existing algorithm. For example, if your code is GNU GPL compatible, here's the glibc implementation:

/* We assume to have `unsigned long int' value with at least 32 bits.  */
#define HASHWORDBITS 32

/* Defines the so called `hashpjw' function by P.J. Weinberger
   [see Aho/Sethi/Ullman, COMPILERS: Principles, Techniques and Tools,
   1986, 1987 Bell Telephone Laboratories, Inc.]  */
static inline 
unsigned long int
hash_string(const char *str_param)
{
    unsigned long int hval, g;
    const char *str = str_param;

    /* Compute the hash value for the given string.  */
    hval = 0;
    while (*str != '\0') {
        hval <<= 4;
        hval += (unsigned long int) *str++;
        g = hval & ((unsigned long int) 0xf << (HASHWORDBITS - 4));
        if (g != 0) {
            hval ^= g >> (HASHWORDBITS - 8);
            hval ^= g;
        }
    }
    return hval;
}