PSET5 Load: Memory allocation while passing / storing strings in Hash Function

Question

Working on speller and have to stop, but would like some help on where I'm stuck. So far, have decided to go with a hash table approach.

Assume: 1) I've already created a 2d massive array to store words as my hash table

In load, I 1) read from the file char by char into an array 2) terminate with /0

Now I'd like to: 1) hash the 'word' 2) Store the word in my hash table

A couple related questions: 1) Do I have to malloc to store the word? 2) Can I pass the word directly from the array to my hash function and into my table?

My thinking is that since I already have the characters stored in memory, I should somehow be able to pass it to the hash function, get the key, and then just strcpy it into the array without an intermediate step of malloc'ing. Since the array is already allocated, this would save a bunch of time.

But I find a couple problems in advance: each word will be a different length; if I just create max length, I think the 'null' bytes will effect the hash function, since it is based on length of the input; also, the array variable itself is just a pointer to the beginning of the string of characters. I don't know how I can pass the full word into the hash function.

Since I'm relying on the hash function returning the same result, I need to get this right, but feel like I'm not understanding exactly how the stack memory works here, and what tools I have to copy from the stack memory into other functions and parts of the program.

Thanks for any help!

Answer 1

I would take into consideration everything that ronga said! It's a bad idea to create such a massive array to serve as a giant buffer, when all that you need is one small buffer to hold only one word at a time.

But to specifically address your question about how to pass the word in memory to the hash function, you can merely pass it a pointer to the string to be hashed.

The function will probably be written to stop as soon the null string terminator is seen, so the size of the container inside of which the word is doesn't matter.

Something like this:

unsigned int hash(const char* strPtr)  // or unsigned long if you wish
{
    // set initial value for hashValue here

    while (*strPtr != '\0')
    {
        // hashValue updated by hash operation here
        // increase strPtr here
    }

    return hashValue % tablesize;
}

Answer 2

As this PSET has to do with linked lists, you'd have been better off declaring a struct node as shown in the lecture, each holding a word and a pointer to the next node in the list, rather than a 2D array. While not impossible to do with an array, a linked list will be easier to work with, at the very least it will make the search process a lot faster. You also need to declare an array's size beforehand so unless you know how many words you're storing, it is a drain on memory to declare an arbitrarily large array, not to mention the possibility of your declared array being too small. By malloc'ing as you go along, you only use as much memory as you need (dynamic memory allocation). Once you've done that, then yes, you will have to malloc a new node each time you need to store a new word. Then yes, you can strcpy the word as you go along.