Thread: Hash Table resizing question

  1. #1
    Registered User
    Join Date
    Dec 2011

    Hash Table resizing question

    I have an implementation of a hash table, where a table structure stores an array of pointers to linked list nodes. I wish to resize the table after a certain point by creating a new table of a bigger size, then hashing all the elements of the old table to the new table. Lastly I will need to free the old table from memory.
    Each of the linked list nodes contain a pointer to another structure as their data.

    I want to extract the data from each of the nodes and hash them into the new table. When I delete the old table, the new table prints rubbish. Is this because the hashed entries in the old table point to the same location as the entries in the new table? I tried allocating memory to copy the old entries but this doesn't work either, what should I try to do next?


  2. #2
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    CA, USA
    That should be relatively straightforward, but there may be a couple of gotchas.

    Create new array and initialize each to empty list
    For each i from 0 to OldLen-1
        For each node in chain i
            Compute new hash value j using NewSize instead of OldSize
            Link the node into chain j in the new array
    Delete the old array
    Point the hash table at the new array

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hash Table pointer question
    By gibson221 in forum C Programming
    Replies: 4
    Last Post: 10-06-2012, 07:16 AM
  2. Hash table code question
    By Boxknife in forum C Programming
    Replies: 20
    Last Post: 08-13-2008, 05:55 AM
  3. dynamic hash table resizing
    By agentsmith in forum C Programming
    Replies: 1
    Last Post: 01-19-2008, 04:59 PM
  4. Question on free() ing a hash table
    By Overworked_PhD in forum C Programming
    Replies: 3
    Last Post: 10-26-2007, 01:16 PM
  5. quick hash table question
    By Brian in forum C Programming
    Replies: 7
    Last Post: 07-30-2005, 07:22 PM