can someone help me to implement a hash table in C?? is it just basically using struct?
Printable View
can someone help me to implement a hash table in C?? is it just basically using struct?
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?
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.
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"....
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)
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?
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.