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

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

প্রথমে [ধারণা](concept.md), তারপর [সম্পূর্ণ চিত্র ও ধাপে ধাপে উদাহরণ](visual-explanation.md), তারপর [কোন প্রশ্নে কোন pattern](patterns.md) পড়ো। প্রয়োজন হলে [operation ও খরচ](operations.md) পাশে রাখো। [সমস্ত problem ও বাংলা নোট](problems/README.md) এবং [উৎসের তালিকা](source-map.md) সরাসরি খোলা যাবে।

| ধাপ | কী শিখবে | প্রথম অনুশীলন |
| --- | --- | --- |
| 1 | আগে দেখা value মনে রাখা | [Contains Duplicate](problems/002-contains-duplicate.md) |
| 2 | দরকারি সঙ্গী খোঁজা | [Two Sum](problems/001-two-sum.md) |
| 3 | প্রতিটি অক্ষর কতবার | [Valid Anagram](problems/003-valid-anagram.md) |
| 4 | সমতুল্য item group করা | [Group Anagrams](problems/010-group-anagrams.md) |
| 5 | prefix-এর frequency রাখা | [Subarray Sum K](problems/013-subarray-sum-equals-k.md) |
| 6 | count ও window একসঙ্গে | [Minimum Window](problems/020-minimum-window-substring.md) |

প্রতিটি ধাপে আগে ছোট 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/](../02-arrays-and-strings/README.md) যদি তোমার 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](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 | [নোট পড়ো](problems/001-two-sum.md) |
| Contains Duplicate | <https://leetcode.com/problems/contains-duplicate/> | Seen-set | [নোট পড়ো](problems/002-contains-duplicate.md) |
| Valid Anagram | <https://leetcode.com/problems/valid-anagram/> | Frequency counting | [নোট পড়ো](problems/003-valid-anagram.md) |
| First Unique Character in a String | <https://leetcode.com/problems/first-unique-character-in-a-string/> | Frequency counting | [নোট পড়ো](problems/005-first-unique-character.md) |
| Ransom Note | <https://leetcode.com/problems/ransom-note/> | Frequency counting | [নোট পড়ো](problems/004-ransom-note.md) |
| Intersection of Two Arrays | <https://leetcode.com/problems/intersection-of-two-arrays/> | Seen-set | [নোট পড়ো](problems/006-intersection-two-arrays.md) |
| Missing Number | <https://leetcode.com/problems/missing-number/> | Seen-set (একটা math trick-ও আছে) | [নোট পড়ো](problems/007-missing-number.md) |

### Medium

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

### Hard

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

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

## Source map

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