Rehashing and extendible hashing
Rehashing resizes in-memory hash tables when load grows; extendible hashing grows a disk-friendly directory and splits buckets using hash-bit prefixes.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use hash-based indexing to keep lookups fast even as data grows. In-memory structures (caches, symbol tables) use rehashing to resize tables; on-disk indexes (databases, file systems) use extendible hashing to grow or shrink gracefully without expensive full rebuilds.
Key ideas
- Hash function: A deterministic function h that maps a key to a large integer. In array-based tables, the index is computed as h(key) mod m, where m is the table size.
- Collision: When two different keys map to the same index. Must be resolved by an algorithm.
- Open addressing: Collision resolution where all entries live in the same array; on collision we probe other slots (e.g., linear probing, quadratic probing, double hashing). No external pointers.
- Chaining: Collision resolution where each array cell holds a pointer to a linked list (or dynamic array) of entries sharing that index.
- Load factor (α): The ratio of stored entries n to table capacity m. Exact definition: α = n/m for open addressing; for chaining, α is the average list length. Assumption: m > 0.
- Rehashing (resizing): The operation of allocating a new hash table (usually with larger capacity), and re-inserting every active entry using the same or a new hash function so that the distribution remains good. Trigger: α crosses a threshold (commonly 0.7–0.8 for open addressing; may be higher for chaining).
- Amortized cost of rehashing (exact statement): Under doubling-resize strategy (when α exceeds a fixed constant threshold, allocate new table of capacity at least 2m and re-insert all n items), the amortized time per insertion is O(1). Assumptions: each re-insertion during a resize takes O(1) expected time (simple uniform hashing), and the number of resizes is O(log n) across n insertions. Derivation sketch: Over k insertions into capacities 1, 2, 4, …, each resize moves at most the current number of elements; total moves ≤ k + k/2 + k/4 + … < 2k, so average per insertion is O(1).
- Primary clustering (linear probing): A phenomenon where contiguous blocks of occupied cells grow, increasing probe lengths. Rehashing helps by increasing m, lowering α and shortening clusters.
- Extendible hashing: A dynamic hashing scheme that grows and shrinks a directory of pointers and splits/merges buckets based on the low-order bits of the hash value. Designed for disk blocks but works in memory too.
- Bucket: A container (typically a disk block) that can hold up to B records. Each bucket has a local depth (ld): the number of hash suffix bits used to determine membership in that bucket.
- Directory: An array of size 2^g where g is the global depth (gd). Entry i (0 ≤ i < 2^g) points to a bucket whose keys share the same low-order g-bit pattern equal to i. Multiple directory entries can point to the same bucket if that bucket’s ld < gd.
- Insert rule (exact algorithm):
- Compute h = hash(key) (a non-negative integer); compute index i = low gd bits of h.
- If directory[i] bucket has space (< B), insert key into that bucket.
- Else (bucket full): a) If bucket.ld < gd: split the bucket (increase bucket.ld by 1; create a new bucket with the same ld; redistribute keys between the two using the new ld bits; update only those directory entries that pointed to the old bucket and whose new ld-bit pattern selects the new bucket). Retry insertion. b) Else (bucket.ld == gd): double the directory (gd = gd + 1; duplicate pointers so both halves point to the same buckets); then perform step 3a. Retry insertion.
- Search rule: Compute i from low gd bits and search only that bucket. Expected O(1).
- Delete rule: Delete within the bucket. If a bucket and its buddy (the bucket differing in the most significant of its ld bits) together fit within one bucket and both have the same ld, they may be merged, decreasing ld by 1 and repointing directory entries. If after merges no bucket has ld == gd across an entire half of the directory, gd may be decreased by 1 (directory halved). Precise merge policy may vary in implementations.
- Correctness assumption for extendible hashing: The hash function distributes keys uniformly in the low-order bits used at any time (simple uniform hashing; low-order independence). If low bits are biased, use a good hash or mix bits.
Exact definitions often asked in exams:
- Definition: Extendible hashing is a dynamic hashing technique that uses a directory of size 2^gd indexed by the low gd bits of the hash; each directory entry points to a bucket with local depth ld ≤ gd. On overflow, a bucket is split by increasing ld, and the directory is doubled only when needed (ld == gd). On underflow, adjacent buckets with equal ld can be merged; gd may decrease if possible.
- Statement: Expected time complexity for search/insert/delete in a hash table with simple uniform hashing is O(1); in extendible hashing, expected I/O cost is O(1) buckets per operation (usually one directory access in memory plus one bucket access on disk).
Derivations universities commonly ask (step by step):
- Amortized O(1) for rehashing with doubling:
- Consider a sequence of n inserts into a table that doubles from sizes 1, 2, 4, …, 2^k.
- Each element is moved only when a resize happens; total moves ≤ n + n/2 + n/4 + … < 2n.
- Total insertion cost = O(n) normal inserts + O(n) moves = O(n), hence amortized O(1) per insert.
- Space overhead in extendible hashing:
- Directory size is 2^gd pointers. If many directory entries point to the same buckets (ld < gd), pointer duplication is the main overhead. Buckets store at most B records each, so total buckets ≤ ⌈number of records / B⌉ (ceil; accounts for partially filled buckets). The directory can be much smaller than a full static hash table when data are sparse in key space, and it grows only as needed.
Diagrams to draw (text description):
- Rehashing with linear probing:
- Draw an array of m cells labeled 0 … m−1. Show the initial insertions with arrows from h(k) to the first free slot by probing right (wrapping around). Label collisions and final positions. Then draw a larger array of size 2m, and arrows showing re-insertion of each key to its new h(k) mod 2m location. Mark load factor α before and after.
- Extendible hashing directory and buckets:
- Draw a small rectangle “Directory (gd = g)” with 2^g entries labeled with their g-bit binary indices (e.g., 00, 01, 10, 11 for gd=2). From each directory entry, draw an arrow to a bucket rectangle. On each bucket, write “ld = local depth” and list the keys inside. Indicate when multiple directory entries point to the same bucket (shared arrows). For a split, redraw with gd increased if needed, show the split bucket’s ld increased, keys redistributed by low-order bits, and directory entries updated.
Formulas
α = n / m— load factor α (dimensionless); n is number of stored entries; m is table capacity (number of buckets). For chaining, α = n/m equals the average list length; for open addressing, 0 ≤ α < 1.gd = ⌈log₂ |Directory|⌉— global depth gd (dimensionless bits); |Directory| is number of entries (must be a power of 2). Applies to extendible hashing.i = h(key) & ((1 << gd) - 1)— i is directory index (dimensionless);&is bitwise AND;<<is left shift. Applies when using low-order bits of a non-negative integer hash for extendible hashing.ld ≤ gd— local depth (ld) never exceeds global depth (gd). Applies to extendible hashing invariants.Expected probes (linear probing)— Unsuccessful search: ≈ 1 / (1 − α); Successful search: ≈ (1/2) · (1 + 1 / (1 − α)). Dimensionless; holds under simple uniform hashing for α < 1; use for intuition in exams.
Syntax to remember (Python-like pseudocode):
- Resizing trigger:
if n / m > alpha_threshold: rehash(new_m) - Doubling size to next power of two:
new_m = 1 << (m.bit_length()) - Linear probe step:
idx = (idx + 1) % m - Extendible hashing index:
idx = hash(key) & ((1 << gd) - 1) - Update directory on split: for all j in [0, 2^gd): if directory[j] is old_bucket and (j >> (ld-1)) & 1 == 1 then directory[j] = new_bucket
Worked examples
Example 1 — Python: Hash table with linear probing and rehashing when load factor exceeds 0.75
# Linear probing hash table with rehashing (integers as keys)
TOMBSTONE = object()
class HashTable:
def __init__(self, init_cap=8, alpha_threshold=0.75):
# capacity must be power of two for simple doubling
m = 1
while m < init_cap:
m <<= 1
self.m = m
self.n = 0
self.alpha_threshold = alpha_threshold
self.a = [None] * self.m
def _hash(self, key):
# stable integer hash
if not isinstance(key, int):
raise TypeError("Only int keys in this demo")
return key & 0x7FFFFFFF
def _find_slot(self, key):
m = self.m
idx = self._hash(key) % m
first_tomb = None
while True:
if self.a[idx] is None:
return (first_tomb if first_tomb is not None else idx, False)
if self.a[idx] is TOMBSTONE:
if first_tomb is None:
first_tomb = idx
else:
k, v = self.a[idx]
if k == key:
return (idx, True)
idx = (idx + 1) % m
def _rehash(self, new_m):
old = [x for x in self.a if x is not None and x is not TOMBSTONE]
self.m = new_m
self.a = [None] * self.m
self.n = 0
for k, v in old:
self.insert(k, v)
def _maybe_resize(self):
if self.n / self.m > self.alpha_threshold:
self._rehash(self.m * 2)
def insert(self, key, value):
idx, found = self._find_slot(key)
if found:
self.a[idx] = (key, value)
return False
self.a[idx] = (key, value)
self.n += 1
self._maybe_resize()
return True
def search(self, key):
idx, found = self._find_slot(key)
if found:
return self.a[idx][1]
return None
def delete(self, key):
idx, found = self._find_slot(key)
if found:
self.a[idx] = TOMBSTONE
self.n -= 1
return True
return False
if __name__ == "__main__":
ht = HashTable(init_cap=8, alpha_threshold=0.75)
# Insert 7 keys to exceed load factor threshold and trigger rehash
for k in [10, 18, 26, 35, 53, 14, 22]:
ht.insert(k, str(k))
print("Capacity after inserts:", ht.m)
print("Find 26:", ht.search(26) is not None)
print("Find 99:", ht.search(99) is not None)
print("Delete 26:", ht.delete(26))
print("Find 26:", ht.search(26) is not None)
Sample input
- No input; the program contains its own test sequence.
Exact output
Capacity after inserts: 16
Find 26: True
Find 99: False
Delete 26: True
Find 26: False
Explanation: Initial capacity 8; inserting 7 items makes α = 7/8 = 0.875, which exceeds 0.75, so the table rehashes to capacity 16. Searches and delete behave as shown.
Example 2 — Python: Extendible hashing (global/local depth, bucket splits)
# Extendible hashing demo with integer keys, low-order bits, bucket capacity = 2
class Bucket:
_next_id = 0
def __init__(self, ld, capacity=2):
self.ld = ld
self.capacity = capacity
self.keys = []
self.id = Bucket._next_id
Bucket._next_id += 1
def __repr__(self):
return f"B{self.id}(ld={self.ld}): {self.keys}"
class ExtHash:
def __init__(self, gd=1, bucket_capacity=2):
self.gd = gd
self.bucket_capacity = bucket_capacity
# start with two distinct buckets for suffix 0 and 1
b0 = Bucket(ld=gd, capacity=bucket_capacity)
b1 = Bucket(ld=gd, capacity=bucket_capacity)
self.dir = [b0, b1]
def _idx(self, key):
return key & ((1 << self.gd) - 1)
def _double_directory(self):
self.dir = self.dir + self.dir[:] # duplicate pointers
self.gd += 1
def _update_pointers_after_split(self, old_bucket, new_bucket):
# After increasing old_bucket.ld by 1, redirect indices where the new high bit is 1
ld = old_bucket.ld
for i in range(len(self.dir)):
if self.dir[i] is old_bucket:
if ((i >> (ld - 1)) & 1) == 1:
self.dir[i] = new_bucket
def insert(self, key):
while True:
i = self._idx(key)
b = self.dir[i]
if len(b.keys) < b.capacity:
b.keys.append(key)
return
# need to split
if b.ld == self.gd:
self._double_directory()
# recompute index under new gd
i = self._idx(key)
b = self.dir[i]
# split bucket b
b.ld += 1
new_b = Bucket(ld=b.ld, capacity=b.capacity)
self._update_pointers_after_split(b, new_b)
# redistribute keys currently in b (collect from all dir refs)
old_keys = b.keys
b.keys = []
for k in old_keys:
idx = k & ((1 << b.ld) - 1)
# If the new bit is 1, it should go to new_b; else stays in b
if ((idx >> (b.ld - 1)) & 1) == 1:
new_b.keys.append(k)
else:
b.keys.append(k)
# retry insertion (loop continues)
def dump(self):
print(f"Global depth: {self.gd}")
for i in range(len(self.dir)):
b = self.dir[i]
print(f"{i:0{self.gd}b} -> B{b.id} (ld={b.ld}): {b.keys}")
if __name__ == "__main__":
eh = ExtHash(gd=1, bucket_capacity=2)
for k in [7, 1, 5, 3, 9]:
eh.insert(k)
eh.dump()
Sample input
- No input; the program contains its own test sequence.
Exact output
Global depth: 3
000 -> B0 (ld=1): []
001 -> B1 (ld=3): [1, 9]
010 -> B0 (ld=1): []
011 -> B2 (ld=2): [7, 3]
100 -> B0 (ld=1): []
101 -> B3 (ld=3): [5]
110 -> B0 (ld=1): []
111 -> B2 (ld=2): [7, 3]
Explanation (brief):
- Start gd=1 with B0 for suffix 0 and B1 for suffix 1. Insert 7,1 into B1. Inserting 5 overflows B1 with ld=1==gd, so directory doubles (gd=2) and B1 splits into B1 (suffix 01) and B2 (suffix 11). Insert 3 goes to B2. Inserting 9 targets suffix 01 (bucket B1), which is full with ld=2==gd; directory doubles (gd=3), B1 splits into suffix 001 (B1) and 101 (B3), then 9 is inserted into B1. Directory entries that end with 11 point to B2, and those ending with 0 point to B0 (ld=1), which remains shared and empty for these inserts.
Example 3 — Model answer (theory): Compare rehashing and extendible hashing
- Rehashing is an in-memory resizing technique: when load factor α passes a threshold, allocate a new array (often doubling capacity) and re-insert all entries using h(key) mod new_m. Pros: simple, high cache locality, good for RAM-resident structures. Cons: resize is a big O(n) pause; not ideal for disk because it rewrites everything at once.
- Extendible hashing is a dynamic file hashing technique: a directory indexed by low-order gd bits points to buckets with local depths ld. On overflow, only one bucket is split; the directory doubles only when needed (ld == gd). Pros: expected O(1) I/O per operation; grows one bucket at a time; localized changes. Cons: directory pointer overhead; relies on good low-order bits; slightly more complex code.
- When to use: Rehashing for in-memory maps/caches with tolerant pause on rare resizes. Extendible hashing for disk-based indexes, large data that should avoid global rebuilds, and workloads with incremental growth.
Common mistakes
- Writing ld can exceed gd during split in extendible hashing; by definition ld ≤ gd must always hold (if ld == gd and split is needed, first double the directory, then split).
- Forgetting to update all directory entries that point to a split bucket; multiple indices may alias the same bucket when ld < gd.
- Off-by-one errors in bit tests: the “new bit” after increasing ld is at position (ld−1) (0-based), not at ld.
- In linear probing, not preserving tombstones for deletes; without tombstones, search may stop early and miss existing keys.
- Triggering rehash at α ≥ threshold vs α > threshold inconsistently; define and stick to one rule in code and in the explanation.
- Assuming worst-case O(1) for open addressing; worst-case is O(n). Expected O(1) holds only under simple uniform hashing.
For your exam
- Short notes: Advantages/disadvantages of rehashing vs extendible hashing; discuss clustering; typical α thresholds; where each is used (RAM vs disk).
- Algorithms: Step-by-step insert/search/delete for extendible hashing. Show the condition for doubling and the exact directory update on split. For rehashing, give the resizing algorithm and amortized analysis sketch.
- Tracing questions: “Given bucket capacity B=2, initial gd=1, insert sequence …, draw the directory and buckets after each insertion.” Include binary indices on the directory, show ld on each bucket, and list contents. State which entries alias the same bucket.
- Programs: Implement a hash table with linear probing and rehashing; or simulate extendible hashing splits. Full-marks programs handle collisions, resizing, and print clear state; avoid non-deterministic hashes.
- Complexity: State expected O(1) per op under simple uniform hashing; amortized O(1) inserts with doubling rehash; explain why.
- Diagrams: For extendible hashing, draw the directory with 2^gd entries labeled in binary, arrows to buckets with ld and contents; show split steps and updated pointers.
Quick check
- In extendible hashing, when exactly do we double the directory?
- Define load factor α and state a typical threshold that triggers rehashing for open addressing.
- In linear probing, why do we keep tombstones after delete?
Answers: 1) When an insertion overflows a bucket whose local depth ld equals the global depth gd; we double first, then split and reinsert. 2) α = n/m; typical threshold ≈ 0.7–0.8 (e.g., 0.75) for good performance. 3) To ensure searches do not stop early; tombstones preserve probe chains so existing keys beyond the deleted slot remain discoverable.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?