Lab Assignment 27 (Hashing)

1.Write a program named Lab27A that will make a hash table of customer names and customer ID numbers. The customer ID number (integer) will be the key for each entry.

a.Create a class named Customer that will have

i.Two instance variables: the customer ID (int) and the customer name (String)

ii.A constructor that receives an int and a String parameter and fills in both instance variables.

iii.A void method to return the customer ID

iv.A toString method to print both variables (with labels as always)

b.Back in the main class, do the following:

i.Write an int method that receives an int parameter (the customer ID) and returns the result of performing the hash function on the parameter.

The hash function separates the key into digits and adds the digits together. If that sum has more than one digit, then the digits of the sum are added together. This will be repeated until the final result is only one digit long (hint: it must be < 10).

Example: hash(83945) = 8 + 3 + 9 + 4 + 5 = 29

But 29 has 2 digits so we do it again ? 2 + 9 = 11

11 still has 2 digits, so we do it one more time ? 1 + 1 = 2

Thus, hash(83045) = 2

ii.In the main method:

1.Create an array of 10 Customer objects.

2.Read the customer ID’s and names in from the text file (Lab27A.txt). (You don’t know how many customers there will be, but it will be < 10). For each one:

a. Calculate the hash code by sending the customer ID to your hashing function method

b.Write the customer’s name and hash function result

c.Create a Customer object

d.Add the object to your hash table array at the index returned by your hash function method. If there is a collision, then keep moving forward one array location at a time until you find an empty one (linear probing). Place the object there.

If you get to the end of the array, go back up to index 0 again.

3.After all customers have been added to the hash table, print the hash table array. (Don’t print the nulls, though.) Print the index number before each customer object’s info.
(You’ll probably need to write a for loop for this instead of using Arrays.toString.)

Hint: To check if an array named arr has an object at location i, you would write:

if (arr[i] != null)

2.Write a program named Lab27B where you will create a hash table of “gadgets” using a different hash function and quadratic probing.

a.Create a class named Gadget that you will make objects of. It should have the following:

i.Two instance variables: the gadget ID (int) and the gadget name (String)

ii.A constructor that receives an int and a String parameter and fills in both instance variables.

iii.A void method to return the gadget ID

iv.A toString method to print both variables (with labels)

b.In your main class do the same things you did for Lab27A, but with following changes.

i.The hash table array should have a length of 20.

ii.Read the data from Lab27B.txt

iii.The hash function will be key % 20

iv.You should use quadratic probing to find a new location for an entry if a collision occurs.