DSA Hash Tables and Collisions

How it works

This teaching table uses a deliberately simple character-sum hash and separate chaining. It is not Python’s production dict algorithm or a secure hash. Updating an existing key replaces its value without adding another entry; deletion removes only the matching key. The fixed bucket count makes collisions easy to inspect, but a real growing table needs an explicit load-factor and resizing policy. The key length and equality comparison costs also matter.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as hash-buckets.py and run python hash-buckets.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

class BucketMap:
    def __init__(self, capacity=3):
        if type(capacity) is not int or capacity < 1:
            raise ValueError("Positive capacity required")
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def bucket(self, key):
        if not isinstance(key, str):
            raise ValueError("String keys required")
        return self.buckets[sum(map(ord, key)) % len(self.buckets)]

    def put(self, key, value):
        bucket = self.bucket(key)
        for index, (stored, _) in enumerate(bucket):
            if stored == key:
                bucket[index] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1

    def get(self, key):
        for stored, value in self.bucket(key):
            if stored == key:
                return value
        raise KeyError(key)

    def delete(self, key):
        bucket = self.bucket(key)
        for index, (stored, _) in enumerate(bucket):
            if stored == key:
                bucket.pop(index)
                self.size -= 1
                return
        raise KeyError(key)

table = BucketMap(3)
table.put("gate", 7)
table.put("date", 4)
print(table.bucket("gate") is table.bucket("date"))
table.put("gate", 9)
table.delete("date")
print(table.get("gate"), table.size)

Expected result

True
9 1

Gate and date share a bucket but retain independent values. Replacing gate keeps its identity, and deleting date leaves gate intact. The property tests exercise collisions, missing keys and repeated updates against an ordinary dictionary model.

Time, space and assumptions

Hashing a string of length m costs O(m) in this model. Bucket scans are O(b) for b colliding entries, with O(n) worst-case lookup; approximately constant expected bucket work needs appropriate distribution and controlled load.