Open addressing: probing, deletion और full tables
Contract और संबंध
Chaining के dictionary और load-factor concepts आगे बढ़ाएँ। Open addressing में हर slot में अधिकतम एक live record है। Slot EMPTY (इस table initialization से कभी occupied नहीं), LIVE या DELETED tombstone है। m slots में live α=n/m अधिकतम 1 है। Hash/equality operations O(1) हैं।
1. पूरा probe sequence मानें
Linear probing: h(k,i)=(h0(k)+i) mod m, i=0,...,m−1। हर slot एक बार visit होता है। Search में matching LIVE मिले तो success; दूसरा LIVE या DELETED हो तो आगे जाएँ; EMPTY पर absent। m probes बिना match पूरे हों तो absent। Full table या बिना EMPTY वाली table में explicit limit infinite loop रोकती है।
Unique-key insertion में पहला DELETED याद रखें, लेकिन existing key के लिए आगे search करें। Key मिले तो update करें। EMPTY मिलने पर remembered tombstone में, अन्यथा उसी EMPTY में insert करें। पूरा sequence scan होने पर tombstone हो तो reuse करें; नहीं तो full/resize। पहले tombstone पर तुरंत insert करने से आगे मौजूद key की duplicate copy बन सकती है।
2. Deletion का सही trace
m=7, h0(k)=k mod 7, linear probing। 10,17,24 insert करने पर indices 3,4,5 भरते हैं। 17 delete करके 4 को DELETED करें। Search 24 क्रम 3,4,5 से सफल है। 4 को गलत तरीके से EMPTY करने पर search वहीं रुककर false absence देगा। अब 31 insert करें: 3,4,5,6 scan करें; EMPTY 6 मिलने पर duplicate absence तय है, remembered slot 4 में 31 रखें।
Tombstones search correctness बचाते हैं लेकिन probe cost बढ़ा सकते हैं। Live α छोटा होते हुए भी लगभग हर slot LIVE/DELETED हो सकता है। Clean table में rehash tombstones हटाता है; केवल n घटाने से पुराने probe paths छोटे नहीं होते।
3. Probe families और coverage
Linear probing में primary clustering होता है: contiguous occupied runs और insertions खींचते हैं। Quadratic (h0(k)+i²) mod m सभी slots नहीं visit कर सकता। m=8,h0=0 में केवल 0,1,4,1,0,... आते हैं। अन्य empty slot reachable जरूरी नहीं।
Double hashing: (h1(k)+i h2(k)) mod m। Step modulo m nonzero तथा m के coprime हो तो सभी slots visit होते हैं। m=10,step=4 पर 0,4,8,2,6 के बाद repeat; step=3 सभी दस visit करता है। Prime m और step 1,...,m−1 coprimality देते हैं। केवल दो hash functions कहना coverage proof नहीं।
4. लागत की assumptions और गलतियाँ
Ideal uniform probing और α<1 में unsuccessful search का expected probe count अधिकतम 1/(1−α), उस model में जहाँ accumulated tombstones नहीं हैं। यह probabilistic upper bound है, linear probing की exact संख्या नहीं। α=0.75 पर bound 4 है। Linear probing clustering का अलग analysis चाहिए। Worst case Θ(m) probes; m=Θ(n) maintain करें तो Θ(n)।
Space Θ(m)। Chaining से अलग, पूरी LIVE full table में resize बिना नई distinct key नहीं रख सकते। Search फिर भी success या अधिकतम m probes में terminate हो सकता है। Deleted slot reusable है, search terminator नहीं। Load formulas से पहले tombstone assumptions बताएँ।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Slots 3:10,4:17,5:24 में 17 delete करने पर slot 4:
A. EMPTY B. DELETED C. हमेशा 0 D. Array से हटाया गया
उत्तर: B
A: 24 की search टूटेगी।
B: Tombstone probe chain बचाता है।
C: 0 valid key हो सकता है।
D: Length बदलने से hash indices बदलेंगे।
P02. Linear probing m=7, start 6: पहले तीन indices?
A. 6,7,8 B. 6,0,1 C. 6,1,3 D. 0,1,2
उत्तर: B
A: Modulo 7 wrap होगा।
B: (6+i) mod 7 से 6,0,1।
C: Step one नहीं है।
D: पहला index 6 है।
P03. Double hashing m=10, step 4 कितने distinct slots?
A. 2 B. 4 C. 5 D. 10
उत्तर: C
A: Cycle m/gcd(m,step)।
B: Step cycle length नहीं।
C: 10/gcd(10,4)=5।
D: Step/capacity coprime नहीं।
P04. Duplicate check से पहले tombstone मिले तो insertion:
A. तुरंत insert और stop B. याद रखकर आगे search C. EMPTY करके stop D. कभी reuse नहीं
उत्तर: B
A: आगे की key duplicate हो सकती है।
B: Key, EMPTY या bounded full scan तक जाएँ।
C: दूसरी searches टूटेंगी।
D: सही check के बाद reuse मान्य है।
P05. बिना tombstones ideal uniform probing, α=0.75: unsuccessful expected upper bound?
A. 0.25 B. 0.75 C. 3 D. 4
उत्तर: D
A: यह empty fraction है।
B: यह load factor है।
C: यह α/(1−α) है।
D: 1/(1−0.75)=4।
P06. Full linear-probing table में absent key: सही termination?
A. EMPTY तक हमेशा चलते रहें B. अधिकतम m probes C. हमेशा एक probe D. Search अवश्य सफल
उत्तर: B
A: EMPTY नहीं है।
B: m slots के बाद absence तय है।
C: Collisions में extra probes लगेंगे।
D: Full table सभी possible keys नहीं रखती।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन