हैश टेबल
कंप्यूटिंग में, एक हैश टेबल (हैश मैप) एक आंकड़ा संरचना है जो एक साहचर्य सरणी सार डेटा प्रकार( ) को लागू करता है, एक संरचना जो मुख्य/कुंजी() के लिए मूल्य/मान() मैप कर सकती है। एक हैश टेबल एक इंडेक्स की गणना करने के लिए एक का उपयोग करता है, जिसे हैश कोड भी कहा जाता है, "बाल्टी या स्लॉट" की एक सरणी में, जहां से वांछित मूल्य मिल सकता है। देखने के दौरान, कुंजी को हैश करते हैं और परिणामी हैश जहां इंगित करता है संबंधित मान संग्रहीत किया जाता है।
आदर्श रूप से, हैश फ़ंक्शन प्रत्येक कुंजी को एक अद्वितीय बकेट को असाइन करेगा, लेकिन अधिकांश हैश टेबल डिज़ाइन एक अपूर्ण हैश फ़ंक्शन को नियोजित करते हैं, जो हैश का कारण बन सकता है जहां हैश फ़ंक्शन एक से अधिक कुंजी के लिए एक ही इंडेक्स बनाता है। इस तरह के टकराव हमेशा किसी तरह से समायोजित किए जाते हैं। एक अच्छी तरह से आयाम वाली हैश तालिका में, प्रत्येक लुकअप के लिए औसत लागत (निर्देशों की संख्या) तालिका में संग्रहीत तत्वों की संख्या से स्वतंत्र है। कई हैश टेबल डिजाइन भी मनमाने ढंग से आवेषण और कुंजी-मूल्य जोड़े के विलोपन की अनुमति देते हैं, ((परिशोधित)) प्रति ऑपरेशन लगातार औसत लागत।  कई स्थितियों में, हैश टेबल औसत रूप से खोज पेड़ों या किसी अन्य टेबल लुकिंग संरचना की तुलना में अधिक कुशल हैं। इस कारण से, वे कई प्रकार के कंप्यूटर सॉफ़्टवेयर में व्यापक रूप से उपयोग किए जाते हैं, विशेष रूप से साहचर्य सरणियों, डेटाबेस अनुक्रमण, कैश और सेट के लिए।
हैशिंग का विचार है कि विभिन्न प्रकार की "बाल्टियों" में प्रविष्टियाँ (कुंजी / मूल्य जोड़े) वितरित करना। एक कुंजी को देखते हुए, एल्गोरिथ्म एक सूचकांक की गणना करता है जो बताता है कि प्रविष्टि कहां पाई जा सकती है:
अक्सर यह दो चरणों में किया जाता है:
इस पद्धति में, हैश सरणी आकार से स्वतंत्र होता है, और फिर इसे मॉडुलो ऑपरेटर ( codice_1) का उपयोग करके एक इंडेक्स ( codice_2 और codice_3 के बीच की संख्या) तक घटा दिया जाता है।
इस मामले में कि सरणी का आकार दो की शक्ति है, शेष ऑपरेशन को मास्किंग में कम किया जाता है, जो गति में सुधार करता है, लेकिन खराब हैश फ़ंक्शन के साथ समस्याएं बढ़ा सकता है।
हैश टकराव व्यावहारिक रूप से अपरिहार्य होते हैं जब संभव कुंजियों के एक बड़े सेट का एक यादृच्छिक सबसेट हैशिंग। उदाहरण के लिए, यदि 2,450 चाबियों को एक लाख बाल्टियों में रखा गया है, यहां तक कि पूरी तरह से समान यादृच्छिक वितरण के साथ, जन्मदिन की समस्या के अनुसार एक ही स्लॉट में कम से कम दो चाबियों के 95% होने की संभावना है।
इसलिए, इस तरह की घटनाओं को संभालने के लिए लगभग सभी हैश टेबल कार्यान्वयन में कुछ टकराव संकल्प रणनीति होती है। कुछ सामान्य रणनीतियों का वर्णन नीचे किया गया है। इन सभी तरीकों के लिए आवश्यक है कि कुंजी (या उनके लिए संकेत) तालिका में संग्रहीत की जाए, साथ में संबंधित मूल्यों के साथ।
सरलतम मॉडल में, हैश फ़ंक्शन पूरी तरह से अनिर्दिष्ट है और तालिका आकार नहीं देती है। एक आदर्श हैश फ़ंक्शन के साथ, आकार की एक तालिका formula_1 जिसमें खुले पते का कोई टकराव नहीं होता है और सफल देखने के लिए एक एकल तुलना के साथ formula_1 तत्वों को रखता है, जबकि आकार की एक तालिका formula_1 श्रृंखलन के साथ और formula_4 कुंजियों में न्यूनतम टकराव और देखने के लिए तुलना। सबसे खराब संभव हैश फ़ंक्शन के साथ, हर प्रविष्टि एक टकराव का कारण बनती है, और हैश तालिकाओं को रेखीय खोज में पतित कर देती है, formula_5 के साथ प्रति सम्मिलन और formula_4 तुलना करने के लिए तुलना की जाती है एक सफल खोज के लिए।
कभी-कभी किसी टेबल के लिए मेमोरी की आवश्यकता कम से कम होनी चाहिए। चाइनिंग के तरीकों में मेमोरी के उपयोग को कम करने का एक तरीका यह है कि कुछ चेनिंग पॉइंटर्स को खत्म कर दिया जाए या उन्हें किसी प्रकार के संक्षिप्त पॉइंटर्स के साथ बदल दिया जाए।
एक और तकनीक डोनाल्ड नुथ द्वारा शुरू की गई थी और इसे " भागफल " कहा जाता है। इस चर्चा के लिए मान लें कि कुंजी, या उस कुंजी का उल्टा-सीधा संस्करण है, {0, 1, 2, ..., M-1} से पूर्णांक " m " और बाल्टी की संख्या है " N "। " m " को " N " से विभाजित किया जाता है ताकि भागफल " q " और शेष " r " का निर्माण किया जा सके। शेष " आर " का उपयोग बाल्टी का चयन करने के लिए किया जाता है; बाल्टी में केवल भागफल " q " को संग्रहीत करने की आवश्यकता है। यह प्रति तत्व "log"(N) बिट्स बचाता है, जो कुछ अनुप्रयोगों में बहुत महत्वपूर्ण हो सकता है। हैश टेबल का उपयोग आमतौर पर कई प्रकार के इन-मेमोरी टेबल को लागू करने के लिए किया जाता है। वे साहचर्य सरणी को लागू करने के लिए उपयोग किए जाते हैं (ऐसे सरणियाँ जिनके सूचकांक मनमानी हैं स्ट्रिंग्स या अन्य जटिल वस्तुएं), विशेष रूप से व्याख्या प्रोग्रामिंग भाषा जैसे रूबी, पायथन, और PHP।
जब एक नई वस्तु को मल्टीमैप में संग्रहीत किया जाता है और एक हैश टक्कर होती है, तो मल्टीमैप बिना शर्त के इन वस्तुओं को संग्रहीत करता है।
जब एक नई वस्तु को एक विशिष्ट साहचर्य सरणी में रखा जाता है और एक हैश टकराव होता है, लेकिन वास्तविक कुंजियाँ स्वयं अलग होती हैं, तो सहयोगी सरणी दोनों वस्तुओं को संग्रहीत करती है। हालाँकि, यदि नए आइटम की कुंजी वास्तव में एक पुरानी वस्तु की कुंजी से मेल खाती है, तो सहयोगी सरणी आमतौर पर पुरानी वस्तु को मिटा देती है और इसे नए आइटम से अधिलेखित कर देती है, इसलिए तालिका में प्रत्येक आइटम की एक अद्वितीय कुंजी होती है।
हैश तालिकाओं का उपयोग डिस्क - आधारित डेटा संरचनाओं और डेटाबेस संकेत के रूप में भी किया जा सकता है (जैसे dbm) में हालांकि बी पेड़ इन अनुप्रयोगों में अधिक लोकप्रिय हैं। मल्टी-नोड डेटाबेस सिस्टम में, हैश टेबल का उपयोग आमतौर पर नोड्स के बीच पंक्तियों को वितरित करने के लिए किया जाता है, हैश जॉइन के लिए नेटवर्क ट्रैफ़िक को कम करता है।