So I am asked to store the key and value in the hash table, what if I want to get the value corresponding to a key and there are two similar keys?? how do I handle this??
say that I have a string "abc" and "cba" ,which both have the key 10.. when I search for key 10 in the hash table in the table I found two similar values... how can I do this without collision handling and using the key that is stored in the table itself??
You can't have a hash table without collision handling of some sort -- how did you get both "abc" and "cba" in the table if they both hash to 10? And then once you answer that, you've answered your own question -- wherever you put it, that's where you go to look for it.
You can't do that without collision handling - the only way to solve it without collision handling is to have a hash-function that completely avoids collisions for the valid range of keys - if the keys are rather arbitrary, that may be difficult to achieve.
If you are storing 7-digit phone numbers, using the WHOLE PHONENUMBER as a hash would of course solve the problem [but not gain much, as the has-table then has to be 9999999 entries long].
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
what if I just append the linked list that stores the (key, value) pair if it ends up being the same key??
That is one common way of solving the problem in fact.Originally Posted by -EquinoX-
QuantumPete
"No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
"Have you tried turning it off and on again?" - The IT Crowd
Append it to what? Do you mean that each of your hashes leads to a linked list? If so, when you're searching, you just walk the linked list until you find what you're looking for.
yes each of my hashes leads to a linked lists.. but say as an example above I have a string "abc" and "bca" in one linked list, how do I know which one is to look for?? because abc and bca have the same key value so therefore it's stored in the same linked list...
how do I know if it's "abc" that I am actually looking for or is it "bca"?? both have same keys.. and that's why they are put in the same linked list.. if all linked list just have one element then it would be easy..because there's no confusion on which to look for
So in that case, your linked list stores both the key and the value.
Inserting is like you described. You hash the key, go to the end of the linked list and then insert the (key, value) pair at the end (not the (hashedkey, value) pair!!!)
When searching, hash the key, iterate through the hash table and check each item's key against your original key. When they match, hey presto! you have your value.
QuantumPete
"No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
"Have you tried turning it off and on again?" - The IT Crowd
so the key is the one that hash unique values??
If you're asking "can I have two pieces of data with the same key", the answer is no. Keys must be unique.
The KEY is your "variable name" in my above example - two variables can't have the same name [in the same scope, and when you have multiple scopes, you have a hash-table per scope-level, if that's how we implement the variables - and search the hash-tables from current scope out].
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
Ok, perhaps we should clean up the terminology. Say you want a hash-table of names->phone numbers. The name is your key, the phone number your data.
You apply the hashing function to the key and you get your hashkey. The keys are all unique, the hashkeys aren't necessarily. That's why you get collisions. You use the hashkey as an index into your hashtable, where you proceed to store the key and value together. The hashkey is only ever used to access the hashtable.
Hope that clears things up a bit.
QuantumPete
"No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
"Have you tried turning it off and on again?" - The IT Crowd
yes I got it now.. thank you!
It doesnt necessarily have to be used as the index into the table, but they are used to speed up searching. The hashkey is generally much smaller that the key. Imagine you had a list of names, say the average name is 20 characters long, thats 160 bytes. So you make a hash of the 160 bytes into a 16 bit hashkey, now you can just compare the 16 bit values with the search parameters to find potential matches, which you can then verify by doing a full comparison of the 160+/- bits of actual data. It gets even more interestign when you have enormous databases (like google) and multi-level hashkeys running in a multiprocessor system. The speed increase can be huge vs physically comparing each database entry.
okay I got it now.. this may be a simple question but is this function doing according to what it's suppose to do? I am just doing this as a helper function for the hash table later on:
Code:/* Create a brand new copy of the given string on the heap */ char* StringConstruct(const char *s) { char* result = (char*) malloc(strlen(s) + 1); strcpy(result, s); return result; }
