DSA A Hash Set from Scratch

The problem

A hash set is a store that keeps each value at most once and answers membership questions. This lesson builds one from scratch, with plain lists only. No real set is used inside it.

The spec has three operations. Add stores a value if it is absent. Contains reports whether a value is stored. Remove deletes a value if it is present, and the operation sequence below is the test every version in this article must pass.

ops = [
    ("add", 4, None),
    ("add", 9, None),
    ("add", 14, None),
    ("add", 4, None),
    ("contains", 4, True),
    ("contains", 20, False),
    ("remove", 9, None),
    ("contains", 9, False),
    ("contains", 14, True),
]
for name, value, expected in ops:
    if expected is None:
        print(name, value)
    else:
        print(name, value, "-> expected:", expected)

Read the script in order. The value 4 is added twice and must be stored once. The value 9 is removed midway, so its second contains answers False while 14, added before the removal, still answers True.

Intuition: one plain list passes the small tests

The first idea keeps every value in one list. Add appends after a membership scan. Contains is that same scan. Remove finds and deletes.

Small tests pass. The trap is the scan itself. Every operation walks the list from the front, and the walk length grows with every value ever added.

def list_contains(values, target):
    scanned = 0
    for item in values:
        scanned += 1
        if item == target:
            return True, scanned
    return False, scanned

for size in [5, 50, 500]:
    values = list(range(size))
    found, scanned = list_contains(values, size - 1)
    print("stored values:", size, "- contains last value scanned:", scanned)
found, scanned = list_contains(list(range(500)), 999)
print("missing value in 500 stored - scanned:", scanned)

The last value costs a full pass. A missing value costs a full pass too, because only the end of the list proves absence. One list turns every question into a walk past everything stored before it.

Brute force: the list-backed set

The list-backed version is the brute force. It honours the whole spec. Add checks before appending, so duplicates never enter.

Correctness was never its problem. Cost is its problem. The counter below charges one unit per item examined, across the whole script.

class ListSet:
    def __init__(self):
        self.values = []
        self.scanned = 0

    def add(self, value):
        if not self.contains(value):
            self.values.append(value)

    def contains(self, value):
        for item in self.values:
            self.scanned += 1
            if item == value:
                return True
        return False

    def remove(self, value):
        if value in self.values:
            self.values.remove(value)

mine = ListSet()
ops = [
    ("add", 4, None),
    ("add", 9, None),
    ("add", 14, None),
    ("add", 4, None),
    ("contains", 4, True),
    ("contains", 20, False),
    ("remove", 9, None),
    ("contains", 9, False),
    ("contains", 14, True),
]
for name, value, expected in ops:
    if name == "add":
        mine.add(value)
    elif name == "remove":
        mine.remove(value)
    else:
        print("contains", value, "->", mine.contains(value), "expected:", expected)
print("stored, sorted:", sorted(mine.values))
print("items scanned by contains and add checks:", mine.scanned)

Nine operations on at most three stored values already scanned twelve items inside the counted methods. The count looks harmless only because the script is tiny. Section 2 showed what the same scan costs at 500 stored values.

The optimal solution: buckets chosen by a hash

A hash function sends each value to one small bucket list, and every operation then touches only that one bucket. That one sentence is the whole design.

The hash here is value % 5, the remainder after division by 5. Five buckets exist, numbered 0 to 4. A collision happens when two values share one bucket, and the bucket list simply holds both.

class HashSet:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    def add(self, value):
        bucket = self.buckets[value % 5]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        return value in self.buckets[value % 5]

    def remove(self, value):
        bucket = self.buckets[value % 5]
        if value in bucket:
            bucket.remove(value)

    def contents(self):
        found = []
        for bucket in self.buckets:
            found.extend(bucket)
        return sorted(found)

mine = HashSet()
real = set()
ops = [
    ("add", 4, None),
    ("add", 9, None),
    ("add", 14, None),
    ("add", 4, None),
    ("contains", 4, True),
    ("contains", 20, False),
    ("remove", 9, None),
    ("contains", 9, False),
    ("contains", 14, True),
]
agree = True
for name, value, expected in ops:
    if name == "add":
        mine.add(value)
        real.add(value)
    elif name == "remove":
        mine.remove(value)
        real.discard(value)
    else:
        got = mine.contains(value)
        want = value in real
        agree = agree and got == want == expected
        print("contains", value, "-> mine:", got, "real set:", want, "expected:", expected)
print("contents, sorted:", mine.contents())
print("real set, sorted:", sorted(real))
print("every check agrees:", agree)

Every contains check agrees with Python's own set on the same script. The sorted contents agree too. Sorting is used only for printing, never inside the set itself.

Walkthrough: the script, bucket by bucket

Values 4, 9 and 14 all hash to bucket 4, because each leaves remainder 4 on division by 5. That one bucket carries the whole story of this script. The state below prints after every operation.

class HashSet:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    def add(self, value):
        bucket = self.buckets[value % 5]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        return value in self.buckets[value % 5]

    def remove(self, value):
        bucket = self.buckets[value % 5]
        if value in bucket:
            bucket.remove(value)

mine = HashSet()
mine.add(4)
print("add 4 ->", mine.buckets)
mine.add(9)
print("add 9 ->", mine.buckets)
mine.add(14)
print("add 14 ->", mine.buckets)
mine.add(4)
print("add 4 again ->", mine.buckets)
mine.remove(9)
print("remove 9 ->", mine.buckets)
print("contains 14 ->", mine.contains(14))

The duplicate add changes nothing. The membership check inside add sees 4 already in bucket 4 and skips the append. Removing 9 shortens bucket 4 and leaves its neighbours untouched.

Complexity

A list-backed contains scans up to n items for n stored values, so its time is O(n) per operation. A bucket contains scans only its own bucket, which holds about n divided by the bucket count on average, so its average time is O(1) when the bucket count grows with the data.

Both versions store each value once, so both use O(n) space. The bucket version adds one small list object per bucket, and that overhead is fixed by the bucket count.

def list_scan(values, target):
    scanned = 0
    for item in values:
        scanned += 1
        if item == target:
            return scanned
    return scanned

def bucket_scan(buckets, target):
    scanned = 0
    for item in buckets[target % 5]:
        scanned += 1
        if item == target:
            return scanned
    return scanned

for size in [10, 100]:
    values = list(range(size))
    buckets = [[] for _ in range(5)]
    for v in values:
        buckets[v % 5].append(v)
    target = size - 1
    print("stored:", size, "- list scan for last value:", list_scan(values, target), " bucket scan:", bucket_scan(buckets, target))

Counts beat clocks here. The list scan grows with the store. The bucket scan grows with one bucket only, which is a fifth of the store at five buckets, and real hash sets add buckets as they grow to keep that share small.

Edge cases and pitfalls

Removing a missing value must change nothing. The remove method checks membership in the bucket first. An unguarded removal would raise an error on a value that was never added.

A collision is not an error. Values 4, 9 and 14 share bucket 4 and coexist there. A bucket that holds several values is the design working, not the design failing.

class HashSet:
    def __init__(self):
        self.buckets = [[] for _ in range(5)]

    def add(self, value):
        bucket = self.buckets[value % 5]
        if value not in bucket:
            bucket.append(value)

    def contains(self, value):
        return value in self.buckets[value % 5]

    def remove(self, value):
        bucket = self.buckets[value % 5]
        if value in bucket:
            bucket.remove(value)

mine = HashSet()
print("contains on empty set:", mine.contains(3))
mine.remove(3)
print("remove missing, still empty:", mine.buckets)
mine.add(4)
mine.add(9)
mine.add(14)
print("three values in bucket 4:", mine.buckets[4])
mine.remove(9)
print("after removing the middle one:", mine.buckets[4])
print("4 still present:", mine.contains(4), "- 14 still present:", mine.contains(14))
mine.add(4)
print("duplicate add, bucket 4:", mine.buckets[4])

The middle removal is the sharpest test. Deleting 9 from a shared bucket must not disturb 4 or 14. The final prints show both neighbours intact.