Static Hashing
STATIC HASHING
In static hashing, when a search-key value is provided, the hash function always computes the same address. For example, if mod-4 hash function is used, then it shall generate only 5 values. The output address shall always be same for that function. The number of buckets provided remains unchanged at all times.
Operation
- Insertion − When a record is required to be entered using static hash, the hash function hcomputes the bucket address for search key K, where the record will be stored.Bucket address = h(K)
- Search − When a record needs to be retrieved, the same hash function can be used to retrieve the address of the bucket where the data is stored.
- Delete − This is simply a search followed by a deletion operation.
BUCKET OVERFLOW
The condition of bucket-overflow is known as collision. This is a fatal state for any static hash function. In this case, overflow chaining can be used.
- Overflow Chaining − When buckets are full, a new bucket is allocated for the same hash result and is linked after the previous one. This mechanism is calledClosed Hashing.
- Linear Probing − When a hash function generates an address at which data is already stored, the next free bucket is allocated to it. This mechanism is calledOpen Hashing.
