When does a HashTable / Python dict stop probing?

In Java I’m building a datastructure that is supposed to resemble dictionaries in Python. (As far as I understand this is called a “HashTable” in java context.)

I have read the following Python documentation in order to arrive at the probing function (as I wished to prevent using linear probing)

Now I have come to a point where Im trying to retrieve an element from my “dict” that doesn’t exist in its internal array. It seems that my probing function will go in circles endlessly searching for the non-existent element, and i therefor wish to break and return null at some point.

When should I stop probing and return null?

My current solution is to count every probe. Once probeCount > size I break. This however, seems like a poor solution as the time complexity to determine that an element is not present would be O(n), n being size of my array.

The following in my probing code:

public Object get(long id) {

        int count = 0;

        int hashedIndex = (int) id;
        if (hashedIndex < 0) hashedIndex = -hashedIndex;
        hashedIndex = hashedIndex % size;
        int perturb = hashedIndex;
        while(true) {
            if (nodes[hashedIndex] != null || count > size) {
                if (count > size) {
                    System.out.println("null");
                    break;
                }
                if (nodes[hashedIndex].identifier == id) {
                    break;
                }
            }                       
            hashedIndex = (5*hashedIndex + 1 + perturb) % size;
            perturb >>= 5;
            count++;
        }
        return nodes[hashedIndex];
}

Answer

A Python dict stops probing once it finds an empty, non-“dummy” slot – one that is not holding a key, and is not holding a “dummy” marker that indicates a key was deleted there.

The dict implementation ensures that at least one such slot always exists (and usually many more), and the probe sequence is guaranteed to check all slots eventually, so this guarantees termination.

Advertisement

Answer