Why does this implementation of Quadratic Probing fail when not overriding values on collision?

Question

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.

score 1 · Answer 1 · answered Jan 17 '19 at 19:00

1

You get overflow because you do % M after some operations with ints that cause overflow. You need to replace i = (i + h * h++) % M with some additional operations based on modulo operation properties (https://en.wikipedia.org/wiki/Modulo_operation):

(a + b) mod n = [(a mod n) + (b mod n)] mod n.
ab mod n = [(a mod n)(b mod n)] mod n.

answered Jan 17 '19 at 19:00

Ivan

8,508
2
19
30

Could you be more specific as in which sort of additional operations i should perform? – user24028 Jan 17 '19 at 20:16

score 0 · Accepted Answer · answered Jan 18 '19 at 01:25

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:
- check if N==M (or maybe some smaller threshold like 90% of M)
- make 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.

You didn't take into account how mod (%) 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);
}

Why does this implementation of Quadratic Probing fail when not overriding values on collision?

2 Answers2