0

I'm using a hash table to implement the spell checker for speller.c with a hash function I found on reddit but it prints out way too many misspelled words and I have no idea why. Any help would be thoroughly appreciated. Here's my code for the various functions in dictionary.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#include "dictionary.h"

#define HASH_TABLE_LENGTH 65536

typedef struct node{
    char dict_word[LENGTH + 1];
    struct node* next;
}node;

node* Hash_Table[HASH_TABLE_LENGTH] = {NULL};

int num_words = 0;

unsigned int hash(const char* word)
{
    unsigned int hash = 0;

    for (int i = 0, len = strlen(word); i < len; i++)
    {
            hash = (hash << 2) ^ (word[i]);
    }

    unsigned int hash_value = hash % (HASH_TABLE_LENGTH);

    return hash_value;

}


/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{

    unsigned int hash_value = hash(word);

    if (Hash_Table[hash_value] == NULL)
    {
        return false;
    }

    node* crawler = Hash_Table[hash_value];

    char temp[LENGTH + 1];

    int len = strlen(word);

    for (int i = 0; i < len; i++)
    {
        temp[i] = tolower(word[i]);
    }

    temp[len] = '\0';

    while (crawler != NULL)
    {
        if (strcmp(crawler->dict_word, temp) == 0)
        {
            return true;
        }

        else crawler = crawler->next;
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{

    FILE* file = fopen(dictionary, "r");

    char word[LENGTH + 1];

    while (fscanf(file, "%s", word) != EOF)
    {

        if(ferror(file) != 0)
        {
            return false;
        }

        node* new_node = malloc(sizeof(node));

        strcpy(new_node->dict_word, word);

        //hash the word
        unsigned int hash_value = hash(new_node -> dict_word);

        //store the corresponding node in correct linked list in hash table
        if(Hash_Table[hash_value] == NULL)
        {
            Hash_Table[hash_value] = new_node;
            new_node -> next = NULL;
        }

        else
        {
            new_node -> next = Hash_Table[hash_value];
            Hash_Table[hash_value] = new_node;
        }

        num_words++;

    }

    fclose(file);

    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    if (num_words > 0)
    {
        return num_words;
    }

    else
        return 0;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    for (int i = 0; i < HASH_TABLE_LENGTH; i++)
    {
        node* cursor = Hash_Table[i];

        while (cursor != NULL)
        {
            node* temp = cursor;
            cursor = cursor -> next;
            free(temp);
        }
    }
    return true;
}
1

In check:

Always normalize (lowercase) your word before hashing, and hash the normalized version. (This might be the reason for too many misspelled words)

Other, more random thoughts:

Your hash function might not be most efficient in distributing over all the table entries, but should work.

In check:

Also, your first test whether the list is empty is redundant, as your while loop later already covers that.

In load:

You rely on the word in the dict to be normalized, which is probably ok.

The code

            new_node -> next = Hash_Table[hash_value];
            Hash_Table[hash_value] = new_node;

works even if the hash table entry is NULL, so you would not need a check and alternative code before.

2
  • Thanks a lot. Do you know of some other, more efficient hash function to optimise the look up process?
    – user34304
    Jan 20 '17 at 12:23
  • One could use something like the Jenkins hash function
    – Blauelf
    Jan 20 '17 at 15:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .