0

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!

2 Answers 2

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;
}
3
  • Thanks, so all I need to do is modify the hash function to stop at terminating character. I'm still unclear from a performance perspective why allocating a (still relatively) small buffer is a bad idea compared to eating cycles allocating / deallocating memory, but maybe I don't understand computer performance that well. My idea was to trade space for processor time, which at this scale seems reasonable.
    – borker
    Oct 5, 2016 at 17:31
  • 1
    But what you said was that you would allocate a buffer the size of a INT_MAX! Seeing that INT_MAX is 2147483647, that would be a giant array of 2GB of memory or something. While a normal approach would take 3mb or something. Oct 5, 2016 at 17:34
  • Yes, but only because I don't understand how the hash function works - ideally if I were a better programmer I could scale down the values of the hash function to be far more compact - odds of collision in a 128MB hash table are still pretty low. However, I don't know how to do that
    – borker
    Oct 5, 2016 at 17:43
0

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.

2
  • In previous problem sets, I've been told that space in memory is cheap and that processing time is at a premium, hence storing in an arbitrarily large hash table. Given the bounds on the number of possible words (certainly less than a maximum sized int), I'd go this way. Nonetheless, I'd still like to know how to pass the word in memory to the hash function so I can know where to store it in the first place.
    – borker
    Oct 5, 2016 at 14:29
  • What is the big picture here? This is an assignment for a programming class! The primary goals of this pset are to learn to use linked lists, structures and heap memory by allocating and freeing structures. If you are trying to write the fastest program possible by trading off memory for speed, fine. Any practice with any technique is great, and the more experience the better. BUT are you sacrificing properly learning one or more very important techniques in favor of making a program run faster? Of course, you could to all of the above. ;-)
    – Cliff B
    Oct 5, 2016 at 20:37

You must log in to answer this question.

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