Thread: hash table in C

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    569

    hash table in C

    can someone help me to implement a hash table in C?? is it just basically using struct?

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    thanks for the info.. I have another question though, is there a way to implement a hash table without using a linked list? what options is that?

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Yes there is.

    Suppose you have an array of buckets. Each bucket holds one entry.

    If you go to put an item into the bucket at index 'i' and a collision occurs, you simply put it in bucket 'i+1'. If another collision occurs, you put it in bucket 'i+2'... and so on. If you reach the end of the array you wrap around.

    Finding an item in the hash table would work the same way. If you reach an empty bucket at any point, or you wrap around to where you started searching at, then the item isn't in the table.

    There are other slightly better strategies for handling collisions this way, but I wanted to keep it simple.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    okay so to create a hash table in C, I need to create a hash function?? and is this hash function necessary? if I use the buckets example then accessing the value of the hash table using the key won't be a O(1) process because we will have to iterate over all the "buckets"....

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    A hash function IS necessary, although it doesn't have to be complicated.

    The performance of your hash table depends entirely on how uniformly the hash function distributes your keys to the buckets. Even using the 'next bucket' collision handling, you can still achieve an insertion time of O(1) for a given input set. By the same token, a linked list hash table can perform insertions/removals in O(n) time given a poor hash function or a pathological input set.

    (Insertions can take O(n) if you need to check for duplicate keys)
    Last edited by arpsmack; 03-25-2008 at 09:12 PM. Reason: Had to re-type and clarify things

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    so what are some simple hash functions that I can use?? and I just learned about struct, so I should use struct to do this.. so do I have to create some kind of struct which has a key and a value inside?

  8. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Hah I can't just make all the decisions for you or I'D be writing the hash table. How you implement it is up to you.

    Google turns up lots of results for simple hash tables.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 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 creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM