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

परिचय

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

हैश फंक्शन्स

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

विभाजन विधि (Division Method)

हैश फंक्शन बनाने के लिए यह सबसे आसान विधि है। हैश फंक्शन को इस प्रकार वर्णित किया जा सकता है:

h(k) = k mod n

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

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

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

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

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

गुणन विधि (Multiplication Method)

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

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 के किसी भी मान के साथ काम कर सकता है, हालांकि कुछ मान दूसरों की तुलना में बेहतर माने जाते हैं।

मिड स्क्वेयर विधि (Mid Square Method)

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

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

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

k = 50
k*k = 2500
h(50) = 50
प्राप्त हैश मान 50 है

हैश टेबल्स

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

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

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

35 50 11 79 76 85

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

h(k) = k mod 10

रैखिक प्रोबिंग का उपयोग करके, मानों को हैश टेबल में इस प्रकार संग्रहीत किया जाता है: