Assignment 4: This Ought to Settle Your Hash

Due by: Friday, October 25, 2024 at 11:59 p.m.

Your mission, should you choose to accept it, is to implement a hash table using the double-hashing approach to open addressing.

Specification

HashTable.java contains an incomplete implementation of a hash table. You are required to implement every method in it. These methods are:

• hash():
  Private helper method that that finds the hash value of a particular String for the current table. First use the hashCode() method on the String to find its hash value. Then, use the trick described in the book to make sure that it's non-negative. Finally, take this value modulus the length of the table and return the result. Note that this approach differs from the mid-square approach used in class.


• step():
  Private helper method that finds the step size used when searching for an unused bucket with the double-hashing approach. Like the previous method, you first call hashCode() on the String and then make the value non-negative. Next take this value modulus 97 and then add 1 to the result and return it.


• nextPrime():
  Private helper method that takes the current length of the table, multiplies it by 2, and then finds the next prime number larger than that value. This method aids the resizing process for the table. The double-hashing scheme we are using depends on having a table whose length is prime.


• isPrime():
  Private helper method that determines if a number is prime. This is a helper method for the previous nextPrime() method.


• containsKey():
  Public method that returns true if the hash table contains the given key and false otherwise.


• put():
  Public method that adds the given key-value pair to the hash table, using a double-hashing approach to handle collisions. This method returns true if the key was not present in the hash table beforehand and false if an update is being done to an existing key. When adding a key, resize the table if the load factor is 0.75 or higher. Use the helper methods above to find the next prime number larger than twice the current table size, and resize the table to that prime number.


• get():
  Public method that finds the value associated with the given key inside the hash table. The value is returned if the key is present in the hash table. Otherwise, this method returns null.

Restrictions

You may not import any classes or packages.

Do not change the method signatures. You can add some if you want, but I doubt it will make things easier.

Hints

Test your code thoroughly. You may wish to use the simple test file HashTest.java to test your program.

Turn In

Upload HashTable.java to Brightspace. Grace days are not available for assignments.

All work must be done individually. You may discuss general concepts with your classmates, but it is never acceptable for you to look at someone else's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Under no circumstances should any student look at the code written by another student. Tools will be used to detect code similarity automatically.

Grading

There are 4 private helper methods and 3 public methods specified in HashTable.java. The private methods are each worth 10% of the grade. The public methods are each worth 20%. Be sure that you put your name, date, course number, and assignment number in comments at the top of your file. Failure to compile will result in a zero for the assignment.