Thread: Dynamic Hash Table Implementation

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    21

    Dynamic Hash Table Implementation

    Hi all,

    I'm working on a hash table that expands in size dynamically as it fills up. Basically when the existing table is a certain percentage (say 90%) full i want to double it in size. I propose to use a pointer to my struct (list struct for chaining) and then allocating memory e.g. realloc(table_size*sizeof(struct)). The only problem with this is that my hash function will rely on the table size so changing the table size will change the hash values, rendering data in the table 'unreachable'.

    Can anyone recommend a solution to this - the only thing I can think to do is build a completely new table each time it is resized which is obviously inefficient.

    Thanks,
    James

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    Rebuilding the hash table on a resize is the easiest way. If this creates too many performance problems for you, then read up on Linear Hashing.
    bit∙hub [bit-huhb] n. A source and destination for information.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help understanding Hash Table
    By boblettoj99 in forum C Programming
    Replies: 3
    Last Post: 12-29-2009, 01:23 PM
  2. dynamic hash table resizing
    By agentsmith in forum C Programming
    Replies: 1
    Last Post: 01-19-2008, 04:59 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash Table implementation
    By supaben34 in forum C++ Programming
    Replies: 6
    Last Post: 09-26-2003, 12:48 PM
  5. hash table data structure implementation
    By sanju in forum C Programming
    Replies: 1
    Last Post: 09-27-2002, 05:06 AM