Introduction
A database often needs to locate a record using an exact key, such as a customer ID or account number. Hashing provides an access method that maps a search key to a bucket where matching records can be found.
Static and dynamic hashing differ in how they handle growth. Static hashing keeps its primary bucket count fixed, while dynamic hashing adjusts its structure as records are added or removed.
How Hashing Organizes Records
A hash function transforms a search key into a value used to select a bucket. A bucket is a storage unit that can hold records or references to records.
For a simple illustration, suppose there are four primary buckets:
h(key) = key MOD 4Here, MOD returns the remainder after division.
Key | Calculation | Bucket |
|---|---|---|
10 | 10 MOD 4 = 2 | B2 |
14 | 14 MOD 4 = 2 | B2 |
19 | 19 MOD 4 = 3 | B3 |
21 | 21 MOD 4 = 1 | B1 |
To find key 14, compute its bucket and then examine the entries in B2.
Different keys can map to the same bucket. This is a collision. A collision does not necessarily mean the bucket is full: B2 may have enough room for both 10 and 14.
Static Hashing
In static hashing, the number of primary buckets remains fixed during normal operation. With four buckets and the hash function h(key) = key MOD 4, each new record is assigned to B0, B1, B2, or B3. This provides a straightforward mapping, but additional storage may be needed when a bucket becomes full.
Static hashing can suit datasets whose size remains relatively stable. However, changing the primary bucket count generally requires reorganizing records according to a revised mapping.
Handling Bucket Overflow
Assume each bucket holds two records. Keys 10 and 14 both map to B2 and fill its available space. Inserting 18 also targets B2 because:
18 MOD 4 = 2Since B2 is full, one common solution is to store 18 in an overflow bucket linked to B2. A lookup checks the primary bucket and follows its overflow chain when necessary.
As records accumulate, longer overflow chains can increase the number of page accesses. This can happen even when other buckets still have free space, because records are assigned by their hash values rather than by available space.
Keep the existing static hashing image immediately after this explanation.
Static Hashing : Bucket overflow
Linear Hashing
Linear hashing grows through a controlled sequence of bucket splits, typically without the directory used by extendible hashing. It maintains a split pointer that identifies the next bucket to split. Depending on the implementation, an overflow or a load threshold can trigger growth.
When growth is triggered, the bucket identified by the split pointer is split, and its records are redistributed using an expanded hash mapping. This is not necessarily the bucket that just overflowed. The pointer then advances to the next bucket.
After every bucket in the current round has been split, the pointer returns to the beginning and a new round starts with the expanded address range. This spreads growth across incremental operations, although overflow buckets may still be needed.
Dynamic Hashing
Dynamic hashing changes its bucket structure as the dataset grows or shrinks.
Instead of relying only on increasingly long overflow chains, it can split buckets and redistribute their entries. Some methods can also merge buckets when conditions allow.
The aim is to adapt capacity without rebuilding the entire structure for every increase in data volume.
Two important approaches are extendible hashing and linear hashing.
Extendible Hashing
Extendible hashing uses a directory whose entries point to buckets. A selected number of hash bits determines which directory entry to follow.
Two depth values control the structure:
Global depth: The number of hash bits used to address the directory.
Local depth: The number of hash bits that distinguish a particular bucket.
Several directory entries can point to the same bucket.
When a bucket overflows:
The bucket is split.
Its records are redistributed using an additional hash bit.
Directory pointers are updated.
If the bucket’s local depth already equals the global depth, the directory doubles.
A bucket split does not always require directory doubling. When the directory already uses enough bits, its existing entries can distinguish the new buckets.
Directory doubling expands the pointer structure; it does not mean every data bucket is split.
Extendible Hashing : Split and Growing
Linear Hashing
Linear hashing grows through a controlled sequence of bucket splits, typically without an extendible-hashing-style directory.
It maintains a split pointer that identifies the next bucket to split. Depending on the algorithm, growth may be triggered by overflow or a load threshold.
The bucket selected for splitting is determined by the split pointer. It is not necessarily the bucket that just overflowed.
After a split, the pointer advances. Once a complete round of buckets has been split, a new round begins with an expanded address range.
This spreads growth across incremental operations, although overflow buckets may still be needed.
Static vs Dynamic Hashing
Feature | Static hashing | Dynamic hashing |
|---|---|---|
Primary bucket count | Fixed during normal operation | Adapts as data changes |
Growth handling | Often uses overflow storage | Uses bucket splits, sometimes with overflow storage |
Reorganization | Resizing can require a broad rebuild | Usually redistributes records incrementally |
Structural overhead | Simpler mapping | Additional pointers or split metadata |
Typical fit | Relatively stable data volume | Changing data volume |
Dynamic hashing reduces some growth-related problems, but it does not eliminate collisions or guarantee that every lookup needs only one page access.
When Is Hashing Useful?
Hashing is well suited to equality searches, such as finding a record with customer_id = 101.
It does not naturally preserve key order. Therefore, it is generally unsuitable for efficiently finding a range such as IDs from 100 to 200, or returning records in sorted order.
Tree-based indexes are usually a better fit when ordered traversal or range searching is important.
Performance also depends on the hash function, bucket capacity, data distribution, and overflow behavior. Repeated search-key values require appropriate handling because identical keys produce the same hash value.
Summary
Static hashing uses a fixed primary bucket structure and commonly handles excess records through overflow storage. Its simplicity can work well when data volume remains predictable.
Dynamic hashing adapts through bucket splits and related structural changes. Extendible hashing uses a directory, while linear hashing expands through a split sequence. Both approaches support equality access, but neither naturally provides ordered range traversal.
Be the first to add a comment.