Thread: Resizing hash table

Hi,

As the title, my questions is about hash table. I implemented all functions to be used in open addressing - quadratic probing. I created the hash table with initial size entered by me, and then when the table is 80% full, I do rehashing. And, it works fine. But, I'm thinking of something that when I delete some elements and there are no need for bigger size, how can I resize the hash table to the previous size?

For example, the current size is 23, and the number of elements is 8, I think 10 is enough. Or should I take the first prime number after 8? I think this works fine. And, I'm asking for guidance in this case.

I would be wary of trying to down-size a hash table. First, because I'm not sure when you would need it: would it be easier to wait and destroy the whole thing?

Second, because if you shrink it, then need to re-inflate it, are you going to create memory fragmentation? If this is for an embedded project, you need to worry about this. (For desktop projects, of course, everything resets when the program exits.)

That said, you could take two approaches: if you have code that really does grow/shrink a hash table, then put in some monitoring that tracks when the table starts to grow or shrink. Define 3 consecutive adds in a row as growing, and 3 deletes in a row as shrinking, or something. Then print out the sizes where the grow/shink occurred.

Or, you could assign an arbitrary percentage, like you did with 80. The complement seems like 20? So when you reach 20% full, you shrink the table. As for the new target size, try to reverse the computation that you use to grow the table. So if you double the size to grow, then cut it in half to shrink. Make your operations symmetrical as much as you can. Once you get it working you can test it, and see if a "better" idea strikes you.

First of all, thank you for helping. I'm working on a university course project and we don't take memory fragmentation in consideration.

What I did that when I do insertion I check if count == 0.8 ht size, it works as it should. But, when I delete an element I made a reindexing function in case to return handled collision elements to their original indexes, even though while reindexing I firstly check if count == (ht size)/2, if yes, I create new array its size is the first prime number after count. I think it works good.