PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining (कोलिजन समाधान: ओपन एड्रेसिंग (लीनियर प्रोबिंग) बनाम सेपरेट चेनिंग) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Hash collisions occur when two distinct keys map to the same slot under h(k) = k mod m, requiring deterministic resolution via Separate Chaining or Open Addressing. Separate Chaining links overflowing keys outside the primary array (supporting load factor alpha > 1), whereas Open Addressing probes alternative slots inside the array itself (requiring alpha <= 1).
अध्याय सार: जब दो अलग-अलग कुंजियाँ (Keys) हैश फंक्शन h(k) = k mod m द्वारा एक ही स्लॉट इंडेक्स पर मैप होती हैं, तो हैश कोलिजन उत्पन्न होता है जिसे Separate Chaining या Open Addressing से हल किया जाता है। सेपरेट चेनिंग में बकेट से जुड़ी लिंक्ड लिस्ट बाहर तक बढ़ती है (लोड फैक्टर alpha > 1 संभव), जबकि ओपन एड्रेसिंग में सभी कुंजियाँ टेबल एरे के भीतर ही प्रोब सीक्वेन्स से रखी जाती हैं (alpha <= 1 अनिवार्य)।
Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining: Detailed Notes & Architecture (कोलिजन समाधान: ओपन एड्रेसिंग (लीनियर प्रोबिंग) बनाम सेपरेट चेनिंग)
1. Separate Chaining (Closed Addressing) & Load Factor Analysis (सेपरेट चेनिंग (Closed Addressing) और लोड फैक्टर विश्लेषण)
[EN] In Separate Chaining (often termed Open Hashing or Closed Addressing), each bucket of size-m table T points to a dynamic linked list holding all keys that hash to that slot. Because collisions reside outside the primary bucket array, the load factor alpha = n / m can exceed 1.0 without table overflow. Under Simple Uniform Hashing (SUHA), an unsuccessful search scans an entire chain in Theta(1 + alpha) expected time, while a successful search takes Theta(1 + alpha/2). Modern implementations such as Java 8 HashMap convert chains exceeding 8 nodes (when table capacity >= 64) into balanced Red-Black trees, capping worst-case bucket lookup at O(log n) instead of O(n).
[HI] सेपरेट चेनिंग (जिसे Open Hashing भी कहा जाता है) में m आकार की टेबल का प्रत्येक बकेट एक लिंक्ड लिस्ट (चेन) को पॉइंट करता है जहाँ समान हैश वाले सभी तत्व रखे जाते हैं। इसमें लोड फैक्टर alpha = n / m का मान 1 से अधिक भी हो सकता है। सिंपल यूनिफॉर्म हैशिंग में असफल सर्च का औसत समय Theta(1 + alpha) तथा सफल सर्च का Theta(1 + alpha/2) होता है; Java 8 HashMap में चेन की लंबाई 8 से अधिक होने पर उसे Red-Black ट्री में बदल दिया जाता है ताकि वर्स्ट केस O(log n) रहे।
2. Open Addressing & Linear Probing (Primary Clustering) (ओपन एड्रेसिंग और लीनियर प्रोबिंग (Primary Clustering))
[EN] Open Addressing (Closed Hashing) stores every key directly inside the hash table array itself with zero external pointers, strictly enforcing alpha = n / m <= 1. Linear Probing resolves collisions by inspecting sequential slots modulo m: h(k, i) = (h'(k) + i) mod m for probe step i = 0, 1, ..., m - 1. Sequential access gives Linear Probing exceptional CPU cache locality and fast performance at low load factors. However, as alpha approaches 1, occupied runs coalesce into long contiguous blocks—a phenomenon called Primary Clustering—causing average probe counts to surge approximately as 1/2 * (1 + 1 / (1 - alpha)^2).
[HI] ओपन एड्रेसिंग (Closed Hashing) में कोई अतिरिक्त पॉइंटर या लिंक लिस्ट नहीं होती; सभी कुंजियाँ स्वयं हैश टेबल एरे में रखी जाती हैं, जिससे alpha <= 1 अनिवार्य है। लीनियर प्रोबिंग सूत्र h(k, i) = (h'(k) + i) mod m द्वारा अगले क्रमिक स्लॉट खोजती है, जिससे CPU कैश लोकैलिटी बेहतरीन मिलती है। परंतु इसके कारण भरे हुए स्लॉट्स के लंबे समूह बन जाते हैं जिसे Primary Clustering कहते हैं, और लोड फैक्टर 1 के करीब जाने पर प्रदर्शन तेजी से गिरता है।
3. Quadratic Probing & Double Hashing (Eliminating Clustering) (क्वाड्रैटिक प्रोबिंग और डबल हैशिंग (क्लस्टरिंग का समाधान))
[EN] Quadratic Probing jumps by quadratic offsets via h(k, i) = (h'(k) + c1*i + c2*i^2) mod m (commonly h(k, i) = (h'(k) + i^2) mod m), breaking up contiguous Primary Clusters. Because keys sharing the same initial hash h'(k) still follow identical probe paths, Quadratic Probing still exhibits milder Secondary Clustering, and requires prime m with alpha <= 0.5 to guarantee finding an empty slot. Double Hashing uses a second independent hash function: h(k, i) = (h1(k) + i * h2(k)) mod m, where h2(k) must never return 0 and must be coprime to m (e.g., h2(k) = R - (k mod R) for prime R < m). This yields Theta(m^2) distinct probe sequences and eliminates both primary and secondary clustering.
[HI] क्वाड्रैटिक प्रोबिंग सूत्र h(k, i) = (h'(k) + c1*i + c2*i^2) mod m से वर्ग दूरी पर स्लॉट जांचती है, जिससे Primary Clustering समाप्त हो जाती है, यद्यपि एक जैसे प्रारंभिक हैश वाली कुंजियाँ अब भी समान पथ (Secondary Clustering) अपनाती हैं (अभाज्य m और alpha <= 0.5 पर खाली स्लॉट पक्का मिलता है)। डबल हैशिंग दूसरे फंक्शन h2(k) के साथ h(k, i) = (h1(k) + i * h2(k)) mod m उपयोग करती है; यहाँ h2(k) != 0 तथा gcd(h2(k), m) = 1 होने पर प्राइमरी और सेकेंडरी दोनों क्लस्टरिंग समाप्त हो जाती हैं।
4. Deletion Tombstones & Chaining vs Open Addressing Trade-offs (डिलीशन टॉम्बस्टोन और दोनों विधियों की तुलना)
[EN] Deleting a key in Open Addressing cannot simply reset the slot to EMPTY, because doing so would prematurely terminate probe chains for subsequent keys, causing false negative search failures. Instead, deleted slots are overwritten with a Tombstone (DELETED) sentinel: searches keep probing past tombstones, while insertions may overwrite them; excessive tombstones necessitate periodic rehashing. By contrast, Separate Chaining deletes keys cleanly in O(1) after locating the node without tombstones. Overall, Open Addressing saves pointer memory and excels in cache-sensitive tables (like Python dict or SwissTable) when alpha <= 0.7, whereas Chaining handles frequent deletions and high/unpredictable load factors gracefully.
[HI] ओपन एड्रेसिंग में किसी कुंजी को डिलीट करके स्लॉट को सीधे EMPTY नहीं किया जा सकता, वरना आगे प्रोब की गई कुंजियों की सर्च बीच में ही टूट जाएगी; इसलिए डिलीट किए गए स्लॉट पर Tombstone (DELETED) मार्कर रखा जाता है। इसके विपरीत, सेपरेट चेनिंग में नोड को सीधे लिंक्ड लिस्ट से अनलिंक कर दिया जाता है। कम लोड फैक्टर (alpha <= 0.7) और कैश दक्षता के लिए ओपन एड्रेसिंग श्रेष्ठ है, जबकि बार-बार डिलीशन व उच्च लोड फैक्टर के लिए चेनिंग बेहतर रहती है।
Syntax, Formula & Technical Example (Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining)
// Hash Table m = 7, h1(k) = k % 7, h2(k) = 5 - (k % 5)
// Insert keys in order: 50, 700, 76, 85, 92
50 % 7 = 1 -> Slot[1] = 50
700 % 7 = 0 -> Slot[0] = 700
76 % 7 = 6 -> Slot[6] = 76
85 % 7 = 1 -> Collision at 1!
Linear (i=1): (1 + 1) % 7 = 2 -> Slot[2] = 85
Quadratic (i=1): (1 + 1^2) % 7 = 2 -> Slot[2] = 85
Double h2=5 : (1 + 1*5)%7=6 (hit), i=2: (1 + 10)%7 = 4 -> Slot[4]
92 % 7 = 1 -> Linear i=2 -> Slot[3] | Quadratic i=2 -> (1+4)%7 = Slot[5]
Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining Quick Reference & Comparison Table
| Collision Method | Probe / Storage Mechanism | Clustering & Load Factor |
|---|---|---|
| Separate Chaining | Array of bucket pointers to linked lists/trees | Supports alpha > 1; zero clustering or tombstones |
| Linear Probing | h(k, i) = (h'(k) + i) mod m | Best CPU cache locality; suffers Primary Clustering |
| Quadratic Probing | h(k, i) = (h'(k) + c1*i + c2*i^2) mod m | Avoids primary clustering; exhibits Secondary Clustering |
| Double Hashing | h(k, i) = (h1(k) + i * h2(k)) mod m | No primary/secondary clustering; needs gcd(h2(k), m)=1 |
Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining Top 20 Bilingual MCQs with Answers
Q1. What is the strict upper bound on the load factor alpha = n/m for any Open Addressing hash table?
(किसी भी Open Addressing हैश टेबल के लोड फैक्टर alpha = n/m की अधिकतम संभव सीमा क्या होती है?)
(A) alpha <= 0.1
(B) alpha <= 1
(C) alpha can exceed 5 freely
(D) alpha >= 2
Correct Answer: (B)
[EN] Because Open Addressing stores all n keys inside the m slots of the table array itself, n cannot exceed m, so alpha <= 1 always.
[HI] ओपन एड्रेसिंग में सभी n कुंजियाँ स्वयं m आकार की टेबल में रखी जाती हैं, इसलिए n कभी m से बड़ा नहीं हो सकता (alpha <= 1)।
Q2. Which collision resolution technique is also known in textbooks as Open Hashing (Closed Addressing)?
(किस कोलिजन समाधान तकनीक को पाठ्यपुस्तकों में Open Hashing (या Closed Addressing) भी कहा जाता है?)
(A) Linear Probing
(B) Double Hashing
(C) Separate Chaining
(D) Quadratic Probing
Correct Answer: (C)
[EN] Separate Chaining lets keys reside in external linked lists outside the primary array slots (Open Hashing), while fixing each key's bucket address (Closed Addressing).
[HI] सेपरेट चेनिंग में डेटा प्राइमरी टेबल से बाहर लिंक्ड लिस्ट में रखा जाता है, इसलिए इसे Open Hashing कहा जाता है।
Q3. Primary Clustering is a major performance degradation characteristic of which probing scheme?
(Primary Clustering (प्राथमिक समूहन) किस प्रोबिंग विधि की मुख्य प्रदर्शन समस्या है?)
(A) Separate Chaining
(B) Cuckoo Hashing
(C) Double Hashing
(D) Linear Probing
Correct Answer: (D)
[EN] Linear Probing inspects adjacent slots (h+1, h+2, ...), causing filled blocks to merge into long contiguous runs that lengthen every probe.
[HI] लीनियर प्रोबिंग में क्रमिक स्लॉट्स की जांच से भरे हुए स्लॉट्स का बड़ा समूह बन जाता है जिसे Primary Clustering कहते हैं।
Q4. Why does Quadratic Probing suffer from Secondary Clustering even after eliminating Primary Clustering?
(Primary Clustering समाप्त करने के बावजूद Quadratic Probing में Secondary Clustering क्यों उत्पन्न होती है?)
(A) Quadratic probing checks adjacent slots +1, +2, +3
(B) Keys with the same initial hash value h'(k) still trace the exact same probe sequence
(C) It requires doubling the hash table on every collision
(D) It links colliding keys in an external singly linked list
Correct Answer: (B)
[EN] In (h'(k) + i^2) mod m, probe offsets depend only on i, so any two keys sharing h'(k) collide along the same entire chain.
[HI] एक ही प्रारंभिक हैश h'(k) वाली सभी कुंजियाँ वर्ग ऑफसेट i^2 के समान क्रम में ही प्रोब करती हैं, जिससे सेकेंडरी क्लस्टरिंग बनती है।
Q5. Which two conditions must hold for the secondary hash function h2(k) in Double Hashing?
(डबल हैशिंग में द्वितीयक हैश फंक्शन h2(k) के लिए कौन सी दो शर्तें अनिवार्य होती हैं?)
(A) h2(k) == 0 and h2(k) must be even
(B) h2(k) > m and alpha > 2
(C) h2(k) == h1(k) and m must be power of 10
(D) h2(k) != 0 and gcd(h2(k), m) = 1 (coprime to table size m)
Correct Answer: (D)
[EN] If h2(k) = 0, probing stalls on the same slot infinitely; coprimality with m guarantees the probe visits every single slot in the table.
[HI] यदि h2(k) = 0 होगा तो प्रोबिंग एक ही स्लॉट पर रुक जाएगी, और m से सह-अभाज्य (coprime) होने पर पूरी टेबल के सभी स्लॉट जांचे जाते हैं।
Q6. Given table size m = 10, hash h(k) = k mod 10, and Linear Probing, into which slot will key 23 go after inserting keys [43, 13, 23] in order?
(m = 10 और h(k) = k mod 10 के साथ लीनियर प्रोबिंग में [43, 13, 23] को क्रमशः डालने पर कुंजी 23 किस स्लॉट में जाएगी?)
(A) Slot 4
(B) Slot 6
(C) Slot 3
(D) Slot 5
Correct Answer: (D)
[EN] 43%10=3 (Slot 3); 13%10=3 -> probes to Slot 4; 23%10=3 -> probes 3 (full), 4 (full), lands in Slot 5.
[HI] 43 स्लॉट 3 में, 13 स्लॉट 4 में और 23 को 3 व 4 भरे मिलने पर लीनियर प्रोबिंग से स्लॉट 5 में रखा जाएगा।
Q7. Given table size m = 7, h(k) = k mod 7, and Quadratic Probing h(k, i) = (h(k) + i^2) mod 7, where is key 16 placed after inserting [9, 2, 16]?
(m = 7, h(k) = k mod 7 और क्वाड्रैटिक प्रोबिंग (h(k) + i^2) mod 7 से [9, 2, 16] डालने पर 16 किस स्लॉट में जाएगा?)
(A) Slot 5
(B) Slot 4
(C) Slot 3
(D) Slot 6
Correct Answer: (D)
[EN] 9%7=2 -> Slot 2; 2%7=2 -> (2+1^2)%7=3 -> Slot 3; 16%7=2 -> i=1 gives 3 (full), i=2 gives (2+4)%7 = Slot 6.
[HI] 9 स्लॉट 2 में, 2 (i=1) स्लॉट 3 में और 16 के लिए i=1 (3 भरा), i=2 पर (2+2^2)%7 = स्लॉट 6 मिलेगा।
Q8. Why must deleted slots in Open Addressing be marked with a Tombstone sentinel instead of being set back to EMPTY?
(ओपन एड्रेसिंग में डिलीट किए गए स्लॉट को सीधे EMPTY करने के बजाय Tombstone (DELETED) मार्कर से क्यों चिह्नित किया जाता है?)
(A) Tombstones automatically compress the array size by half
(B) EMPTY slots trigger stack overflow in linked lists
(C) EMPTY slots violate two's complement key hashing
(D) Setting a slot to EMPTY breaks search probe chains for keys inserted later past that slot
Correct Answer: (D)
[EN] If search encounters EMPTY before finding a probed key further down the sequence, it falsely reports the key as absent.
[HI] स्लॉट को EMPTY करने पर बाद में प्रोब होकर आगे रखी गई कुंजियों की सर्च बीच में ही रुककर गलत परिणाम देगी।
Q9. Under Simple Uniform Hashing, what is the expected time complexity of an UNSUCCESSFUL search in Separate Chaining with n keys and m buckets (alpha = n/m)?
(सिंपल यूनिफॉर्म हैशिंग के अंतर्गत n कुंजियों व m बकेट्स वाली Separate Chaining टेबल में असफल सर्च की औसत समय जटिलता क्या है?)
(A) Theta(1 + alpha)
(B) Theta(n^2)
(C) Theta(1 / (1 - alpha)^2)
(D) Theta(log m)
Correct Answer: (A)
[EN] Computing h(k) takes O(1) and traversing the expected alpha = n/m nodes in that bucket before seeing NULL takes Theta(alpha).
[HI] हैश गणना में O(1) और उस बकेट की औसत alpha = n/m लंबाई की चेन जांचने में Theta(alpha) समय लगता है।
Q10. In Java 8+ HashMap (which uses Separate Chaining), what structure replaces a long linked-list bucket when its chain exceeds 8 nodes (and capacity >= 64)?
(Java 8+ के HashMap में बकेट की चेन लंबाई 8 से अधिक (व क्षमता >= 64) होने पर लिंक्ड लिस्ट को किस संरचना में बदला जाता है?)
(A) Min-Heap
(B) Circular Queue
(C) Red-Black Tree (reducing bucket worst-case to O(log n))
(D) Quadratic Probe Array
Correct Answer: (C)
[EN] Treeification converts pathological collision chains into balanced Red-Black trees so worst-case search drops from O(n) to O(log n).
[HI] लंबे कोलिजन चेन से बचने के लिए Java 8 इसे Red-Black ट्री में बदल देता है, जिससे वर्स्ट-केस सर्च O(log n) हो जाती है।
Q11. For Quadratic Probing h(k, i) = (h'(k) + i^2) mod m, what pair of conditions guarantees that a new key insertion always finds an empty slot?
(क्वाड्रैटिक प्रोबिंग (h'(k) + i^2) mod m में किन दो शर्तों के पूरा होने पर नया एलिमेंट डालने के लिए खाली स्लॉट मिलना सुनिश्चित रहता है?)
(A) m is a power of 10 and alpha = 1.0
(B) Table size m is even and alpha <= 0.9
(C) Table size m is prime and load factor alpha <= 0.5
(D) Key values are strictly negative
Correct Answer: (C)
[EN] Number theory proves that the first ceil(m/2) quadratic residues modulo prime m are all distinct, guaranteeing an open slot when the table is at least half empty.
[HI] अभाज्य संख्या m होने पर पहले (m+1)/2 वर्ग मॉड्यूलो शेषफल भिन्न होते हैं, अतः टेबल आधी खाली (alpha <= 0.5) होने पर स्लॉट अवश्य मिलता है।
Q12. Why can Linear Probing outperform Separate Chaining in real-world CPUs despite having higher theoretical clustering at moderate load factors?
(मध्यम लोड फैक्टर पर भी वास्तविक CPU पर लीनियर प्रोबिंग कई बार सेपरेट चेनिंग से तेज क्यों चलती है?)
(A) Linear Probing supports load factor alpha = 5.0
(B) Adjacent array probes hit L1/L2 CPU cache lines with zero pointer-chasing or malloc overhead
(C) Linear Probing never encounters any hash collisions
(D) Separate Chaining runs in O(n^2) space
Correct Answer: (B)
[EN] Consecutive slots lie in the same 64-byte cache line, avoiding cache misses and dynamic heap allocations per node.
[HI] लगातार मेमोरी स्लॉट्स एक ही CPU कैश लाइन में आते हैं और हर नोड के लिए पॉइंटर या डायनामिक मेमोरी आवंटन की आवश्यकता नहीं पड़ती।
Q13. In Double Hashing with m = 11, h1(k) = k mod 11, and h2(k) = 7 - (k mod 7), what is the 2nd probe index (i = 1) for key k = 25 after colliding at i = 0?
(डबल हैशिंग (m = 11, h1(k) = k % 11, h2(k) = 7 - (k % 7)) में कुंजी k = 25 के i = 0 पर टकराने के बाद i = 1 का प्रोब इंडेक्स क्या होगा?)
(A) 8
(B) 6
(C) 9
(D) 3
Correct Answer: (B)
[EN] h1(25) = 25 % 11 = 3; h2(25) = 7 - (25 % 7) = 7 - 4 = 3; for i = 1: (3 + 1*3) % 11 = 6.
[HI] h1(25) = 3 तथा h2(25) = 7 - 4 = 3; इसलिए i = 1 पर (3 + 1*3) % 11 = 6 प्राप्त होगा।
Q14. What happens to Open Addressing search complexity if too many Tombstones accumulate without rehashing?
(बिना रिहैशिंग किए ओपन एड्रेसिंग टेबल में बहुत अधिक Tombstones जमा होने पर सर्च प्रदर्शन पर क्या असर पड़ता है?)
(A) Tombstones automatically re-balance like AVL trees
(B) Lookup speeds up to O(1) strictly
(C) The load factor drops below 0
(D) Search degenerates toward O(n) because searches must skip over every tombstone until hitting EMPTY
Correct Answer: (D)
[EN] Although tombstones hold no active keys, search cannot stop on a tombstone and traverses long tombstone runs until finding EMPTY.
[HI] यद्यपि टॉम्बस्टोन में सक्रिय कुंजी नहीं होती, पर सर्च EMPTY मिलने तक हर टॉम्बस्टोन को पार करता है जिससे समय O(n) की ओर बढ़ जाता है।
Q15. Which collision strategy is BEST suited when the maximum number of keys is completely unknown ahead of time and deletions occur very frequently?
(यदि कुल कुंजियों की संख्या पहले से अज्ञात हो और बार-बार डिलीशन करना हो, तो कौन सी तकनीक सबसे उपयुक्त होती है?)
(A) Linear Probing with fixed array
(B) Quadratic Probing without tombstones
(C) Separate Chaining
(D) Static Direct Addressing
Correct Answer: (C)
[EN] Separate Chaining grows dynamically beyond m (alpha > 1) and supports clean O(1) node removal without leaving tombstones.
[HI] सेपरेट चेनिंग बिना निश्चित सीमा (alpha > 1 संभव) के बढ़ सकती है और बिना टॉम्बस्टोन छोड़े सरल डिलीशन करती है।
Q16. Which statement comparing Open Addressing and Separate Chaining is FALSE?
(ओपन एड्रेसिंग और सेपरेट चेनिंग की तुलना के बारे में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) Double Hashing suffers from severe Primary Clustering identical to Linear Probing
(B) Open Addressing never allocates nodes outside the hash array
(C) Separate Chaining allocates extra memory for node pointers
(D) Resizing/rehashing is triggered in both methods when alpha grows too high
Correct Answer: (A)
[EN] Double Hashing uses a key-dependent step size h2(k), eliminating both Primary and Secondary Clustering.
[HI] डबल हैशिंग कुंजी-आधारित स्टेप h2(k) का उपयोग करती है, जिससे प्राइमरी और सेकेंडरी दोनों क्लस्टरिंग समाप्त हो जाती हैं।
Q17. Within Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining, which collision method directly maps to: "Array of bucket pointers to linked lists/trees"?
(Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining में कौन सा Collision Method सीधे "Array of bucket pointers to linked lists/trees" से संबंधित है?)
(A) Linear Probing
(B) Quadratic Probing
(C) Double Hashing
(D) Separate Chaining
Correct Answer: (D)
[EN] In Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining, 'Separate Chaining' handles 'Array of bucket pointers to linked lists/trees' (Supports alpha > 1; zero clustering or tombstones).
[HI] Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining में 'Separate Chaining' का कार्य/विवरण 'Array of bucket pointers to linked lists/trees' (Supports alpha > 1; zero clustering or tombstones) है।
Q18. Which option accurately describes 'Linear Probing' in Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining?
(Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining के संदर्भ में 'Linear Probing' की सही विशेषता कौन सी है?)
(A) Array of bucket pointers to linked lists/trees
(B) h(k, i) = (h'(k) + i) mod m
(C) h(k, i) = (h'(k) + c1*i + c2*i^2) mod m
(D) h(k, i) = (h1(k) + i * h2(k)) mod m
Correct Answer: (B)
[EN] 'Linear Probing' provides 'h(k, i) = (h'(k) + i) mod m' — key point: Best CPU cache locality; suffers Primary Clustering.
[HI] 'Linear Probing' का मुख्य विवरण 'h(k, i) = (h'(k) + i) mod m' है (Best CPU cache locality; suffers Primary Clustering)।
Q19. In Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining, identify the correct parameter for the specification: "h(k, i) = (h'(k) + c1*i + c2*i^2) mod m".
(Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining में "h(k, i) = (h'(k) + c1*i + c2*i^2) mod m" विवरण किस विकल्प के लिए सही है?)
(A) Separate Chaining
(B) Quadratic Probing
(C) Linear Probing
(D) Double Hashing
Correct Answer: (B)
[EN] 'Quadratic Probing' corresponds to 'h(k, i) = (h'(k) + c1*i + c2*i^2) mod m' (Avoids primary clustering; exhibits Secondary Clustering).
[HI] 'Quadratic Probing' का संबंध 'h(k, i) = (h'(k) + c1*i + c2*i^2) mod m' (Avoids primary clustering; exhibits Secondary Clustering) से है।
Q20. Considering Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining, what key behavior defines 'Double Hashing'?
(Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining में 'Double Hashing' की मुख्य भूमिका या मान क्या है?)
(A) h(k, i) = (h1(k) + i * h2(k)) mod m
(B) h(k, i) = (h'(k) + c1*i + c2*i^2) mod m
(C) h(k, i) = (h'(k) + i) mod m
(D) Array of bucket pointers to linked lists/trees
Correct Answer: (A)
[EN] 'Double Hashing' represents 'h(k, i) = (h1(k) + i * h2(k)) mod m' (No primary/secondary clustering; needs gcd(h2(k), m)=1).
[HI] 'Double Hashing' का अर्थ/मान 'h(k, i) = (h1(k) + i * h2(k)) mod m' है (No primary/secondary clustering; needs gcd(h2(k), m)=1)।
Collision Resolution: Open Addressing (Linear, Quadratic) vs Chaining — Exam FAQs
Q1: Why is Separate Chaining called Open Hashing while Open Addressing is called Closed Hashing?
सेपरेट चेनिंग को Open Hashing और ओपन एड्रेसिंग को Closed Hashing क्यों कहा जाता है?
[EN] The naming refers to where keys live relative to the table array: in Open Hashing (Separate Chaining), keys overflow into open external linked lists outside the table; in Closed Hashing (Open Addressing), all keys stay closed strictly inside the table slots.
[HI] नामकरण टेबल के बाहर या भीतर डेटा रखने पर आधारित है: Open Hashing (चेनिंग) में डेटा टेबल से बाहर लिंक्ड लिस्ट में जाता है, जबकि Closed Hashing (ओपन एड्रेसिंग) में सभी कुंजियाँ टेबल एरे के भीतर ही बंद रहती हैं।
Q2: How is a practical table size m chosen for Double Hashing?
डबल हैशिंग के लिए व्यावहारिक रूप से टेबल का आकार m कैसे चुना जाता है?
[EN] Choose m to be a prime number and define h2(k) = R - (k mod R) where R is a prime slightly smaller than m, ensuring 1 <= h2(k) <= R < m and gcd(h2(k), m) = 1.
[HI] m को एक अभाज्य संख्या (Prime) चुना जाता है तथा h2(k) = R - (k mod R) रखा जाता है जहाँ R, m से छोटी अभाज्य संख्या है, ताकि h2(k) कभी 0 न हो और m से सह-अभाज्य रहे।
Q3: What load factor threshold typically triggers rehashing in Open Addressing vs Separate Chaining?
ओपन एड्रेसिंग बनाम सेपरेट चेनिंग में सामान्यतः किस लोड फैक्टर पर रिहैशिंग (Rehashing) की जाती है?
[EN] Open Addressing usually rehashes around alpha = 0.5 to 0.75 (for instance Python dicts resize at 2/3 full) before clustering spikes, while Separate Chaining often rehashes at alpha = 0.75 to 1.0 (Java HashMap uses 0.75).
[HI] क्लस्टरिंग से बचने के लिए ओपन एड्रेसिंग में alpha = 0.5 से 0.75 (जैसे Python dict में 2/3) पर रिहैशिंग होती है, जबकि सेपरेट चेनिंग में सामान्यतः 0.75 से 1.0 (Java HashMap में 0.75) थ्रेशहोल्ड रखा जाता है।
Post a Comment
Post a Comment