चेनड हैश टेबल्स बनाम ओपन-एड्रेस किए गए हैश टेबल्स

Question

क्या कोई दो कार्यान्वयन (फायदे/नुकसान) के बीच मुख्य मतभेदों को समझा सकता है?

लाइब्रेरी के लिए, किस कार्यान्वयन की अनुशंसा की जाती है?

Answer 1

Wikipedia's article on hash tables विभिन्न हैश टेबल योजनाओं का एक स्पष्ट रूप से बेहतर स्पष्टीकरण और अवलोकन देता है जो लोगों ने मेरे सिर के शीर्ष से बाहर निकलने में सक्षम है। असल में आप यहां सवाल पूछने से पहले उस लेख को पढ़ने से बेहतर हैं। :)

कहा ...

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

जुड़ी हुई हैशिंग के डाउनसाइड को लिंक्ड सूचियों को खोजने के लिए पॉइंटर्स का पालन करना पड़ रहा है। उल्टा यह है कि जंजीर हैश टेबल केवल लोड कारक (हैश टेबल में बाल्टी सरणी की लंबाई तक तत्वों का अनुपात) बढ़ता है, यहां तक ​​कि यदि यह ऊपर उगता है तो भी बढ़ता जा सकता है।

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

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

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

उपरोक्त सभी पर बहुत सारे बदलाव हैं। फिर, कृपया विकिपीडिया लेख देखें, यह वास्तव में काफी अच्छा है।

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

यदि आप जीटीके के साथ काम कर रहे हैं, उदाहरण के लिए, तो आप पाएंगे कि hash table in GLib अच्छा है।

Answer 2

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

भार कारक (वस्तुओं/तालिका आकार की संख्या) को बढ़ाने से खुली संबोधित हैश तालिकाओं में प्रमुख प्रदर्शन दंड का कारण बनता है, लेकिन प्रदर्शन केवल जंजीर हैश तालिकाओं में रैखिक रूप से घटता है।

यदि आप कम स्मृति से निपट रहे हैं और मेमोरी उपयोग को कम करना चाहते हैं, तो खुले पते के लिए जाएं। यदि आप स्मृति के बारे में चिंतित नहीं हैं और गति चाहते हैं, तो जंजीर हैश टेबल के लिए जाएं।

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

ओपन को संबोधित करते:

Answer 3

के बाद से उत्कृष्ट विवरण दिया जाता है, मैं तो बस आगे उदाहरण के लिए CLRS से लिया विज़ुअलाइज़ेशन शामिल था

श्रृंखलन:

Answer 4

मेरे समझ (सरल शब्दों में) यह है कि दोनों तरीकों में पेशेवर और विपक्ष हैं, हालांकि अधिकांश पुस्तकालय चेनिंग रणनीति का उपयोग करते हैं।

श्रृंखलन विधि:

यहाँ हैश तालिकाओं सरणी वस्तुओं का एक लिंक किए गए सूची में नक्शे। टक्कर की संख्या काफी छोटी है तो यह प्रभावी है। सबसे खराब स्थिति परिदृश्य O(n) है जहां एन तालिका में तत्वों की संख्या है।

ओपन रैखिक जांच के साथ संबोधित:

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

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