My current implementation of Quadratic Probing overrides the item being stored at the current index with the new item when a collision occurs. I insert three Person objects which are stored by using their lastname as key. To test the collision resolution of the implementation they all have the same last name which is "Windmill".
I need the implementation to keep all person objects but just move them to a different index instead of overriding them.
The list size has been set as 7, stored in variable "M" used for modulo in the insert function.
Insert function
@Override
public void put(String key, Person value) {
int tmp = hash(key);
int i, h = 0;
for (i = tmp; keys[i] != null; i = (i + h * h++) % M) {
collisionCount++;
if (keys[i].equals(key)) {
values[i] = value;
return;
}
}
keys[i] = key;
values[i] = value;
N++;
}
Hash function
private int hash(String key) {
return (key.hashCode() & 0x7fffffff) % M;
}
get function
@Override
public List<Person> get(String key) {
List<Person> results = new ArrayList<>();
int tmp = hash(key);
int i = hash(key), h = 0;
while (keys[i] != null)
{
if (keys[i].equals(key))
results.add(values[i]);
i = (i + h * h++) % M;
}
return results;
}
When i remove the piece of code that overrides previous values, the index int overflows and turns into a negative number, causing the program to crash.
I think there are two issues with your code:
You don't check whether the (multi-)map is full. In practice you want to do 2 checks:
N==M
(or maybe some smaller threshold like 90% of M
)collisionCount
a local variable and when it reaches N
(unfortunately this check is also necessary to avoid some pathological cases)in both cases you should extend your storage area and copy old data into it (re-insert). This alone should fix your bug for small values of M
but for really big sizes of the map you still need the next thing.
%
) operation works in Java. Particularly for negative value of a
the value of a % b
is also negative. So when you insert a lot of values and check for next index, i + h^2
might overflow Integer.MAX_VALUE
and become negative. To fix this you might use a method like this:static int safeMod(int a, int b) {
int m = a % b;
return (m >= 0) ? m : (m+b);
}