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.

Static Hashing

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.

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

Static Hashing

More in sem3
B+ tree Index Files

B+ tree Index Files A B+ tree is a balanced binary search tree that follows a multi-level index format. The...

Close