McMaster University Dept. Electrical and Comp. Engineering

COE 2SI4 - Term II (Winter) 2018

Lab 4 - Hash Tables with Linear Probing

Due Date: Assessment:

Lab Sessions March 12 23, 2018 5% of the total course mark.

Description:

In this lab you will implement a hash table with linear probing and perform simulations to observe its performance. The hash table will store integers. The hash function to be used is h(x) = x%M (the remainder after dividing x by M), where M is the size of the hash table. The set of possible keys x is the set of positive integers representable by the int data type. You must write a Java class HashTableLin and a class TestHashTable for testing and for measuring its performance.

Specifications:

Class HashTableLin must contain a eld named table, of type Integer[], which is a reference to the array which stores the keys. There must be other elds to store the size of the table, the number of keys stored in the table and the maximum load factor allowed. All elds must be private. Pay attention to update these elds when performing hash table operations (when necessary).

Class HashTableLin must contain at least the following constructor

public HashTableLin(int maxNum, double load) - creates a HashTableLin object representing an empty hash table with maximum allowed load factor equal to load. The amount of memory allocated for the hash table should be large enough so that maxNum keys could be stored without its load factor exceeding the value of parameter load. The size of the table should be the smallest prime number such that the above requirement to be met. For instance, if maxNum=5 and load=0.4, then the size of the table should be at least 5/0.4 = 12.5. The smallest prime number satisfying the requirement is 13.

Class HashTableLin must contain at least the following public methods:

1) public void insert(int n): Inserts the key n in this hash table if the key is not already there. If the insertion will cause the load factor to exceed the maximum limit prescribed for this table, then rehashing should be performed by invoking the method rehash().

2) private void rehash(): Allocates a bigger table of size equal to the smallest prime number at least twice larger than the old size. Then all keys from the old table are hashed into the bigger table with the appropriate hash function and with linear probing.

3) public boolean isIn(int n): Returns true if key n is in this hash table.

It returns false otherwise.

4) public void printKeys(): Prints all keys stored in this table, in no particular order.

4) public void printKeysAndIndexes(): Prints all keys stored in this table and the array index were each key is stored, in increasing order of array indexes.

1 of 3 McMaster University Dept. Electrical and Comp. Engineering

COE 2SI4 - Term II (Winter) 2018

The purpose of this method is mainly to be invoked in your test class for verifying that insertions are correct.

6) Accessor public methods (get methods) to allow the user to see the values of the elds relevant to the table (max load factor, number of keys, etc.)

The test class has to be designed to carefully check that all specications are met. For instance, you need to verify, among other things, that rehashing is performed when needed, that the size of the table is a prime number and it is selected as specied, that no duplicates appear in the table, etc. During testing instructive messages should be printed to clarify what is tested (i.e., your method performing the tests should print such messages). You may write additional methods in your HashTableLin class to aid in testing, if necessary.

Additionally, the test class must contain a static method to perform simulations to measure the average number of probes for successful search. For each (0, 1), S denotes the average number of probes for successful search in a table with load factor and size approaching . Note that the number of probes to nd a key which is in the table is the same as the number of probes performed when the key was inserted. Thus the average number of probes for a successful search in a particular table can be determined by computing the average number of probes needed when the elements were inserted (by adding all numbers of probes and dividing by the number of elements in the table). You need to perform this measurement for load factors = 0.1, 0.2, , 0.9, and output the results. For each load factor allocate a hash table, insert at least 100, 000 randomly generated numbers and compute the average number of probes needed. Repeat the test 100 times for a good average (i.e., have a loop with 100 iterations and then average again over all iterations). In order to perform the test ensure that the initial hash table size is large enough so that no rehashing is needed, and after all 100, 000 keys are inserted the load factor is the required (to do this, when creating the test object pass the number of tests, i.e., 100, 000, and to the constructor). Note that the random number generator may create duplicates, and duplicates should not be inserted, so make sure that you properly count the number of inserted keys. In order to count the number of probes performed during an insertion (i.e., the number of table slots that are examined, including the one where the key is inserted), write another public method in class HashTableLin called public int insert(int n) which inserts and returns the number of probes required. The method which performs the measurements should also output the theoretical values of S for linear probing, for comparison. Note that the theoretical values are given by 1 1 S 1+ . = 2 1

You should compute the run time and space complexity of all methods written and be prepared to justify them to the TA.

2 of 3 McMaster University Dept. Electrical and Comp. Engineering

COE 2SI4 - Term II (Winter) 2018

Notes:

To get credit for the lab you have to demonstrate your code in front of a TA during your lab session. A 50% penalty will be applied for late demo. A 25% penalty will be applied if the demo is on time, but the electronic submission is late.

Submission Instructions:

NO REPORT IS NEEDED. Submit the source code for each of the classes HashTableLin and TestHashTable in a separate text le. Include your student number in the name of each le. For instance, if your student number is 12345 then the les should be named as follows: HashTableLin12345.txt, TestHashTable12345.txt, etc. Submit the les in the Assignments Box on Avenue by the end of your designated lab session.

Bonus:

A bonus of 0.5% of the course mark will be awarded if the test class also contains a method to measure the average number of probes for unsuccessful search U , for each = 0.1, 0.2, , 0.9. Each average should be computed over at least 100, 000 searches (for randomly generated numbers) in a table with at least 100, 000 keys randomly generated. Make sure that you only count the unsuccessful searches (i.e., when the key is not in the table). Your method should also output the theoretical value of each U for linear probing, given by 1 1 U = 1 + 2 .

2 (1 )

3 of 3