Chapter 27.4, Problem 27.4.3CP

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.

Linear Probing:

• Linear probing is one of the variations of open addressing.
• When an entry is inserted into a hash table, a collision occurs. At the time of collision, linear probing will start finding the next available location sequentially.
• Linear probing will look at the consecutive cells which begin at index “k”.
• Starting from the initial index, linear probing will add an increment of 1 to “k” to define a search sequence.

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 at indices $\left({\text{k + j}}^{\text{2}}\right)\text{ \% n}$ , for $\text{j}\ge \text{0}$ , which means that $\text{k}$ , $\left(\text{k + 1}\right)\text{ \% n}$ , $\left(\text{k + 4}\right)\text{ \% n}$ , $\left(\text{k + 9}\right)\text{ \% n}$ ... and so on.
• Starting from the initial index, quadratic probing will add an increment of 2 to k to define a search sequence.