Data structure
Budget: $10 – $30 USD
Based on previous homerworks, you should have a complete implementation of the SkipList
ADT (SkipQLinkList), and a program you wrote to test the speed of the skipSearch() method. In
this assignment you are required to do the following:
1. Design and implement a HashTable class, using a hash function of your own design and
a bucket array with external chaining to resolve collisions. In your implementation, the
class shall provide the following public methods:
a. HashTable (int N, float loadFactor):
Constructs an empty HashTable with a capacity of N entries and the specified load factor.
b. insert (int key):
Adds the specified key into this HashTable; Note that repeated keys are allowed.
c. find (int key):
Returns true if the specified key is found in this HashTable, or false if the key is not found.
d. remove (int key):
Removes one instance of the specified key from this HashTable if present.
e. size ():
Returns the number of keys currently in this HashTable.
2. Use the same test program you used in the previous homework, namely: (a) The
program shall automatically generate up to 50,000 random integer keys in the range [0 –
100,000] in steps of 5,000 each time, and insert them in the SkipList structure; (b) At
each step (i.e. every additional 5000 keys), use the system clock (System.nanoTime()) to
measure the average time it takes to skipSearch() for 10,000 automatically and randomly
generated keys in the same range; (c) Calculate and report to a file, the average search
time (t) versus the size of the list (n).
Note: The output file should have a pair of values {n<single-space>t} in every line.
3. Design HashTable parameters, N and loadFactor to suite the same data as above, then use
the same program you used in step 2, to test the speed of the find() method used in the
HashTable class in exactly the same way described in step (2) above, and then report the
new average search time results to another file, using the same format.
4. Use gnuplot to plot the two output files that came out from the two experiments above –
both files in one plot, showing two curves.
What to turn in:
1. The full listing of your HashTable class, in step (1), fully documented and commented.
2. Only the changed parts of your test program from step (3).
3. Your designed HashTable parameters, N and loadFactor; explaining your choices.
4. The reported results from the tests, the two output files and your plotted curves.
5. A one-page report discussing the effect of the HashTable parameters on its search
performance, and commenting on your findings.
6. Submit only one .zip file containing all the above.
IMPORTANT#
All SkipList work is already been done and files are attached need you to do all hash related tasks and comparison.
ADT (SkipQLinkList), and a program you wrote to test the speed of the skipSearch() method. In
this assignment you are required to do the following:
1. Design and implement a HashTable class, using a hash function of your own design and
a bucket array with external chaining to resolve collisions. In your implementation, the
class shall provide the following public methods:
a. HashTable (int N, float loadFactor):
Constructs an empty HashTable with a capacity of N entries and the specified load factor.
b. insert (int key):
Adds the specified key into this HashTable; Note that repeated keys are allowed.
c. find (int key):
Returns true if the specified key is found in this HashTable, or false if the key is not found.
d. remove (int key):
Removes one instance of the specified key from this HashTable if present.
e. size ():
Returns the number of keys currently in this HashTable.
2. Use the same test program you used in the previous homework, namely: (a) The
program shall automatically generate up to 50,000 random integer keys in the range [0 –
100,000] in steps of 5,000 each time, and insert them in the SkipList structure; (b) At
each step (i.e. every additional 5000 keys), use the system clock (System.nanoTime()) to
measure the average time it takes to skipSearch() for 10,000 automatically and randomly
generated keys in the same range; (c) Calculate and report to a file, the average search
time (t) versus the size of the list (n).
Note: The output file should have a pair of values {n<single-space>t} in every line.
3. Design HashTable parameters, N and loadFactor to suite the same data as above, then use
the same program you used in step 2, to test the speed of the find() method used in the
HashTable class in exactly the same way described in step (2) above, and then report the
new average search time results to another file, using the same format.
4. Use gnuplot to plot the two output files that came out from the two experiments above –
both files in one plot, showing two curves.
What to turn in:
1. The full listing of your HashTable class, in step (1), fully documented and commented.
2. Only the changed parts of your test program from step (3).
3. Your designed HashTable parameters, N and loadFactor; explaining your choices.
4. The reported results from the tests, the two output files and your plotted curves.
5. A one-page report discussing the effect of the HashTable parameters on its search
performance, and commenting on your findings.
6. Submit only one .zip file containing all the above.
IMPORTANT#
All SkipList work is already been done and files are attached need you to do all hash related tasks and comparison.