05 — Hashing (Hash Maps, Hash Sets, and Friends)

এখান থেকে শুরু করো

প্রথমে ধারণা, তারপর সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ, তারপর কোন প্রশ্নে কোন pattern পড়ো। প্রয়োজন হলে operation ও খরচ পাশে রাখো। সমস্ত problem ও বাংলা নোট এবং উৎসের তালিকা সরাসরি খোলা যাবে।

ধাপ	কী শিখবে	প্রথম অনুশীলন
1	আগে দেখা value মনে রাখা	Contains Duplicate
2	দরকারি সঙ্গী খোঁজা	Two Sum
3	প্রতিটি অক্ষর কতবার	Valid Anagram
4	সমতুল্য item group করা	Group Anagrams
5	prefix-এর frequency রাখা	Subarray Sum K
6	count ও window একসঙ্গে	Minimum Window

প্রতিটি ধাপে আগে ছোট input নিজে আঁকো, তারপর code লেখো। পরের ধাপে যাওয়ার আগে বলো: কোন তথ্য রাখছি, প্রতি ধাপে কোন নিয়ম ঠিক থাকছে, এবং কাজের মোট খরচ কত?

বাস্তব প্রোগ্রামে সিদ্ধান্ত নেওয়া

প্রোগ্রামে দরকার	key → value	কেন উপযোগী	খেয়াল রাখবে
log-এ প্রতিটি error code কতবার এসেছে	code → count	এক pass-এ frequency	distinct code যত, memory তত
import-এর duplicate record শনাক্ত	stable record ID → seen	প্রতিবার পুরো পুরনো list scan লাগে না	একই ID মানেই একই record কি না আগে নির্ধারণ করো
dictionary-তে anagram group	sorted letters → words	একই signature এক bucket-এ	key বানানোর sorting খরচও গুনতে হবে
cache থেকে ID দিয়ে record নেওয়া	ID → record	গড়ে O(1) lookup	cache eviction ও persistence আলাদা design
নির্দিষ্ট মোটের contiguous transaction গোনা	prefix sum → frequency	আগে দেখা complement একবারেই পাওয়া যায়	negative value থাকলেও কাজ করে

Interview coding-এ সবচেয়ে বেশি ব্যবহৃত trick হলো hashing। Array যদি তোমার হাত হয়, তাহলে hashing হলো তোমার স্মৃতি।

এই data structure-টা কী?

Hash table key → value pair জমা রাখে আর তিনটা প্রশ্নের উত্তর প্রায় সাথে সাথে দিয়ে দেয়:

• "এই key-টা কি আমার কাছে আছে?"
• "এই key-র জন্য কোন value রেখেছিলাম?"
• "এই key-টা মুছে দাও।"

Python-এ hashing-এর সাথে তোমার দেখা হয় dict, set, collections.Counter, আর collections.defaultdict হিসেবে। ভেতরে ভেতরে সবগুলো একই idea ব্যবহার করে: key-কে একটা সংখ্যায় (the hash) বদলে ফেলো, আর সেই সংখ্যা দিয়ে array-র ঠিক slot-টায় সরাসরি লাফ দাও।

কেন এটা দরকার (কোন কষ্টটা দূর করে)

ভাবো একটা সাধারণ list-এ একটা নাম খুঁজছ:

• Unsorted list: প্রতিটা item চেক করো → প্রতি lookup-এ O(n)।
• Sorted list: binary search → O(log n), কিন্তু insert করলে sorted রাখতে হয়, যেটা slow।

Hashing বলে: খোঁজা বন্ধ করো। Item-টা থেকেই হিসেব করে ফেলো জিনিসটা কোথায় থাকতে বাধ্য, আর সরাসরি সেখানে চলে যাও। Average lookup, insert, আর delete — সবই হয়ে যায় O(1)। এতেই "loop-এর ভেতরে loop" solution-গুলো single-pass solution-এ বদলে যায়।

বাস্তব software-এ কোথায় ব্যবহার হয়

• Python-এর নিজের object system: প্রতিটা attribute access (obj.name) একটা dict-এর ভেতর দিয়ে যায়।
• Database index আর in-memory cache (Redis আসলে একটা বিশাল hash table)।
• De-duplication: "এই user / URL / file checksum কি আগে দেখেছি?"
• জিনিস গোনা: word frequency, log analysis, vote tally।
• Router আর compiler: symbol table, MAC address table।

Prerequisites

• Array আর basic loop (../02-arrays-and-strings/ যদি তোমার repo-তে থাকে, না হলে যেকোনো array basics)।
• Big-O intuition: O(1), O(n), O(n^2) কেমন লাগে সেই অনুভূতি।
• Python basics: function, for loop, if।

শেখার আগে কী revise করবে

• Modulo operator % — hashing এটা ব্যবহার করে বড় সংখ্যাকে ছোট index-এ মুড়ে ফেলতে।
• Python list-এ index কীভাবে কাজ করে (a[i] হলো O(1))।
• Tuple বনাম list (tuple dict-এর key হতে পারে, list পারে না — কেন, সেটা এখানে শিখবে)।

Learning goals

• [ ] এক বাক্যে বলতে পারা dict lookup average-এ কেন O(1)।
• [ ] স্মৃতি থেকে buckets-and-chaining ছবিটা আঁকতে পারা।
• [ ] Collision কী আর সেটা সামলানোর একটা উপায় বলতে পারা।
• [ ] কখন dict, set, Counter, আর defaultdict — প্রত্যেকটা কোথায় জ্বলে ওঠে, সেটা জানা।
• [ ] এক pass-এ Two Sum solve করা আর "যা দেখেছ মনে রাখো" tweak-টা ব্যাখ্যা করা।
• [ ] Canonical key দিয়ে anagram group করা।
• [ ] Prefix sum-এর সাথে hash map জোড়া লাগানো (subarray-sum pattern)।
• [ ] একদম গোড়া থেকে একটা ছোট্ট hash map বানানো (দেখো implementation.py)।

Problem categories

Category	One-line idea
Frequency counting	Map দিয়ে occurrence গোনো, তারপর count নিয়ে ভাবো
Complement lookup	যা দেখেছ জমা রাখো; জিজ্ঞেস করো "আমার missing piece কি আছে?"
Grouping by canonical key	"Equivalent" item-গুলোকে একই key-তে map করো (sorted string, signature)
Seen-set / de-duplication	Set "আগে দেখা হয়েছে?" প্রশ্নের উত্তর দেয় O(1)-এ
Prefix sum + hash map	আগের prefix value মনে রেখে subarray গোনো
Hash as index accelerator	O(n) membership scan-কে O(1) লাফে বদলে দাও

Practice list

প্রতিটা problem তার pattern দিয়ে tag করা আছে। প্রতিটা band-এর ভেতরে ক্রমানুসারে solve করো।

Easy

Problem	Official task	Pattern	বাংলা ব্যাখ্যা
Two Sum	https://leetcode.com/problems/two-sum/	Complement lookup	নোট পড়ো
Contains Duplicate	https://leetcode.com/problems/contains-duplicate/	Seen-set	নোট পড়ো
Valid Anagram	https://leetcode.com/problems/valid-anagram/	Frequency counting	নোট পড়ো
First Unique Character in a String	https://leetcode.com/problems/first-unique-character-in-a-string/	Frequency counting	নোট পড়ো
Ransom Note	https://leetcode.com/problems/ransom-note/	Frequency counting	নোট পড়ো
Intersection of Two Arrays	https://leetcode.com/problems/intersection-of-two-arrays/	Seen-set	নোট পড়ো
Missing Number	https://leetcode.com/problems/missing-number/	Seen-set (একটা math trick-ও আছে)	নোট পড়ো

Medium

Problem	Official task	Pattern	বাংলা ব্যাখ্যা
Group Anagrams	https://leetcode.com/problems/group-anagrams/	Grouping by canonical key	নোট পড়ো
Top K Frequent Elements	https://leetcode.com/problems/top-k-frequent-elements/	Frequency counting	নোট পড়ো
Longest Consecutive Sequence	https://leetcode.com/problems/longest-consecutive-sequence/	Seen-set + smart start	নোট পড়ো
Subarray Sum Equals K	https://leetcode.com/problems/subarray-sum-equals-k/	Prefix sum + hash map	নোট পড়ো
Valid Sudoku	https://leetcode.com/problems/valid-sudoku/	প্রতিটা row/col/box-এ seen-set	নোট পড়ো
Encode and Decode TinyURL	https://leetcode.com/problems/encode-and-decode-tinyurl/	Hash as index accelerator	নোট পড়ো
4Sum II	https://leetcode.com/problems/4sum-ii/	Complement lookup (pair sums)	নোট পড়ো
Continuous Subarray Sum	https://leetcode.com/problems/continuous-subarray-sum/	Prefix sum + hash map (mod trick)	নোট পড়ো

Hard

Problem	Official task	Pattern	বাংলা ব্যাখ্যা
Minimum Window Substring	https://leetcode.com/problems/minimum-window-substring/	Frequency counting + sliding window	নোট পড়ো
Substring with Concatenation of All Words	https://leetcode.com/problems/substring-with-concatenation-of-all-words/	Frequency counting + windows	নোট পড়ো
String Matching	CSES 1753	Rolling hash; exact KMP	নোট পড়ো
CSES "Sum of Two Values"	https://cses.fi/problemset/task/1640/ (task name: Sum of Two Values)	Complement lookup	নোট পড়ো

Visualization ideas

• 8টা bucket-কে বাক্স হিসেবে আঁকো; hash(key) % 8 দিয়ে 5টা key ছুড়ে দাও; দেখো একটা বাক্সে দুটো key পড়ে (collision) আর সেখানে একটা chain গজায়।
• Two Sum-এর animation বানাও: একটা pointer array ধরে হাঁটে আর পাশে একটা "memory cloud" (the dict) ভরতে থাকে।
• Load factor বাড়লে collision-এর চাপ কীভাবে বাড়তে পারে তা দেখো। Resize নতুন bucket দেয়, কিন্তু সব collision সরায় না; threshold implementation অনুযায়ী আলাদা।
• Interactive version-এর জন্য https://visualgo.net/en → Hash Table দেখো।

Common mistakes (সাধারণ ভুল)

• যেখানে set চলত সেখানে list ব্যবহার → loop-এর ভেতরে accidental O(n) membership check → O(n^2)।
• Dict-এর উপর iterate করতে করতে সেটাকে mutate করা (RuntimeError)।
• List-কে dict-এর key বানানোর চেষ্টা (list unhashable; tuple-এ convert করো)।
• ভুলে যাওয়া যে worst-case-এ dict operation O(n); adversarial input-ও আছে (interview-তে বিরল, CP-তে বাস্তব)।
• d[k] (key না থাকলে KeyError) আর d.get(k) (None ফেরত দেয়) গুলিয়ে ফেলা।
• Float-কে key বানানো: 0.1 + 0.2 != 0.3, তাই float key চুপচাপ miss করে।

Interview problem-এর সাথে সংযোগ

Hashing হলো default "make it faster" চাল। বেশিরভাগ O(n^2) brute-force interview উত্তর dict বা set-এ জিনিস মনে রেখে O(n)-এ নেমে আসে। Two Sum, Group Anagrams, আর Subarray Sum Equals K — এই তিনটাই canonical demonstration; প্রায় প্রতিটা big-tech interview loop-এ অন্তত একটা hashing pattern ছুঁয়ে যায়।

Competitive programming-এর সাথে সংযোগ

• Codeforces-এর প্রায় প্রতিটা Div 2 A/B counting problem-এ frequency map হাজির থাকে।
• Prefix sum + hash map subarray গোনে O(n^2)-র বদলে O(n)-এ।
• Rolling hash (patterns.md-এ teaser আছে) fast string matching চালায়; দেখো https://cp-algorithms.com/string/string-hashing.html।
• Codeforces-এর anti-hash test থেকে সাবধান: competitively string-hashing করলে তোমার hash base randomize করো।

Recommended learning order

1. concept.md — analogy, buckets-এর ছবি, O(1) কেন কাজ করে।
2. visual-explanation.md — frame-by-frame: key → hash → bucket, সাথে একটা collision।
3. operations.md — প্রতিটা dict/set operation, তার cost আর pitfall সহ।
4. patterns.md — ছয়টা named pattern, worked example সহ (Two Sum এখানেই থাকে)।
5. implementation.py — run করো; chaining + resize সহ from-scratch HashMap-টা পড়ো।
6. problems/README.md — practice tracker শুরু করো, easy থেকে hard।

Source map

এই folder-এর সব source, link, আর copying status: দেখো source-map.md।