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

Linear hashing: split one bucket at a time as a table grows

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

Linear hashing grows a hash table by splitting buckets in fixed round-robin order. A level defines a base modulus; buckets before the split pointer use the doubled modulus, while later buckets still use the base. A split appends one bucket, redistributes only the pointed-to bucket with the doubled modulus, and advances the pointer. When the pointer completes a round, the level increases and the pointer resets. This teaching model stores nonnegative integer case IDs in Python sets and starts with two buckets. It splits when global average occupancy exceeds a configured count. A bucket may still overflow its nominal capacity under skew; the capacity is a growth trigger, not a hard per-bucket limit.

Operational case

With a trigger of two IDs per bucket, inserting seven case IDs expands the table from two to four buckets. The fourth bucket is not obtained by rehashing every stored case ID in one stop-the-world pass. An ID is always located by its current level and split pointer, so membership for 61 remains true after intervening splits. Removing 29 changes membership but does not contract the table. A service that assumes all buckets use the same modulus during a partial round will send some old keys to the wrong bucket and report false negatives.

Working Python program

python
class LinearCaseIndex:
    def __init__(self, bucket_capacity=3):
        if bucket_capacity < 1:
            raise ValueError("bucket capacity must be positive")
        self.bucket_capacity = bucket_capacity
        self.level = 0
        self.split = 0
        self.buckets = [set(), set()]
        self.size = 0

    def bucket_for(self, case_id):
        if case_id < 0:
            raise ValueError("case IDs must be nonnegative")
        base = 2 << self.level
        slot = case_id % base
        if slot < self.split:
            slot = case_id % (base * 2)
        return slot

    def contains(self, case_id):
        return case_id in self.buckets[self.bucket_for(case_id)]

    def insert(self, case_id):
        slot = self.bucket_for(case_id)
        if case_id in self.buckets[slot]:
            return False
        self.buckets[slot].add(case_id)
        self.size += 1
        if self.size > len(self.buckets) * self.bucket_capacity:
            self._split_next()
        return True

    def remove(self, case_id):
        slot = self.bucket_for(case_id)
        if case_id not in self.buckets[slot]:
            return False
        self.buckets[slot].remove(case_id)
        self.size -= 1
        return True

    def _split_next(self):
        base = 2 << self.level
        old_slot = self.split
        self.buckets.append(set())
        old_keys = self.buckets[old_slot]
        self.buckets[old_slot] = set()
        for case_id in old_keys:
            self.buckets[case_id % (base * 2)].add(case_id)
        self.split += 1
        if self.split == base:
            self.level += 1
            self.split = 0


if __name__ == "__main__":
    index = LinearCaseIndex(bucket_capacity=2)
    for case_id in [19, 29, 47, 61, 83, 103, 127]:
        index.insert(case_id)
    print("buckets:", len(index.buckets), "split:", index.split)
    print("has 61:", index.contains(61))
    print("removed 29:", index.remove(29))
    print("has 29:", index.contains(29))

Output

Output
buckets: 4 split: 0
has 61: True
removed 29: True
has 29: False

Time, space, and tradeoff

Locating a bucket uses O(1) integer arithmetic. Membership, insertion, and removal then pay for that bucket's set operation; expected O(1) lookup depends on ordinary hashing and a usable distribution, while adversarial skew has no fixed bucket-size bound. A split takes O(B) time and temporary space for B entries in the pointed-to bucket, not necessarily the bucket that triggered growth. Table storage is O(N plus bucket count). This example does not persist bucket pages, manage overflow chains, shrink after deletion, or handle concurrent readers during a split. Extendible hashing uses a different directory-doubling policy.

Common Mistakes

  • Do not use the doubled modulus for buckets that have not split yet.
  • Do not split only the bucket that happened to overflow.
  • Do not interpret the occupancy trigger as a hard collision limit.
  • Do not assume deletion contracts this grow-only implementation.

Connected lessons

Compare its update and query contract with Compressed 2D Fenwick trees: toggle known points and count rectangles, Persistent two-list queues: fork FIFO dispatch history, Balanced-parentheses trees: encode an ordered hierarchy, then complete the structure audit and decision quiz.

Two-level perfect hashing: exact static case membership adds a distinct structure contract to compare.

data structures
hash-tables
Storage details