Let K denote all the search-key values.
Let B represent the set of all bucket addresses.
A bucket is a unit of storage that contains some records.
Here, h is a ‘hash function’ from K to B.
‘Hash function’ is used to avoid ‘index structure’.
Bucket Overflow :
This will occur only in two ways.
- Insufficient buckets.
- Skew in distribution of records. Some buckets are given more records than others, so a bucket can overflow even though the other buckets still have space. This situation is called ‘bucket skew’.
Overflow Chaining :
The overflows of a given bucket are chained together in a linked list. This is called ‘Closed Hashing’.
In ‘Open Hashing’, the set of buckets are fixed, and there are no overflow chains. Here, if a bucket is full, the system inserts records in some other bucket in the initial set of buckets.
A hash index arranges the search keys, with their associated pointers, into a hash file structure. In this, one applies a hash function on a search key to helping identify a bucket, and store the key and its associated pointers in the bucket.