CODEWITHSUNDEEP
pythonhashtablequadratic-probing
Sook Lim
Sook Lim

Reputation: 551

How to convert from linear probe in hash table to quadratic probe?

Hi I'm new to python and I have a hash table that uses linear probing to resolve collisions. I know linear probe is when N+1 ,N+2, N+3, but quadratic probe is when n+1, n+4, n+9 ... This is my set item function for linear probe

def __setitem__(self, key, value):
    position = self.hash_value(key)
    for _ in range(self.table_size):
        if self.array[position] is None:#found empty slot
            self.array[position] = (key, value)
            self.count += 1
            return
        elif self.array[position][0] == key:#found key
            self.array[position] = (key, value)#update value
            return
        else:#not found try next
            position = (position+1) % self.table_size
    raise ValueError("Table is Full!")

To convert it to quadratic probe I tried to change position to 

position = (position+(i+1)**2) % self.table_size

but clearly this is wrong because the quadratic index is added to the last position and not the the original position? Any help will be apreciated!

Upvotes: 1

Views: 1380

Answers (1)

sshashank124
sshashank124

Reputation: 32189

If you notice the sequence of quadratic numbers: 1, 4, 9, 16, 25, ..., you'll notice that the difference between the consecutive elements is 3, 5, 7, 9 i.e. odd numbers. Therefore you can use a variable i which acts as a counter/index and use it to increase your position for the next iteration as follows:

position = (position + (2 * i + 1)) % self.table_size

where position is the index that was just used for the current iteration.

expected    |  i  |    new_position
1           |  0  |     0 + (2 * 0 + 1) = 1
4           |  1  |     1 + (2 * 1 + 1) = 4
9           |  2  |     4 + (2 * 2 + 1) = 9
16          |  3  |     9 + (2 * 3 + 1) = 16
25          |  4  |    16 + (2 * 4 + 1) = 25

However, you will need to modify the number of times you increment i. A common choice is to just use table length but you should know that in quadratic probing, it is possible to not find a valid index in a table even if it exists by just iterating table_length times and sometimes it might even not find it even if you keep probing forever. Therefore, you'll have to be careful to set a proper limit on the number of times to probe for a single operation

Alternatively, you could keep track of the first calculated/hashed index and always calculate position as:

current_position = original_position + i**2

Upvotes: 2

Related Questions