हैश टेबल

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

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

एक अच्छी तरह से आयाम वाली हैश तालिका में, प्रत्येक लुकअप के लिए औसत लागत (निर्देशों की संख्या) तालिका में संग्रहीत तत्वों की संख्या से स्वतंत्र है। कई हैश टेबल डिजाइन भी मनमाने ढंग से आवेषण और कुंजी-मूल्य जोड़े के विलोपन की अनुमति देते हैं, ((परिशोधित^[2])) प्रति ऑपरेशन लगातार औसत लागत। ^[3]^[4]

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

हैशिंग का विचार है कि विभिन्न प्रकार की बाल्टियों में प्रविष्टियाँ (कुंजी / मूल्य जोड़े) वितरित करना। एक कुंजी को देखते हुए, एल्गोरिथ्म एक सूचकांक की गणना करता है जो बताता है कि प्रविष्टि कहां पाई जा सकती है:

सूची = f(कुंजी, array_size)

अक्सर यह दो चरणों में किया जाता है:

हैश = हैश_फंकशन(कुंजी)
सूची = हैश % array_size

इस पद्धति में, हैश सरणी आकार से स्वतंत्र होता है, और फिर इसे मॉडुलो ऑपरेटर ( % ) का उपयोग करके एक इंडेक्स ( 0 और array_size - 1 के बीच की संख्या) तक घटा दिया जाता है।

इस मामले में कि सरणी का आकार दो की शक्ति है, शेष ऑपरेशन को मास्किंग में कम किया जाता है, जो गति में सुधार करता है, लेकिन खराब हैश फ़ंक्शन के साथ समस्याएं बढ़ा सकता है।^[5]

हैश टकराव व्यावहारिक रूप से अपरिहार्य होते हैं जब संभव कुंजियों के एक बड़े सेट का एक यादृच्छिक सबसेट हैशिंग। उदाहरण के लिए, यदि 2,450 चाबियों को एक लाख बाल्टियों में रखा गया है, यहां तक कि पूरी तरह से समान यादृच्छिक वितरण के साथ, जन्मदिन की समस्या के अनुसार एक ही स्लॉट में कम से कम दो चाबियों के 95% होने की संभावना है।

इसलिए, इस तरह की घटनाओं को संभालने के लिए लगभग सभी हैश टेबल कार्यान्वयन में कुछ टकराव संकल्प रणनीति होती है। कुछ सामान्य रणनीतियों का वर्णन नीचे किया गया है। इन सभी तरीकों के लिए आवश्यक है कि कुंजी (या उनके लिए संकेत) तालिका में संग्रहीत की जाए, साथ में संबंधित मूल्यों के साथ।

गति विश्लेषण

सरलतम मॉडल में, हैश फ़ंक्शन पूरी तरह से अनिर्दिष्ट है और तालिका आकार नहीं देती है। एक आदर्श हैश फ़ंक्शन के साथ, आकार की एक तालिका $k$ जिसमें खुले पते का कोई टकराव नहीं होता है और सफल देखने के लिए एक एकल तुलना के साथ $k$ तत्वों को रखता है, जबकि आकार की एक तालिका $k$ श्रृंखलन के साथ और $n$ कुंजियों में न्यूनतम $max(0,n-k)$ टकराव और $\Theta (1+{\frac {n}{k}})$ देखने के लिए तुलना। सबसे खराब संभव हैश फ़ंक्शन के साथ, हर प्रविष्टि एक टकराव का कारण बनती है, और हैश तालिकाओं को रेखीय खोज में पतित कर देती है, $\Theta (n)$ के साथ प्रति सम्मिलन और $n$ तुलना करने के लिए तुलना की जाती है एक सफल खोज के लिए।

स्मृति उपयोग

कभी-कभी किसी टेबल के लिए मेमोरी की आवश्यकता कम से कम होनी चाहिए। चाइनिंग के तरीकों में मेमोरी के उपयोग को कम करने का एक तरीका यह है कि कुछ चेनिंग पॉइंटर्स को खत्म कर दिया जाए या उन्हें किसी प्रकार के संक्षिप्त पॉइंटर्स के साथ बदल दिया जाए।

एक और तकनीक डोनाल्ड नुथ ^{[उद्धरण चाहिए]} द्वारा शुरू की गई थी और इसे भागफल कहा जाता है। इस चर्चा के लिए मान लें कि कुंजी, या उस कुंजी का उल्टा-सीधा संस्करण है, {0, 1, 2, ..., M-1} से पूर्णांक m और बाल्टी की संख्या है N । m को N से विभाजित किया जाता है ताकि भागफल q और शेष r का निर्माण किया जा सके। शेष आर का उपयोग बाल्टी का चयन करने के लिए किया जाता है; बाल्टी में केवल भागफल q को संग्रहीत करने की आवश्यकता है। यह प्रति तत्व log₂(N) बिट्स बचाता है, जो कुछ अनुप्रयोगों में बहुत महत्वपूर्ण हो सकता है।

लाभ

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

कमियां

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

सहयोगी सरणियाँ

हैश टेबल का उपयोग आमतौर पर कई प्रकार के इन-मेमोरी टेबल को लागू करने के लिए किया जाता है। वे साहचर्य सरणी को लागू करने के लिए उपयोग किए जाते हैं (ऐसे सरणियाँ जिनके सूचकांक मनमानी हैं स्ट्रिंग्स या अन्य जटिल वस्तुएं), विशेष रूप से व्याख्या प्रोग्रामिंग भाषा जैसे रूबी, पायथन, और PHP।

जब एक नई वस्तु को मल्टीमैप में संग्रहीत किया जाता है और एक हैश टक्कर होती है, तो मल्टीमैप बिना शर्त के इन वस्तुओं को संग्रहीत करता है।

जब एक नई वस्तु को एक विशिष्ट साहचर्य सरणी में रखा जाता है और एक हैश टकराव होता है, लेकिन वास्तविक कुंजियाँ स्वयं अलग होती हैं, तो सहयोगी सरणी दोनों वस्तुओं को संग्रहीत करती है। हालाँकि, यदि नए आइटम की कुंजी वास्तव में एक पुरानी वस्तु की कुंजी से मेल खाती है, तो सहयोगी सरणी आमतौर पर पुरानी वस्तु को मिटा देती है और इसे नए आइटम से अधिलेखित कर देती है, इसलिए तालिका में प्रत्येक आइटम की एक अद्वितीय कुंजी होती है।

डाटाबेस इंडेक्सिंग

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

[1]
https://en.wikipedia.org/wiki/Hash_table
[2]
Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Archived अगस्त 7, 2009 at the वेबैक मशीन Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005
[3]
Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd संस्करण). Addison-Wesley. पपृ॰ 513–558. आई॰ऍस॰बी॰ऍन॰ 978-0-201-89685-5.
[4]
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd संस्करण). Massachusetts Institute of Technology. पपृ॰ 253–280. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.
[5]
"JDK HashMap Hashcode implementation". मूल से मई 21, 2017 को पुरालेखित. अभिगमन तिथि अगस्त 25, 2020.

[Hash_Table-1] [1]
https://en.wikipedia.org/wiki/Hash_table

[leiser-2] [2]
Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Archived अगस्त 7, 2009 at the वेबैक मशीन Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005

[knuth-3] [3]
Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd संस्करण). Addison-Wesley. पपृ॰ 513–558. आई॰ऍस॰बी॰ऍन॰ 978-0-201-89685-5.

[Cormen_et_al-4] [4]
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd संस्करण). Massachusetts Institute of Technology. पपृ॰ 253–280. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.

[5] [5]
"JDK HashMap Hashcode implementation". मूल से मई 21, 2017 को पुरालेखित. अभिगमन तिथि अगस्त 25, 2020.

[1]

[2]

[3]

[4]

[5]