👩🏼‍🤝‍👨🏾 📚 👾 हाश-आधारित संग्रह के बारे में आपको क्या जानना चाहिए ⛱️ 🛢️ 🎧

सभी को नमस्कार। व्लादिस्लाव रोडिन के संपर्क में। मैं वर्तमान में ओटीयूएस में हाई लोड आर्किटेक्ट कोर्स का प्रमुख हूं, और मैं सॉफ्टवेयर आर्किटेक्चर पर पाठ्यक्रम भी पढ़ाता हूं।

शिक्षण के अलावा, जैसा कि आपने देखा होगा, मैं Habr पर OTUS ब्लॉग के लिए कॉपीराइट सामग्री भी लिख रहा हूं और मैं आज का लेख "डेवलपर्स के लिए एल्गोरिदम" की एक नई धारा शुरू करने के लिए समर्पित करना चाहता हूं ।

परिचय

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

समस्या का निरूपण

आइए एक डेटा संरचना बनाने के लिए एक लक्ष्य निर्धारित करें जो आपको निम्नलिखित की अनुमति देता है:

इसमें (तत्व तत्व) यह जाँचता है कि O (1) के लिए कोई तत्व इसमें है या नहीं
जोड़ें (तत्व तत्व) O (1) में एक तत्व जोड़ें
हटाएँ (तत्व तत्व) O (1) में एक तत्व को हटाएं

सरणी

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

उपलब्धता की जांच

सरणी के माध्यम से एक रेखीय खोज करना आवश्यक है, क्योंकि तत्व संभवतः किसी भी सेल में हो सकता है। Asymptotically, यह O (n) में किया जा सकता है, जहाँ n सरणी का आकार है।

जोड़ा जा रहा है

यदि हमें कहीं भी एक तत्व जोड़ने की आवश्यकता है, तो पहले हमें एक खाली सेल खोजने की आवश्यकता है, और फिर उस पर तत्व लिखें। इस प्रकार, हम फिर से एक रैखिक खोज करते हैं और O (n) के स्पर्शोन्मुख व्यवहार को प्राप्त करते हैं।

हटाएं

किसी तत्व को हटाने के लिए, आपको पहले इसे ढूंढना होगा, और फिर पाए गए सेल में नल लिखना होगा। फिर से रैखिक खोज हमें O (n) तक ले जाती है।

सबसे सरल हैश सेट

कृपया ध्यान दें कि प्रत्येक ऑपरेशन के साथ, हमने पहले वांछित सेल के सूचकांक के लिए खोज की, और फिर ऑपरेशन का प्रदर्शन किया, और यह वह खोज है जो हमारे लिए asymptotics को खराब करती है! यदि हमने O (1) के लिए यह इंडेक्स प्राप्त करना सीख लिया, तो मूल समस्या हल हो जाएगी।

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

हैश सेट के सरल कार्यान्वयन की समस्याएं

कोई फर्क नहीं पड़ता कि हैश फ़ंक्शन कैसे लिखा जाता है, सरणी में कोशिकाओं की संख्या हमेशा सीमित होती है, जबकि उन तत्वों का सेट जो हम डेटा संरचना में संग्रहीत करना चाहते हैं, असीमित है। आखिरकार, हम डेटा संरचना से परेशान नहीं होंगे यदि केवल दस पहले से ज्ञात तत्वों को बचाने की आवश्यकता थी, है ना? मामलों की यह स्थिति अपरिहार्य संघर्षों की ओर ले जाती है । टकराव एक स्थिति है जब विभिन्न वस्तुओं को जोड़ते समय, हम सरणी में एक ही सेल में आते हैं।

टकराव को हल करने के लिए दो तरीकों का आविष्कार किया गया था: चेनिंग विधि और ओपन एड्रेसिंग विधि ।

चैनिंग विधि

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

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

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

ओपन एड्रेसिंग विधि

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

हैश सेट से हैश टेबल पर (हैशपॉप)

आइए एक डेटा संरचना बनाएं जो आपको आइटम को जोड़ने, हटाने, खोजने की अनुमति देता है, लेकिन एक निश्चित कुंजी द्वारा, जल्दी से एक हैश सेट (जैसे कि ओ (1) के लिए)।

हम हैश सेट के समान डेटा संरचना का उपयोग करेंगे, लेकिन हम तत्वों को संग्रहीत नहीं करेंगे, लेकिन तत्वों के जोड़े।

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

कुंजी द्वारा प्राप्त वस्तु कैसे है? हां, एक समान सिद्धांत के अनुसार: हमें कुंजी द्वारा एक बाल्टी मिलती है, जोड़े के माध्यम से जाते हैं और एक जोड़ी में मूल्य वापस करते हैं, कुंजी जिसमें अनुरोध में कुंजी के बराबर है, अगर ऐसी जोड़ी है, और अन्यथा शून्य है।

इस डेटा संरचना को हैश टेबल कहा जाता है ।

विशिष्ट साक्षात्कार प्रश्न

प्रश्न: हशसेट और हाशप को कैसे व्यवस्थित किया जाता है? इन संग्रहों में मुख्य संचालन कैसे किए जाते हैं? कैसे समान हैं () और हैशकोड () विधियों को लागू किया जाता है?
A : इन सवालों के जवाब ऊपर पाए जा सकते हैं।

प्रश्न: समान () और हैशकोड () के लिए अनुबंध क्या है? इसकी वजह क्या है?
A : यदि ऑब्जेक्ट समान हैं, तो उनके पास हैशकोड समान होना चाहिए। इस प्रकार, हैशकोड को बराबरी में शामिल क्षेत्रों की क्षमता से निर्धारित किया जाना चाहिए। इस अनुबंध के उल्लंघन से बहुत दिलचस्प प्रभाव हो सकते हैं। यदि ऑब्जेक्ट समान हैं, लेकिन उनका हैशकोड अलग है, तो हो सकता है कि आपको उस कुंजी के अनुरूप मान न मिले जिसके द्वारा आपने ऑब्जेक्ट को HashSet या HashMap में जोड़ा था।

निष्कर्ष

साक्षात्कार में, वे इन डेटा संरचनाओं से संबंधित विभिन्न मामलों को पूछना पसंद करते हैं। इसके अलावा, उनमें से किसी के निर्णय को उनके कार्यों के सिद्धांतों को समझने के लिए बिना किसी "संकटग्रस्त" के कटौती की जा सकती है।

बस इतना ही। यदि आपने सामग्री को अंत तक पढ़ा है, तो मैं अपने सहकर्मी एवगेनी वोलोसाटोव को आमंत्रित करता हूं कि आप "डायनामिक प्रोग्रामिंग के रहस्य" विषय पर एक मुफ्त पाठ के लिए डायनामिक प्रोग्रामिंग के विचारों का उपयोग करके ओलंपियाड समस्या को कैसे हल करें।

हाश-आधारित संग्रह के बारे में आपको क्या जानना चाहिए