DO TODO please 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; } // ------------------------------------------------------- // to insert, we enter a loop (helper recursive function // actually). We calculate the hash of the key giving us // the position where we should store the item in the // case of no collisions. We also start a counter of // collisions initialized to 0. void insert(K key, V value) { insert(key, value, hash(key), 0); } // this is the general case of an insertion after // some given number of collisions: // - first thing calculate the index 'h' at which we // will attempt to store (use nextHash) // - if slot 'h' is not empty, make a recursive // call incrementing the number of collisions // - otherwise, store the current key and value // in the hashtable at index 'h' // - do not forget to increment size and to // remove 'h' from the collection of deleted // indices // - after a successful insertion add the following // if (size > capacity / 2) rehash(); // this will force the array to grow as soon as // it is half full void insert(K key, V value, int index, int collision) { // TODO }