0

I do apologise for the unspecific question, however I have been slaving away at this problem set for almost two weeks and have only just managed to get code that compiles. I have reached my wits end.

I suspect there is a problem with the way my library is loading in to the hash table, or the way the hash table is being searched.

There could be a problem with the way I am using the hash function but I am not sure.

Here is a snippet from the command line when checking alice.txt, to give an idea of the problem

WORDS MISSPELLED: 27523 WORDS IN DICTIONARY: 143093 WORDS IN TEXT: 29758 TIME IN load: 0.08 TIME IN check: 0.03 TIME IN size: 0.00 TIME IN unload: 0.03 TIME IN TOTAL: 0.14

I am using a c version of spookyhash which can be found here: https://github.com/jibsen/spooky

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // store word in array
    int len = strlen(word);
    char word_copy[len + 1];

    // convert to lower case
    for (int i = 0; i < len; i++)
        word_copy[i] = tolower(word[i]);

    // add null terminator to end of character array
    word_copy[len] = '\0';

    // hash word
    unsigned long int hashcode = spooky_hash64(word_copy, LENGTH, SEED) % HASH_MAX;

    // assign cursor node to first node of the bucket
    node* cursor = hash_table[hashcode];

    // check until end of linked list
    while (cursor != NULL)
    {
        if (strcmp(cursor->buffer, word_copy)) // word is in dictionary
            return true;

        cursor = cursor->next; // check next node
    }

    return false;
}

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

    // assign NULL to each bucket in hash table
    for (int i = 0; i < HASH_MAX; i++)
    {
        hash_table[i] = NULL;
    }

    // open dictionary for reading
    FILE *inptr = fopen(dictionary, "r");
    if (inptr == NULL)
        return false;

    // iterate through dictionary one line at a time
    while(true)
    {
        // malloc node for each word
        node* new_node = malloc(sizeof(node));
        if (new_node == NULL) // check that memory was successfully allocated
            return false;
        else
            new_node->next = NULL; // make new node point to NULL

        // end condition
        if (feof(inptr))
        {
            free(new_node);
            break;
        }

        // increase word count
        wordcount++;

        // iterate one line at a time. storing line in node
        fgets(new_node->buffer, LENGTH, inptr);

        // hash word
        unsigned long int hashcode = spooky_hash64(new_node->buffer, LENGTH, SEED) % HASH_MAX;

        // check for collision
        if (hash_table[hashcode] == NULL) // bucket is empty
        {
            hash_table[hashcode] = new_node;
        }
        else // add new node to beginning of linked list
        {
            new_node->next = hash_table[hashcode]; // new node points to head node
            hash_table[hashcode] = new_node; // hash table points to new node
        }
    }

    // close dictionary
    fclose(inptr);
    loaded = true;
    return true;
}
0

I'd assume

    // hash word
    unsigned long int hashcode = spooky_hash64(word_copy, LENGTH, SEED) % HASH_MAX;

should be

    // hash word
    unsigned long int hashcode = spooky_hash64(word_copy, len, SEED) % HASH_MAX;

or maybe len+1, but not LENGTH. Function-scope variables are allocated on stack and initially contain arbitrary values, and you only write the first len+1 characters.

Also,

        if (strcmp(cursor->buffer, word_copy)) // word is in dictionary
            return true;

should be

        if (strcmp(cursor->buffer, word_copy) == 0) // word is in dictionary
            return true;

as strcmp returns negative value for first word "less than" second, 0 for equal, or a positive value for first word "greater than" second. Comparison is done character by character, the first difference found determining the result.

In load, same problem with the hash.

Also, feof works only after attempting to read, so I guess it should be called after fgets.


3
  • didnt work unfortunately. Somehow i think the hash function is giving me a different value when I call it the second time
    – kevin
    Nov 7 '17 at 17:21
  • So you changed the hash function call to use the actual word length instead of LENGTH in both cases?
    – Blauelf
    Nov 8 '17 at 8:54
  • Also, is there some documentation for your hash function, does it have to be reset between hashes (unlikely since you pass a seed)? Have you tried some other hash function, maybe even a simple one like uint32_t hash(char *word) { uint64_t state = 42; while (*word) { state = (state * 23 + *(word++)) & 0xffffffff; } return (uint32_t) state; } (numbers are arbitrary, just that the factor should be odd)
    – Blauelf
    Nov 8 '17 at 9:04

You must log in to answer this question.

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