I need help implementing in Java for my Linear Probing class, the booleans conta
ID: 3752145 • Letter: I
Question
I need help implementing in Java for my Linear Probing class, the booleans contains, void delete, and int size methods, as well as the #int probeOffset(int i). I appreciate any help
LinearProbingHT -int N -int M -Entry Key, Value entries +LinearProbingHTO +LinearProbingHT(int M) -int hash(Key key, int i) int probeOffset(int i) o+void put(Key key, Value val) O+Value get(Key key) o+boolean contains(Key key) entries +void delete(Key key) +boolean isEmpty0 o+ int size +Iterable Key keys0 Entry EntryKey, EntryValue> -EntryKey key -EntrWalue value QuadProbingHT +EntryWalue Entry(EntryKey key, EntryValue +QuadProbingHTO sint probeOffset(int i)Explanation / Answer
Please find the code below.
CODE
======================
import java.util.LinkedList;
import java.util.Queue;
class Entry<EntryKey, EntryValue> {
EntryKey key;
EntryValue value;
public Entry(EntryKey key, EntryValue value) {
this.key = key;
this.value = value;
}
}
public class LinearProbingHT<Key, Value> {
private static final int INIT_CAPACITY = 10;
private int n; // number of key-value pairs in the symbol table
private int m; // size of linear probing table
Entry<Key, Value>[] entries;
/**
* Initializes an empty symbol table.
*/
public LinearProbingHT() {
this(INIT_CAPACITY);
}
/**
* Initializes an empty symbol table with the specified initial capacity.
*
* @param capacity the initial capacity
*/
public LinearProbingHT(int capacity) {
m = capacity;
n = 0;
entries = (Entry[]) new Object[capacity];
}
/**
* 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) {
LinearProbingHT<Key, Value> temp = new LinearProbingHT<Key, Value>(capacity);
for (int i = 0; i < m; i++) {
if (entries[i].key != null) {
temp.put(entries[i].key, entries[i].value);
}
}
entries = temp.entries;
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); entries[i].key != null; i = (i + 1) % m) {
if (entries[i].key.equals(key)) {
entries[i].value = val;
return;
}
}
entries[i].key = key;
entries[i].value = 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); entries[i].key != null; i = (i + 1) % m)
if (entries[i].key.equals(key))
return entries[i].value;
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(entries[i].key)) {
i = (i + 1) % m;
}
// delete key and associated value
entries[i].key = null;
entries[i].value = null;
// rehash all keys in same cluster
i = (i + 1) % m;
while (entries[i].key != null) {
// delete keys[i] an vals[i] and reinsert
Key keyToRehash = entries[i].key;
Value valToRehash = entries[i].value;
entries[i].key = null;
entries[i].value = 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);
}
/**
* 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<Key> keys() {
Queue<Key> queue = new LinkedList<>();
for (int i = 0; i < m; i++)
if (entries[i].key != null) queue.add(entries[i].key);
return queue;
}
}
NOTE: I have not implemented the #int probeOffset(int i) function. In order to implement it, you would need to explain what this function does. Then after understanding, I can provide you the implementation of #int probeOffset(int i).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.