This question relates to the final part of an assignment requiring several storage / search techniques. The final method I am to use is hash table chaining. I know how hash tables operate and how to store and search on them. I do need some help though at least shoving me in the right direction for chaining. I have two arrays (successful and unsuccessful) and I search for each element of successful array in a master array. Can anyone provide some possible approach advice, solid sources to help me, or some code that will at least jump start me?
For some reason I can't wrap my head around this one. I know I need to initialize the chain hash table to null, and I need to work with pointers for each chained location but am having trouble visualizing this code wise.
Any help, suggestions or feedback would be appreciated... again, just looking for a jump start in the right direction here, not a solution.
Hash table, synonym chaining
Page 1 of 14 Replies  6874 Views  Last Post: 03 December 2009  10:07 PM
Replies To: Hash table, synonym chaining
#2
Re: Hash table, synonym chaining
Posted 02 December 2009  07:19 PM
I don't know much about hash tables and chaining but I would try using a linked list with hash tables as separate nodes in the linked list.
Here is a linked list walkthrough if you don't understand how they work:
http://www.dreaminco...?showentry=1822
Here is a linked list walkthrough if you don't understand how they work:
http://www.dreaminco...?showentry=1822
#3
Re: Hash table, synonym chaining
Posted 03 December 2009  09:57 AM
A hash table by means of separate chaining? It means that for each possible hash value, there is a linked list. So instead of a collision, you just append that value into the list for that hash value.
For example, if your hash was number mod 10 (it's simple and crappy, but just for illustrative purposes), you would have quite a bit of collision since mod 10 only gives 09 as choices based on remainders. So for each index you have a linked list.
The above is very rough, as I would most likely use an STL container for the actual hash values/buckets, etc...
For example, if your hash was number mod 10 (it's simple and crappy, but just for illustrative purposes), you would have quite a bit of collision since mod 10 only gives 09 as choices based on remainders. So for each index you have a linked list.
//pseudo for(int i = 0; i < someLimit;i++){ hashValue = i mod 10; hashtable[hashValue].append(i); //so on and so forth }
The above is very rough, as I would most likely use an STL container for the actual hash values/buckets, etc...
#4
Re: Hash table, synonym chaining
Posted 03 December 2009  11:50 AM
KYA, on 3 Dec, 2009  08:57 AM, said:
A hash table by means of separate chaining? It means that for each possible hash value, there is a linked list. So instead of a collision, you just append that value into the list for that hash value.
For example, if your hash was number mod 10 (it's simple and crappy, but just for illustrative purposes), you would have quite a bit of collision since mod 10 only gives 09 as choices based on remainders. So for each index you have a linked list.
The above is very rough, as I would most likely use an STL container for the actual hash values/buckets, etc...
For example, if your hash was number mod 10 (it's simple and crappy, but just for illustrative purposes), you would have quite a bit of collision since mod 10 only gives 09 as choices based on remainders. So for each index you have a linked list.
//pseudo for(int i = 0; i < someLimit;i++){ hashValue = i mod 10; hashtable[hashValue].append(i); //so on and so forth }
The above is very rough, as I would most likely use an STL container for the actual hash values/buckets, etc...
This seems helpful. I will be working on this tonight. the .append(i) will handle adding each collision node? As you can tell, I haven't worked much with linked lists Thanks for the post.
#5
Re: Hash table, synonym chaining
Posted 03 December 2009  10:07 PM
KYA, this post combined with the linked list guide you put up really helped me with this problem.
Seeing a test program run and stepping through the code helped me understand linked list structures a lot better.
Thanks again KYA, you are one helpful member!
Seeing a test program run and stepping through the code helped me understand linked list structures a lot better.
Thanks again KYA, you are one helpful member!
Page 1 of 1
