objective: Work with hash tables by creating a hash table using linear probing D
ID: 3729554 • Letter: O
Question
objective: Work with hash tables by creating a hash table using linear probing Description: Create a generic class called LinearProbingHashTablecK,> It should contain a private static class, Entry Because Java cannot create an array of a generic class, create the array for the table 1ike this: EntrycK, v> table / declare generic table new Entrytsize]: / create as non-generic Note that this will generate a warning message when compiled Your class should have the following methods. The methods should all operate on the object making the cal1 (none are static) Perform checking of the parameters and throw exceptions where appropriate You may use code from the textbook, but all other code must be your own. 15 points a) public boolean insert(K key, V value) inserts entry, rehashes if half full, can re-use deleted entries, throws exception if key is null, returns true if inserted, false if duplicate 15 points b) public v find(K key) returns value for key, or null if not found 15 points c) public boolean delete(K key) marks the entry deleted but leaves it there, returns true if deleted, false if not found 15 points d) private void rehash( doubles the table size, hashes everything to the new table, omitting items marked deleted 10 points e) public int getHashvalue(K key) returns the hash value for the given key (this is the value before probing occurs) 10 points f) public int getlocation( key) returns the location for the given key or -1 if not found (this is the value after probing occurs) 10 points g} public String toString returns a formatted string of the hash table, where k, v is the key and value at this location: 0 k,v 2 k, v deleted 10 points h) public static void main(String args ]) demonstrate each of your methodsExplanation / Answer
PROGRAM:
public class LinearProbingHashTable<Key, Value> {
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];
}
// hash function for keys - returns value between 0 and M-1
private int getHashvalueKey key) {
return (key.hashCode() & 0x7fffffff) % m;
}
// resizes the hash table to the given capacity by re-hashing all of the keys
private void rehash(int capacity) {
LinearProbingHashTable<Key, Value> temp = new LinearProbingHashTable<Key, Value>(2*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) {
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 find(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 <= m/8) resize(m/2);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.