हैश फ़ंक्शंस और हैश टेबल्स

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

हैश फंक्शन

कुछ हैश फंक्शन निम्नलिखित हैं -

विभाजन विधि

हैश फ़ंक्शन बनाने का यह सबसे आसान तरीका है। हैश फ़ंक्शन को −

h(k) = k mod n

यहाँ, h(k) कुंजी मान k को हैश तालिका n के आकार से विभाजित करके शेष का उपयोग करके प्राप्त हैश मान है। यह सबसे अच्छा है कि n एक अभाज्य संख्या है क्योंकि यह सुनिश्चित करता है कि कुंजियों को अधिक एकरूपता के साथ वितरित किया जाता है।

विभाजन विधि का एक उदाहरण इस प्रकार है -

k=1276
n=10
h(1276) = 1276 mod 10
= 6

प्राप्त हैश मान 6

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

गुणा विधि

गुणन विधि के लिए उपयोग किया जाने वाला हैश फ़ंक्शन है -

h(k) = floor( n( kA mod 1 ) )

यहाँ, k कुंजी है और A 0 और 1 के बीच कोई भी स्थिर मान हो सकता है। k और A दोनों को गुणा किया जाता है और उनके भिन्नात्मक भाग को अलग किया जाता है। इसके बाद हैश मान प्राप्त करने के लिए इसे n से गुणा किया जाता है।

गुणन विधि का एक उदाहरण इस प्रकार है -

k=123
n=100
A=0.618033
h(123) = 100 (123 * 0.618033 mod 1)
= 100 (76.018059 mod 1)
= 100 (0.018059)
= 1

प्राप्त हैश मान 1

गुणन विधि का एक लाभ यह है कि यह A के किसी भी मान के साथ काम कर सकता है, हालाँकि कुछ मान दूसरों से बेहतर माने जाते हैं।

मध्य वर्ग विधि

मध्य वर्ग विधि एक बहुत अच्छा हैश फ़ंक्शन है। इसमें कुंजी के मान को चुकता करना और फिर मध्य r अंकों को हैश मान के रूप में निकालना शामिल है। r का मान हैश तालिका के आकार के अनुसार तय किया जा सकता है।

मिड स्क्वायर मेथड का एक उदाहरण इस प्रकार है -

मान लीजिए हैश टेबल में 100 मेमोरी लोकेशन हैं। तो r=2 क्योंकि स्मृति स्थान की कुंजी को मैप करने के लिए दो अंकों की आवश्यकता होती है।

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

हैश टेबल

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

हैश टेबल का एक उदाहरण इस प्रकार है -

मुख्य अनुक्रम जिसे हैश तालिका में संग्रहीत करने की आवश्यकता है वह है -

35 50 11 79 76 85

उपयोग किया गया हैश फ़ंक्शन h(k) है:

h(k) = k mod 10

रैखिक जांच का उपयोग करते हुए, मान हैश तालिका में -