डेटा संरचना में हैश टेबल: पायथन उदाहरण

हाशिंग क्या है?

एक हैश एक मान है जिसकी एक निश्चित लंबाई है, और यह गणितीय सूत्र का उपयोग करके उत्पन्न होता है। हैश वैल्यू का उपयोग डेटा कम्प्रेशन, क्रिप्टोलॉजी इत्यादि में किया जाता है। डेटा इंडेक्सिंग में हैश वैल्यू का उपयोग किया जाता है क्योंकि इनका उपयोग उन मानों की परवाह किए बिना किया जाता है, जिनकी लंबाई निर्धारित है। यह अलग-अलग लंबाई के अन्य मूल्यों की तुलना में न्यूनतम स्थान पर कब्जा करने के लिए हैश मान बनाता है।

एक हैश फ़ंक्शन कुंजी को हैश में बदलने के लिए एक गणितीय एल्गोरिदम को नियोजित करता है। टक्कर तब होती है जब एक हैश फ़ंक्शन एक से अधिक कुंजी के लिए समान हैश मान पैदा करता है।

इस एल्गोरिथ्म ट्यूटोरियल में, आप सीखेंगे:

• हाशिंग क्या है?
• हैश टेबल क्या है?
• हैश फ़ंक्शन
• एक अच्छे हैश फ़ंक्शन की योग्यता
• टक्कर
• हैश टेबल संचालन
• हैश टेबल पायथन उदाहरण
• हैश टेबल कोड स्पष्टीकरण
• पायथन डिक्शनरी उदाहरण
• जटिलता विश्लेषण
• वास्तविक दुनिया अनुप्रयोगों
• हैश टेबल के लाभ
• हैश टेबल का नुकसान

हैश टेबल क्या है?

एक HASH टेबल एक डेटा संरचना है कि कुंजी और मूल्यों की एक जोड़ी का उपयोग कर स्टोर मूल्यों है। प्रत्येक मान को एक अद्वितीय कुंजी सौंपी जाती है जो हैश फ़ंक्शन का उपयोग करके उत्पन्न होती है।

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

हैश फ़ंक्शन

उदाहरण के लिए, यदि हम कर्मचारी रिकॉर्ड को संग्रहीत करना चाहते हैं, और प्रत्येक कर्मचारी को कर्मचारी संख्या का उपयोग करके विशिष्ट रूप से पहचाना जाता है।

हम कर्मचारी संख्या को कुंजी के रूप में उपयोग कर सकते हैं और मूल्य के रूप में कर्मचारी डेटा असाइन कर सकते हैं।

उपरोक्त दृष्टिकोण को (m * n ² ) के क्रम के अतिरिक्त खाली स्थान की आवश्यकता होगी जहां चर m सरणी का आकार है, और कर्मचारी संख्या के लिए चर n अंकों की संख्या है। यह दृष्टिकोण एक संग्रहण स्थान समस्या का परिचय देता है।

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

निम्नलिखित एक साधारण हैश फ़ंक्शन का एक उदाहरण है

h(k) = k1 % m

यहां,

• h (k) हैश फंक्शन है जो एक पैरामीटर k को स्वीकार करता है। पैरामीटर k वह मान है जिसके लिए हम कुंजी की गणना करना चाहते हैं।
• k ₁ % m हमारे हैश फ़ंक्शन के लिए एल्गोरिथ्म है जहाँ k1 वह मान है जिसे हम संग्रहीत करना चाहते हैं, और m सूची का आकार है। हम कुंजी की गणना करने के लिए मापांक ऑपरेटर का उपयोग करते हैं।

उदाहरण

मान लेते हैं कि हमारे पास 3 के निश्चित आकार और निम्न मानों के साथ एक सूची है

[१,२,३]

हम उपरोक्त सूत्र का उपयोग उन पदों की गणना करने के लिए कर सकते हैं जो प्रत्येक मूल्य पर कब्जा करना चाहिए।

निम्न छवि हमारे हैश तालिका में उपलब्ध अनुक्रमित दिखाती है।

चरण 1)

उस स्थिति की गणना करें जो पहले मूल्य पर कब्जा कर लेगी जैसे कि

h (1) = 1% 3

= 1

मान 1 अनुक्रमणिका 1 पर स्थान पर होगा

चरण 2)

उस स्थिति की गणना करें जो दूसरे मूल्य पर कब्जा कर लिया जाएगा

h (2) = 2% 3

= २

मान 2 अनुक्रमणिका 2 पर स्थान पर कब्जा करेगा

चरण 3)

उस स्थिति की गणना करें जो तीसरे मूल्य पर कब्जा कर लिया जाएगा।

h (3) = 3% 3

= 0

मान 3 अनुक्रमणिका 0 पर स्थान पर कब्जा करेगा

अंतिम परिणाम

हैश टेबल में हमारा भरा अब इस प्रकार होगा।

एक अच्छे हैश फ़ंक्शन की योग्यता

एक अच्छे हैश फ़ंक्शन में निम्नलिखित गुण होने चाहिए।

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

टक्कर

एक टकराव तब होता है जब एल्गोरिथ्म एक से अधिक मूल्य के लिए एक ही हैश उत्पन्न करता है।

आइए एक उदाहरण देखें।

मान लें कि हमारे पास मूल्यों की निम्नलिखित सूची है

[3,2,9,11,7]

मान लेते हैं कि हैश तालिका का आकार 7 है, और हम सूत्र (k ₁ % m) का उपयोग करेंगे जहां m हैश तालिका का आकार है।

निम्न तालिका उन हैश मानों को दिखाती है जो उत्पन्न होंगे।

चाभी	हैश एल्गोरिदम (k 1 % m)	हैश वैल्यू
३	३% 7	३
२	३% 7	२
९	३% 7	२
1 1	३% 7	४
।	३% 7	०

जैसा कि हम उपर्युक्त परिणामों से देख सकते हैं, मान 2 और 9 में समान हैश मान है, और हम प्रत्येक स्थिति में एक से अधिक मान संग्रहीत नहीं कर सकते हैं।

दी गई समस्या को या तो जंजीर का उपयोग करके या हल करके हल किया जा सकता है। निम्नलिखित अनुभागों में विस्तार से चर्चा और जांच की जाती है।

चेनिंग

चेनिंग एक ऐसी तकनीक है जिसका उपयोग लिंक की गई सूचियों का उपयोग करके टकराव की समस्या को हल करने के लिए किया जाता है जिसमें प्रत्येक अद्वितीय अनुक्रमित होता है।

निम्न छवि दिखाती है कि एक जंजीर सूची कैसी दिखती है

2 और 9 दोनों एक ही सूचकांक पर कब्जा कर लेते हैं, लेकिन उन्हें लिंक की गई सूचियों के रूप में संग्रहीत किया जाता है। प्रत्येक सूची में एक विशिष्ट पहचानकर्ता होता है।

जंजीर सूची के लाभ

जंजीर सूची के लाभ निम्नलिखित हैं:

• डेटा सम्मिलित करते समय जंजीर सूचियों का प्रदर्शन बेहतर होता है क्योंकि डालने का क्रम O (1) है।
• यह एक हैश तालिका का आकार बदलने के लिए आवश्यक नहीं है जो एक जंजीर सूची का उपयोग करता है।
• यह बड़ी संख्या में मूल्यों को आसानी से समायोजित कर सकता है जब तक कि मुक्त स्थान उपलब्ध है।

जांच

दूसरी तकनीक जो टकराव को हल करने के लिए उपयोग की जाती है, वह जांच कर रही है। जांच विधि का उपयोग करते समय, यदि कोई टक्कर होती है, तो हम बस आगे बढ़ सकते हैं और अपने मूल्य को संग्रहीत करने के लिए एक खाली स्लॉट ढूंढ सकते हैं।

जांच करने के तरीके निम्नलिखित हैं:

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

हमारे उपरोक्त उदाहरण का उपयोग करके, प्रोबिंग का उपयोग करने के बाद हैश तालिका निम्नानुसार दिखाई देगी:

हैश टेबल संचालन

यहाँ, हैश तालिकाओं द्वारा समर्थित संचालन हैं:

• सम्मिलन - इस ऑपरेशन का उपयोग हैश तालिका में एक तत्व जोड़ने के लिए किया जाता है
• खोज - इस ऑपरेशन का उपयोग हैश तालिका में तत्वों की खोज के लिए किया जाता है
• हटाना - इस ऑपरेशन का उपयोग हैश तालिका से तत्वों को हटाने के लिए किया जाता है

डेटा ऑपरेशन सम्मिलित करना

सम्मिलित ऑपरेशन का उपयोग हैश तालिका में मानों को संग्रहीत करने के लिए किया जाता है। जब कोई नया मान हैश तालिका में संग्रहीत किया जाता है, तो उसे एक इंडेक्स नंबर असाइन किया जाता है। सूचकांक संख्या की गणना हैश फ़ंक्शन का उपयोग करके की जाती है। हैश फ़ंक्शन किसी भी टकराव को हल करता है जो सूचकांक संख्या की गणना करते समय होता है।

डेटा ऑपरेशन के लिए खोजें

खोज ऑपरेशन का उपयोग सूचकांक संख्या का उपयोग करते हुए हैश तालिका में मूल्यों को देखने के लिए किया जाता है। खोज ऑपरेशन वह मान देता है जो खोज अनुक्रमणिका संख्या से जुड़ा होता है। उदाहरण के लिए, यदि हम इंडेक्स 2 पर मान 6 संग्रहीत करते हैं, तो इंडेक्स नंबर 2 के साथ खोज ऑपरेशन 6 मान लौटाएगा।

डेटा ऑपरेशन हटाएं

हटाए गए ऑपरेशन का उपयोग हैश तालिका से मान निकालने के लिए किया जाता है। हटाने के लिए अनुक्रमणिका संख्या का उपयोग करके ऑपरेशन किया जाता है। एक बार जब कोई मूल्य हटा दिया जाता है, तो इंडेक्स नंबर को मुफ्त कर दिया जाता है। यह डालने के ऑपरेशन का उपयोग कर अन्य मूल्यों को संग्रहीत करने के लिए इस्तेमाल किया जा सकता है।

पायथन उदाहरण के साथ हैश टेबल का कार्यान्वयन

आइए एक साधारण उदाहरण देखें जो एक कुंजी के हैश मान की गणना करता है

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

हैश टेबल कोड स्पष्टीकरण

यहां,

1. एक फ़ंक्शन hash_key को परिभाषित करता है जो पैरामीटर कुंजी और मीटर को स्वीकार करता है।
2. हैश मान निर्धारित करने के लिए एक सरल मापांक ऑपरेशन का उपयोग करता है
3. एक वैरिएबल m को परिभाषित करता है जो मान 7 से आरंभ होता है। यह हमारे हैश टेबल का आकार है
4. गणना करता है और 3 के हैश मान को प्रिंट करता है
5. गणना करता है और 2 के हैश मान को प्रिंट करता है
6. गणना करता है और 9 के हैश मान को प्रिंट करता है
7. गणना करता है और 11 के हैश मान को प्रिंट करता है
8. गणना करता है और 7 के हैश मूल्य को प्रिंट करता है

उपरोक्त कोड को निष्पादित करने से निम्नलिखित परिणाम प्राप्त होते हैं।

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

पायथन डिक्शनरी उदाहरण

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

निम्न उदाहरण दिखाता है कि आप अजगर 3 में एक शब्दकोश डेटा प्रकार का उपयोग कैसे कर सकते हैं

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

यहां,

1. एक शब्दकोश चर कर्मचारी को परिभाषित करता है। कुंजी नाम का उपयोग मूल्य जॉन डो, उम्र 36 स्टोर करने के लिए किया जाता है, और स्थिति मूल्य व्यापार प्रबंधक संग्रहीत करता है।
2. कुंजी नाम का मान निकालता है और इसे टर्मिनल में प्रिंट करता है
3. सॉफ्टवेयर इंजीनियर के लिए महत्वपूर्ण स्थिति के मूल्य को अद्यतन करता है
4. कुंजी के नाम और स्थिति के मूल्यों को प्रिंट करता है
5. उन सभी मूल्यों को हटाता है जो हमारे शब्दकोश चर कर्मचारी में संग्रहीत हैं
6. कर्मचारी के मूल्य को छापता है

उपरोक्त कोड चलाने से निम्नलिखित परिणाम मिलते हैं।

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

जटिलता विश्लेषण

हैश तालिकाओं में ओ-(1) की सबसे अच्छी स्थिति में औसत समय की जटिलता है। सबसे खराब स्थिति समय जटिलता O (n) है। सबसे खराब स्थिति तब होती है जब कई मूल्य समान हैश कुंजी उत्पन्न करते हैं, और हमें टकराव को जांच करके हल करना होगा।

वास्तविक दुनिया अनुप्रयोगों

वास्तविक दुनिया में, डेटा को संग्रहीत करने के लिए हैश टेबल का उपयोग किया जाता है

• डेटाबेस
• सहयोगी सरणियाँ
• सेट
• मेमोरी कैश

हैश टेबल के लाभ

यहाँ, हैश टेबल का उपयोग करने के लाभ / लाभ हैं:

• डेटा को देखने, डालने और मौजूदा मानों को हटाने के दौरान हैश टेबल का प्रदर्शन उच्च होता है।
• हैश टेबल के लिए समय की जटिलता तालिका में मदों की संख्या की परवाह किए बिना स्थिर है।
• बड़े डेटासेट के साथ काम करने पर भी वे बहुत अच्छा प्रदर्शन करते हैं।

हैश टेबल का नुकसान

यहाँ, हैश तालिकाओं के उपयोग की बात है:

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

सारांश:

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