Modify the LinearProbingHashST 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.

oScan 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.)

THE CODE BELOW DOES NOT WORK WITH TESTS: EXAMPLE PUT IS NOT PUTTING NEW KEYS INTO THE CORRECT HASH LOCATION AND INSTEAD PUTS THEM INTO NEW NULL SPOTS.

import edu.princeton.cs.algs4.BST; import edu.princeton.cs.algs4.BinarySearchST; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.RedBlackBST; import edu.princeton.cs.algs4.ST; import edu.princeton.cs.algs4.SeparateChainingHashST;

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 < m; i++) { if (keys[i] != null) { temp.put(keys[i], vals[i]); } } keys = temp.keys; vals = temp.vals; m = temp.m; }

/** * 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) { 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; }

// Set the vals[i] = null and use this as a way of verifying deleted keys vals[i] = null;

i = (i + 1) % m; while (keys[i] != null) { 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 <= m / 8) { resize(m / 2); }

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 < m; i++) { if (keys[i] != null) { queue.enqueue(keys[i]); } } return queue; }

// 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 < 2*n) { System.err.println("Hash table size m = " + m + "; array size n = " + n); return false; }

// check that each key in table can be found by get() for (int i = 0; i < m; i++) { if (keys[i] == null) { continue; } else if (get(keys[i]) != vals[i]) { System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + vals[i]); return false; } } return true; } /******************* You may not change any of the 3 methods below ******/ public Value getValueAt(int i) { return vals[i]; } public Key getKeyAt(int i) { return keys[i]; }

public int tableSize() { return m; } }

/******************* TESTs**********************************************************/ /**********************************************************************************/

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNull;

import java.util.TreeSet;

import org.junit.Test;

public class HW6Test {

@Test public void test10ReuseSingleTombstone() { LinearProbingHashST st = new LinearProbingHashST(6); MyString bat = new MyString("bat"); MyString boot = new MyString("boot"); MyString big = new MyString("big"); MyString bag = new MyString("bag");

Integer one = Integer.valueOf(1); Integer two = Integer.valueOf(2); Integer three = Integer.valueOf(3); Integer four = Integer.valueOf(4);

st.put(bat, one); st.put(boot, two); st.put(big, three); assertEquals(3, st.size()); assertEquals(6, st.tableSize()); st.delete(boot); assertEquals(2, st.size()); assertEquals(6, st.tableSize()); assertNull(st.get(boot)); assertEquals(boot, st.getKeyAt(2)); st.put(bag, four); assertEquals(3, st.size()); assertEquals(6, st.tableSize()); assertEquals(one, st.get(bat)); assertEquals(four, st.get(bag)); assertEquals(three, st.get(big)); assertEquals(bag, st.getKeyAt(2)); }

}

/******************* MYSTRING CLASS **************************************/ /************************************************************************* ******/ *

/* * Example, "Apple" and "after" both have hashcode 0, while "fast" and "Fog" both have hashcode 5

/*

public class MyString implements Comparable{ private String val; public MyString(String s) { val = s; } public boolean equals(Object o2) { if (o2 == null) return false; if (o2 == this) return true; if (o2.getClass() != this.getClass()) return false; MyString s2 = (MyString) o2; return this.val.equals(s2.val); } @Override public int hashCode() { int hash = val.toUpperCase().charAt(0) - 'A'; return hash; } @Override public String toString() { return val; }

@Override public int compareTo(MyString arg0) { return val.compareTo(arg0.val); } }