4 Replies - 6280 Views - Last Post: 03 December 2009 - 10:07 PM Rate Topic: -----

#1 david.bobrowski  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 19-November 09

Hash table, synonym chaining

Posted 02 December 2009 - 04:38 PM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Hash table, synonym chaining

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

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
Was This Post Helpful? 0
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

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 0-9 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...
Was This Post Helpful? 1
  • +
  • -

#4 david.bobrowski  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 19-November 09

Re: Hash table, synonym chaining

Posted 03 December 2009 - 11:50 AM

View PostKYA, 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 0-9 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.
Was This Post Helpful? 0
  • +
  • -

#5 david.bobrowski  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 19-November 09

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!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1