HashTable help?

This is a discussion on HashTable help? within the C Programming forums, part of the General Programming Boards category; So I am asked to store the key and value in the hash table, what if I want to get ...

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

    HashTable help?

    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??

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    what if I just append the linked list that stores the (key, value) pair if it ends up being the same key??

  5. #5
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by -EquinoX- View Post
    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.

    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

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by -EquinoX- View Post
    what if I just append the linked list that stores the (key, value) pair if it ends up being the same key??
    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.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    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

  8. #8
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by -EquinoX- View Post
    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

  9. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    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 09:30 AM.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by -EquinoX- View Post
    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
    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.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  12. #12
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    so the key is the one that hash unique values??

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by -EquinoX- View Post
    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.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by -EquinoX- View Post
    so the key is the one that hash unique values??
    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.

  15. #15
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    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;
    }

Page 1 of 5 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hashtable v.s. Dictionary
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 06-06-2008, 03:09 AM
  2. Missing Entries in Hashtable
    By wuzzo87 in forum C Programming
    Replies: 3
    Last Post: 05-13-2007, 01:46 AM
  3. Replies: 12
    Last Post: 10-22-2006, 09:37 PM
  4. game hashtable
    By disks86 in forum C++ Programming
    Replies: 1
    Last Post: 12-16-2005, 01:42 PM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 12:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21