🗂️ धडा 05 — Hash maps आणि sets: नावानुसार कप्पे

📍 तुम्ही इथे आहात: 12 पैकी धडा 05 · पुढे: lesson-06-recursion

📦 या ब्रँचमध्ये काय आहे

धडे 01–05. dict आणि set मागचा structure, दिसणाऱ्या buckets सह बनवलेला, म्हणजे collisions आणि rehashing घडताना तुम्हाला दिसतात.

dsa/structures.py — HashMap: buckets, put/get, collision counter, 75% भरल्यावर rehash
dsa/demo.py — hashmap: चार boxes मध्ये आठ विद्यार्थी, मग सोळा boxes; शब्द मोजणे

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

प्रत्येक विद्यार्थ्याला एक कप्पा मिळतो, आणि शिपायाकडे एक नियम आहे जो कोणत्याही नावाचे box क्रमांकात रूपांतर करतो: hash("Dipika") % 8 = 3. दीपिकाचे पत्र ठेवायला किंवा काढायला box मोजा, उघडा — एक step, शाळा कितीही मोठी असो. कधीकधी दोन नावे एकाच box मध्ये येतात (collision): box मध्ये एक छोटी list असते, म्हणून तुम्ही एकाऐवजी दोन पत्रे तपासता. boxes तीन चतुर्थांश भरले की शिपाई त्यांना दुप्पट करतो आणि सगळे पुन्हा लावतो, म्हणजे boxes छोटे राहतात.

🗺️ आकृती

flowchart LR
  K["'Dipika'"] -->|"hash % 8"| B3["box 3: (Dipika, 3A)"]
  Z["'Zoya'"] -->|"hash % 8"| B3
  S["'Katrina'"] -->|"hash % 8"| B6["box 6: (Katrina, 3A)"]

❓ काय

Hash function: नाव → संख्या, जलद, समान पसरलेली. Python मध्ये hash().
Bucket: hash(key) % buckets; collisions bucket च्या list मध्ये जातात (chaining) किंवा पुढच्या रिकाम्या slot मध्ये (open addressing — CPython चा dict).
Load factor: items / buckets; buckets छोटे ठेवायला ~0.75 ओलांडले की rehash (दुप्पट) करा. Get/put सरासरी O(1), फक्त अतिशय वाईट hash असेल तर O(n).
Keys hashable असायलाच हव्यात (immutable): str, int, tuple — list नाही.
Set = values नसलेला hash map: membership आणि dedupe O(1) मध्ये.
Patterns: मोजणी (counts[w] += 1), grouping, dedupe (set(xs)), एका pass मध्ये two-sum (seen[target - x]), caching (धडा 11).

🤔 का

"जलद करा" याचा अर्धा भाग म्हणजे "तो आतला loop dict ने बदला". नावाने गोष्टी शोधायच्या असतील तेव्हा हाच पहिला structure हाती घ्यायचा, आणि त्याचे दोन खर्च (memory, क्रम नाही) माहीत असले की तो टाळायचा अशी दुर्मिळ प्रकरणे कळतात.

🔧 कसे (या repo मध्ये)

HashMap 25 ओळींचा आहे: _slot box मोजतो, put box मध्ये आधीची key आहे का ते पाहतो, box रिकामा नसेल तर एक collision मोजतो, append करतो, आणि 75% ओलांडले की rehash करतो. demo.py hashmap चार boxes ने सुरू होतो म्हणजे तुम्ही तो वाढताना पाहू शकता.

🧪 करून पाहा

python3 dsa/demo.py hashmap
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import HashMap
hm = HashMap(buckets=2)
for i in range(1000): hm.put(f"pupil{i}", i)
print(len(hm), "pupils in", len(hm._b), "boxes; longest box:", max(len(b) for b in hm._b))
# two-sum in one pass with a dict (unsorted input — no two pointers needed):
xs, target, seen = [8, 3, 11, 6, 1], 14, {}
for i, x in enumerate(xs):
    if target - x in seen: print("pair:", seen[target - x], i); break
    seen[x] = i
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

आठ विद्यार्थी शेवटी 16 boxes मध्ये जातात (collision count प्रत्येक run ला बदलतो कारण Python string hashes ना salt लावतो); शब्दांची मोजणी {'the': 3, …}. तुमचे हजार विद्यार्थी 2,048 boxes मध्ये बसतात आणि सर्वात लांब box मध्ये फक्त काहीच असतात; two-sum pair: 1 2 print करतो (3 + 11).

🏁 तुम्ही आत्ताच काय सिद्ध केले

hashing मुळे lookup O(1) होताना तुम्ही पाहिले, collisions हाताळले जाताना आणि boxes दुप्पट होताना पाहिले, आणि n² loop ची जागा घेणारा एका pass चा dict pattern वापरला.

⚠️ नेहमीच्या चुका

loop च्या आत x in list (O(n²)), जिथे x in set एकूण O(n) आहे.
list ला dict key म्हणून वापरणे (unhashable) किंवा insertion नंतर बदलणारा mutable object वापरणे.
logic साठी dict च्या क्रमावर अवलंबून राहणे (insertion order टिकतो, पण ते sorting नाही).

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: caches, sessions, indexes, deduplication, database engine मधले joins, DNS resolvers — hash maps हेच कामाचे घोडे आहेत. वाईट hash असलेला "O(1)" cache म्हणजे एक incident.

⏭️ पुढे

धडा 06 — recursion: मुख्याध्यापक उपमुख्याध्यापकांना विचारतात, आणि फळ्याशिवाय fib का फुटते.

🗂️ Lesson 05 — Hash maps & sets: pigeonholes by name

📍 You are here: Lesson 05 of 12 · Next: lesson-06-recursion

📦 What's in this branch

Lessons 01–05. The structure behind dict and set, built with visible buckets so you can see collisions and rehashing happen.

dsa/structures.py — HashMap: buckets, put/get, collision counter, rehash at 75% full
dsa/demo.py — hashmap: eight pupils in four boxes, then sixteen; counting words

🧒 Explain like I'm 5

Each pupil gets a pigeonhole, and the porter has a rule that turns any name into a box number: hash("Dipika") % 8 = 3. To file or fetch Dipika's letter, compute the box, open it — one step, whatever the school's size. Sometimes two names land in one box (a collision): the box holds a short list, so you check two letters instead of one. When the boxes get three quarters full, the porter doubles them and re-files everything, so boxes stay short.

🗺️ Diagram

flowchart LR
  K["'Dipika'"] -->|"hash % 8"| B3["box 3: (Dipika, 3A)"]
  Z["'Zoya'"] -->|"hash % 8"| B3
  S["'Katrina'"] -->|"hash % 8"| B6["box 6: (Katrina, 3A)"]

❓ What

Hash function: name → number, fast, spread evenly. hash() in Python.
Bucket: hash(key) % buckets; collisions go in the bucket's list (chaining) or the next free slot (open addressing — CPython's dict).
Load factor: items / buckets; rehash (double) past ~0.75 to keep buckets tiny. Get/put O(1) average, O(n) only with a terrible hash.
Keys must be hashable (immutable): str, int, tuple — not list.
Set = a hash map with no values: membership and dedupe in O(1).
Patterns: counting (counts[w] += 1), grouping, dedupe (set(xs)), two-sum in one pass (seen[target - x]), caching (lesson 11).

🤔 Why

Half of "make it faster" is "replace that inner loop with a dict". It is the first structure to reach for whenever you look things up by name, and knowing its two costs (memory, no order) tells you the rare cases to avoid it.

🔧 How (in this repo)

HashMap is 25 lines: _slot computes the box, put scans the box for an existing key, counts a collision if the box was non-empty, appends, and rehashes past 75%. demo.py hashmap starts with four boxes so you can watch it grow.

🧪 Try it

python3 dsa/demo.py hashmap
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from structures import HashMap
hm = HashMap(buckets=2)
for i in range(1000): hm.put(f"pupil{i}", i)
print(len(hm), "pupils in", len(hm._b), "boxes; longest box:", max(len(b) for b in hm._b))
# two-sum in one pass with a dict (unsorted input — no two pointers needed):
xs, target, seen = [8, 3, 11, 6, 1], 14, {}
for i, x in enumerate(xs):
    if target - x in seen: print("pair:", seen[target - x], i); break
    seen[x] = i
EOF

✅ Verify — what you should see

Eight pupils end in 16 boxes (the collision count varies run to run because Python salts string hashes); the word count is {'the': 3, …}. Your thousand pupils sit in 2,048 boxes with the longest box holding only a few; two-sum prints pair: 1 2 (3 + 11).

🏁 What you just proved

You watched hashing turn lookup into O(1), saw collisions handled and boxes doubled, and used the one-pass dict pattern that replaces an n² loop.

⚠️ Common mistakes

x in list inside a loop (O(n²)) where x in set is O(n) total.
Using a list as a dict key (unhashable) or a mutable object that changes after insertion.
Relying on dict order for logic (insertion order is kept, but that is not sorting).

🏭 Why this matters in production: caches, sessions, indexes, deduplication, joins in a database engine, DNS resolvers — hash maps are the workhorse. A cache that is "O(1)" with a poor hash is an incident.

⏭️ Next

Lesson 06 — recursion: the head asks the deputy, and why fib without a board explodes.

← Previousstacks queues Next →recursion

This page is the lesson's README from the lesson-05-hash-maps branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.