I have searched the web on this and asked my TAs and I haven’t received a very solid answer. I am testing different data structures on performance for inserting and searching for data. One of the data structures I am testing is a hash table.
I understand that dynamically allocating memory is beneficial If you don’t know the end size of the array and want to implement array double for any number of reasons. But say we know the amount of data. In this case 40,000 integer values. Do I need to dynamically allocate an array on the heap or can I get the same functionality and use from instantiating statically with the stack? I would do everything the same, create my header file, my implementation file, and main() but not dynamically allocate memory.
If you know the maximum (or fixed) size that your hash table will be, you can very much statically allocate it.
The main reason for dynamic allocation is to vary the size at runtime and to be able to pass ownership of the structure from function to function. For example (and this is not tied to hash tables at all so I'll just use a generic structure):
Item *GetItem() {
return new Item();
}
That dynamically allocates the item and passes it back to the caller (along with the ownership (responsibility for managing its lifetime)). A naive way of avoiding dynamic allocation would be:
Item *GetItem() {
Item item;
return &item;
}
Unfortunately, that address is unusable on return since item has gone out of scope at that point, so you could stop that from happening with:
Item *GetItem() {
static Item item;
return &item;
}
That preserves the object even after return from the function but has the restriction that only one copy of it ever exists. If you try to get two items from that function, they'll be the same one, and you may have bugs unless you realise that.
So, I would say that, provided you only need one hash table, you can avoid dynamic memory allocation simply by having a static copy of it.
Of course, aside from the single copy restriction, that also has the downside of requiring you to allocate the maximum space needed. That's not necessarily a bad idea (especially if it's fixed size) but it may cause inefficiencies.
In any case, you may be worrying about performance unnecessarily. You can just as easily dynamically allocate the structure in its maximum/fixed size up front (rather than doing lots of small allocations and de-allocations). Since that only really happens once per hash table (with hopefully a lot of use of the hash table before deallocating), the cost will be be relatively minor.
And it gives you back the ability to have more than one hash table in the program.