public class LinearProbingHashST { private static final int INIT_CAPACITY = 4;

private int n; // number of key-value pairs in the symbol table private int m; // size of linear probing table private Key[] keys; // the keys private Value[] vals; // the values

/** * Initializes an empty symbol table. */ public LinearProbingHashST() { this(INIT_CAPACITY); }

/** * Initializes an empty symbol table with the specified initial capacity. * * @param capacity the initial capacity */ public LinearProbingHashST(int capacity) { m = capacity; n = 0; keys = (Key[]) new Object[m]; vals = (Value[]) new Object[m]; }

/** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; }

/** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; }

/** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; }

// hash function for keys - returns value between 0 and M-1 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % m; }

// resizes the hash table to the given capacity by re-hashing all of the keys private void resize(int capacity) { LinearProbingHashST temp = new LinearProbingHashST(capacity); for (int i = 0; i

/** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null");

if (val == null) { delete(key); return; }

// double table size if 50% full if (n >= m/2) resize(2*m);

int i; for (i = hash(key); keys[i] != null; i = (i + 1) % m) { if (keys[i].equals(key)) { vals[i] = val; return; } } keys[i] = key; vals[i] = val; n++; }

/** * Returns the value associated with the specified key. * @param key the key * @return the value associated with {@code key}; * {@code null} if no such value * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); for (int i = hash(key); keys[i] != null; i = (i + 1) % m) if (keys[i].equals(key)) return vals[i]; return null; }

/** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { if (key == null) throw new IllegalArgumentException("argument to delete() is null"); if (!contains(key)) return;

// find position i of key int i = hash(key); while (!key.equals(keys[i])) { i = (i + 1) % m; }

// delete key and associated value keys[i] = null; vals[i] = null;

// rehash all keys in same cluster i = (i + 1) % m; while (keys[i] != null) { // delete keys[i] an vals[i] and reinsert Key keyToRehash = keys[i]; Value valToRehash = vals[i]; keys[i] = null; vals[i] = null; n--; put(keyToRehash, valToRehash); i = (i + 1) % m; }

n--;

// halves size of array if it's 12.5% full or less if (n > 0 && n

assert check(); }

/** * Returns all keys in this symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * @return all keys in this symbol table */ public Iterable keys() { Queue queue = new Queue(); for (int i = 0; i

// integrity check - don't check after each put() because // integrity not maintained during a delete() private boolean check() {

// check that hash table is at most 50% full if (m

// check that each key in table can be found by get() for (int i = 0; i Modify the LinearProbing HashST class to use lazy deletion as follows: When a key is deleted, set the corresponding value for that key to null, but do not physically remove the key from the key array. This means that the key is "logically" deleted from the symbol table, even though it is not "physically" removed from the key array. When searching for a key, remember that such logically deleted keys no longer mark the end of a chain. When inserting, make use of any lazy deleted slots (slots whose keys are not null but whose values are null) whenever possible. o Scan the chain until you find a valid slot for insertion. If the slot is the key itself or an empty slot, you can insert as before. If the slot is a lazy deleted key, reuse the slot, but then you have to continue looking down the chain to try to lazy delete the old key if it appears further down the chain, otherwise the same key will appear twice in the symbol table (It will have 2 different non-null values). When returning a key iterator with the keys() method, make sure that lazy deleted keys are not included. When resizing, make sure not to copy over lazy deleted keys. NOTE: Besides lazy deleted slots being reused, this is the only time keys are physically removed the key array. The field n which keeps track of the number of keys in the symbol table should reflect the number of logical keys. In other words, it should not include lazy deleted keys in the count. (It should not include keys whose corresponding value is null.) Modify the LinearProbing HashST class to use lazy deletion as follows: When a key is deleted, set the corresponding value for that key to null, but do not physically remove the key from the key array. This means that the key is "logically" deleted from the symbol table, even though it is not "physically" removed from the key array. When searching for a key, remember that such logically deleted keys no longer mark the end of a chain. When inserting, make use of any lazy deleted slots (slots whose keys are not null but whose values are null) whenever possible. o Scan the chain until you find a valid slot for insertion. If the slot is the key itself or an empty slot, you can insert as before. If the slot is a lazy deleted key, reuse the slot, but then you have to continue looking down the chain to try to lazy delete the old key if it appears further down the chain, otherwise the same key will appear twice in the symbol table (It will have 2 different non-null values). When returning a key iterator with the keys() method, make sure that lazy deleted keys are not included. When resizing, make sure not to copy over lazy deleted keys. NOTE: Besides lazy deleted slots being reused, this is the only time keys are physically removed the key array. The field n which keeps track of the number of keys in the symbol table should reflect the number of logical keys. In other words, it should not include lazy deleted keys in the count. (It should not include keys whose corresponding value is null.)