Hashing MCQ Quiz in हिन्दी - Objective Question with Answer for Hashing - मुफ्त [PDF] डाउनलोड करें

सही उत्तर हैश टेबल है। 

Key Points

• हैश टेबल:
  • हैश टेबल कुछ परिचालनों के लिए तेज़ पहुँच समय प्राप्त करने के लिए अतिरिक्त मेमोरी का उपयोग करती हैं।
  • वे किसी सरणी में सूचकांकों की कुंजियों को मैप करने के लिए हैश फ़ंक्शन का उपयोग करते हैं, जो खोज, सम्मिलन और विलोपन के लिए नियत समय औसत-स्थिति पहुंच प्रदान करते हैं।
  • हालाँकि, स्थान के संदर्भ में एक समझौता है क्योंकि टकराव (एक ही सूचकांक में दो कुंजियाँ हैशिंग) हो सकती हैं, जिससे लिंक की गई सूचियाँ या ओपन एड्रेसिंग जैसी अतिरिक्त संरचनाओं की आवश्यकता होती है।

Additional Information

• सरणियाँ:
  • सरणियाँ एक सूचकांक का उपयोग करके अवयवों तक नियत समय पहुंच प्रदान करते हैं।
  • उनका एक निश्चित आकार होता है, जिससे यदि सरणी उसमें मौजूद अवयवों की वास्तविक संख्या से बड़ी हो तो मेमोरी बेकार हो सकती है।
  • संचालन को तेज़ करने के लिए किसी अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है, और एक्सेस समय पहले से ही कुशल होता है।
• लिंक्ड सूचियाँ:
  • लिंक्ड सूचियाँ गतिशील मेमोरी आवंटन प्रदान करती हैं, जिससे अवयवों को कुशल सम्मिलन और हटाने की अनुमति मिलती है।
  • हालाँकि, किसी विशिष्ट सूचकांक पर किसी अवयव तक पहुँचने में रैखिक समय लगता है, क्योंकि आपको शुरुआत से ही सूची को पार करना होगा।
  • लिंक्ड सूचियाँ संचालन को गति देने के लिए अतिरिक्त मेमोरी का उपयोग नहीं करती हैं।
• स्टैक:
  • स्टैक लास्ट-इन-फर्स्ट-आउट (LIFO) सिद्धांत का पालन करते हैं और एक छोर पर अवयवों को कुशल सम्मिलन और हटाने की अनुमति देते हैं।
  • इन्हें आम तौर पर सरणियों या लिंक्ड सूचियों का उपयोग करके कार्यान्वित किया जाता है।
  • स्टैक संचालन को गति देने के लिए अतिरिक्त मेमोरी का उपयोग नहीं करते हैं; उनकी दक्षता LIFO संरचना की प्रकृति से आती है।

सही उत्तर रैखिक जांच है। 

Key Points

• रैखिक जांच:
  • जब संघट्ट होता है (दो अवयव एक ही स्थान पर हैश होते हैं), तो रैखिक जांच में संघट्टित अवयवों को हैश तालिका में अगले उपलब्ध (खाली) स्थान में रखना शामिल होता है।
  • यदि उस स्थान पर भी कब्जा कर लिया गया है, तो यह एक रैखिक फैशन में अगले खाली स्थान की खोज जारी रखता है (एक समय में एक स्थान को आगे बढ़ाते हुए) जब तक कि एक खाली स्थान नहीं मिल जाता है।
  • रैखिक जांच से समूहीकरण हो सकता है, जहां क्रमागत अवयव हैश तालिका में समूह बनाते हैं।

Additional Information

• द्विघात जांच:
  • रैखिक जांच के समान, लेकिन एक समय में एक स्थान को स्थानांतरित करने के बजाय, द्विघात जांच जांच के लिए अगली स्थिति निर्धारित करने के लिए एक द्विघात फलन का उपयोग करती है।
  • यदि हैश सूचकांक पर स्थान पर कब्जा कर लिया गया है, तो यह क्रमिक वर्गों द्वारा बढ़ाए गए पदों पर स्थान की जांच करता है।
  • द्विघात जांच, रैखिक जांच की तुलना में समूहीकरण को कम करने में मदद करती है।
• पृथक श्रृंखला:
  • संघट्टित अवयवों को हैश तालिका में अगले उपलब्ध स्थान में रखने के बजाय, अलग श्रृंखला में हैश तालिका में प्रत्येक स्थान पर एक लिंक की गई सूची बनाए रखना शामिल है।
  • जब कोई संघट्ट होता है, तो संघट्टित अवयव उस स्थान पर लिंक की गई सूची में जुड़ जाते हैं।
  • संघट्ट को संभालने के लिए प्रत्येक स्थान में एक अलग डेटा संरचना (जैसे लिंक की गई सूची या वृक्ष) होती है।
• द्वि-हैशिंग:
  • द्वि-हैशिंग में, जांच प्रयासों के बीच चरण आकार निर्धारित करने के लिए एक द्वितीयक हैश फलन का उपयोग किया जाता है।
  • यदि कोई संघट्ट होता है, तो एल्गोरिदम जांच के लिए एक नए सूचकांक की गणना करने के लिए द्वितीयक हैश फलन का उपयोग करता है।
  • यह समूहन से बचने में मदद करता है और खाली स्थान ढूंढने का अधिक व्यवस्थित तरीका प्रदान करता है।

सही विकल्प हैशिंग के द्वारा सर्च है।

संकल्पना:

रैखिक सर्च में, दी गई सूची के प्रत्येक घटक की तुलना किसी भी घटक को छोड़े बिना दी गई कुंजी(की) के साथ एक-एक करके की जाती है।

यह तब उपयोगी होता है जब हमें एक छोटी सी अवर्गीकृत सूची में किसी आइटम को खोजने की आवश्यकता होती है, लेकिन सूची के आकार में वृद्धि के साथ सूची को खोजने में समय लगता है।

 

उदाहरण के लिए, लंबाई 5 की एक सूची पर विचार करें और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 5

यदि हम उसी सूची का आकार बढ़ाते हैं (मान लीजिए 15) और मुख्य घटक इस सूची के अंत में मौजूद है। प्रमुख घटक को खोजने के लिए आवश्यक तुलनाओं की संख्या = सूची का आकार अर्थात् 15

 

बाइनरी सर्च में, खोजी जाने वाली कुंजी(की) की तुलना वर्गीकृत सूची के बीच के घटक से की जाती है, इसके परिणामस्वरूप तीन में से कोई भी संभावना हो सकती है:

i) यदि मध्य स्थिति का घटक कुंजी(की) से मेल खाता है तो खोज सफल होती है।

ii) यदि मध्य स्थिति का घटक कुंजी(की) से बड़ा है तो मुख्य घटक सूची के बाएं भाग में मौजूद हो सकता है।

iii) यदि मध्य स्थान पर स्थित घटक कुंजी(की) से छोटा है, तो कुंजी घटक सूची के दाहिने हिस्से में मौजूद हो सकता है।

यह प्रक्रिया तब तक जारी रहती है जब तक कि घटक नहीं मिल जाता या सूची पूरी तरह से ट्रेवर्स्ड नहीं हो जाती।

इस प्रकार जैसे-जैसे सूची का आकार बढ़ता है, सूची को खोजने में लगने वाला समय बढ़ता जाता है। लेकिन यह रैखिक सर्च के लिए आवश्यक समय जितना बड़ा नहीं होगा।

हैश-आधारित सर्चिंग के लिए कुंजी(की) की स्थिति का पता लगाने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है, बशर्ते कि प्रत्येक घटक हैश फलन द्वारा तय की गई अपनी निर्दिष्ट स्थिति में मौजूद हो।

उदाहरण के लिए, लंबाई 5 और हैश फलन की सूची पर विचार करें:

फलन: h(element) = element % size(list)

हैशिंग फलन एक गणितीय फलन है जो स्थिर समय में हैश फलन को प्रदान किए गए प्रत्येक अद्वितीय मान के लिए अद्वितीय परिणाम उत्पन्न करता है।

उदाहरण के लिए: लंबाई 5 की एक सूची पर विचार करें और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 2 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी(की) तुलना की आवश्यकता होती है। 

उसी तरह सूची का आकार बढ़ाना (15 मान लें) और यदि हम कुंजी(की) = 12 की खोज करना चाहते हैं, तो हैश फलन द्वारा रिटर्न किया गया सूचकांक h(12) = 12% 5 = 12 है और सूचकांक पर कुंजी(की) खोजने के लिए केवल एक कुंजी तुलना की आवश्यकता है।

इस प्रकार यह सूची की लंबाई से स्वतंत्र होता है।

प्राथमिक क्लस्टरिंग:

• यह ओपन एड्रेस आधारित हैश तालिकाओं के दो प्रमुख विफलता मोडों में से एक है, विशेष रूप से रैखिक प्रोबिंग का उपयोग करने वाले।
• यह हैश आघात के बाद हैश तालिका में दो अभिलेखों को एक ही स्थान पर हैश करने का कारण बनता है, और एक रिकॉर्ड को उसके जांच क्रम में अगले स्थान पर ले जाने का कारण बनता है।

द्वितीयक क्लस्टरिंग:

द्वितीयक क्लस्टरिंग आम तौर पर रैखिक संबोधन और द्विघात प्रोबिंग सहित ओपन एड्रेसिंग मोड के साथ होता है जिसमें प्रोब अनुक्रम कुंजी और साथ ही हैश श्रृंखलन में भी स्वतंत्र होता है,।

दोहरी हैशिंग:

दोहरी हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग हैश आघात को हल करने के लिए हैश टेबलों में ओपन-एड्रेसिंग के साथ किया जाता है, जब आघात होता है तो ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके।

दोहरी हैशिंग तकनीक क्लस्टिंग समस्याओं से मुक्त है

सही उत्तर हैश टेबल का आकार सूची के आकार से बड़ा हो सकता है।

Key Points

• हैशिंग द्वारा खोज में, हैश टेबल का आकार वास्तव में सूची के आकार (तत्वों की संख्या) से बड़ा हो सकता है।
• एक हैश टेबल को एक हैश फ़ंक्शन का उपयोग करके बकेट या स्लॉट की एक सरणी में एक इंडेक्स की गणना करके डेटा तक कुशल पहुँच प्रदान करने के लिए डिज़ाइन किया गया है।
• हैश टेबल का आकार (बकेट की संख्या) अक्सर टकराव को कम करने और कुशल डेटा पुनर्प्राप्ति सुनिश्चित करने के लिए तत्वों की संख्या से अधिक चुना जाता है।
• आकार में यह अंतर खोज, सम्मिलित और हटाने के संचालन के लिए O(1) की औसत समय जटिलता को बनाए रखने में मदद करता है।
• एक बड़ा हैश टेबल होने से तत्वों को फैलाने और एक ही इंडेक्स में कई तत्वों के हैश होने की संभावना को कम करने में मदद मिलती है।

Additional Information

• जबकि एक बड़ा हैश टेबल आकार टकराव को कम कर सकता है, लेकिन इसके लिए अधिक मेमोरी की भी आवश्यकता होती है। इसलिए, मेमोरी उपयोग और प्रदर्शन के बीच एक ट्रेड ऑफ है।
• रीहैशिंग एक तकनीक है जिसका उपयोग हैश टेबल का आकार गतिशील रूप से बदलने के लिए किया जाता है जब लोड फैक्टर (हैश टेबल आकार के लिए तत्वों की संख्या का अनुपात) एक निश्चित सीमा से अधिक हो जाता है।
• सामान्य हैश टेबल कार्यान्वयन में टकराव को संभालने के लिए ओपन एड्रेसिंग और अलग चेनिंग शामिल हैं।
• टकराव की संभावना को और कम करने के लिए हैश टेबल का आकार अक्सर एक अभाज्य संख्या होता है।

चूंकि हम यादृच्छिक प्रोबिंग का उपयोग कर रहे हैं:

इन्सर्ट 15:

(15)%7 = 1

इन्सर्ट 11:

(11)%7 = 4

इन्सर्ट 25:

(25)%7 = 4 / संघट्‍टन:

i = 4

 i = (i + 5) % 7    / यादृच्छिक फ़ंक्शन का उपयोग करना

i = (4 + 5)%7 = 2

अत: 25 की स्थिति 2nd है 

प्राथमिक क्लस्टरिंग:

• यह ओपन एड्रेस आधारित हैश तालिकाओं के दो प्रमुख विफलता मोडों में से एक है, विशेष रूप से रैखिक प्रोबिंग का उपयोग करने वाले।
• यह हैश आघात के बाद हैश तालिका में दो अभिलेखों को एक ही स्थान पर हैश करने का कारण बनता है, और एक रिकॉर्ड को उसके जांच क्रम में अगले स्थान पर ले जाने का कारण बनता है।

द्वितीयक क्लस्टरिंग:

द्वितीयक क्लस्टरिंग आम तौर पर रैखिक संबोधन और द्विघात प्रोबिंग सहित ओपन एड्रेसिंग मोड के साथ होता है जिसमें प्रोब अनुक्रम कुंजी और साथ ही हैश श्रृंखलन में भी स्वतंत्र होता है,।

दोहरी हैशिंग:

दोहरी हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग हैश आघात को हल करने के लिए हैश टेबलों में ओपन-एड्रेसिंग के साथ किया जाता है, जब आघात होता है तो ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके।

दोहरी हैशिंग तकनीक क्लस्टिंग समस्याओं से मुक्त है

अवधारणा:

सजातीय डेटा संरचना (HDS):

• HDS जिसमें केवल पूर्णांक या केवल फ्लोट मान जैसे समान प्रकार के डेटा होते हैं।
• सजातीय डेटा संरचना का मूल उदाहरण सरणी है।

 

व्याख्या

प्रश्न में हमें आदेश दिया गया कि परिमित HDS जो कुछ भी नहीं है, लेकिन सरणी लेकिन सरणी में मौजूद नहीं है

विकल्प इसलिए हमें उनमें से सबसे अच्छा विकल्प चुनना है। विकल्प के अनुसार चलते है

विकल्प 1: अनबद्ध सूची

अनबद्ध सूची HDS है, लेकिन परिमित नहीं है क्योंकि अनबद्ध सूची आकार रन टाइम पर तय किया गया है।

विकल्प 2: ग्राफ़

ग्राफ़ HDS है लेकिन परिमित नहीं है क्योंकि रन टाइम पर ग्राफ़ का आकार तय किया जाता है।

विकल्प 3: ट्री

ट्री HDS है लेकिन परिमित नहीं है क्योंकि ट्री का आकार रन टाइम पर तय किया जाता है।

विकल्प 4: हैश तालिका

हैश तालिका का आदेश दिया गया है और परिमित डेटा संरचना है (आकार संकलन समय पर तय किया गया है)।

इसलिए उत्तर के लिए विकल्प 4 सबसे अच्छा विकल्प है।

टकराव तब होता है जब दो आइटम एक ही स्लॉट में हैश हो जाते हैं। आदर्श रूप से, एक आदर्श हैश फ़ंक्शन वह होता है जिसमें कोई टकराव नहीं होता है। लेकिन वास्तविक दुनिया के अनुप्रयोगों में यह संभव नहीं है। इसलिए जब किसी भरे हुए स्लॉट में या प्राथमिक बकेट में भरे हुए स्थान पर रिकॉर्ड डालने का प्रयास किया जाता है, तो टकराव होता है।

सही उत्तर विकल्प 4 है।

संकल्पना:

खुला एड्रेसिंग या बंद हैशिंग हैश तालिका में टकराव वियोजन की एक विधि है। इस विधि के साथ हैश टकराव को ऐरे में वैकल्पिक स्थानों के माध्यम से जाँच या खोज द्वारा वियोजित किया जाता है।

दी गयी जानकारी,

हैश तालिका आकार = 7

हैश फंक्शन = (MOD 7)

हैश तालिका कुंजी, 53, 32, 43, 51, 99 हैं।

53 के हैश तालिका मान = 53 MOD 7 =4

32 के हैश तालिका मान = 32 MOD 7 =4

43 के हैश तालिका मान = 43 MOD 7 =1

51 के हैश तालिका मान = 51 MOD 7 =2

99 के हैश तालिका मान = 99 MOD 7 =1

ऐरे के साथ हैश तालिका A[ 0...6] है।

सूचकांक 0

सूचकांक 1 43

सूचकांक 2 51

सूचकांक 3 99

सूचकांक 4 53

सूचकांक 5 32

सूचकांक 6

अतः सही उत्तर EMPTY, 43, 51, 99, 53, 32, EMPTY है।

चूंकि हम यादृच्छिक प्रोबिंग का उपयोग कर रहे हैं:

इन्सर्ट 15:

(15)%7 = 1

इन्सर्ट 11:

(11)%7 = 4

इन्सर्ट 25:

(25)%7 = 4 / संघट्‍टन:

i = 4

 i = (i + 5) % 7    / यादृच्छिक फ़ंक्शन का उपयोग करना

i = (4 + 5)%7 = 2

अत: 25 की स्थिति 2nd है 

प्राथमिक क्लस्टरिंग:

• यह ओपन एड्रेस आधारित हैश तालिकाओं के दो प्रमुख विफलता मोडों में से एक है, विशेष रूप से रैखिक प्रोबिंग का उपयोग करने वाले।
• यह हैश आघात के बाद हैश तालिका में दो अभिलेखों को एक ही स्थान पर हैश करने का कारण बनता है, और एक रिकॉर्ड को उसके जांच क्रम में अगले स्थान पर ले जाने का कारण बनता है।

द्वितीयक क्लस्टरिंग:

द्वितीयक क्लस्टरिंग आम तौर पर रैखिक संबोधन और द्विघात प्रोबिंग सहित ओपन एड्रेसिंग मोड के साथ होता है जिसमें प्रोब अनुक्रम कुंजी और साथ ही हैश श्रृंखलन में भी स्वतंत्र होता है,।

दोहरी हैशिंग:

दोहरी हैशिंग एक कंप्यूटर प्रोग्रामिंग तकनीक है जिसका उपयोग हैश आघात को हल करने के लिए हैश टेबलों में ओपन-एड्रेसिंग के साथ किया जाता है, जब आघात होता है तो ऑफसेट के रूप में कुंजी के द्वितीयक हैश का उपयोग करके।

दोहरी हैशिंग तकनीक क्लस्टिंग समस्याओं से मुक्त है

उत्तर: विकल्प 3

स्पष्टीकरण:

इन्सर्ट 37: 

 37 मोड 7 ≡ 2 ;

37 को हैश तालिका की दूसरी बकेट में मैप किया जाएगा।

0
1
2	37
3
4
5
6

इन्सर्ट 38: 

 38 मोड 7 ≡ 3

38 को तीसरी बकेट में मैप किया जाएगा।

0
1
2	37
3	38
4
5
6

इन्सर्ट 72:

 72 मोड 7 ≡ 2

2 आघात होंगे (बकेट 2 और 3 पर)

अंत में, 72 को 4 बकेट में मैप किया जाएगा।

0
1
2	37
3	38
4	72
5
6

 

इन्सर्ट 48: 

 48 मोड 7 = 6

48 को छठे बकेट में मैप किया जाएगा

इन्सर्ट 98:

 98 मोड 7 ≡ 0

98 को 0 बकेट में मैप किया जाएगा।

0	98
1
2	37
3	38
4	72
5
6	48

 

इन्सर्ट 11: 

 11 मोड 7 ≡ 4 

लेकिन 4 खाली नहीं है, इसलिए एक आघात होता है और 11 को पांचवी बकेट में मैप किया जाएगा।

0	98
1
2	37
3	38
4	72
5	11
6	48

अवधारणा:

सजातीय डेटा संरचना (HDS):

• HDS जिसमें केवल पूर्णांक या केवल फ्लोट मान जैसे समान प्रकार के डेटा होते हैं।
• सजातीय डेटा संरचना का मूल उदाहरण सरणी है।

 

व्याख्या

प्रश्न में हमें आदेश दिया गया कि परिमित HDS जो कुछ भी नहीं है, लेकिन सरणी लेकिन सरणी में मौजूद नहीं है

विकल्प इसलिए हमें उनमें से सबसे अच्छा विकल्प चुनना है। विकल्प के अनुसार चलते है

विकल्प 1: अनबद्ध सूची

अनबद्ध सूची HDS है, लेकिन परिमित नहीं है क्योंकि अनबद्ध सूची आकार रन टाइम पर तय किया गया है।

विकल्प 2: ग्राफ़

ग्राफ़ HDS है लेकिन परिमित नहीं है क्योंकि रन टाइम पर ग्राफ़ का आकार तय किया जाता है।

विकल्प 3: ट्री

ट्री HDS है लेकिन परिमित नहीं है क्योंकि ट्री का आकार रन टाइम पर तय किया जाता है।

विकल्प 4: हैश तालिका

हैश तालिका का आदेश दिया गया है और परिमित डेटा संरचना है (आकार संकलन समय पर तय किया गया है)।

इसलिए उत्तर के लिए विकल्प 4 सबसे अच्छा विकल्प है।

टकराव तब होता है जब दो आइटम एक ही स्लॉट में हैश हो जाते हैं। आदर्श रूप से, एक आदर्श हैश फ़ंक्शन वह होता है जिसमें कोई टकराव नहीं होता है। लेकिन वास्तविक दुनिया के अनुप्रयोगों में यह संभव नहीं है। इसलिए जब किसी भरे हुए स्लॉट में या प्राथमिक बकेट में भरे हुए स्थान पर रिकॉर्ड डालने का प्रयास किया जाता है, तो टकराव होता है।