1,105,208 Community Members

A program involving hash tables

Member Avatar
CSWalls
Newbie Poster
4 posts since Mar 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hi guys!!...

I am just looking for some startup guidance with a program I am supposed to write.. it goes like this ->

A program which compares these three hashing methods: 1) open addressing with linear probing, 2) open addressing with quadratic probing, and 3) separate chaining. Input will come from in.txt. The first line of the file will contain the hash table size (assume < 100); the remaining lines (except the last) each contain one non-negative integer per line (you may assume no duplicate keys, and that the number of keys is ≤ the table size); the last line of the file will be a negative integer (being used as a sentinel). You should initially read those keys into an array; this is because you will be using these keys three times, one for each hashing method.

First, you are to insert the keys, in order that they were read in, into an initially empty hash table, using linear probing to resolve collisions. Upon completing this, the table should be output to out.txt, along with what the average search time would be, to two decimal places. Then, the same thing should be repeated for quadratic probing and separate chaining, starting with an empty hash table in each case. (Note that the average search time is the same as the average insertion time for linear probing and quadratic probing, but not for separate chaining.)

Here is an example input file:

7
15
16
22
17
30
-1

Here is the corresponding output file:

LINEAR PROBING

Address     Key
0           -1
1           15
2           16
3           22
4           17
5           30
6           -1

Average search time: 2.20

QUADRATIC PROBING

Address     Key
0           -1
1           15
2           16
3           17
4           -1
5           22
6           30

Average search time: 1.80

SEPARATE CHAINING

Address     Key
0           -1
1           15 -> 22
2           16 -> 30
3           17
4           -1
5           -1
6           -1

Average search time: 1.40


Note: No ADTs are required for this program.

Thanks for your reponses in advance.. and once again.. I am not asking for you to complete it.. I just wanna know how to go about doing it.. or some start up !deas..

Thanks once again!!

Member Avatar
mike_2000_17
21st Century Viking
4,061 posts since Jul 2010
Reputation Points: 2,244 [?]
Q&As Helped to Solve: 795 [?]
Skill Endorsements: 71 [?]
Moderator
Featured
Sponsor
 
0
 

I personally don't know much at all about hash tables (except for what they are and what they are useful for). But I think this article by Narue is probably a good place to start.

Member Avatar
thekashyap
Practically a Posting Shark
809 posts since Feb 2007
Reputation Points: 193 [?]
Q&As Helped to Solve: 77 [?]
Skill Endorsements: 0 [?]
 
0
 
Member Avatar
CSWalls
Newbie Poster
4 posts since Mar 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Guys that was very helpful!!

Anybody else have more !dea with starting up the code?

Thanks!!

Question Answered as of 3 Years Ago by thekashyap and mike_2000_17
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: