Please do the "TOD0" in function "delete" import java.math.BigInteger; import java.util.*; import java.util.function.Function; // ------------------------------------------------------- class NotFoundE extends Exception {} // ------------------------------------------------------- abstract class HashTable { // the current capacity of the underlying array private int capacity; // the number of elements currently stored in the hashtable private int size; // the underlying array: each index of the array is either // Optional.empty(), or // Optional.of(new AbstractMap.SimpleImmutableEntry<>(key, value)) private ArrayList>> slots; // collects the indices of deleted items private HashSet deleted; // a function defined in subclasses that determines // the next offset in case of collisions: // we will only define linear and quadratic probing private Function offset; HashTable() { this.capacity = 17; this.size = 0; this.slots = new ArrayList<>(capacity); for (int i = 0; i < capacity; i++) this.slots.add(i, Optional.empty()); deleted = new HashSet<>(); } // called from subclasses void setOffset(Function offset) { this.offset = offset; } // Getters for debugging int getCapacity() { return capacity; } int getSize() { return size; } ArrayList>> getSlots() { return slots; } HashSet getDeleted() { return deleted; } // use Java hashcode (wrapping around to make sure the index // remains in bound int hash(K key) { return key.hashCode() % capacity; } // in case of collisions we add to the current index the // offset calculated by the given function (linear // or quadratic); and of course we wrap around to make // sure we stay in bounds int nextHash(int index, int collision) { return (index + offset.apply(collision)) % capacity; }

-----------------------------------------------------------------------------------------

// like the case for insert, we enter a loop // keeping track of the number of collisions void delete(K key) throws NotFoundE { delete(key, hash(key), 0); } // This is the general case for deleting an item after // a number of collisions. There are several scenarios // to keep track of: // - if the number of collisions = capacity, the item // is not present; throw an exception // Challenge: write a test case that forces this // exception to be thrown // - calculate the index 'h' we will focus on nextHash // - if the collection of deleted items contains 'h' // skip this iteration and make a recursive call // after incrementing the number of collisions // - if slot 'h' is empty, the item is not present; // throw an exception // - if slot 'h' contains some key that is different // from the key we are looking for, skip this // iteration and make a recursive call after // incrementing the number of collisions // - otherwise, set slot 'h' to empty, decrement size, // and add 'h' to the collection of deleted indices void delete(K key, int index, int collision) throws NotFoundE { // TODO }