Solution: Hash Tables

Review the solution that implements the addSlow() method in LinearHashTable.

We'll cover the following...

Task

Here is the code that implements the addSlow() method for adding an element x to a LinearHashTable, which simply stores x in the first null array entry it finds.

Solution

The addSlow() method uses linear probing to handle collisions by sequentially checking the next available slot until an empty slot is found.

public class Factory < T > {
  Class < T > t;

  public Class < T > type() { // Return the type associated with this factory
    return t;
  }

  // Constructor - creates a factory for creating objects and 
  // arrays of type t(=T)
  // t0
  public Factory(Class < T > t0) {
    t = t0;
  }

  // Allocate a new array of objects of type T.
  // n the size of the array to allocate
  // @return the array allocated
  @SuppressWarnings({
    "unchecked"
  })
  protected T[] newArray(int n) {
    return (T[]) Array.newInstance(t, n);
  }

  public T newInstance() {
    T x;
    try {
      x = t.getDeclaredConstructor().newInstance();
    } catch (Exception e) {
      x = null;
    }
    return x;
  }
}
Solution code to implement the addSlow() method
...