Data Structures - Hash Table
Closed Hashing alias Open Addressing
Closed Hashing is another method in which the elements are hashed to the table itself. In open addressing, if two elements hash to the same location, this is known as collision, then alternative location are chosen until an empty location is found. 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.
Actually, the open addressing needs a large table than separate chanining because all the data will be stored inside the hash table. This is also called closed hashing. There are three collision resolution techniques:
- Linear Probing
- Quadratic Probing
- Double Hashing