""" 05 - Hashing: scratch থেকে বানানো একটা ছোট্ট hash map, সাথে dict/set/Counter demo। লক্ষ্য: Python-এর dict-কে যে machinery জাদুকরী বানায়, সেটা চোখে দেখা। - MiniHashMap separate chaining ব্যবহার করে (প্রতিটা bucket একটা Python list)। - Load factor একটা threshold পেরোলে এটা resize (rehash) করে। - সবকিছু শুধু standard library দিয়ে। File-টা সরাসরি চালাও: python implementation.py নিচের সব assert চুপচাপ pass করতে হবে; demo একটা ছোট tour print করে। """ from collections import Counter, defaultdict class MiniHashMap: """Separate chaining আর resizing সহ একটা beginner-friendly hash map। Layout (concept.md-র সেই ছবিটা): buckets[0] -> [(key, value), (key, value), ...] buckets[1] -> [] buckets[2] -> [(key, value)] ... প্রতিটা bucket হলো (key, value) pair-এর একটা ছোট list — এটাই "chain"। """ def __init__(self, initial_buckets=8): # কয়েকটা খালি bucket দিয়ে শুরু। self._buckets = [[] for _ in range(initial_buckets)] self._size = 0 # কয়টা key->value pair এখানে আছে self._max_load = 0.75 # size/buckets এটা ছাড়ালে resize # ---------- internal helpers ------------------------------------- def _bucket_index(self, key): """Fingerprint থেকে ঠিকানা: key-কে hash করো, bucket index-এ মুড়ে দাও।""" return hash(key) % len(self._buckets) def _resize(self): """Bucket সংখ্যা double করো আর প্রতিটা pair নতুন করে বসাও। Resize-এর পর `hash(key) % len(buckets)` নতুন উত্তর দেয়, তাই প্রতিটা pair-কে rehash করে তার নতুন ঘরে পাঠাতে হয়। এর খরচ O(n), কিন্তু এত বিরল ঘটে যে insert-গুলো amortized O(1)-ই থাকে। """ old_buckets = self._buckets self._buckets = [[] for _ in range(2 * len(old_buckets))] self._size = 0 for chain in old_buckets: for key, value in chain: self.put(key, value) # স্বাভাবিক পথ দিয়েই re-insert # ---------- public API -------------------------------------------- def put(self, key, value): """Insert বা update। Average O(1)।""" idx = self._bucket_index(key) chain = self._buckets[idx] # Key যদি এই chain-এ আগে থেকেই থাকে, তার value overwrite করো। for i, (k, _) in enumerate(chain): if k == key: chain[i] = (key, value) return # নতুন key: chain-এ append করো। chain.append((key, value)) self._size += 1 # Chain ছোট রাখো: বেশি ভরে গেলে resize। if self._size / len(self._buckets) > self._max_load: self._resize() def get(self, key, default=None): """Key lookup। Average O(1): একটা hash, একটা jump, ছোট্ট scan।""" idx = self._bucket_index(key) for k, v in self._buckets[idx]: if k == key: return v return default def remove(self, key): """Key delete করো। Key থাকলে True ফেরত দেয়।""" idx = self._bucket_index(key) chain = self._buckets[idx] for i, (k, _) in enumerate(chain): if k == key: chain.pop(i) self._size -= 1 return True return False def __contains__(self, key): # `key in my_map` চালু করে। sentinel = object() # unique marker, কোনো stored value-র সমান হতে পারে না return self.get(key, sentinel) is not sentinel def __len__(self): return self._size def items(self): """প্রতিটা (key, value) pair yield করে (order = bucket order, insertion না)।""" for chain in self._buckets: for pair in chain: yield pair def debug_picture(self): """Bucket-গুলোর একটা ASCII ছবি ফেরত দেয় — শেখার জন্য দারুণ।""" lines = [] for i, chain in enumerate(self._buckets): shown = ", ".join(f"{k!r}:{v!r}" for k, v in chain) lines.append(f" bucket {i:>2}: [{shown}]") load = self._size / len(self._buckets) lines.append(f" size={self._size}, buckets={len(self._buckets)}, load={load:.2f}") return "\n".join(lines) # --------------------------------------------------------------------- # Python-এর built-in দিয়ে pattern demo (বাস্তবে এই tool-গুলোই ব্যবহার করবে) # --------------------------------------------------------------------- def two_sum(nums, target): """Complement lookup: search না করে, যা দেখেছ সেটা মনে রাখো। একবার হাঁটো। প্রতিটা x-এর জন্য দরকারি partner হলো target - x। Dict-কে জিজ্ঞেস করো partner আগেই এসেছে কি না। """ seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] def group_anagrams(words): """Canonical key দিয়ে grouping: sorted letters একটা anagram class চেনায়।""" groups = defaultdict(list) for w in words: groups["".join(sorted(w))].append(w) return list(groups.values()) def has_duplicate(nums): """Seen-set: O(1) membership, O(n^2) pairwise check-কে O(n) বানিয়ে দেয়।""" seen = set() for x in nums: if x in seen: return True seen.add(x) return False def subarray_sum_equals_k(nums, k): """Prefix sum + hash map: এক pass-এ sum k-ওয়ালা subarray গোনো। sum(i..j] == prefix[j] - prefix[i], তাই প্রতিটা j-তে প্রশ্ন: "আগের কয়টা prefix-এর মান prefix[j] - k?" """ count = 0 prefix = 0 seen = {0: 1} # খালি prefix-টা for x in nums: prefix += x count += seen.get(prefix - k, 0) seen[prefix] = seen.get(prefix, 0) + 1 return count # --------------------------------------------------------------------- # Demo + tests # --------------------------------------------------------------------- if __name__ == "__main__": print("=== MiniHashMap tour ===") m = MiniHashMap(initial_buckets=4) for fruit, price in [("apple", 3), ("pear", 2), ("plum", 5), ("fig", 7)]: m.put(fruit, price) print(m.debug_picture()) # chain-গুলো দেখো (হয়তো একটা resize-ও) # --- MiniHashMap correctness --- assert m.get("apple") == 3 assert m.get("plum") == 5 assert m.get("kiwi") is None assert m.get("kiwi", -1) == -1 assert "pear" in m and "kiwi" not in m assert len(m) == 4 m.put("apple", 30) # update, duplicate না assert m.get("apple") == 30 assert len(m) == 4 assert m.remove("fig") is True assert m.remove("fig") is False # আগেই চলে গেছে assert len(m) == 3 assert "fig" not in m # একটু চাপ দাও: কয়েকটা resize ঘটাও, প্রতিটা value টিকে আছে কি না দেখো। big = MiniHashMap(initial_buckets=4) for i in range(200): big.put(f"key{i}", i * i) assert len(big) == 200 assert all(big.get(f"key{i}") == i * i for i in range(200)) assert sorted(v for _, v in big.items()) == sorted(i * i for i in range(200)) # --- dict / set / Counter built-ins --- freq = {} for ch in "banana": freq[ch] = freq.get(ch, 0) + 1 assert freq == {"b": 1, "a": 3, "n": 2} c = Counter("mississippi") assert c["s"] == 4 assert c["z"] == 0 # missing -> 0, কখনো KeyError না assert (Counter("aab") - Counter("ab")) == Counter({"a": 1}) dd = defaultdict(list) dd["x"].append(1) dd["x"].append(2) assert dd["x"] == [1, 2] s = {1, 2, 3} assert (s & {3, 4}) == {3} assert (s | {4}) == {1, 2, 3, 4} assert (s - {1}) == {2, 3} # --- pattern functions --- assert two_sum([3, 8, 5, 4], 9) == [2, 3] assert two_sum([2, 7, 11, 15], 9) == [0, 1] assert two_sum([1, 2], 100) == [] groups = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) canon = sorted(tuple(sorted(g)) for g in groups) assert canon == [("ate", "eat", "tea"), ("bat",), ("nat", "tan")] assert has_duplicate([3, 1, 4, 1]) is True assert has_duplicate([3, 1, 4]) is False assert subarray_sum_equals_k([1, 1, 1], 2) == 2 assert subarray_sum_equals_k([1, 2, 3], 3) == 2 # [1,2] আর [3] assert subarray_sum_equals_k([1, -1, 0], 0) == 3 # [1,-1], [-1,...? ] -> [1,-1],[0],[1,-1,0] print("\nAll asserts passed. Hashing toolkit verified.")