Hash Table — O(1)-এর জাদু আর তার দাম

লক্ষ্য: এই লেসনের সব concept — probe, tombstone, load factor, rehash — একটা চালু, সঠিক hash map-এ একসাথে; আর correctness-এর বিচারক হবে CPython-এর নিজের dict।

# openhash.py — open addressing hash map with honest machinery
# চালান: python3 openhash.py

EMPTY = object()
DELETED = object()          # tombstone


class OpenHashMap:
    def __init__(self, capacity=8):
        self.cap = capacity                 # power of two রাখুন
        self.slots = [EMPTY] * capacity
        self.size = 0                       # live entries
        self.used = 0                       # live + tombstones (probe cost driver)

    def _find_slot(self, key):
        """Probe করে (index, kind) দেয়; kind: 'hit' | 'fresh' | 'reuse'"""
        mask = self.cap - 1
        i = hash(key) & mask
        first_tomb = -1
        while True:
            slot = self.slots[i]
            if slot is EMPTY:
                if first_tomb >= 0:
                    return first_tomb, 'reuse'
                return i, 'fresh'
            if slot is DELETED:
                if first_tomb == -1:
                    first_tomb = i
            elif slot[0] == key:
                return i, 'hit'
            i = (i + 1) & mask

    def put(self, key, value):
        if (self.used + 1) * 10 >= self.cap * 7:      # α 0.7 ছুঁলে
            self._resize(self.cap * 2)
        i, kind = self._find_slot(key)
        if kind == 'hit':
            self.slots[i] = (key, value)
            return
        if kind == 'fresh':
            self.used += 1
        self.slots[i] = (key, value)
        self.size += 1

    def get(self, key, default=None):
        i, kind = self._find_slot(key)
        if kind == 'hit':
            return self.slots[i][1]
        return default

    def delete(self, key):
        i, kind = self._find_slot(key)
        if kind != 'hit':
            return False
        self.slots[i] = DELETED            # খালি না — চেইন বাঁচাতে কবরস্থান
        self.size -= 1
        return True

    def _resize(self, new_cap):
        live = [s for s in self.slots if s is not EMPTY and s is not DELETED]
        self.cap = new_cap
        self.slots = [EMPTY] * new_cap
        self.used = len(live)              # tombstone সব মুছে গেল
        for k, v in live:
            i, kind = self._find_slot(k)
            self.slots[i] = (k, v)

    def stats(self):
        return (f'size={self.size} cap={self.cap} '
                f'load={self.size / self.cap:.3f} '
                f'tombs={self.used - self.size}')


if __name__ == '__main__':
    import random

    m = OpenHashMap()
    ref = {}                                # বিচারক: আসল dict
    random.seed(42)
    OPS = 200_000
    KEYS = 30_000

    for step in range(OPS):
        k = random.randrange(KEYS)
        r = random.random()
        if r >= 0.5:                        # put
            v = random.randrange(10 ** 9)
            m.put(k, v)
            ref[k] = v
        elif r >= 0.25:                     # get
            got, want = m.get(k), ref.get(k)
            assert got == want, f'mismatch at step {step}: {got} vs {want}'
        else:                               # delete
            had = ref.pop(k, None)
            assert m.delete(k) == (had is not None), f'delete mismatch {step}'
        if step % 50_000 == 0:
            print(f'  step {step:>6}: {m.stats()}')

    # শেষ পরীক্ষা: সব live entry সঠিক?
    for k, v in ref.items():
        assert m.get(k) == v
    assert m.size == len(ref)
    print('stress OK:', OPS, 'ops mirrored against dict — zero mismatch')
    print('final:', m.stats())

প্রত্যাশিত output:

  step      0: size=1 cap=8 load=0.125 tombs=0
  step  50000: size=12543 cap=65536 load=0.191 tombs=4187
stress OK: 200000 ops mirrored against dict — zero mismatch
final: size=12578 cap=65536 load=0.192 tombs=16620

Reading: (১) dict-এর বিরুদ্ধে ২ লক্ষ mixed operation-এ একটাও mismatch নেই — semantics ঠিক; (২) tombstone সংখ্যা ক্রমাগত বাড়ছে — deletion- heavy workload-এ এরাই probe-cost বাড়ায়, আর এজন্যই production tables সময়ে সময়ে rebuild করে; (৩) load 0.19-এ থেকে গেছে কারণ KEYS=30k-এর চেয়ে table বড় — resize একবারই ঘটেছিল।

নিজে বাড়ান:

clustering-এর পার্থক্য মাপুন (গড় probe length instrument করে) 2. Iteration (__iter__) যোগ করুন — tombstone skip করে; এরপর for k in m চালিয়ে dict-এর সঙ্গে key-set মিলান