Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

Solution: Hash Tables

Explore the implementation of hash tables with a focus on the addSlow() method that uses linear probing to handle collisions. Understand how to check for occupancy, compute hash codes, find empty slots, and manage element insertion and resizing for efficient storage.

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
...