There are two subclasses, LinearHashtable and QuadraticHashtable, which need to be implemented to provide the definition of the rehash() method. The rehash() method is used when determining the hash table index. When the initial index, returned by the provided hash() method, represents a space in the array list that is already occupied, a probing strategy is used. The rehash() method takes the previously found index (which represents an occupied space in the array list), and uses it to determine the next index. rehash() will implement these strategies: 1. LinearHashtable the rehash() method will simply add one to the previous index, returning the new value modulus the size of the array list (capacity) This is called linear probing https://en.wikipedia.org/wiki/Linear_probing 2. QuadraticHashtable the rehash() method will square the previous index, returning the new value modulus the size of the array list (capacity) This is a variation of a probing strategy called quadratic probing https://en.wikipedia.org/wiki/Quadratic_probing The insert() method will continuously call rehash() until an unoccupied position has been found, then it will insert to the new value at that position. While performing the probing, use the instance variable probeCount to keep track of how many probes is required for both hash tables.

Hashtable.java:

import java.util.*;

public abstract class Hashtable { protected int capacity = 0; private List keys = null; private List values = null;

private int probeCount = 0;

public int getProbeCount() { return this.probeCount; }

public void resetProbeCount() { this.probeCount = 0; }

public Hashtable(int capacity) { this.keys = new ArrayList(); for (int i = 0; i < capacity; i++) { this.keys.add(null); } this.values = new ArrayList(); for (int i = 0; i < capacity; i++) { this.values.add(null); } this.capacity = capacity; }

public int hash(String key) { int sum = 0; for (int i = 0; i < key.length(); i++) { sum += (int)key.charAt(i); } return sum % capacity; }

public abstract int rehash(int previousHash);

public void insert(String key, T value) { // determine the hash int hash = hash(key); int oldHash = hash; // if the hash is taken, continuously until a free space is found while (keys.get(hash) != null) { hash++; if (hash == capacity) hash = 0; if (hash == oldHash) //This will ensure that if the hashtable is full, it stops searching and notifies the user throw new RuntimeException("Hashtable is full"); } // insert the value at that position values.add(hash, value); } }

HashtableDriver.java:

public class HashtableDriver { private static String characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";

public static String generateRandomString(int length) { StringBuilder result = new StringBuilder(); for (int i = 0; i < length; i++) { int index = (int)(Math.random() * 62.0); result.append(characters.charAt(index)); } return result.toString(); }

public static void main(String[] args) { int size = 10007; // prime number int numValues = 1000; LinearHashtable linearTable = new LinearHashtable<>(size); QuadraticHashtable quadraticTable = new QuadraticHashtable<>(size);

// generate random strings and insert them into both tables for (int i = 0; i < numValues; i++) { String newValue = generateRandomString(25); linearTable.insert(newValue, newValue); quadraticTable.insert(newValue, newValue); }

System.out.println("# probes linear: " + linearTable.getProbeCount()); System.out.println("# probes quadratic: " + quadraticTable.getProbeCount()); } }