Chapter 27.6, Problem 27.6.2CP

Program Plan Intro

Open Addressing:

• Open Addressing is a method of finding an open location in the hash table at the time of collision.
• There are several variations for open addressing such as linear probing, quadratic probing, and double hashing.

Quadratic Probing:

• Quadratic probing is one other variation of open addressing.
• It is introduced to avoid the clustering problem in linear probing.
• Quadratic probing will look at the cells of indices $\left({\text{k + j}}^{\text{2}}\right)\text{ \% n, for j}\ge \text{ 0, k}$ , $\left(\text{k + 1}\right)\text{ \% n, }\left(\text{k + 4}\right)\text{ \% n, }\left(\text{k + 9}\right)\text{ \% n }\mathrm{...}$ , and so on.
• Starting from the initial index, quadratic probing will add an increment of 2 to “k” to define a search sequence.

Load Factor:

Load factor is used to measure how full a hash table is. It is defined as the ratio between the number of elements in the hash table and the hash table size.