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
oh I think I am in a confusion between the key and the hashed key here.. so the key is not a the value we get from the hashing?? if not where do we get it?
is the key specified by the user and then we do hashing on the key to get the value where it is stored in the table??
correct me if I am wrong
Last edited by -EquinoX-; 03-28-2008 at 08:30 AM.
That's right: the key is, in your case, the string, and you should store the key and its associated value (not the hash, but your piece of data) in your list.
In most hash-tables, you have three things:
a key
a hashed value from the key
some data.
Let's say we implement "variables" in a language, the "key" is the variable name, the "data" is the value of the variable [e.g. an integer]. To find the variable, we has the variable name, and using our collision management to find search for the variable of that name. Hopefully, this linked list is short.
--
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.
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.
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; }
