Thread: Resizing hash table

  1. #1
    Registered User
    Join Date
    Apr 2020
    Posts
    30

    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.

  2. #2
    Registered User
    Join Date
    Apr 2021
    Posts
    68
    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.

  3. #3
    Registered User
    Join Date
    Apr 2020
    Posts
    30
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hash Table resizing question
    By gibson221 in forum C Programming
    Replies: 1
    Last Post: 10-22-2012, 02:30 PM
  2. dynamic hash table resizing
    By agentsmith in forum C Programming
    Replies: 1
    Last Post: 01-19-2008, 04:59 PM
  3. Hash Table
    By siavoshkc in forum C++ Programming
    Replies: 4
    Last Post: 08-29-2006, 04:29 PM
  4. What is a Hash Table?
    By rip1968 in forum C++ Programming
    Replies: 3
    Last Post: 06-18-2002, 08:57 PM
  5. Hash table
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 01-14-2002, 07:06 PM

Tags for this Thread