2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Those for loops look completely broken. \$\endgroup\$ – twohundredping Dec 13 '16 at 9:49
  • \$\begingroup\$ @twohundredping: Thanks for the comment. It didn't compile. I made the changes. \$\endgroup\$ – Vivek Agrawal Dec 13 '16 at 12:51
4
\$\begingroup\$

"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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed explanation. I could not grasp the whole as of now and therefore will answer your questions after understanding each part of your answer. Thanks for the answer :) \$\endgroup\$ – Vivek Agrawal Dec 13 '16 at 12:54
  • \$\begingroup\$ Yes, your assumption is right that I need minimal requirement. No cryptographic-strength collision resistance. I'm using this for insertion in hash data structure. Combination of k1, k2 and k3 makes a unique key. Therefore I used k1 as one of the member of key structure. Since I just need a pointer value so used "void *" as a datatype for k1. Why to expose what sort of data structure it is pointing to when I'm not going to see the data in that? That's the main motivation of having it as "void *". \$\endgroup\$ – Vivek Agrawal Dec 15 '16 at 13:28
  • \$\begingroup\$ Thanks for suggesting hash_string() usage and pointing to concatenation bug. For concatenation, I've used a delimiter character and used it in hash calculation. I had the temptation to fix that before posting here, but I think I ignored it just being a bit lazy. But after your comment, I couldn't ignore it more. :) Lastly, my code is not GNU GPL compatible, so can't use that in my code. But thanks for pointing to the source code. It is really great to learn from them. :) I really appreciate your time for this review. It helped. :) \$\endgroup\$ – Vivek Agrawal Dec 15 '16 at 13:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.