7.5Hashing: static and extendible
The idea
Hashing maps a key straight to a bucket. Extendible hashing uses a growing directory so buckets can split without rehashing everything.
Think of it like this: A mail room with pigeonholes: the first letters of the address pick the hole; when a hole overflows, you add more holes.
Why it exists
Hashing questions ask about the directory size, depths and lookup cost.
How it works
- Hash the key to bits; the first d bits (global depth) index the directory.
- Insert into the bucket; if it is full, split it (local depth + 1).
- If local depth equals global depth, first double the directory.
- Equality search is O(1), but range queries are not supported.
Worked example: Bucket capacity 2; keys 4, 8, 12 hash to 00100, 01000, 01100.
All start with 0 for d = 1, so the first bucket overflows; the directory doubles to d = 2 and it splits into prefixes 00 and 01.
Now play with it
- →Insert keys one at a time and watch the directory double.
- →Increase the bucket capacity to 3.
Press Next step to insert the first key.
- insert 4 (00100)
- insert 8 (01000)
- insert 12 (01100); bucket full, directory doubles to 2 bits; bucket split (local depth 2)
- insert 20 (10100)
- insert 24 (11000)
- insert 28 (11100); bucket split (local depth 2)
- insert 31 (11111); bucket full, directory doubles to 3 bits; bucket split (local depth 3)
- insert 2 (00010)
When a full bucket has local depth = global depth, the directory doubles; if it is smaller, only the bucket splits and the directory pointers are redirected. A lookup always costs one directory access plus one bucket access.
Check yourself
In extendible hashing the directory doubles when
Exam notes (the dense version)
Static hashing sends a key to bucket h(k) among a fixed number of buckets; overflow is handled by chaining. Extendible hashing keeps a directory of 2^d pointers indexed by the first d bits of the hash (d = global depth); each bucket has a local depth. A full bucket splits; if its local depth equals the global depth the directory doubles. Linear hashing grows one bucket at a time in a fixed order without a directory. Hashing gives O(1) equality search but no range search.
Previous year questions: File Organisation & Indexing (9)
PYQs are grouped by topic, so this is the full set for File Organisation & Indexing; try the ones that match this subtopic. Open all 9 on the topic page.