Simple string hashing algorithm implementation

Question

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;
}

Answer 1

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;
   }
   

Answer 2

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.