How Quadratic Probing works?
Let hash(x) be the slot index computed using the hash function.
- If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.
- If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
- If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
- This process is repeated for all the values of i until an empty slot is found.
Quadratic Probing in Python
Hashing is an improvement technique over the Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as the index in a table called a hash table.