Quadratic probing
Quadratic probing is intended to avoid primary clustering. We probe one step at a time, but our stride varies as the square of the step. Stride values follow the sequence 1, 4, 9, 16, 25, 36, 鈥� etc. In this way, we avoid primary clustering.
Resources:
Comprehension check:
The third step in a quadratic probe sequence will have stride of ___________.
True or false? The nth index in a quadratic probe sequence is given by
\Bigg( i + \sum\limits_{j=1}^n j^2 \Bigg) \mod t
where i is the starting index, j is the step, and t is the size of the table.
True or false? Quadratic probing avoids secondary clustering but is prone to tertiary clustering.
Just as with linear probing, when using quadratic probing, if we delete or remove an item from our hash table, we must mark it as 鈥渄eleted鈥� or 鈥渞emoved鈥�, otherwise we may break the __________________.
Answers: 菨蓴u菨nb菨s 菨qo晒d / 菨sl蓯蔁 / 菨n晒蕠 / 菨u岽塽
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.