Question: How to convert from linear probe in hash table to quadratic probe?linear probe is when N+1 ,N+2, N+3, but quadratic probe is when n+1, n+4,
How to convert from linear probe in hash table to quadratic probe?linear probe is when N+1 ,N+2, N+3, but quadratic probe is when n+1, n+4, n+9 ...
I have a hash table that uses linear probing to resolve collisions.This is my set item function.
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**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. So how do I implement the quadratic probe?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
