PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Hashing: Hash Table, Hash Functions (Division, Mid-Square) (हैशिंग: हैश टेबल, हैश फंक्शन्स और की-टू-एड्रेस मैपिंग) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Hashing maps arbitrary keys directly into fixed-size Hash Table slots via mathematical Hash Functions like Division (k mod m) and Mid-Square, targeting O(1) average lookup while managing collisions via Load Factor.
अध्याय सार: हैशिंग डिवीजन (k mod m) व मिड-स्क्वायर जैसे हैश फंक्शन्स द्वारा कुंजियों को सीधे हैश टेबल इंडेक्स पर मैप करती है, जिससे लोड फैक्टर व टकराव (Collision) नियंत्रण के साथ औसत O(1) खोज संभव होती है।
Hashing: Hash Table, Hash Functions (Division, Mid-Square): Detailed Notes & Architecture (हैशिंग: हैश टेबल, हैश फंक्शन्स और की-टू-एड्रेस मैपिंग)
1. Hash Table Concept, Key-to-Address Mapping & O(1) Goal (हैश टेबल अवधारणा व कुंजी-से-पता मैपिंग)
[EN] When keys span a vast universe U (e.g., 10-digit phone numbers or long strings), allocating a Direct Address Table of size |U| wastes massive memory. Hashing compresses U onto a compact Hash Table T[0..m-1] using a deterministic Hash Function h(k) in {0, 1, ..., m-1}. Under Uniform Hashing assumptions and bounded Load Factor alpha = n / m, insert, search, and delete run in O(1) average time, degrading to O(n) worst-case only if all keys collide onto one slot.
[HI] जब संभावित कुंजियों का क्षेत्र U बहुत विशाल हो, तो सीधे इंडेक्स एरे बनाना असंभव मेमोरी खर्च करता है। हैशिंग एक हैश फंक्शन h(k) द्वारा बड़ी कुंजी को सीमित आकार m की हैश टेबल के इंडेक्स 0..m-1 में मैप करती है। समान वितरण व नियंत्रित लोड फैक्टर (alpha = n/m) के साथ खोज, जोड़ना और हटाना औसत O(1) समय में होता है (यद्यपि सभी कुंजियों के एक ही स्लॉट पर टकराने पर वर्स्ट केस O(n) हो सकता है)।
2. Division Method (k mod m) & Prime Table Size Rule (डिवीजन मेथड (k mod m) व अभाज्य संख्या नियम)
[EN] The Division Method computes h(k) = k mod m—extremely fast with a single modulo instruction. Selecting table size m is critical: avoid m = 2^p (which inspects only the lowest p binary bits of k, ignoring upper bits) and avoid m = 10^p (which ignores upper decimal digits). Instead, choose m as a PRIME number NOT close to an exact power of 2 or 10 so every bit of k influences the remainder and patterned keys scatter evenly.
[HI] डिवीजन मेथड में h(k) = k mod m सूत्र लगता है जो एक ही भागफल संक्रिया से बहुत तेज चलता है। इसमें टेबल का आकार m चुनना अत्यंत महत्वपूर्ण है: m को 2^p या 10^p के बराबर या बहुत पास नहीं रखना चाहिए क्योंकि 2^p लेने पर केवल निचले p बिट्स ही काम आते हैं और ऊपरी बिट्स अनदेखे रह जाते हैं। अतः m को हमेशा 2 की घातों से दूर एक अभाज्य संख्या (Prime Number) चुना जाता है।
3. Mid-Square, Folding & Multiplication Hash Functions (मिड-स्क्वायर, फोल्डिंग व मल्टीप्लिकेशन हैश विधियाँ)
[EN] The Mid-Square Method squares the key (k^2) and extracts r middle digits or middle binary bits as the table address—effective because middle digits of k^2 depend on nearly every digit/bit of k (e.g., k = 123 -> 123^2 = 15129 -> middle 2 digits 51). Folding splits k into equal chunks and sums them mod m. Knuth's Multiplication Method computes floor(m * ((k * A) mod 1)) using irrational constant A ~ 0.6180339887 (golden ratio conjugate), permitting power-of-2 table sizes like m = 2^p safely.
[HI] मिड-स्क्वायर विधि में कुंजी का वर्ग (k^2) करके बीच के अंक या मध्य बिट्स निकाल लिए जाते हैं; इसका लाभ यह है कि वर्ग के मध्य अंक मूल कुंजी के लगभग सभी अंकों पर निर्भर करते हैं (जैसे 123^2 = 15129 के मध्य दो अंक 51)। फोल्डिंग में कुंजी के हिस्से जोड़कर mod m करते हैं। नुथ (Knuth) की मल्टीप्लिकेशन विधि floor(m * ((k * A) mod 1)) में A ≈ 0.618 उपयोग करती है, जहाँ m को 2^p रखना भी सुरक्षित रहता है।
4. Collisions, Pigeonhole Principle, Load Factor & Resolution (टकराव, पिजनहोल सिद्धांत, लोड फैक्टर व समाधान)
[EN] By the Pigeonhole Principle, whenever distinct keys |U| exceed slots m (and even earlier via the Birthday Paradox), two different keys k1 != k2 map to the same index h(k1) == h(k2)—called a Hash Collision. Load Factor alpha = n / m measures occupancy: Separate Chaining links colliding items in per-bucket lists (allowing alpha > 1, avg search O(1 + alpha)), whereas Open Addressing probes alternate array slots inside the table (Linear Probing causes primary clustering, Double Hashing prevents it, requiring alpha <= 1).
[HI] पिजनहोल सिद्धांत के अनुसार जब कुंजियाँ टेबल स्लॉट्स m से अधिक हों तो दो भिन्न कुंजियों का एक ही इंडेक्स पर आना (Collision) अवश्यंभावी है। लोड फैक्टर alpha = n/m भराव दर्शाता है: सेपरेट चेनिंग में हर बकेट में लिंक्ड लिस्ट जुड़ती है (जहाँ alpha > 1 संभव है), जबकि ओपन एड्रेसिंग में खाली स्लॉट टेबल के अंदर ही खोजे जाते हैं (लीनियर प्रोबिंग में प्राइमरी क्लस्टरिंग होती है और डबल हैशिंग इसे रोकती है; यहाँ alpha <= 1 अनिवार्य है)।
Syntax, Formula & Technical Example (Hashing: Hash Table, Hash Functions (Division, Mid-Square))
# Division & Mid-Square Hash Examples (m = 97 prime / 100)
def hash_division(k, m=97):
return k % m # e.g. 12345 % 97 = 26
def hash_midsquare(k, digits=2):
sq = str(k * k).zfill(4) # k=123 -> sq='15129'
mid = len(sq) // 2
return int(sq[mid - 1 : mid - 1 + digits]) # extracts '51'
Hashing: Hash Table, Hash Functions (Division, Mid-Square) Quick Reference & Comparison Table
| Hash Function / Concept | Formula / Definition | Design Rule & Exam Fact |
|---|---|---|
| Division Method | h(k) = k mod m | Choose m as a prime far from powers of 2 or 10 |
| Mid-Square Method | Extract r middle digits/bits of k^2 | Output depends on almost all digits/bits of key k |
| Multiplication Method | floor(m * ((k * A) mod 1)) | Knuth constant A ~ 0.618; m = 2^p works cleanly |
| Load Factor (alpha) | alpha = n / m (keys / table size) | Triggers rehash around 0.75; alpha <= 1 in open addressing |
Hashing: Hash Table, Hash Functions (Division, Mid-Square) Top 20 Bilingual MCQs with Answers
Q1. In the Division hash function h(k) = k mod m, what type of value should table size m ideally be?
(डिवीजन हैश फंक्शन h(k) = k mod m में टेबल का आकार m आदर्श रूप से कैसा होना चाहिए?)
(A) Always an even composite number
(B) A prime number not too close to an exact power of 2 or 10
(C) An exact multiple of 10 such as 100 or 1000
(D) An exact power of 2 such as 64 or 1024
Correct Answer: (B)
[EN] Choosing m = 2^p only uses the lowest p bits of k; a prime away from 2^p mixes all bits uniformly.
[HI] 2^p चुनने से केवल निचले p बिट्स ही इंडेक्स तय करते हैं, इसलिए सभी बिट्स का प्रभाव शामिल करने हेतु 2 की घात से दूर अभाज्य संख्या चुनी जाती है।
Q2. Using the Mid-Square hash method on key k = 32 with a 2-digit table index (00..99), what is the square and extracted middle 2 digits?
(मिड-स्क्वायर हैश विधि में कुंजी k = 32 का वर्ग करने पर मध्य के 2 अंकों का हैश इंडेक्स क्या निकलेगा?)
(A) 32^2 = 1024 -> 24
(B) 32^2 = 1024 -> 10
(C) 32^2 = 1024 -> 42
(D) 32^2 = 1024 -> middle two digits = 02 (index 2)
Correct Answer: (D)
[EN] Squaring 32 gives 4-digit '1024'; discarding outer digits '1' and '4' yields middle digits '02' (slot 2).
[HI] 32 का वर्ग 1024 चार अंकों का है; पहला (1) और अंतिम (4) अंक छोड़ने पर मध्य के दो अंक 02 प्राप्त होते हैं।
Q3. What does the Load Factor (alpha) of a Hash Table with n stored elements and m slots equal?
(m स्लॉट्स वाली हैश टेबल में n तत्व संग्रहित होने पर लोड फैक्टर (alpha) का सूत्र क्या होता है?)
(A) alpha = n * m
(B) alpha = n / m
(C) alpha = log2(m / n)
(D) alpha = m / n
Correct Answer: (B)
[EN] Load factor measures average items per bucket: stored keys n divided by table capacity m.
[HI] लोड फैक्टर प्रति स्लॉट औसत तत्वों की संख्या अर्थात n / m के बराबर होता है।
Q4. In a Hash Table using Open Addressing (Linear Probing, Quadratic Probing, or Double Hashing), what is the maximum possible Load Factor alpha?
(ओपन एड्रेसिंग (लीनियर प्रोबिंग आदि) वाली हैश टेबल में लोड फैक्टर alpha का अधिकतम संभव मान क्या हो सकता है?)
(A) alpha can grow up to infinity
(B) alpha <= 1 (at most 1 key per slot)
(C) alpha <= log2(m)
(D) alpha <= 0.25 strictly
Correct Answer: (B)
[EN] Because every element resides directly inside the m-slot array without external lists, n cannot exceed m (alpha <= 1).
[HI] ओपन एड्रेसिंग में हर तत्व सीधे m स्लॉट्स में से एक में ही रहता है, अतः n कभी m से अधिक (alpha <= 1) नहीं हो सकता।
Q5. What is the average vs worst-case time complexity of searching in a Hash Table?
(हैश टेबल में किसी कुंजी को खोजने की औसत (Average) और वर्स्ट-केस (Worst-Case) टाइम कॉम्प्लेक्सिटी क्रमशः क्या होती है?)
(A) Average: O(log n), Worst Case: O(n)
(B) Average: O(n), Worst Case: O(n^2)
(C) Average: O(1), Worst Case: O(n)
(D) Average: O(1), Worst Case: O(1) always
Correct Answer: (C)
[EN] Uniform hashing with constant alpha gives O(1) expected time, while all n keys colliding on one slot degrades search to O(n).
[HI] अच्छे हैश वितरण में औसत समय O(1) मिलता है, परंतु सभी n कुंजियों के एक ही स्लॉट में टकरा जाने पर वर्स्ट केस O(n) हो जाता है।
Q6. In Knuth's Multiplication Method h(k) = floor(m * ((k * A) mod 1)), which constant A is famously recommended?
(नुथ (Knuth) की मल्टीप्लिकेशन हैश विधि में किस अचर मान A की अनुशंसा की जाती है?)
(A) A = 0.5 exactly
(B) A ~ (sqrt(5) - 1) / 2 ~ 0.6180339887
(C) A = 3.14159
(D) A = 1.0
Correct Answer: (B)
[EN] The golden ratio conjugate ~0.618 distributes multiples smoothly even when table size m is a power of 2.
[HI] गोल्डन रेशियो संयुग्मी A ≈ 0.6180339887 चुनने पर m को 2^p रखने पर भी कुंजियाँ समान रूप से फैलती हैं।
Q7. Why are hash collisions mathematically guaranteed whenever universe size |U| > table size m?
(जब कुंजियों का क्षेत्र |U| टेबल आकार m से बड़ा हो, तो टकराव (Collision) होना गणितीय रूप से तय क्यों है?)
(A) Because Open Addressing prohibits empty slots
(B) Because all hash functions ignore the last bit
(C) By the Pigeonhole Principle: mapping > m keys into m slots forces at least two keys to share a slot
(D) Because modulo arithmetic only returns odd indices
Correct Answer: (C)
[EN] If more pigeons (> m keys) enter m pigeonholes (table slots), at least one slot receives multiple keys.
[HI] पिजनहोल सिद्धांत के अनुसार m से अधिक वस्तुओं को m खानों में रखने पर कम से कम एक खाने में एक से अधिक वस्तु आना निश्चित है।
Q8. Which Open Addressing technique suffers severely from 'Primary Clustering' (long contiguous occupied blocks slowing down probes)?
(इनमें से कौन सी ओपन एड्रेसिंग तकनीक 'प्राइमरी क्लस्टरिंग (Primary Clustering)' से गंभीर रूप से प्रभावित होती है?)
(A) Double Hashing: (h1(k) + i * h2(k)) mod m
(B) Separate Chaining with Red-Black Trees
(C) Cuckoo Hashing
(D) Linear Probing: (h(k) + i) mod m
Correct Answer: (D)
[EN] Linear Probing steps by +1 sequentially, merging nearby clusters so new keys get trapped scanning long filled runs.
[HI] लीनियर प्रोबिंग +1 क्रम से खाली जगह खोजती है जिससे भरे हुए स्लॉट्स के बड़े-बड़े गुच्छे (Primary Clusters) बनते जाते हैं।
Q9. How does Double Hashing (h(k, i) = (h1(k) + i * h2(k)) mod m) avoid both primary and secondary clustering?
(डबल हैशिंग (h1(k) + i * h2(k)) mod m प्राइमरी और सेकेंडरी दोनों क्लस्टरिंग से कैसे बचती है?)
(A) Because it allocates linked lists outside the table
(B) Because probe step size h2(k) depends on the key k itself, giving colliding keys different probe sequences
(C) Because h2(k) always equals 1
(D) Because it sets alpha = 2
Correct Answer: (B)
[EN] Two keys colliding at h1(k) almost certainly have distinct secondary steps h2(k), avoiding identical probe paths (provided h2(k) != 0 and gcd(h2(k), m) = 1).
[HI] इसमें प्रोब स्टेप h2(k) स्वयं कुंजी k पर निर्भर होता है, जिससे एक ही स्थान पर टकराने वाली दो कुंजियाँ अलग-अलग रास्तों पर आगे बढ़ती हैं।
Q10. In the Folding Hash Method (Shift Folding) with 2-digit chunks for key k = 123456 and m = 100, what is h(k)?
(शिफ्ट फोल्डिंग विधि में 2-2 अंकों के टुकड़ों के साथ कुंजी k = 123456 और m = 100 का हैश मान क्या होगा?)
(A) (12 * 34 * 56) mod 100 = 48
(B) (1 + 2 + 3 + 4 + 5 + 6) mod 100 = 21
(C) (12 + 34 + 56) mod 100 = 102 mod 100 = 2
(D) 56 mod 100 = 56
Correct Answer: (C)
[EN] Splitting 123456 into 2-digit segments gives 12 + 34 + 56 = 102; taking mod 100 discards carry to yield 02.
[HI] 123456 को दो-दो अंकों (12, 34, 56) में जोड़ने पर 102 आता है और mod 100 लेने पर 02 (इंडेक्स 2) मिलता है।
Q11. If a hash table uses Separate Chaining with m = 100 slots and n = 250 keys distributed uniformly, what is the expected chain length per bucket?
(यदि m = 100 स्लॉट्स वाली सेपरेट चेनिंग हैश टेबल में n = 250 कुंजियाँ समान रूप से बंटी हों, तो प्रति बकेट औसत चेन लंबाई कितनी होगी?)
(A) 0.4
(B) 25
(C) 2.5 (equals Load Factor alpha = 250 / 100)
(D) 100
Correct Answer: (C)
[EN] Average chain length equals load factor alpha = n / m = 250 / 100 = 2.5, giving O(1 + alpha) search time.
[HI] औसत चेन लंबाई लोड फैक्टर alpha = n / m = 250 / 100 = 2.5 होती है।
Q12. What happens during 'Rehashing' when a Hash Table's Load Factor exceeds a threshold like 0.75?
(जब हैश टेबल का लोड फैक्टर 0.75 जैसी सीमा पार कर जाता है, तब 'रिहैशिंग (Rehashing)' में क्या किया जाता है?)
(A) All chains are merged into index 0
(B) Old keys are permanently deleted to make room
(C) The hash function is disabled and replaced with Binary Search
(D) A new larger table (usually ~2x prime size) is allocated and every existing key is re-inserted using the updated table size m
Correct Answer: (D)
[EN] Simply copying indices into a bigger table breaks k mod m_old != k mod m_new, so all keys must be re-hashed into the new array.
[HI] लगभग दोगुने आकार की नई टेबल बनाकर पुरानी सभी कुंजियों को नए आकार m के अनुसार पुनः हैश (Re-insert) किया जाता है।
Q13. Why must a Hash Table function h(k) be strictly DETERMINISTIC?
(हैश टेबल के लिए हैश फंक्शन h(k) का पूर्णतः नियतात्मक (Deterministic) होना क्यों आवश्यक है?)
(A) So that collisions never happen
(B) So it matches cryptographic SHA-256 bit length
(C) Calling h(k) during search must always yield the exact same bucket index produced during insert
(D) So keys become sorted alphabetically inside the table
Correct Answer: (C)
[EN] If h(k) returned random or time-dependent slots, inserted keys could never be located reliably later.
[HI] यदि एक ही कुंजी के लिए अलग-अलग समय पर अलग इंडेक्स मिले, तो संग्रहित कुंजी को बाद में खोजा ही नहीं जा सकेगा।
Q14. If h(k) = k mod 16 is used as a Division hash for keys [16, 32, 48, 64], what critical flaw shows up immediately?
(यदि कुंजियों [16, 32, 48, 64] के लिए h(k) = k mod 16 उपयोग किया जाए, तो कौन सी बड़ी खामी तुरंत सामने आती है?)
(A) Mid-square bits overflow
(B) Every key hashes to index 0 because m = 16 is a power of 2 sharing a factor with the keys
(C) Keys hash outside 0..15 bounds
(D) Search time improves to O(0)
Correct Answer: (B)
[EN] Multiples of 16 share factor 16 with m=16, collapsing all keys to bucket 0; choosing prime m=17 scatters them to [16, 15, 14, 13].
[HI] 16 के गुणज होने और m = 16 (2^4) लेने से सभी कुंजियाँ इंडेक्स 0 पर टकरा जाती हैं; अभाज्य m = 17 इन्हें अलग-अलग बिखेर देता।
Q15. Which statement is NOT true about Hash Table Hash Functions vs Cryptographic Hash Functions?
(हैश टेबल के हैश फंक्शन और क्रिप्टोग्राफिक हैश फंक्शन की तुलना में इनमें से कौन सा कथन असत्य है?)
(A) Division Method works best when m is a prime number
(B) Hash Table functions prioritize speed and uniform slot distribution
(C) Mid-Square uses all bits of k inside k^2 before extracting middle bits
(D) Hash Table functions like k mod m provide cryptographic pre-image resistance and collision intractability
Correct Answer: (D)
[EN] Simple table hashes (Division, Mid-Square) are trivial to invert or collide deliberately—unlike SHA-256 which prioritizes cryptographic security.
[HI] k mod m या मिड-स्क्वायर केवल गति और समान वितरण के लिए हैं; इनमें SHA-256 जैसी क्रिप्टोग्राफिक सुरक्षा या अपरिवर्तनीयता नहीं होती।
Q16. In Open Addressing, why can't deleting a key simply set its slot back to EMPTY (NULL)?
(ओपन एड्रेसिंग हैश टेबल से कोई तत्व हटाते (Delete) समय स्लॉट को सीधे EMPTY (NULL) क्यों नहीं किया जा सकता?)
(A) Because Separate Chaining deletes the entire bucket
(B) Because deleting a key reduces m by 1
(C) Setting it to EMPTY would prematurely break probe chains for later keys that skipped past that slot—requiring a DELETED (Tombstone) marker
(D) Because arrays cannot store NULL values
Correct Answer: (C)
[EN] If key B probed past slot X (held by A) and A is deleted to EMPTY, searching for B would stop at X and falsely report 'not found'—tombstones prevent this.
[HI] यदि हटाई गई कुंजी के आगे प्रोब करके रखी गई दूसरी कुंजी को बाद में खोजा जाए, तो बीच में EMPTY मिलने पर खोज वहीं रुक जाएगी; इसलिए 'Deleted/Tombstone' चिह्न लगाया जाता है।
Q17. Within Hashing: Hash Table, Hash Functions (Division, Mid-Square), which hash function / concept directly maps to: "h(k) = k mod m"?
(Hashing: Hash Table, Hash Functions (Division, Mid-Square) में कौन सा Hash Function / Concept सीधे "h(k) = k mod m" से संबंधित है?)
(A) Multiplication Method
(B) Load Factor (alpha)
(C) Division Method
(D) Mid-Square Method
Correct Answer: (C)
[EN] In Hashing: Hash Table, Hash Functions (Division, Mid-Square), 'Division Method' handles 'h(k) = k mod m' (Choose m as a prime far from powers of 2 or 10).
[HI] Hashing: Hash Table, Hash Functions (Division, Mid-Square) में 'Division Method' का कार्य/विवरण 'h(k) = k mod m' (Choose m as a prime far from powers of 2 or 10) है।
Q18. Which option accurately describes 'Mid-Square Method' in Hashing: Hash Table, Hash Functions (Division, Mid-Square)?
(Hashing: Hash Table, Hash Functions (Division, Mid-Square) के संदर्भ में 'Mid-Square Method' की सही विशेषता कौन सी है?)
(A) floor(m * ((k * A) mod 1))
(B) Extract r middle digits/bits of k^2
(C) alpha = n / m (keys / table size)
(D) h(k) = k mod m
Correct Answer: (B)
[EN] 'Mid-Square Method' provides 'Extract r middle digits/bits of k^2' — key point: Output depends on almost all digits/bits of key k.
[HI] 'Mid-Square Method' का मुख्य विवरण 'Extract r middle digits/bits of k^2' है (Output depends on almost all digits/bits of key k)।
Q19. In Hashing: Hash Table, Hash Functions (Division, Mid-Square), identify the correct parameter for the specification: "floor(m * ((k * A) mod 1))".
(Hashing: Hash Table, Hash Functions (Division, Mid-Square) में "floor(m * ((k * A) mod 1))" विवरण किस विकल्प के लिए सही है?)
(A) Division Method
(B) Multiplication Method
(C) Mid-Square Method
(D) Load Factor (alpha)
Correct Answer: (B)
[EN] 'Multiplication Method' corresponds to 'floor(m * ((k * A) mod 1))' (Knuth constant A ~ 0.618; m = 2^p works cleanly).
[HI] 'Multiplication Method' का संबंध 'floor(m * ((k * A) mod 1))' (Knuth constant A ~ 0.618; m = 2^p works cleanly) से है।
Q20. Considering Hashing: Hash Table, Hash Functions (Division, Mid-Square), what key behavior defines 'Load Factor (alpha)'?
(Hashing: Hash Table, Hash Functions (Division, Mid-Square) में 'Load Factor (alpha)' की मुख्य भूमिका या मान क्या है?)
(A) floor(m * ((k * A) mod 1))
(B) Extract r middle digits/bits of k^2
(C) alpha = n / m (keys / table size)
(D) h(k) = k mod m
Correct Answer: (C)
[EN] 'Load Factor (alpha)' represents 'alpha = n / m (keys / table size)' (Triggers rehash around 0.75; alpha <= 1 in open addressing).
[HI] 'Load Factor (alpha)' का अर्थ/मान 'alpha = n / m (keys / table size)' है (Triggers rehash around 0.75; alpha <= 1 in open addressing)।
Hashing: Hash Table, Hash Functions (Division, Mid-Square) — Exam FAQs
Q1: Why does Division Method fail badly when table size m is a power of 2?
टेबल का आकार m को 2 की घात (Power of 2) रखने पर डिवीजन मेथड क्यों खराब प्रदर्शन करता है?
[EN] Computing k mod 2^p simply strips away everything except the lowest p bits of k. If keys share common suffixes (like memory addresses ending in 00 or IDs with fixed trailing codes), massive collisions pile into just a few buckets.
[HI] k mod 2^p केवल संख्या के सबसे निचले p बिट्स देखता है और ऊपरी बिट्स को पूरी तरह अनदेखा कर देता है। यदि कुंजियों के अंतिम बिट्स एक जैसे हों, तो लगभग सभी कुंजियाँ कुछ ही बकेट्स में टकरा जाती हैं।
Q2: Why is Mid-Square considered better than just taking the first or last digits of a key?
कुंजी के केवल पहले या अंतिम अंक लेने की बजाय मिड-स्क्वायर विधि बेहतर क्यों मानी जाती है?
[EN] When multiplying k by itself (k^2), digits in the middle of the product combine cross-products of almost all digits/bits of k, reducing bias from leading prefixes or trailing suffixes.
[HI] k को k से गुणा (k^2) करने पर गुणनफल के बीच के अंकों में मूल कुंजी के लगभग सभी अंकों का योगदान शामिल हो जाता है, जिससे समान प्रीफिक्स या सफिक्स का पक्षपात समाप्त हो जाता है।
Q3: Does Hashing keep elements in sorted order like a Binary Search Tree?
क्या हैशिंग बाइनरी सर्च ट्री (BST) की तरह तत्वों को सॉर्टेड क्रम में रखती है?
[EN] No. Hash functions intentionally scatter keys across buckets randomly-looking; therefore range queries (like 'find all keys between 50 and 100') or min/max lookups require O(n) scans instead of O(log n) as in balanced BSTs.
[HI] नहीं। हैशिंग कुंजियों को बिखेरकर O(1) खोज देती है; अतः रेंज क्वेरी या न्यूनतम/अधिकतम खोजने जैसे कार्य हैश टेबल में O(n) लेते हैं, जबकि संतुलित BST में O(log n) में हो जाते हैं।
Post a Comment
Post a Comment