Static and Dynamic Hashing

4
0

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 4

Here, 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 = 2

Since 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

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:

  1. The bucket is split.

  2. Its records are redistributed using an additional hash bit.

  3. Directory pointers are updated.

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

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.

CS Core

Read Similar Blogs

Comments0