Hashing: separate chaining और load factor
Contract और पूर्वज्ञान
Arrays, linked lists और asymptotic bounds आधार हैं। Hash table distinct keys की dictionary है; existing key का update उसका value बदलता है। Hash function m buckets, indices 0,...,m−1 में key भेजता है। Hash computation तथा key comparison O(1) मानें; variable-length strings की length का cost अलग जोड़ना होगा।
1. Collision का अर्थ equal key नहीं
Separate chaining में हर bucket records की list रखता है। Search h(k) निकालकर उसी list में key compare करता है, मिलने या list समाप्त होने तक। Dictionary में uniqueness चाहिए तो insert से पहले duplicate खोजें, फिर नया record head पर जोड़ें। Delete record खोजकर unlink करता है। Node pointer से search तभी बचता है जब representation उपयुक्त हो, जैसे doubly linked list; singly linked list में predecessor चाहिए हो सकता है।
उदाहरण m=5, h(k)=k mod 5; 7,12,4,17 को head पर insert करें। Bucket 2: [7], फिर [12,7], फिर [17,12,7]; bucket 4: [4]। Search 7 तीन key comparisons लेता है। Absent 22 भी तीन records scan करता है: hash bucket वही है, key अलग। Collision में location समान है, original keys जरूरी नहीं।
2. Load factor और expected time
α=n/m औसत records per bucket है। Chaining में α>1 संभव है। Simple uniform hashing में प्रत्येक key हर bucket में समान probability से जाता है; expected chain analysis के आवश्यक independence assumptions भी मानें। Unsuccessful search की expected chain length α, total expected time Θ(1+α), जिसमें hash work शामिल है। Standard uniform/random-order model में successful search भी expected Θ(1+α)। Exact constants insertion order और queried keys पर निर्भर हैं।
n=24,m=8 पर α=3। इसका अर्थ हर bucket में ठीक तीन records नहीं। Unlucky/adversarial keys से सारे 24 एक bucket में भी हो सकते हैं। Worst-case search Θ(n), O(1) नहीं। Expected hashing guarantee, binary search की worst-case guarantee जैसी नहीं है।
3. Insertion और resizing की शर्तें
Key absent होने की guarantee और head insertion की अनुमति हो तो pointer splice O(1), allocation और model से अधिक hash cost छोड़कर। Uniqueness check करना हो तो search शामिल है: expected Θ(1+α)। दोनों अलग operation contracts हैं।
α=O(1) रखने के लिए m को n के अनुपात में बढ़ाएँ और नई bucket count से सभी keys rehash करें। नई bucket array initialize और records move करने में Θ(n+m_new), proportional capacity पर Θ(n)। Geometric growth से sequence पर amortized constant insertion overhead मिल सकता है; resize trigger करने वाला एक insertion फिर भी linear है। Expected hashing randomness पर average है; amortized पूरे operation sequence की लागत का average। दोनों का अर्थ हर operation constant नहीं।
4. Space और गलतियाँ
Bucket heads तथा records मिलाकर storage Θ(m+n)। Buckets से ज्यादा keys रख सकते हैं; α<1 आवश्यक नहीं। Hash function को relevant keys अच्छे से distribute करनी चाहिए; केवल valid index देना पर्याप्त नहीं। Mod उदाहरण deterministic trace है, uniform-hashing proof नहीं। तुलना में collision method, comparison cost, load factor, expected/worst-case और duplicate-check contract स्पष्ट करें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. 8 chained buckets में 24 keys का α:
A. 1/3 B. 3 C. 8 D. 24
उत्तर: B
A: Ratio n/m है।
B: 24/8=3।
C: यह bucket count है।
D: यह key count है।
P02. Uniform hashing में expected unsuccessful search time:
A. α→0 होने पर भी Θ(α) B. Θ(1+α) C. हमेशा Θ(n) D. हमेशा Θ(log n)
उत्तर: B
A: Hash/bucket access cost बचता है।
B: Hash work और expected chain scan।
C: Worst case expectation नहीं।
D: Binary-search ordering नहीं।
P03. 7,12,4,17 head-insert, h(k)=k mod 5। Search 7 comparisons?
A. 1 B. 2 C. 3 D. 4
उत्तर: C
A: पहला 17 है।
B: दूसरा 12 है।
C: Bucket 2 में [17,12,7]।
D: 4 अलग bucket में है।
P04. Chaining में कौन-सा सही?
A. α हमेशा 1 से छोटा B. Collision वाली keys एक समान हैं C. हर bucket में ठीक α records D. α 1 से बड़ा हो सकता है
उत्तर: D
A: Chain multiple records रखता है।
B: केवल hash values समान हैं।
C: α average है।
D: Buckets से अधिक keys मान्य हैं।
P05. सभी n keys collide हों तो worst-case search?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)
उत्तर: C
A: पूरी लंबी list scan हो सकती है।
B: List पर binary search नहीं।
C: n तक key comparisons।
D: एक scan linear है।
P06. Proportional rehash trigger करने वाला एक insertion:
A. अनिवार्य Θ(1) B. Θ(n) C. अनिवार्य Θ(log n) D. शून्य work
उत्तर: B
A: Amortization हर individual operation नहीं बाँधता।
B: सभी existing keys move होंगे।
C: सारे records move करना logarithmic नहीं।
D: नई storage/rehash में work है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन