A program involving hash tables

[CSWalls]

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

[mike_2000_17]

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.

[thekashyap]

You can start here: http://en.wikipedia.org/wiki/Open_addressing

[CSWalls]

Guys that was very helpful!!

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

Thanks!!