Static Hashing

Static hashing uses a fixed number of buckets that is determined at design time and never changes. A hash function maps each search key value to one of...

Definition

Static hashing uses a fixed number of buckets that is determined at design time and never changes. A hash function maps each search key value to one of these buckets, where the corresponding record is stored. The number of buckets remains constant regardless of how much data is inserted.

Example

h: Key -> {0, 1, 2, ..., B-1} where B is fixed forever Example: h(key) = key mod 10 (always maps to buckets 0-9)

Static hashing provides O(1) average-case access for equality searches — you compute the hash, go to the bucket, and find the record. No searching through indexes or scanning multiple blocks.

Operations

Search (Equality Lookup)

To find record with key K

1. Compute bucket number: b = h(K)

2. Read the disk block for bucket b

3. Scan the block for record with key K

4. If not found and overflow chain exists -> follow chain, read next block

5. Return record (or "not found")

Cost

Best case: 1 disk read (record in primary bucket block)

Average case: 1 disk read (no overflow)

Worst case: 1 + chain_length disk reads (overflow)

Insert

Example

To insert record R with key K: 1. Compute bucket: b = h(K) 2. Read the disk block for bucket b 3. If space available in the block: -> Write R into the block 4. If bucket block is FULL: -> Allocate a new overflow block -> Link it to the bucket (overflow chain) -> Write R into the overflow block Cost: 1 read + 1 write (best case), more if overflow allocation needed

Delete

1. Compute bucket	b = h(K)
4. If found	remove it (mark slot as free or shift records)
5. If overflow blocks exist and are now empty	deallocate them
6. Optionally	move a record from overflow into the freed primary slot
Cost	Similar to search + 1 write

Hash Function Design

A good hash function should:

Distribute uniformly: Records spread evenly across all buckets
Be deterministic: Same key always maps to same bucket
Be fast to compute: O(1) computation time

Common hash functions:

Division method	h(K) = K mod B
Multiplication method	h(K) = floor(B * (K * A mod 1)) where 0 < A < 1
Folding	Split key into parts, add them, take mod B
Mid-square	Square the key, extract middle digits, take mod B

Example with division method (B=10):

Example

Keys: 105, 237, 312, 489, 520, 741, 823, 956 h(105) = 105 mod 10 = 5 h(237) = 237 mod 10 = 7 h(312) = 312 mod 10 = 2 h(489) = 489 mod 10 = 9 h(520) = 520 mod 10 = 0 h(741) = 741 mod 10 = 1 h(823) = 823 mod 10 = 3 h(956) = 956 mod 10 = 6 All map to different buckets -> ideal distribution (no collisions)

The Overflow Problem

The fundamental weakness of static hashing: as data grows beyond the initial bucket capacity, overflow chains develop.

Example

Initial design: B=100 buckets, each holds 10 records (capacity: 1000 records) After growth: 5000 records inserted Result: +--------+-----------+-----------------------------+ | Bucket | Primary | Overflow Chain | +--------+-----------+-----------------------------+ | 0 | [10 recs] | -> [10] -> [10] -> [10] | 40 total | 1 | [10 recs] | -> [10] -> [10] | 30 total | 2 | [10 recs] | -> [10] -> [10] -> [10] -> [10] | 50 total | ... | | | +--------+-----------+-----------------------------+ Searching bucket 2 now requires 5 disk reads instead of 1! Performance degrades from O(1) to O(chain_length).

Handling Overflow — Strategies

Strategy	Description	Trade-off
Open addressing	Probe next bucket if current is full	Clustering, complex deletion
Overflow chaining	Linked list of extra blocks	Easy but degrades performance
Linear probing	Check bucket+1, bucket+2, ...	Primary clustering problem
Quadratic probing	Check bucket+1², bucket+2², ...	Less clustering

In database systems, overflow chaining is the standard approach because it keeps the hash function unchanged and allows buckets to grow independently.

When Static Hashing Fails

Problem 1	Too many records -> long overflow chains -> slow lookups
Problem 2	Too few records -> many empty buckets -> wasted space
Problem 3	Cannot resize without rehashing ALL records

Static Hashing vs. Dynamic Hashing

Feature	Static Hashing	Dynamic Hashing
Bucket count	Fixed at creation	Grows/shrinks with data
Overflow	Chains grow indefinitely	Buckets split (no chains)
Performance stability	Degrades over time	Stays O(1)
Reorganization	Full rehash needed	Incremental splits
Complexity	Simple	More complex
Examples	Basic hash files	Extendible hashing, Linear hashing

Practical Considerations

Choose static hashing when:

Database size is predictable and stable
Records are rarely inserted/deleted after initial load
Equality lookups dominate (no range queries)
Simplicity of implementation is important

Avoid static hashing when:

Data volume grows unpredictably
Long overflow chains are developing
Range queries are needed (hash destroys ordering)
The database cannot be taken offline for reorganization

Summary

Static hashing provides fast O(1) average-case equality lookups with a simple, deterministic structure. Its fixed bucket count makes it easy to implement but fragile under data growth — overflow chains degrade performance, and resizing requires a full offline reorganization. For growing datasets, dynamic hashing techniques (extendible or linear hashing) solve these problems by allowing the bucket count to adapt automatically.

Definition

Example

h: Key -> {0, 1, 2, ..., B-1} where B is fixed forever Example: h(key) = key mod 10 (always maps to buckets 0-9)

Static hashing provides O(1) average-case access for equality searches — you compute the hash, go to the bucket, and find the record. No searching through indexes or scanning multiple blocks.

Operations

Search (Equality Lookup)

To find record with key K

1. Compute bucket number: b = h(K)

2. Read the disk block for bucket b

3. Scan the block for record with key K

4. If not found and overflow chain exists -> follow chain, read next block

5. Return record (or "not found")

Cost

Best case: 1 disk read (record in primary bucket block)

Average case: 1 disk read (no overflow)

Worst case: 1 + chain_length disk reads (overflow)

Insert

Example

Delete

1. Compute bucket	b = h(K)
4. If found	remove it (mark slot as free or shift records)
5. If overflow blocks exist and are now empty	deallocate them
6. Optionally	move a record from overflow into the freed primary slot
Cost	Similar to search + 1 write

Hash Function Design

A good hash function should:

Distribute uniformly: Records spread evenly across all buckets
Be deterministic: Same key always maps to same bucket
Be fast to compute: O(1) computation time

Common hash functions:

Division method	h(K) = K mod B
Multiplication method	h(K) = floor(B * (K * A mod 1)) where 0 < A < 1
Folding	Split key into parts, add them, take mod B
Mid-square	Square the key, extract middle digits, take mod B

Example with division method (B=10):

Example

The Overflow Problem

The fundamental weakness of static hashing: as data grows beyond the initial bucket capacity, overflow chains develop.

Example

Handling Overflow — Strategies

Strategy	Description	Trade-off
Open addressing	Probe next bucket if current is full	Clustering, complex deletion
Overflow chaining	Linked list of extra blocks	Easy but degrades performance
Linear probing	Check bucket+1, bucket+2, ...	Primary clustering problem
Quadratic probing	Check bucket+1², bucket+2², ...	Less clustering

In database systems, overflow chaining is the standard approach because it keeps the hash function unchanged and allows buckets to grow independently.

When Static Hashing Fails

Problem 1	Too many records -> long overflow chains -> slow lookups
Problem 2	Too few records -> many empty buckets -> wasted space
Problem 3	Cannot resize without rehashing ALL records

Static Hashing vs. Dynamic Hashing

Feature	Static Hashing	Dynamic Hashing
Bucket count	Fixed at creation	Grows/shrinks with data
Overflow	Chains grow indefinitely	Buckets split (no chains)
Performance stability	Degrades over time	Stays O(1)
Reorganization	Full rehash needed	Incremental splits
Complexity	Simple	More complex
Examples	Basic hash files	Extendible hashing, Linear hashing

Practical Considerations

Choose static hashing when:

Database size is predictable and stable
Records are rarely inserted/deleted after initial load
Equality lookups dominate (no range queries)
Simplicity of implementation is important

Avoid static hashing when:

Data volume grows unpredictably
Long overflow chains are developing
Range queries are needed (hash destroys ordering)
The database cannot be taken offline for reorganization

Static Hashing

Definition

Operations

Search (Equality Lookup)

To find record with key K

Cost

Insert

Delete

Hash Function Design

The Overflow Problem

Handling Overflow — Strategies

When Static Hashing Fails

Static Hashing vs. Dynamic Hashing

Practical Considerations

Summary

Continue learning this concept

Static Hashing

Definition

Operations

Search (Equality Lookup)

To find record with key K

Cost

Insert

Delete

Hash Function Design

The Overflow Problem

Handling Overflow — Strategies

When Static Hashing Fails

Static Hashing vs. Dynamic Hashing

Practical Considerations

Summary

Continue learning this concept