Hashing — key থেকে সঠিক বাক্সে¶

Hash table-এ key দেখে আগে একটি bucket বেছে নিই, তারপর সেখানে আসল key মিলিয়ে দেখি। এই উদাহরণে চারটি bucket এবং শেখার জন্য ছোট একটি hash ব্যবহার করছি: a=1, b=2 থেকে z=26; অক্ষরের মান যোগ করে bucket সংখ্যার ভাগশেষ নিই। এটি production hash নয়।

1. Insert: hash হিসাব করে bucket বেছে নাও¶

cab-এর যোগফল 3 + 1 + 2 = 6, তাই bucket 6 % 4 = 2। ad-এর যোগফল 1 + 4 = 5, তাই bucket 5 % 4 = 1। বাক্সের index-ই bucket number।

চার bucket-এ দুটি key রাখা

শুরু · 0টি item
ফাঁকা বা বাদ দেওয়া ঘর: 0খালি
ফাঁকা বা বাদ দেওয়া ঘর: 1খালি
ফাঁকা বা বাদ দেওয়া ঘর: 2খালি
ফাঁকা বা বাদ দেওয়া ঘর: 3খালি
Load factor = item / bucket = 0 / 4 = 0।
cab → 10 রাখো
ফাঁকা বা বাদ দেওয়া ঘর: 0খালি
ফাঁকা বা বাদ দেওয়া ঘর: 1খালি
চিহ্নিত ঘর: 2cab: 10
ফাঁকা বা বাদ দেওয়া ঘর: 3খালি
Load factor = 1 / 4 = 0.25।
ad → 20 রাখো
ফাঁকা বা বাদ দেওয়া ঘর: 0খালি
চিহ্নিত ঘর: 1ad: 20
2cab: 10
ফাঁকা বা বাদ দেওয়া ঘর: 3খালি
Load factor = 2 / 4 = 0.5।

এখন cab খুঁজতে একই hash আবার হিসাব করি: bucket 2-তে যাই, cab key মেলে, উত্তর 10। অন্য bucket দেখার দরকার হয় না।

2. Collision: একই bucket মানে একই key নয়¶

এরপর be → 30 রাখলে 7 % 4 = 3। কিন্তু da → 40-এর hash 5 % 4 = 1, যেখানে ad আগেই আছে। দুই key-কে একই chain-এ রাখলে কেউ হারায় না।

flowchart LR
  B0["bucket 0"] --> E0["খালি"]
  B1["bucket 1"] --> AD["ad · value 20"] --> DA["da · value 40"]
  B2["bucket 2"] --> CAB["cab · value 10"]
  B3["bucket 3"] --> BE["be · value 30"]

খোঁজা key	hash ও bucket	যে তুলনাগুলো হয়	ফল
`cab`	`6 % 4 = 2`	`cab == cab`	10
`da`	`5 % 4 = 1`	`ad != da`, তারপর `da == da`	40
`zz`	`52 % 4 = 0`	bucket খালি; তুলনাও লাগে না	key নেই

be ঢোকার পরে load 3/4 = 0.75; da ঢোকার পরে 4/4 = 1। ছবি separate chaining বোঝায়; Python dict-এর ভেতরের গঠন হুবহু এমন নয়।

3. Resize: শুধু বড় করলেই হয় না, bucket আবার হিসাব করো¶

এই উদাহরণে load 1 হলে চার থেকে আট bucket করি। Resize threshold implementation অনুযায়ী বদলায়। নতুন bucket number হলো hash % 8, তাই পুরনো index রেখে দিলে lookup ভুল হবে।

key	hash	আগে: `% 4`	পরে: `% 8`
cab	6	2	6
ad	5	1	5
da	5	1	5
be	7	3	7

Resize-এর পরে আট bucket

4টি item, 8টি bucket · load 0.5
ফাঁকা বা বাদ দেওয়া ঘর: 0খালি
ফাঁকা বা বাদ দেওয়া ঘর: 1খালি
ফাঁকা বা বাদ দেওয়া ঘর: 2খালি
ফাঁকা বা বাদ দেওয়া ঘর: 3খালি
ফাঁকা বা বাদ দেওয়া ঘর: 4খালি
চিহ্নিত ঘর: 5ad, da
চিহ্নিত ঘর: 6cab
চিহ্নিত ঘর: 7be
Bucket 5-এ ad → da chain আছে; value যথাক্রমে 20 ও 40। cab-এর value 10, be-এর 30।

ad ও da এখনও collide করে: আমাদের hash-এ অক্ষরের যোগফল একই। ভালো hash-এ অক্ষরের অবস্থানও প্রভাব ফেলে, তবু collision সম্ভব। তাই hash মেলার পর key-ও মেলাতে হয়।

4. Two Sum: আগে দেখা জোড়াটি মনে রাখো¶

[2, 7, 11, 15] থেকে যোগফল 9 হয় এমন দুই index চাই। seen রাখে আগে দেখা value → তার index। প্রতিটি x-এর জন্য দরকার 9 - x।

আগের মান মনে রাখলে দ্বিতীয় loop লাগে না

i = 0 · x = 2
চিহ্নিত ঘর: 02↑ i
17
211
315
দরকার 7। seen খালি, তাই মেলেনি। এবার seen-এ 2 → 0 রাখি।
i = 1 · x = 7
চিহ্নিত ঘর: 02↑ আগের
চিহ্নিত ঘর: 17↑ i
211
315
দরকার 2। seen-এ 2 → 0 পাওয়া গেছে। উত্তর indices [0, 1]; এখানেই থামি।

নিজেকে seen-এ রাখার আগে complement খুঁজি। তা না হলে [3, 3], target 6-এর মতো ক্ষেত্রে একই index দুবার নেওয়ার ভুল হতে পারে। গড়ে প্রতিটি lookup O(1); পুরো traversal O(n) সময়, O(n) অতিরিক্ত জায়গা।

5. কেন key ছড়িয়ে থাকা দরকার?¶

একই আট key যদি আট bucket-এ মোটামুটি ছড়ায়, প্রতিটি chain ছোট থাকে। সব key একই bucket-এ পড়লে lookup আবার লম্বা তালিকা খোঁজার মতো হয়। নিচের দুটি distribution কেবল খরচ বোঝানোর উদাহরণ।

bucket	ছড়ানো অবস্থায় key	সব এক জায়গায় পড়লে key
0	k3	খালি
1	k7	খালি
2	k1, k5	k1, k2, k3, k4, k5, k6, k7, k8
3	k8	খালি
4	k2	খালি
5	k6	খালি
6	k4	খালি
7	খালি	খালি

বাঁয়ের উদাহরণে সফল lookup-এ 1–2টি key তুলনা লাগে; ডানের chain-এর শেষে পৌঁছাতে 8টি। ভালো distribution ও নিয়ন্ত্রিত load factor-এ গড় খরচ O(1), কিন্তু worst case O(n)। String key-এর দৈর্ঘ্য m হলে প্রথমবার hash হিসাবেই O(m) লাগতে পারে।

নিজে চেষ্টা করো: ab ও ba-এর bucket বের করো। চার থেকে আট bucket করলেও তারা আলাদা হবে কি? উত্তর দিয়ে বোঝাও কেন শুধু resize দিয়ে খারাপ hash ঠিক করা যায় না। পরের পাঠ: operations। VisuAlgo Hash Table-এ নিজেও insert করে দেখতে পারো।