Lab 5: Hash Collisions

Due Date and Submission Requirements

The goal of this lab is:

In this lab, you are given some Hash Table code (very similar to what we wrote in class). The Hash Table is storing Integers (not ints). You will need to write code that will implement linear probing when dealing with hash collisions. That is, when a collision happens, the program will check sequential spots in the array and look for an empty spot. When an empty spot is found, the value is placed at that index.

Directions

Download Lab5Demo.Java and HashTable.Java as a starting point. You cannot modify the demo class, but you are allowed to make additional modifications to the HashTable class. You are NOT allowed to use HashMaps or HashSets (we are writing our own hash table just like we did in class). The Hash Table constructor accepts the length of the array as an argument, and the hash method does basic modular hashing by the table size.

You will also be keeping track of the amount of collisions happening at each array index. This is represented through a String array called collisions. Index 0 of this array represents the amount of collisions that occured at index 0 of the hash table array, index 1 of this array represents the amount of collisions that occured at index 1 of the hash table array, and so on. Every time a collision happens, either during the initial insertion or during the linear probing process, a star (*) needs to get added to the correct indext of collisions.

Your task for this lab is to implement the following methods.

1. public void insert(int newValue)- this method will insert a value into the hash table. If a collision occurs, then it must be placed in the next empty sequential array spot (linear probing). For example, if there is a collision at index 47, it should check index 48 next, then 49, 0, 1, 2, etc until an open spot is found, or if there are not array spots available. In the given code, you won't have to worry about overfilling the array, so you don't need logic for having a full hash table.

2. public void printHashTable()- this methods prints out each spot in the array line by line (see sample output). Because this is an Integer[] array, null values will be at the empty spots. null should not be printed out.

3. public void insertRandomValues(int n)- this method inserts n random values (between 0 and 1000) into the hash table. This method should not require a lot of code, because you should be able to call the insert() method you did earlier.

4. public void printCollisionTable()- This method prints out the collisions table, where the amount of stars represents the number of collisions at that index.

For example:

3: ****

means that 4 collisions occured at index 3 during the lifespan of this hash table.

5. public int get(int value)- this method returns the index of where a particular element (value) is located at in the hash table. If a value is not located anywhere in the hash table, -1 should be returned. If the hash function does not take you to a match, then the value you are looking for got placed elsewhere during the linear probing process, so you will need to find it. It's possible (but unlikely) that there are duplicate values in the hash table. This method should just return the first occurance it finds if there are duplicate values.

Starting Code

Required Output

The output of your program should look similar to this output. The first printout of the hash table should exactly match, but after that your output will look slightly different due having random values. The output for the two get() method calls should look the same.

Grading (10 points)

NOTE: If your code does not compile, correctness cannot be verified, and you won�t receive any points for your code. Turn in code that compiles!

Deductions
  • -10 points if you use a Hash Map
  • -10 points if you use a Hash Set
  • -10 points if you use a Linked List
  • -10 points if you use an ArrayList
  • yes these deducations can stack