Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Extendible hashing: split buckets through a shared directory

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An extendible hash directory indexes a bucket by the low global-depth bits of a digest. Multiple directory entries can refer to one bucket when that bucket's local depth is smaller. A full bucket splits using its next local-depth bit. If local depth already equals global depth, the directory doubles first, so the new bit becomes addressable. Records are then redistributed between the original and new bucket, and directory references are redirected by that bit. This model uses a deliberately bounded eight-bit digest of nonnegative alert IDs and a Python dictionary inside each bucket. Once two or more distinct IDs share all eight digest bits, they remain together as a collision overflow rather than triggering an impossible ninth-bit split. Deletion removes a record but does not merge buckets or shrink the directory.

Operational case

Insert alert IDs 47, 51, 55, and 303 with bucket capacity two. Several low-bit prefixes must be distinguished, so the global directory reaches depth four; its sixteen entries refer to only five bucket objects. IDs 47 and 303 share the same eight-bit digest but still remain separate dictionary keys. Reading 303 returns its own incident record. Copying a directory entry during doubling does not clone its bucket: both entries initially point to the same object until a later split redirects some references. A consumer that assumes one unique bucket per directory position would double-count records during a scan.

Working Python program

python
class AlertBucket:
    def __init__(self, depth):
        self.depth = depth
        self.records = {}


class ExtendibleAlertDirectory:
    def __init__(self, bucket_capacity=2):
        if bucket_capacity < 1:
            raise ValueError("bucket capacity must be positive")
        self.bucket_capacity = bucket_capacity
        self.global_depth = 1
        self.directory = [AlertBucket(1), AlertBucket(1)]

    @staticmethod
    def _hash(alert_id):
        if not isinstance(alert_id, int) or alert_id < 0:
            raise ValueError("alert ID must be a nonnegative integer")
        return alert_id & 255

    def _index(self, alert_id):
        return self._hash(alert_id) & ((1 << self.global_depth) - 1)

    def get(self, alert_id):
        return self.directory[self._index(alert_id)].records[alert_id]

    def delete(self, alert_id):
        del self.directory[self._index(alert_id)].records[alert_id]

    def set(self, alert_id, state):
        index = self._index(alert_id)
        self.directory[index].records[alert_id] = state
        while len(self.directory[self._index(alert_id)].records) > self.bucket_capacity:
            bucket = self.directory[self._index(alert_id)]
            if bucket.depth == 8:
                break  # Identical eight-bit hashes remain in one collision bucket.
            old_depth = bucket.depth
            if old_depth == self.global_depth:
                self.directory += self.directory[:]
                self.global_depth += 1
            upper = AlertBucket(old_depth + 1)
            bucket.depth += 1
            for directory_index, candidate in enumerate(self.directory):
                if candidate is bucket and directory_index & (1 << old_depth):
                    self.directory[directory_index] = upper
            records = list(bucket.records.items())
            bucket.records.clear()
            for stored_id, stored_state in records:
                self.directory[self._index(stored_id)].records[stored_id] = stored_state


directory = ExtendibleAlertDirectory()
for alert_id in (47, 51, 55, 303):
    directory.set(alert_id, f"incident-{alert_id}")
print("depth=", directory.global_depth, " buckets=", len({id(bucket) for bucket in directory.directory}),
      " collision=", directory.get(303), sep="")

Output

Output
depth=4 buckets=5 collision=incident-303

Time, space, and tradeoff

A lookup computes a directory slot and then uses expected O(1) Python dictionary access; a hostile set of equal digests is handled in one overflow bucket and inherits that dictionary's behavior. A split may scan and redistribute B records in its old bucket, while doubling copies 2^G directory references at global depth G. One insertion can therefore cost O(B + 2^G), and repeated splits may raise that cost further. The directory uses O(2^G) references plus stored records and bucket metadata, with G capped at eight here. This is an in-memory teaching model, not a paged database index with write-ahead logging, durability, bucket merge, or concurrency control.

Common Mistakes

  • Do not double the directory whenever any bucket splits; double only at equal local and global depth.
  • Do not treat every directory entry as a distinct bucket object.
  • Do not keep splitting after all configured hash bits are consumed.
  • Do not claim deletion contracts the directory in this implementation.

Connected lessons

Compare lookup and update behavior with Bitmap hash tries: copy paths for immutable alert maps, Ternary search trees: branch by character and continue prefixes, Binary radix routing: choose the longest matching prefix, then run the index audit and contract quiz.

Linear hashing: split one bucket at a time as a table grows adds a distinct structure contract to compare.

data structures
hash-tables
Storage details