Chapter 27.4, Problem 27.4.1CP

Explanation of Solution

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...