CSC1020 Homework 11

Overview

Using the provided implementation of a Hashtable that uses Open Addressing with Linear Probing, implement the following methods:

public V remove(Object key)

Removes the entry in the Hashtable with the given key, returning the value of that entry.

public int size()

Returns the size of the Hashtable

public String toString()

Returns a String representation of the Hashtable.You should use a StringBuilder object to assemble the String and write the Entry class’s toString() method to assist with this. Remember to be careful with null values.

private int find(Object key)

This method was mostly implemented in class, but you will add functionality so that it keeps track of the number of times probing is used in the Hashtable. Each probe should count as 1, so every time you attempt to add to an index and cannot, that should count as a probe. Additional instance variables many be needed.

public double averageProbes()

Calculates and returns the average number of probes per call to the find method.

Analysis

Please answer the following questions and submit them with your code in a text document called HW11.txt

  1. What does the hashcode() method of the Integer class return? How does it determine that value?
  2. Why do we take the modulus of the hashcode by the capacity of the table before placement?
  3. What is the LOAD_THRESHOLD constant used for?
  4. When running the HashMapTester’s fillTable() method:
    1. Which keys encountered collisions (existing values that forced probing to occur) when being added to the table? List them and how many collisions they encountered before being added to the table.
    2. How many total collisions were encountered when building the table?
    3. How many times was the find() method called? Was it more or less than the capacity of the table? Explain why this is the case.