Question: 8. Implement put and get method inside QuadraticProbingHashST , which uses quadratic probing to resolve conflicts. QuadraticProbingHashST is similar to LinearProbingHashSt, except in picking with
8. Implement put and get method inside QuadraticProbingHashST, which uses quadratic probing to resolve conflicts. QuadraticProbingHashST is similar to LinearProbingHashSt, except in picking with table index to try when there are conflicts. With quadratic probing, the initial index for a key is key.hashCode()%tableSize. If that place is taken, the next place to try is initialIndex + 1*1, if it is taken then try initialIndex + 2*2, if it is taken then try initialIndex + 3*3, etc. The following tables shows the contents of keys array After each key insertion in that order.
My problem is with my get method when ever I try to run it the Unit test tells me that its:
java.lang.AssertionError: expected: but was: . Below is my current code I need help figuring out whats going wrong.
public class QuadraticProbingHashST
private int n; // number of key-value pairs in the table
private int m = 16; // size of linear-probing table
private Key[] keys; // the keys
private Value[] vals; // the values
@SuppressWarnings("unchecked")
public QuadraticProbingHashST() {
keys = (Key[]) new Comparable[m];
vals = (Value[]) new Object[m];
}
@SuppressWarnings("unchecked")
public QuadraticProbingHashST(int capacity) {
m = capacity;
keys = (Key[]) new Comparable[m];
vals = (Value[]) new Object[m];
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
/* If search key exists in the table, return associated value;
* otherwise return null
*/
public Value get(Key key) {
// Provide your implementation here
//throw new UnsupportedOperationException();
int i = hash(key), h = 1; //start searching from index i
while(keys[i] != null) {
if(keys[i].equals(key)) { //if key found return its value
return vals[i];
}
i = (i + h*h++) % m;//quadratic probing in case key is not found
System.out.println(i);
}
return null; //if key not found return null;
}
/* Insert the key value pair into the table
* If the key exists in the table, update the associated value with new value;
* No resize is needed for this implementation
*/
public void put(Key key, Value val) {
// Provide your implementation here
//throw new UnsupportedOperationException();
int tmp = hash(key); // tmp is the index of the hash table at which key is to be inserted
int i = tmp, h = 1;
do {
if(keys[i] == null) { //if the index in which key is to be inserted is null, then insert the key and value there.
keys[i] = key;
vals[i] = val;
n++;
return;
}
if(keys[i].equals(key)) { //if key already present update its value
vals[i] = val;
return;
}
i = (i + h*h++) % m; // quadratic probing in case index(i) is occupied
}while(i != tmp);
}
public void delete(Key key) {
throw new UnsupportedOperationException("Not implemented yet");
}
public boolean contains(Key key) {
return (get(key) != null);
}
@Override
public boolean isEmpty() {
return n==0;
}
@Override
public int size() {
return n;
}
@Override
public Iterable
List
for (Key key: keys) {
list.add(key);
}
return list;
}
}
8. (10 Points) Implement put and get method inside QuadraticProbingHashST, which uses quadratic probing to resolve conflicts. QuadraticProbingHashST is similar to LinearProbingHashSt, except in picking with table index to try when there are conflicts. With quadratic probing, the initial index for a key is key.hashCode()%tableSize. If that place is taken, the next place to try is initiallndex + 1*1, if it is taken then try initiallndex 2*2, if it is taken then try initiallndex + 3*3, etc. The following tables shows the contents of keys array After each kev insertion in that order 4 6 7 8 Initial After 89 After 18 18 18 18 18 89 89 89 89 89 After 4949 After 58 49 58 58 69 After 6949 /If search key exists in the table, return associated value; *otherwise return null public Value get (Key key) ( // Provide your implementation here throw new UnsupportedOperationException(); /Insert the key value pair into the table *If the key exists in the table, update the associated value with new value; *No resize is needed for this implementation public void put (Key key, Value val) ( // Provide your implementation here throw new UnsupportedOperationException(); 8. (10 Points) Implement put and get method inside QuadraticProbingHashST, which uses quadratic probing to resolve conflicts. QuadraticProbingHashST is similar to LinearProbingHashSt, except in picking with table index to try when there are conflicts. With quadratic probing, the initial index for a key is key.hashCode()%tableSize. If that place is taken, the next place to try is initiallndex + 1*1, if it is taken then try initiallndex 2*2, if it is taken then try initiallndex + 3*3, etc. The following tables shows the contents of keys array After each kev insertion in that order 4 6 7 8 Initial After 89 After 18 18 18 18 18 89 89 89 89 89 After 4949 After 58 49 58 58 69 After 6949 /If search key exists in the table, return associated value; *otherwise return null public Value get (Key key) ( // Provide your implementation here throw new UnsupportedOperationException(); /Insert the key value pair into the table *If the key exists in the table, update the associated value with new value; *No resize is needed for this implementation public void put (Key key, Value val) ( // Provide your implementation here throw new UnsupportedOperationException()
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help