Write a Java implementation of a flexible hashTable ADT and provide an efficient

Question

Write a Java implementation of a flexible hashTable ADT and provide an efficient 'open addressing' implementation for strings as keys. Do not adapt any Java.util classes.

The strings will serve as both keys and values, for example, for the string "CdE", you will call hashTable.put("CdE", "CdE"). Design a hash method that accepts these strings as keys and produces hash values. Ensure that the hash method is O(1).

Hint: The hash method consists of two parts; the hash code map from strings to integer values, and the compression map from integer values to the array indexes.

Explanation / Answer

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 // create an empty hash table - use 16 as default size public LinearProbingHashST() { this(INIT_CAPACITY); } // create linear proving hash table of given capacity public LinearProbingHashST(int capacity) { M = capacity; keys = (Key[]) new Object[M]; vals = (Value[]) new Object[M]; } // return the number of key-value pairs in the symbol table public int size() { return N; } // is the symbol table empty? public boolean isEmpty() { return size() == 0; } // does a key-value pair with the given key exist in the symbol table? public boolean contains(Key key) { 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; } // resize 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/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++; } // return the value associated with the given key, null if no such value public Value get(Key key) { for (int i = hash(key); keys[i] != null; i = (i + 1) % M) if (keys[i].equals(key)) return vals[i]; return null; } // delete the key (and associated value) from the symbol table public void delete(Key key) { 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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.