Java

Consider the following simplified version of the code for adding an element x to a LinearHashTable, which simply stores x in the first null array entry it finds. Explain why this could be very slow by giving an example of a sequence of O(n) add(x), remove(x), and find(x) operations that would take on the order of n2 time to execute.

 LinearHashTable 

 boolean addSlow(T x) { if (2*(q+1) > t.length) resize(); // max 50% occupancy int i = hash(x); while (t[i] != null) { 

 if (t[i] != del && x.equals(t[i])) return false; 

 i = (i == t.length-1) ? 0 : i + 1; // increment i } 

 t[i] = x; n++; q++; return true; 

}