Static Hashing
In static hashing we have a bucket overflow problem.
Let suppose we want to store a record or insert a record.
We will calculate the address of a bucket by hashing and address of bucket which get generated does not have enough space, a bucket overflow is occurred.
Reasons for bucket overflow to occur:
Insufficient bucket
nB>nr/Fr where nB= no. of buckets
nr: Number of record
fr: Record in a bucket.
If nB is not greater than nr/Fr then there is insufficient buckets.
Skews: Some buckets are assigned more records than are others, so a bucket may overflow even when other buckets still have space. This situation is called Bucket skew.
• multiple records may have the same search key
• non uniform distribution of Search keys.
Two approaches for reducing the bucket overflow
1) Increase number of bucket with Fudge Factors:
If we choose number of buckets to be
(nr/fr)*(1+d) here d is fudge factor=0.2
About 20 % of the space in the buckets will be empty but the overflow is reduced.
2)Overflow Buckets:
Let suppose we want to insert a record into bucket b as per hashing function. And b is already full then system will provide an overflow buckets for b and inserts the record into it.
If overflow bucket is also full then another overflow bucket will be allotted and they are chained together in a linked list which is called overflow chaining.
