डेटा संरचना में हैश तालिका: Python उदाहरण

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

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

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

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

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

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

हैश फ़ंक्शन

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

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

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

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

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

h(k) = k1 % m

यहाँ,

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

उदाहरण

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

[1,2,3]

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

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

चरण 1) उस स्थिति की गणना करें जो पहले मान द्वारा ली जाएगी जैसे कि

एच(1) = 1 % 3

= 1

महत्व 1 पर कब्जा होगा पर अंतरिक्ष सूचकांक 1

चरण 2) उस स्थिति की गणना करें जो दूसरे मान द्वारा ली जाएगी

एच(2) = 2 % 3

= 2

महत्व 2 पर कब्जा होगा पर अंतरिक्ष सूचकांक 2

चरण 3) तीसरे मान द्वारा ग्रहण की जाने वाली स्थिति की गणना करें।

एच(3) = 3 % 3

= 0

महत्व 3 पर कब्जा होगा पर अंतरिक्ष सूचकांक 0

अंतिम परिणाम

अब हमारी भरी हुई हैश तालिका इस प्रकार होगी।

एक अच्छे हैश फ़ंक्शन के गुण

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

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

टक्कर

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

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

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

[3,2,9,11,7]

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

निम्न तालिका में उत्पन्न होने वाले हैश मान दर्शाए गए हैं।

कुंजी	हैश एल्गोरिथ्म (k1 % m)	हैश मान
3	3% 7	3
2	3% 7	2
9	3% 7	2
11	3% 7	4
7	3% 7	0

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

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

चेनिंग

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

निम्न छवि दर्शाती है कि एक श्रृंखलाबद्ध सूची कैसी दिखती है

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

श्रृंखलाबद्ध सूचियों के लाभ

श्रृंखलाबद्ध सूचियों के लाभ निम्नलिखित हैं:

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

जांच

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

जांच की विधियां निम्नलिखित हैं:

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

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

हैश तालिका संचालन

यहां है ये Operaहैश तालिकाओं द्वारा समर्थित कार्य:

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

डेटा डालने का ऑपरेशन

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

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

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

डेटा हटाने का ऑपरेशन

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

हैश तालिका कार्यान्वयन Python उदाहरण

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

def hash_key( key, m):
    return key % m


m = 7

print(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 परिभाषित करता है जो पैरामीटर key और m को स्वीकार करता है।
2. हैश मान निर्धारित करने के लिए एक सरल मापांक ऑपरेशन का उपयोग करता है
3. एक चर m को परिभाषित करता है जिसे मान 7 पर आरंभीकृत किया जाता है। यह हमारी हैश तालिका का आकार है
4. 3 का हैश मान परिकलित करता है और प्रिंट करता है
5. 2 का हैश मान परिकलित करता है और प्रिंट करता है
6. 9 का हैश मान परिकलित करता है और प्रिंट करता है
7. 11 का हैश मान परिकलित करता है और प्रिंट करता है
8. 7 का हैश मान परिकलित करता है और प्रिंट करता है

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

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

Python शब्दकोश उदाहरण

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

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

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.
{}

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

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

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

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

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

हैश तालिकाओं के लाभ

हैश तालिकाओं के उपयोग के पक्ष/लाभ इस प्रकार हैं:

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

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

हैश तालिकाओं के उपयोग के नुकसान इस प्रकार हैं:

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

सारांश

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