7
\$\begingroup\$

I thought of a simple way to hash a string. By taking the ASCII decimal value of each character, multiplying it by 10, and adding all of the values computed together for each character in a string. Is there a name for this algorithm? I highly doubt I was the first one to think of this.

Compiled with gcc -Wall -Wextra -Werror -std=c99 string.c -o string

#include <stdio.h>
#include <stddef.h>

size_t stringLength(const char* source)
{
    if(source == NULL) { return 0; }

    size_t length = 0;
    while(*source != '\0') {
        length++;
        source++;
    }
    return length;  
}

static size_t getHash(const char* source)
{
    size_t length = stringLength(source);
    size_t hash = 0;
    for(size_t i = 0; i < length; i++) {
        char c = source[i];
        int a = c - '0';
        hash = (hash * 10) + a;     
    } 

    return hash;
}

static const char *const testCases[] = {
    "this",
    "is",
    "a",
    "test",
    "but",
    "i",
    "should",
    "use",
    "real",
    "dictonary"
};

#define TABLE_SIZE (16)

int main()
{
    size_t name = getHash("Ryan McCullagh");
    printf("%zu\n", name);

    for(size_t i = 0; i < (sizeof(testCases) / sizeof(testCases[0])); i++) {
        const char* source = testCases[i];  
        size_t hash = getHash(source);
        printf("%s <==> %zu\n", source, (hash % TABLE_SIZE));

    }   

    return 0;
}
\$\endgroup\$
6
\$\begingroup\$
  1. Don't check for NULL pointer argument. The function should expect a valid null-terminated string, it's responsibility of the caller to ensure correct argument.

  2. You don't need to know the string length. Check for null-terminator right in the hash loop.

  3. It's possible to write it shorter and cleaner.

    static size_t getHash(const char* cp)
    {
        size_t hash = 0;
        while (*cp)
            hash = (hash * 10) + *cp++ - '0';
        return hash;
    }
    
  4. It's not quite clear what do you mean by "ASCII decimal value". Are you referring to this expression in your code: c - '0'? Well, suppose at some moment c == 'Z', so this expression amounts to 'Z' - '0'. If we substitute ASCII codes for these characters, then we get 90 - 48, this is equal to 42 which is ASCII code for '*' character. So you have transformed 'Z' into '*'. Is this somehow supposed to improve the quality of your hash function? I'm in doubt.

  5. Are you aware that for the same expression c - '0' for a number of possible c values (e.g. ' ', '!', and anything with ASCII value less than 48) you will get a negative result and when you add it to the hash it will be sign-extended and converted to a huge unsigned value, something like 0xffffffffffffffxx?

  6. If you are looking for a short and simple hash function then perhaps either of these might work for you.

    /* D. J. Bernstein hash function */
    static size_t djb_hash(const char* cp)
    {
        size_t hash = 5381;
        while (*cp)
            hash = 33 * hash ^ (unsigned char) *cp++;
        return hash;
    }
    
    /* Fowler/Noll/Vo (FNV) hash function, variant 1a */
    static size_t fnv1a_hash(const char* cp)
    {
        size_t hash = 0x811c9dc5;
        while (*cp) {
            hash ^= (unsigned char) *cp++;
            hash *= 0x01000193;
        }
        return hash;
    }
    
\$\endgroup\$
4
\$\begingroup\$

I have only a few comments about your code, otherwise, it looks good. The string hashing algo you've devised should have an alright distribution and it is cheap to compute, though the constant 10 is probably not ideal (check the link at the end).

  1. I don't see a need for reinventing the wheel here. You should use strlen() to compute the length of strings. It will more than likely be a lot better optimized than your custom stringLength().

  2. However, you don't need to compute the string's length beforehand. getHash() can be optimized by using the null terminator in the string itself to infer its length. No need to do a pre-pass just to compute the length:

    static size_t getHash(const char* source)
    {    
        if (source == NULL) {
            return 0;
        }
    
        size_t hash = 0;
        while (*source != '\0') {
            char c = *source++;
            int a = c - '0';
            hash = (hash * 10) + a;     
        } 
        return hash;
    }
    
  3. Two minor details: In C, you should add void to the parameter list of functions that take no arguments, so main should be int main(void). Also, you don't need to explicitly return 0 at the end of main. This function is treated specially by the compiler. If there's no explicit return, a return 0 is added at the end of main by default.


If you are interested in knowing more about hash functions and algorithms, I recommend reading this article.

\$\endgroup\$
  • \$\begingroup\$ #3 is not correct. It is okay to have int main() definition. A definition like int func(void) is only needed to let the compiler check that you always call func without extra arguments. But normally you do not call main() yourself, there is no need for compiler to check non-existing calls, and so this extra typing is of no use. Also compiler doesn't treat main specially. It is treated specially by the C run-time library (libcrt). By the way, libcrt always calls main with argc and argv arguments. So in fact it is more correct to define your main function as main(). \$\endgroup\$ – Aleksey Demakov Apr 3 '15 at 2:01
  • \$\begingroup\$ @AlekseyDemakov Yes, you are correct about void. I wasn't detailed enough on that point because it is a minor detail. Though since it is a good practice to add void to allow better compile-time checking, I don't see harm in being consistent and adding it to main as well. The compiler does treat main differently when it comes to omitting the return statement. In C99, reaching the end of the function will return 0. That is not true for any other function but main. \$\endgroup\$ – glampert Apr 3 '15 at 2:38
  • \$\begingroup\$ Also, we shouldn't assume that the runtime will always call main with argc and argv. That's only true for Windows, AFAIK. \$\endgroup\$ – glampert Apr 3 '15 at 2:40
  • \$\begingroup\$ Okay, I stand corrected on the main return value. Your were right about it for -std=c99 and -std=c11 modes. \$\endgroup\$ – Aleksey Demakov Apr 3 '15 at 3:13

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.