Give the contents of the hash table that results when you insert the following k

Question

Give the contents of the hash table that results when you insert the following keys in that order into an initially empty table of M = 5 lists, using separate chaining with unordered lists. Use the hash function 11k mod Mto transform the kth letter of the alphabet into a table index, e.g., hash(I) = hash(9) = 99 % 5 = 4.

D E M O C R A T S

Give the contents of the hash table that results when you insert the following keys in that order into an initially empty table of size M = 16 using linear probing. Use the hash function 11k mod M to transform the kth letter of the alphabet into a table index.

R E P U B L I C A N S

Explanation / Answer

public class SeparateChainingHashST { private static final int INIT_CAPACITY = 4; private int N; // number of key-value pairs private int M; // hash table size private SequentialSearchST[] st; // array of linked-list symbol tables // create separate chaining hash table public SeparateChainingHashST() { this(INIT_CAPACITY); } // create separate chaining hash table with M lists public SeparateChainingHashST(int M) { this.M = M; st = (SequentialSearchST[]) new SequentialSearchST[M]; for (int i = 0; i = 10*M) resize(2*M); int i = hash(key); if (!st[i].contains(key)) N++; st[i].put(key, val); } // delete key (and associated value) if key is in the table 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 INIT_CAPACITY && N

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---