Assignment 6

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Attach the source code to your email. Send me only the source code (.java files); do not include the .class or any other files. Do not zip or otherwise bundle the .java files.

Requirements

As stated on the assignment handout, you must:

• Write a hash table that includes an insert, remove, traverse, and delete method, with certain specifications.

Suggestions

There are a number of different ways to implement this assignment.

Note that your hash table will be storing objects with more than one field. These data items include both a String and a number, and they are equal if they have the same key value. You should write a class to represent this. (Name this class whatever makes sense to you: PhoneEntry, Person, etc.) However, the assignment examples only shows the String part of these objects. In the examples below, I will also pretend we are storing only Strings. You may want to implement the table this way, and then go back, once it works, and convert it to work with the proper data objects.

One option is to make a Bucket class:

public class Bucket {
  String[] items = new String[2];
  boolean overflow = false;
}

In this case, you would make the table (in the HashTable class) like so: Bucket[] table = new Bucket[7];. Note that the overflow area would use a different kind of bucket, however.

Another option is to use a two-dimensional array for the table. If we were storing only Strings in the table, this could be done this way (in the HashTable class):

final int TABLE_SIZE = 7;
String[][] table = new String[TABLE_SIZE][2];

Note that now we need a separate array to record the overflow values for each row/bucket. Also, the overflow area is just a normal array:

boolean[] overflowedBuckets = new boolean[TABLE_SIZE];
String[] overflowArea = new String[TABLE_SIZE];

These are just two possible ways to get started. You may think of another way.

Other hints:

• To index a character from 0, just subtract the character code for 'A':
  String name = "ABE";
int first = name.charAt(0) - 'A'; //first == 0
  (This technique does mean numbers and certain punctuation cannot be part of the string key, or they will produce a negative hash value.)
• Name your traversal method toString() to make your hash table easier to print out.
• Bucket numbers in the overflow area are optional. (The assignment says they "may be added".)
• In the insert method, use retrieve to easily and correctly check for duplicates before inserting.
• Your deletion marker will need to be some kind of object that will go into the array or bucket. You can declare a constant like this:
    final Object DELETED = new String("@");
  To replace an item in the table with a DELETED marker (assuming you went with the 2D array technique), you can do this:
    table[i][j] = DELETED;
  To test whether a cell in the hash table contains a DELETED marker, you can test like this:
    if (table[i][j] == DELETED) { ...
  If you use the identity/equals operator (==), it doesn't matter what you initialize DELETED to contain. With ==, you are checking if the two objects are the same object (at the same place in memory). So, you could declare DELETED like this, and this method would still work:
    final Object DELETED = new Object();
  Doing it the String way just means it prints out nicely without any extra code required.

Extra credit

It will make your life easier when debugging (and mine easier grading) if you have a way to display all the details of the table. For up to +15 points, write a method that displays the hash table exactly as shown on the assignment handout, including: bucket indexes, deleted object flags, overflow flag, and overflow area (including bucket indexes of overflow items, if you use them). (Note that this is a separate method than the specified traversal method.)

Grading:

Out of 100 points:

10 - Compiles

10 - table

Table is constructed as requested: 7 buckets (2 data items each, with associated overflow flag), and a common overflow area of 7 items that uses open addressing.

10 - Hash function

As specified--sum of first two characters (with characters indexed from 0), % the table size.

20 - Insert method

Uses overflow area if appropriate bucket is full. May throw an exception if overflow area is full.

15 - Traversal method

Shows the items (and only the items) in the hash table in their order in the hash table. (See handout for example.)

15 - Delete method

Uses a deletion marker.

10 - Retrieve method

10 - Miscellaneous

• Hash table takes an object (Person, PhoneEntry, etc) that includes both a String key and a number. (4 points)
• Insert checks for duplicates (same key String, regardless of number) before adding. Throws an exception if a duplicate is found. (4 points)
• Include a main method with some basic test code to see if implemented methods work correctly. (2 points)

+15 - Extra credit display method

Should give a complete display, using the same format as the examples on the assignment handout.