import static java.lang.Math.abs; public class HashTableOpenAddressing extends Dictionary{ private int capacity; // size of the table private int size; // number of elements in the table private int previousPrime; //store prev prime so that it is not calculated again and again in double hashing. private int mode; public static int LINEARPROBING = 1; public static int QUADRATICPROBING = 2; public static int DOUBLEHASHING = 3; private double loadFactor; private Entry[] table; public HashTableOpenAddressing() { this(DOUBLEHASHING, 11, 0.75); // default initial capacity of 10 } public HashTableOpenAddressing(int mode) { this( mode, 11, 0.75); } public HashTableOpenAddressing(int capacity, double loadFactor) { this(DOUBLEHASHING, capacity, loadFactor); } /* TODO: This constructor takes a mode, capacity, loadFactor, and sets those variables + relevant variables according to such. Additionally, it will set up the table according to the capacity. If the mode is DOUBLEHASHING, please calculate the previousPrime and set it. */ public HashTableOpenAddressing(int mode, int capacity, double loadFactor) { } private int previousPrime(int number) { while( true ) { if( isPrime( number ) ) { return number; } number--; } } // TODO: // second hash should be prevPrime - (key % prevPrime)...shouldn't be negative private int hash2(K key) { return 0; } // TODO: gets the next index given the index and the offset. Please take into account the mode. private int getNextIndex(K key, int offset) { return 0; } // TODO: // Put a key, value pair into the table. // If the key already exists/inactive, override it. Else, put it into the table. // Throw a RuntimeException if there is an infinite loops. public void put(K key, V value) { } // TODO: // Retrieves the value of a key in the table. // If there is an infinite loop, throw a RuntimeException. // Return null if not there. public V get(K key) { return null; } // TODO: Searches the table to see if the key exists or not. public boolean containsKey(K key) { return false; } // TODO: // Set the key as inactive if it exists in the table. Return true. // If there is no key, return false. // If there's an infinite loop, throw a RuntimeException. public boolean remove(K key) { return false; } public int size() { return size; } public boolean isEmpty() { return size == 0; } // TODO: // Calculate the absolute hash of the key. Do not overthink this. private int hash(K key) { return 0; } private boolean isPrime(int number) { for( int i = 2; i <= number / 2; i++ ) { if( number % i == 0 ) { return false; } } return true; } private int nextPrime(int number) { while( true ) { if( isPrime( number ) ) { return number; } number++; } } // TODO: // Set the capacity to the nextPrime of the capacity doubled. // Calculate the previousPrime and set up the new table with the old tables' // contents now hashed to the new. private void resize() { } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("{"); int index = 0; for (Entry entry : table) { sb.append(index + ": "); index++; if (entry != null) { sb.append(entry.getKey() + "=" + entry.getValue() + ","); } sb.append(";"); } if (sb.length() > 1) { sb.setLength(sb.length() - 2); } sb.append("}"); return sb.toString(); } private class Entry { private K key; private V value; private boolean isActive; public Entry(K key, V value) { this.key = key; this.value = value; isActive = true; } public K getKey() { return key; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public boolean getActive() { return isActive; } public void setActive(boolean active) { isActive = active; } } public static void main(String []args ) { HashTableOpenAddressing hashTable = new HashTableOpenAddressing<>(QUADRATICPROBING, 10, 1); hashTable.put(2,2); System.out.println(hashTable); for (int i = 0; i < 280; i += 10) { hashTable.put(i, i); hashTable.remove(0); System.out.println(hashTable.get(i)); } } }