Implement a hash table with 15 random values (key, value) (relax the chain method and implement it)

Please fill out the Java code and show the output. thank you :)

If you don't understand the question, let me know.

If you copy it or play it, report it.

Implement this code.

package HashST;

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

// largest prime <= 2^i for i = 3 to 31 // not currently used for doubling and shrinking // private static final int[] PRIMES = { // 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, // 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301, // 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, // 536870909, 1073741789, 2147483647 // };

private int N; // number of key-value pairs private int M; // hash table size private SequentialSearchST[] st; // array of linked-list symbol tables

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

/* Initializes an empty symbol table with M chains. * param M : the initial number of chains */ public SeparateChainingHashST(int M) { this.M = M; st = (SequentialSearchST[]) new SequentialSearchST[M]; for (int i = 0; i < M; i++) st[i] = new SequentialSearchST(); }

// resize the hash table to have the given number of chains b rehashing all of the keys private void resize(int chains) { SeparateChainingHashST temp = new SeparateChainingHashST(chains); for (int i = 0; i < M; i++) { for (Key key : st[i].keys()) { temp.put(key, st[i].get(key)); } } this.M = temp.M; this.N = temp.N; this.st = temp.st; }

// hash value between 0 and M-1 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % 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; }

/* Is this symbol table empty? * return true if this symbol table is empty and false otherwise */ public boolean isEmpty() { return size() == 0; }

/* Does this symbol table contain the given key? * param key : the key * return true if this symbol table contains key and false otherwise * throws NullPointerException if key is null */ public boolean contains(Key key) { return get(key) != null; }

/* Returns the value associated with the given key. * param key : the key * return the value associated with the given key if the key is in the symbol table * and null if the key is not in the symbol table * throws NullPointerException if key is null */ public Value get(Key key) { int i = hash(key); return st[i].get(key); }

/* Inserts the key-value pair into the symbol table, overwriting the old value * with the new value if the key is already in the symbol table. * If the value is null, this effectively deletes the key from the symbol table. * param key : the key; param val : the value * throws NullPointerException if key is null */ public void put(Key key, Value val) { if (val == null) { delete(key); return; }

// double table size if average length of list >= 10 if (N >= 10*M) resize(2*M);

int i = hash(key); if (!st[i].contains(key)) N++; st[i].put(key, val); }

/* Removes the key and associated value from the symbol table * (if the key is in the symbol table). * param key : the key * throws NullPointerException if key is null */ public void delete(Key key) { int i = hash(key); if (st[i].contains(key)) N--; st[i].delete(key);

// halve table size if average length of list <= 2 if (M > INIT_CAPACITY && N <= 2*M) resize(M/2); }

// return keys in symbol table as an Iterable public Iterable keys() { Queue queue = new Queue(); for (int i = 0; i < M; i++) { for (Key key : st[i].keys()) queue.enqueue(key); } return queue; }

/* Unit tests the SeparateChainingHashST data type. */ public static void main(String[] args) { SeparateChainingHashST st = new SeparateChainingHashST(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); }

// print keys for (String s : st.keys()) StdOut.println(s + " " + st.get(s));

} }