Assignment

1. The main goal of this assignment is to create and exercise a hash table of college students. The key is the student ID (an object of the ID class) and the value is an object of the Student class.

2. Use the following classes: Student, ID, StudentTable, Application

3. The ID object represents a pair of two 10-digit integers, each integer will be randomly selected between 0 and 2,000,000,000. The reason for the random selection is that we will have to issue IDs for a large number of students (up to 1,000,000) and using a pair of 10 digit numbers allow us reasonably assume that different students will have different IDs.

4. The ID class has two instance fields to store the first and the second element of the pair. The no-arg constructor randomly initializes the fields. The class has an equals( ) method to compare ID objects for equality of their respective fields.

5. The Student class has two instance fields for a name and an ID of the Student object. The constructor takes a String parameter to initialize name, and calls the ID class constructor to initialize the ID field. The Student class must have an equals( ) method as well, such that Student objects can be compared.

6. The StudentTable class implements a hash table as described in your reading (see pp 584 - 594). The elements are Student objects, the keys are ID objects.

7. Note that the put( ) method you have in this project shall take only an ‘element' for parameter, no ‘key'. When a Student object is instantiated it gets its key as its ID field. Thus you can retrieve the key by using an accessor method.

8. The StudentTable constructor takes a parameter for the size of the table, and instantiates all the three array fields (keys, data, hasBeenUsed) to that size.

9. The Application class tests and drives your program.

10. In the main method instantiate a StudentTable with size 30000. Use open address hashing to populate the arrays with 15000 students (load factor ½).

11. For measuring the performance of linear probing add a fourth array to your table class named experiment. The length is the table length but it is not part of the data structure. Set up a counter variable such that every time a new Student is added to the table, the counter keeps track of the number of iterations the while loop has to make in the put method. When the search is done, store the counting result in the next entry of the experiment array. After the loading procedure compute the average of the array elements. Repeat the entire loading procedure this time to reach load factor 0.85. Compare the averages and comment on your experience. Note: you do not really need the extra array experiment. You may accumulate the sum total of the probing in a single variable, and compute the average at the end. Moreover, you can compute the average on the run, updating average at every call of put.

12. You will need names supplied to the constructor, therefore you need a name generator method in the Application class. Add the method randomName( ) to the class. The method takes an int parameter for the length of the names (use 7). Every call of the method produces a random name such that the first character is a capital letter randomly chosen, the other characters are alternately random vowels and random consonants. A short sample list of 49 such names are shown below:

Yupoyes, Rijaboq, Hipocun, Quvaxim, Uopexod, Facujeq, Vohiyip, Lipeyib, Bezolul, Cefukon, Cemapen, Risisay, Dijewuk, Bepetoz, Kojimoy, Eaxikar, Xihahef, Uimojuq, Metuver, Hepejah, Yawihuk, Xocasal, Bulekiw, Eejuvas, Fapasaj, Gulobok, Uupinof, Fajonum Vuyinor, Lopoyas, Qotiqab, Reduder, Iixelup, Hemepuk, Penilir Piyivaw, Uajaqub, Xugoruq, Yirediy, Zudakup, Xavamow, Ramedaz Aeriwov, Huqurer, Wifaguf, Qahuloj, Jojewiy, Qomanev, Iipunap

13. In the testing phase check if the ID numbers are created correct.

14. To display the table, find the first 50 non-null Students in the table and print their names and the corresponding array indexes to the console. 15. As non-mandatory experiments you may want to try and test other hash method(s) and larger tables with larger load factors, as well.