C++ Data Structures and Algorithms

Implementing the open addressing technique

As we discussed earlier at beginning of this chapter, an open addressing technique stores all elements in the hash table itself. A collision will not happen, since there is a calculation that will be performed if a collision is about to happen. Based on this calculation, we can have three types of open addressing technique—Linear probing, quadratic probing, and double hashing. The difference between the three is the formula for finding the next free space if the hash key of the given element has been occupied:

• In linear probing, if the hash key has been occupied by another element, we use the following formula to find the next free space—(HashFunction(key) + n) % TABLE_SIZE, then increase n from ...