Hashing - Open Addressing or Closed Hashing
Hashing - Open Addressing
The open addressing method is also called closed hashing. In Open addressing, the elements are hashed to the table itself. If two elements hash to the same location, a collision occurs. To resolve the collision, an empty location is searched for. The hash function for open addressing is given that
hi(X) = ( Hash(X) + F(i) ) % TableSize
with F(0) = 0, F(1)=1, F(2)=2 and so on.
where Hash(X) = X % TableSize and the function F(i) is called the Collision Resolution Strategy.
Open addressing needs a large table than separate chaining because all the data will be stored inside the hash table. There are 3 collision resolution techniques:
- Linear Probing
- Quadratic Probing
- Double Hashing