Implementation of Hash Function in C language

Question

I'm new to programming. and I'm learning a C language. Currently working on Harvard's CS50 problem set (this one: https://cs50.harvard.edu/x/2022/psets/5/speller/).

In that problem, they want us to store every word in dictionary inside Hash Table. In which we need a Hash Function to access the table.

So, I'm trying to figure out how to write a hash function. And what I do is: I want to store each word by using their first three letter as a bucket (or keys?) in a Table (Table is an array).

Explanation:

N = 17576
Table[N]

// Each index position in a Table Array act as first three letter in alphabetical order
[0]   : Aaa | [1]   : Aab ... [25] : Aaz
[676] : Baa | [677] : Bab ... [701] : Baz

Example storing a Name:
Hermione
[4853] : Her = Hermione

So this is the code I wrote to get what I want. This code is run successfully for that CS50 problem. And give me fast enough running time when execute it.

Code:

// Hashes word to a number
unsigned int hash(const char *word)
{
    /* 
        Hash Function that uses first three letter in word as a bucket number in a Table 
        Store in a table in which each bucket start with the first three letter in word
        ex: Hermione | [Her] = Hermione
        
        F = (l1 * 676) + (l2 * 26) + l3

        l1: H (72) - (65) A = 7
        l2: E (69) - (65) A = 4
        l3: R (82) - (65) A = 17

        F = (7 * 676 ) + (4 * 26) + 17
          = 4732 + 104 + 17
          = 4853

        Hermione in bucket 4.853 in 17.576 Table
    */ 

    int next_letter = 0;
    int l1 = 0, l2 = 0, l3 = 0;

    for (int i = 0, n = strlen(word); i < n; i++)
    {
        /*
            We need to check if letter in word may apostrophe, if that's the case go to next letter 
            Ex: Ab's | [Abs] = Ab's
            a1: A | a2: b | a3: s
            We ignore apostrophe, go to next letter
        */
        if (isalpha(word[i]))
        {
            // Get first letter in word
            // Actually no need to concern about apostrophe, every word in dictionary start with alphabet
            if (next_letter == 0)
            {
                // Get index postion of word by substract it with ASCII Code
                l1 = toupper(word[i]) - 'A';

                // If we success get first word, it's time for second word
                next_letter++;
            }
            // Get second letter in word 
            else if (next_letter == 1)
            {
                // Get index postion of word by substract it with ASCII Code
                l2 = toupper(word[i]) - 'A';

                // If we success get second word, it's time for third word
                next_letter++;
            }
            // Get third letter in word
            else
            {
                // Get index postion of word by substract it with ASCII Code
                l3 = toupper(word[i]) - 'A';

                // When found just break the loop since the third letter is end of it 
                break;
            }
        }
    }

    // Get index number for a bucket using our Formula
    unsigned int index = (l1 * 676) + (l2 * 26) + l3;
    
    return index;
}

So what you guys think about my hash function? Is it good enough? or too complicated? or maybe there's a good hash function that I didn't know.

Thank you. I hope you understand my explanation and have a time to review it.

(A)/The part about apostrophes needs to be right at the procedure's head. — greybeard, Dec 21, 2022 at 7:23

slepic · Accepted Answer · 2022-12-21 11:39:46Z

Don't compute strlen(word)!

A call to strlen is O(n) in time, where n is the length of the string.

By calling this function you get overall time complexity comparable with a hash function that depends on all characters of the input. And so you loose the presumed performance gain of hashing only 3 letters.

Just terminate the loop if you happen to encounter the \0 character.

Use array for l1, l2, l3

You can simplify your code if you treat those 3 as an array.

Don't create unnecessary variables only to return them on the next line

Just return the expression.

It's probably just a matter of preference, personally I'd even strip the unnecessary parenthesis. Seems much more readable, basically because there is much less to read...

Use the pointer as iterator

You get some small performance gain if you iterate over the word pointer rather then introducing integer iterator i.

Guard against NULL pointer

It may be wise to handle the case when word is NULL to avoid possible segmentation fault.

Overuse of comments

You don't have to comment on every line of your code. It creates disturbance and gets out of date easily.

Describe all important about the function in the comment above the function.

Add comments inside the implementation only when "why" is not obvious. The "how" is never needed in the comment because that's what you discover by reading the code.

For example here

// Get index postion of word by substract it with ASCII Code
l2 = toupper(word[i]) - 'A';

The comment says the same as what the code does. If I were to write a comment for this line I would rather explain WHY toupper needs to be used there. But the info belongs to the main comment anyway...

Modified code - Putting it all together:

hash.c

#include <ctype.h>
#include "hash.h"

#define MAX_HASHED_LETTERS 3

unsigned int hash(const char *word)
{
    if (word == NULL) {
        return 0;
    }

    unsigned int L[MAX_HASHED_LETTERS] = {0, 0, 0};
    unsigned int letter_index = 0;

    for (char c = *word; c != '\0'; c = *(++word))
    {
        if (isalpha(c))
        {
            L[letter_index++] = toupper(c) - 'A';
            if (letter_index == MAX_HASHED_LETTERS) {
                break;
            }
        }
    }

    return L[0] * 676 + L[1] * 26 + L[2];
}

The macro MAX_HASHED_LETTERS is there to improve readability, but it should be private to the hash function. And so I placed it into the module hash.c while a forward declaration of the function should be placed in header file hash.h.

hash.h

#pragma once

/**
 * Returns a hash of the word's first up to 3 "isalpha" characters.
 * The function is case-insensitive meaning the returned value is the same for any case variation of the input.
 * It returns 0 for NULL pointer, words that don't contain "isalpha" characters and words whose first up to 3 letters are all "a" or "A".
 *
 * Example: ....
 */
unsigned int hash(const char *word);

Generalize

In case it is needed we can generalize to be able to hash any number of first letters. We just need to get rid of the fixed size array L and compute the hash incrementally. Although this will probably overflow for larger n (which may not be a problem though).

#define ALPHABET_SIZE ('Z' - 'A' + 1)

unsigned int hash_first_n_letters_ci(const char *word, unsigned int n)
{
    if (word == NULL) {
        return 0;
    }
    
    unsigned int letter_index = 0;
    unsigned int hash = 0; 
    for (char c = *word; c != '\0'; c = *(++word))
    {
        if (isalpha(c))
        {
            hash = hash * ALPHABET_SIZE + (toupper(c) - 'A');
            if (++letter_index == n) {
                // skip the finalizing loop as all n letters were found and so the hash is already final
                return hash;
            }
        }
    }
    
    // finalize the hash if less then n letters were found
    for (; letter_index < n; ++letter_index) {
        hash *= ALPHABET_SIZE;
    }

    return hash;
}

unsigned int hash_first_3_letters_ci(const char *word)
{
    return hash_first_n_letters_ci(word, 3);
}

Test your code

It is good to add some tests to make sure everything works during refactoring. Actually it would be even better to write tests first. Let them fail. Then keep writing the implementation until all the tests succeed. Then improve the implementation while being sure everything still works.

A simple test suite can be carried out using assert.

#include <assert.h>

int main()
{
    assert(hash_first_3_letters_ci(NULL) == 0);
    assert(hash_first_3_letters_ci("") == 0);
    
    assert(hash_first_3_letters_ci("a") == 0);
    assert(hash_first_3_letters_ci("aa") == 0);
    assert(hash_first_3_letters_ci("aaa") == 0);
    assert(hash_first_3_letters_ci("aaabcde") == 0);
    
    assert(hash_first_3_letters_ci("'a") == 0);
    assert(hash_first_3_letters_ci("'aa") == 0);
    assert(hash_first_3_letters_ci("'aaa") == 0);
    assert(hash_first_3_letters_ci("'aaabcde") == 0);
    
    assert(hash_first_3_letters_ci("A") == 0);
    assert(hash_first_3_letters_ci("AA") == 0);
    assert(hash_first_3_letters_ci("AAA") == 0);
    assert(hash_first_3_letters_ci("AAABCDE") == 0);
    
    assert(hash_first_3_letters_ci("'A") == 0);
    assert(hash_first_3_letters_ci("'AA") == 0);
    assert(hash_first_3_letters_ci("'AAA") == 0);
    assert(hash_first_3_letters_ci("'AAABCDE") == 0);
    
    assert(hash_first_3_letters_ci("aab") == 1);
    assert(hash_first_3_letters_ci("AAB") == 1);
    assert(hash_first_3_letters_ci("aabbbbb") == 1);
    assert(hash_first_3_letters_ci("AABBBBB") == 1);
    
    assert(hash_first_3_letters_ci("'aab") == 1);
    assert(hash_first_3_letters_ci("'AAB") == 1);
    assert(hash_first_3_letters_ci("'aabbbbb") == 1);
    assert(hash_first_3_letters_ci("'AABBBBB") == 1);
    
    assert(hash_first_3_letters_ci("aba") == 26);
    assert(hash_first_3_letters_ci("ababcd") == 26);
    assert(hash_first_3_letters_ci("ABA") == 26);
    assert(hash_first_3_letters_ci("ABABCD") == 26);
    
    assert(hash_first_3_letters_ci("a'ba") == 26);
    assert(hash_first_3_letters_ci("a'babcd") == 26);
    assert(hash_first_3_letters_ci("A'BA") == 26);
    assert(hash_first_3_letters_ci("A'BABCD") == 26);
    
    assert(hash_first_3_letters_ci("b") == 676);
    assert(hash_first_3_letters_ci("B") == 676);
    
    assert(hash_first_3_letters_ci("ba") == 676);
    assert(hash_first_3_letters_ci("BA") == 676);
    
    assert(hash_first_3_letters_ci("baa") == 676);
    assert(hash_first_3_letters_ci("baabcd") == 676);
    assert(hash_first_3_letters_ci("BAA") == 676);
    assert(hash_first_3_letters_ci("BAABCD") == 676);
    
    assert(hash_first_3_letters_ci("ba'a") == 676);
    assert(hash_first_3_letters_ci("ba'abcd") == 676);
    assert(hash_first_3_letters_ci("BA'A") == 676);
    assert(hash_first_3_letters_ci("BA'ABCD") == 676);
    
    assert(hash_first_3_letters_ci("aaz") == 25);
    assert(hash_first_3_letters_ci("aazzzz") == 25);
    assert(hash_first_3_letters_ci("AAZ") == 25);
    assert(hash_first_3_letters_ci("AAZZZZ") == 25);
    
    assert(hash_first_3_letters_ci("azz") == 675);
    assert(hash_first_3_letters_ci("azzzzz") == 675);
    assert(hash_first_3_letters_ci("AZZ") == 675);
    assert(hash_first_3_letters_ci("AZZZZZ") == 675);

    assert(hash_first_3_letters_ci("zaa") == 676 * 25);
    assert(hash_first_3_letters_ci("zaazyx") == 676 * 25);
    assert(hash_first_3_letters_ci("ZAA") == 676 * 25);
    assert(hash_first_3_letters_ci("ZAAZYX") == 676 * 25);
    
    assert(hash_first_3_letters_ci("zzz") == (676 + 26 + 1) * 25);
    assert(hash_first_3_letters_ci("zzzzyx") == (676 + 26 + 1) * 25);
    assert(hash_first_3_letters_ci("ZZZ") == (676 + 26 + 1) * 25);
    assert(hash_first_3_letters_ci("ZZZZYX") == (676 + 26 + 1) * 25);

    return 0;
}
```

Don't create unnecessary variables only to return them on the next line stylistically undebatable. Then, there is "debugger" use. — greybeard, Dec 21, 2022 at 8:00
Wow thank you so much. It really gives me new understanding about how to write code. Thank You! — Kevinkun, Dec 21, 2022 at 16:39
slepic, "Don't create unnecessary variables only to return them on the next line" as some sort of performance optimization is unwarranted. Code for clarity. — chux - Reinstate Monica, Dec 21, 2022 at 17:34
You get some small performance gain if you iterate over the word pointer rather then introducing integer iterator i. - If your compiler is any good, this is usually not true. (Assuming of course that you compile with optimization enabled; debug-mode performance usually isn't relevant). Especially in a simple case like this, compilers usually manage to transform i=0 ; i<n; i++ loops into asm that looks like endp = ptr+n; do{ ptr++; }while(ptr != endp);. If you unroll/vectorize with a cleanup loop that uses i, though, that can defeat it and make it worth using pointers manually. — Peter Cordes, Dec 21, 2022 at 19:42
Agreed that with the hash loop looking for a terminator itself instead of calling strlen, it would be more natural and idiomatic to increment the pointer. But if you always want to stop after at most 3 characters, for(int i=0 ; i<3 ; i++) with an if(word[i] == '\0') break; seems good to me. Or if we're stopping after the first 3 alphabetic characters, which might require skipping over non-alphabetic chars, then yeah it makes less sense (for style reasons) to have a loop counter. Your for loop with a pointer increment looks good for that. But it's not a performance problem. — Peter Cordes, Dec 21, 2022 at 19:44

chux - Reinstate Monica · Accepted Answer · 2022-12-21 17:56:14Z

Pedantic: Avoid undefined behavior

if (isalpha(word[i])) risks undefined behavior when word[i] < 0.

Better as if (isalpha(*(unsigned char *)word[i])).

Handle non-letters

Although designed for letters, hash(const char *word) always returns 0 when word is non-letters.

Instead designed code primarily for letters, yet do something reasonable otherwise.

unsigned hash(const char *word) {
  const unsigned char *uword = (const unsigned char *) word;
  unsigned hash = 0;
  for (size_t i = 0; i < 3 && uword[i]; i++) }
    hash *= 26;
    hash += tolower(uword[i]) - 'A';
  }
  return hash % (26u*26*26);
}

Note: There really is no need for the - 'A'.

Hash Table Size

IMO, the hash function should not assume the Hash Table Size. Let the calling code reduce range as needed. This allows for wider use of your hash function.

unsigned pre_hash(const char *word) {
  const unsigned char *uword = (const unsigned char *) word;
  unsigned hash = 0;
  for (size_t i = 0; i < 3 && uword[i]; i++) }
    hash *= 26;
    hash += tolower(uword[i]);
  }
  return hash;
}

unsigned hash_index = pre_hash(word) % hash_table_size.

Well, I have a question. What if I want to search data either by phone number or person name? Means I need to have two different Hash Table, right? One by hashing the phone number, and one by hashing the person name like my code above. Or maybe there's a way that I can do both only in one table? — Kevinkun, Dec 21, 2022 at 20:04
@Kevinkun N hash tables, each with pointers to the records. Records in another collection. — chux - Reinstate Monica, Dec 21, 2022 at 22:17

Stack Exchange Network

Implementation of Hash Function in C language

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
algorithm
c
hash-map
or ask your own question.

Hot Network Questions

Implementation of Hash Function in C language

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
algorithm
c
hash-map
or ask your own question.