0

I've completed "Speller" successfully, but have been trying to optimise it as the run time for "check" is significantly longer than the staff solution.

I suspect the reason is that I don't have enough "buckets" from the simple hash function I made. Knowing the maximum buckets the hash function could produce is 46 based off strlen(word), I have declared my hash table array as

node *head[46] = {NULL};

setting all head pointers to NULL initially.

I'm unable to implement a more complex hash function, as I would not be able to accurately define the number of buckets in the hash table array, and am unsure how to correctly implement null pointers or hash keys in a better way.

Would anyone be able to suggest possible errors/corrections I could make so that I could implement a more complex hash function?

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

node *head[46] = {NULL};
int counter = 0;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    char tempword[LENGTH + 1];
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        unload();
        return false;
    }
    while (fscanf(dict, "%s", tempword) != EOF)
    {
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        else
        {
            strcpy(new_node->word, tempword);
        }
        int key = strlen(tempword);
        new_node->next = head[key];
        head[key] = new_node;
        counter++;
    }
    fclose(dict);
    return true;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int key = strlen(word);
    node *trav = head[key];
    while (trav != NULL)
    {
        if (strcasecmp(word, trav->word) == 0)
        {
            return true;
        }
        else
        {
            trav = trav->next;
        }
    }
    return false;
}

Thank you!

1

There are any number of hash functions available on the internet. You just have to pick one.

As far as controlling the number of buckets, that's easy. Just modulo with the number of buckets. For example end the function with this:

 return hashvalue % HASHSIZE;

where hashvalue is the value calculated by the function and HASHSIZE is a #define value containing the number of buckets. That guarantees that the hash value returned is never larger than the number of buckets you want. You can then test with different HASHSIZE values to see what improves performance. ;-)

But all this is meaningless if you don't have a hash function. The code above doesn't hash the word at all, meaning that there is only one linked list for all words in the dictionary!

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Thanks for sending me on the right track Cliff! I came up with my own hash function (just to try it out) and was able to limit the buckets with HASHSIZE and speed up check() significantly. My program is still too slow to post on the leaderboard however :( As a follow up question, is there any way of determining the best value for HASHSIZE to optimize speed and resources used? A number of the hash functions I saw had certain recommendations regarding prime numbers, powers of two, and collision percentages but I wasn't too sure how to interpret it.
    – pelhayek
    May 15 '18 at 12:34

You must log in to answer this question.

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