साहचर्य सरणी: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 3: Line 3:
{{Redirect|सहयोगी कंटेनर|सी ++ प्रोग्रामिंग भाषा के मानक पुस्तकालय में आदेशित साहचर्य सरणियों का कार्यान्वयन|सहयोगी कंटेनर}}
{{Redirect|सहयोगी कंटेनर|सी ++ प्रोग्रामिंग भाषा के मानक पुस्तकालय में आदेशित साहचर्य सरणियों का कार्यान्वयन|सहयोगी कंटेनर}}
{{Redirect|मानचित्र (कंप्यूटर विज्ञान)|उच्च-क्रम समारोह| मानचित्र (उच्च क्रम समारोह)|अन्य प्रयोग|मानचित्र (बहुविकल्पी)}}
{{Redirect|मानचित्र (कंप्यूटर विज्ञान)|उच्च-क्रम समारोह| मानचित्र (उच्च क्रम समारोह)|अन्य प्रयोग|मानचित्र (बहुविकल्पी)}}
[[कंप्यूटर विज्ञान]] में '''साहचर्य सरणी''', मानचित्र, प्रतीक तालिका या शब्दकोश [[सार डेटा प्रकार]] है। जो विशेषता-मूल्य जोड़ी का [[संग्रह (सार डेटा प्रकार)]] संग्रहीत करता है | एक बार संग्रह में कुंजी, मान जोड़े जैसे कि प्रत्येक संभावित कुंजी अधिकतम दिखाई देती है। गणितीय शब्दों में '''साहचर्य सरणी''' एक फलन  (गणित) है। जिसमें एक फलन का 'सीमित' डोमेन होता है।<ref>{{cite journal |last1=Collins |first1=Graham |last2=Syme |first2=Donald |title=A theory of finite maps |journal=Higher Order Logic Theorem Proving and Its Applications |series=Lecture Notes in Computer Science |date=1995 |volume=971 |pages=122–137 |doi=10.1007/3-540-60275-5_61|isbn=978-3-540-60275-0 }}</ref> यह 'लुकअप', 'रिमूव' और 'इन्सर्ट' ऑपरेशंस को सहयोग प्रदान करता है।
[[कंप्यूटर विज्ञान]] में '''साहचर्य सरणी''', मानचित्र, प्रतीक सारणी या शब्दकोश [[सार डेटा प्रकार]] है। जो विशेषता-मूल्य जोड़ी का [[संग्रह (सार डेटा प्रकार)]] संग्रहीत करता है | एक बार संग्रह में कुंजी, मान जोड़े जैसे कि प्रत्येक संभावित कुंजी अधिकतम दिखाई देती है। गणितीय शब्दों में '''साहचर्य सरणी''' एक फलन  (गणित) है। जिसमें एक फलन का 'सीमित' डोमेन होता है।<ref>{{cite journal |last1=Collins |first1=Graham |last2=Syme |first2=Donald |title=A theory of finite maps |journal=Higher Order Logic Theorem Proving and Its Applications |series=Lecture Notes in Computer Science |date=1995 |volume=971 |pages=122–137 |doi=10.1007/3-540-60275-5_61|isbn=978-3-540-60275-0 }}</ref> यह 'लुकअप', 'रिमूव' और 'इन्सर्ट' ऑपरेशंस को सहयोग प्रदान करता है।


शब्दकोश समस्या कुशल [[डेटा संरचना]]ओं को डिजाइन करने की क्लासिक समस्या है जो साहचर्य सरणियों को लागू करती है।<ref>{{cite journal|title=Optimal Bounds on the Dictionary Problem|last=Andersson|first=Arne|journal= Proc. Symposium on Optimal Algorithms|series=Lecture Notes in Computer Science|date=1989|volume=401|pages=106–114|publisher=Springer Verlag|doi=10.1007/3-540-51859-2_10|isbn=978-3-540-51859-4}}</ref>
शब्दकोश समस्या कुशल [[डेटा संरचना]]ओं को प्रारूपित करने की उत्कृष्ट समस्या है। जो साहचर्य सरणियों को प्रयुक्त करती है।<ref>{{cite journal|title=Optimal Bounds on the Dictionary Problem|last=Andersson|first=Arne|journal= Proc. Symposium on Optimal Algorithms|series=Lecture Notes in Computer Science|date=1989|volume=401|pages=106–114|publisher=Springer Verlag|doi=10.1007/3-540-51859-2_10|isbn=978-3-540-51859-4}}</ref> शब्दकोश समस्या के दो प्रमुख समाधान [[हैश तालिका|हैश सारणी]] और [[खोज पेड़]] हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | author2-link = Charles E. Leiserson|last2=Leiserson|first2=Charles E.|author3-link=Ron Rivest|last3=Rivest|first3=Ronald L.|author4-link=Clifford Stein|last4=Stein|first4=Clifford | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
शब्दकोश समस्या के दो प्रमुख समाधान [[हैश तालिका]] और [[खोज पेड़]] हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | author2-link = Charles E. Leiserson|last2=Leiserson|first2=Charles E.|author3-link=Ron Rivest|last3=Rivest|first3=Ronald L.|author4-link=Clifford Stein|last4=Stein|first4=Clifford | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
[http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf "Dynamic Perfect Hashing: Upper and Lower Bounds"] {{Webarchive|url=https://web.archive.org/web/20160304094014/http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf |date=2016-03-04 }}.
[http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf "Dynamic Perfect Hashing: Upper and Lower Bounds"] {{Webarchive|url=https://web.archive.org/web/20160304094014/http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf |date=2016-03-04 }}.
SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
http://portal.acm.org/citation.cfm?id=182370
http://portal.acm.org/citation.cfm?id=182370
{{doi|10.1137/S0097539791194094}}</ref>
{{doi|10.1137/S0097539791194094}}</ref> कुछ स्थितियों में सीधे संबोधित किए गए [[सरणी डेटा संरचना]], [[बाइनरी सर्च ट्री]] या अन्य अधिक विशिष्ट संरचनाओं का उपयोग करके समस्या को हल करना भी संभव है।
कुछ मामलों में सीधे संबोधित किए गए [[सरणी डेटा संरचना]], [[बाइनरी सर्च ट्री]], या अन्य अधिक विशिष्ट संरचनाओं का उपयोग करके समस्या को हल करना भी संभव है।


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


साहचर्य सरणियों में [[memoization]] जैसे मूलभूत [[सॉफ्टवेयर डिजाइन पैटर्न]] सहित कई अनुप्रयोग हैं<!--NOT a misspelling--> और [[डेकोरेटर पैटर्न]]।<ref name="decorator">{{harvtxt|Goodrich|Tamassia|2006}}, pp. 597–599.</ref>
साहचर्य सरणियों में [[memoization|ज्ञापन]] जैसे मूलभूत [[सॉफ्टवेयर डिजाइन पैटर्न|सॉफ्टवेयर प्रारूप पैटर्न]] सहित कई अनुप्रयोग हैं और [[डेकोरेटर पैटर्न]]<ref name="decorator">{{harvtxt|Goodrich|Tamassia|2006}}, pp. 597–599.</ref> नाम गणित में ज्ञात साहचर्य गुण से नहीं आता है। किन्तु यह इस तथ्य से उत्पन्न होता है कि मान कुंजियों से जुड़े होते हैं। इसे फ्लिन के टैक्सोनॉमी [[संबंधी संपत्ति]] के साथ भ्रमित नहीं होना चाहिए।
नाम गणित में ज्ञात साहचर्य गुण से नहीं आता है। बल्कि, यह इस तथ्य से उत्पन्न होता है कि मान कुंजियों से जुड़े होते हैं। इसे फ्लिन के टैक्सोनॉमी#[[संबंधी संपत्ति]] के साथ भ्रमित नहीं होना चाहिए।


== संचालन ==
== संचालन ==
Line 27: Line 24:
* लुकअप, फाइंड, या गेट: वह मान (यदि कोई हो) खोजें जो किसी दिए गए कुंजी से जुड़ा हो। इस ऑपरेशन का तर्क कुंजी है, और ऑपरेशन से मान वापस किया जाता है। यदि कोई मान नहीं मिलता है, तो कुछ लुकअप फलन  अपवाद हैंडलिंग बढ़ाते हैं, जबकि अन्य डिफ़ॉल्ट मान (शून्य, शून्य, विशिष्ट मान निर्माता को दिए गए ...) लौटाते हैं।
* लुकअप, फाइंड, या गेट: वह मान (यदि कोई हो) खोजें जो किसी दिए गए कुंजी से जुड़ा हो। इस ऑपरेशन का तर्क कुंजी है, और ऑपरेशन से मान वापस किया जाता है। यदि कोई मान नहीं मिलता है, तो कुछ लुकअप फलन  अपवाद हैंडलिंग बढ़ाते हैं, जबकि अन्य डिफ़ॉल्ट मान (शून्य, शून्य, विशिष्ट मान निर्माता को दिए गए ...) लौटाते हैं।


इसके अलावा, साहचर्य सरणियों में अन्य ऑपरेशन भी शामिल हो सकते हैं जैसे मैपिंग की संख्या निर्धारित करना या सभी मैपिंग पर लूप करने के लिए एक [[इटरेटर]] का निर्माण करना। आमतौर पर, इस तरह के ऑपरेशन के लिए, जिस क्रम में मैपिंग लौटाई जाती है, वह कार्यान्वयन-परिभाषित हो सकता है।
इसके अलावा, साहचर्य सरणियों में अन्य ऑपरेशन भी सम्मिलित हो सकते हैं जैसे मैपिंग की संख्या निर्धारित करना या सभी मैपिंग पर लूप करने के लिए एक [[इटरेटर]] का निर्माण करना। आमतौर पर, इस तरह के ऑपरेशन के लिए, जिस क्रम में मैपिंग लौटाई जाती है, वह कार्यान्वयन-परिभाषित हो सकता है।


एक [[मल्टीमैप]] एक एकल कुंजी के साथ कई मानों को संबद्ध करने की अनुमति देकर एक साहचर्य सरणी का सामान्यीकरण करता है।<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> एक [[द्विदिश नक्शा]] एक संबंधित अमूर्त डेटा प्रकार है जिसमें मैपिंग दोनों दिशाओं में संचालित होती है: प्रत्येक मान को एक अद्वितीय कुंजी के साथ जोड़ा जाना चाहिए, और दूसरा लुकअप ऑपरेशन एक मान को एक तर्क के रूप में लेता है और उस मान से जुड़ी कुंजी को देखता है।
एक [[मल्टीमैप]] एक एकल कुंजी के साथ कई मानों को संबद्ध करने की अनुमति देकर एक साहचर्य सरणी का सामान्यीकरण करता है।<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> एक [[द्विदिश नक्शा]] एक संबंधित अमूर्त डेटा प्रकार है जिसमें मैपिंग दोनों दिशाओं में संचालित होती है: प्रत्येक मान को एक अद्वितीय कुंजी के साथ जोड़ा जाना चाहिए, और दूसरा लुकअप ऑपरेशन एक मान को एक तर्क के रूप में लेता है और उस मान से जुड़ी कुंजी को देखता है।
Line 59: Line 56:
== कार्यान्वयन ==
== कार्यान्वयन ==


मैपिंग की बहुत कम संख्या वाले शब्दकोशों के लिए, [[संघ सूची]], मैपिंग की एक [[लिंक्ड सूची]] का उपयोग करके शब्दकोश को लागू करना समझ में आ सकता है। इस कार्यान्वयन के साथ, बुनियादी शब्दकोश संचालन करने का समय मैपिंग की कुल संख्या में रैखिक है; हालाँकि, इसे लागू करना आसान है और इसके चलने के समय में स्थिर कारक छोटे हैं।<ref name="gt"/><ref>{{cite web |url=http://www.faqs.org/faqs/lisp-faq/part2/section-2.html
मैपिंग की बहुत कम संख्या वाले शब्दकोशों के लिए, [[संघ सूची]], मैपिंग की एक [[लिंक्ड सूची]] का उपयोग करके शब्दकोश को प्रयुक्त करना समझ में आ सकता है। इस कार्यान्वयन के साथ, बुनियादी शब्दकोश संचालन करने का समय मैपिंग की कुल संख्या में रैखिक है; हालाँकि, इसे प्रयुक्त करना आसान है और इसके चलने के समय में स्थिर कारक छोटे हैं।<ref name="gt"/><ref>{{cite web |url=http://www.faqs.org/faqs/lisp-faq/part2/section-2.html
|title=When should I use a hash table instead of an association list?
|title=When should I use a hash table instead of an association list?
|publisher=lisp-faq/part2
|publisher=lisp-faq/part2
Line 65: Line 62:
एक अन्य बहुत ही सरल कार्यान्वयन तकनीक, जब कुंजियों को एक संकीर्ण सीमा तक सीमित किया जाता है, तो एक सरणी में सीधे संबोधित किया जाता है: किसी दिए गए कुंजी k के मान को सरणी सेल A [k] में संग्रहीत किया जाता है, या यदि k के लिए कोई मैपिंग नहीं है तब सेल एक विशेष प्रहरी मान संग्रहीत करता है जो मैपिंग की अनुपस्थिति को इंगित करता है। सरल होने के साथ-साथ, यह तकनीक तेज़ है: प्रत्येक शब्दकोश संक्रिया में निरंतर समय लगता है। हालाँकि, इस संरचना के लिए स्थान की आवश्यकता पूरे कीस्पेस का आकार है, जब तक कि कीस्पेस छोटा न हो, यह अव्यावहारिक है।<ref name="clrs" />
एक अन्य बहुत ही सरल कार्यान्वयन तकनीक, जब कुंजियों को एक संकीर्ण सीमा तक सीमित किया जाता है, तो एक सरणी में सीधे संबोधित किया जाता है: किसी दिए गए कुंजी k के मान को सरणी सेल A [k] में संग्रहीत किया जाता है, या यदि k के लिए कोई मैपिंग नहीं है तब सेल एक विशेष प्रहरी मान संग्रहीत करता है जो मैपिंग की अनुपस्थिति को इंगित करता है। सरल होने के साथ-साथ, यह तकनीक तेज़ है: प्रत्येक शब्दकोश संक्रिया में निरंतर समय लगता है। हालाँकि, इस संरचना के लिए स्थान की आवश्यकता पूरे कीस्पेस का आकार है, जब तक कि कीस्पेस छोटा न हो, यह अव्यावहारिक है।<ref name="clrs" />


शब्दकोशों को लागू करने के दो प्रमुख तरीके हैश टेबल या सर्च ट्री हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs"/><ref name="dietzfelbinger"/>
शब्दकोशों को प्रयुक्त करने के दो प्रमुख तरीके हैश टेबल या सर्च ट्री हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs"/><ref name="dietzfelbinger"/>






=== हैश तालिका कार्यान्वयन ===
=== हैश सारणी कार्यान्वयन ===
{{main | Hash table}}
{{main | Hash table}}
[[File:Hash table average insertion time.png|thumb|right|362px|यह ग्राफ बड़े हैश टेबल (कैश के आकार से कहीं अधिक) में तत्वों को देखने के लिए आवश्यक [[सीपीयू कैश]] मिस की औसत संख्या की तुलना चेनिंग और [[रैखिक जांच]] के साथ करता है। संदर्भ की बेहतर स्थानीयता के कारण रेखीय जांच बेहतर प्रदर्शन करती है, हालाँकि जैसे-जैसे तालिका भर जाती है, इसका प्रदर्शन बहुत कम हो जाता है।]]एक साहचर्य सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन एक हैश तालिका के साथ होता है: एक [[हैश फंकशन]] के साथ संयुक्त एक सरणी डेटा संरचना जो प्रत्येक कुंजी को सरणी की एक अलग बाल्टी में अलग करती है। हैश तालिका के पीछे मूल विचार यह है कि किसी सरणी के किसी तत्व को उसके सूचकांक के माध्यम से एक्सेस करना एक सरल, निरंतर-समय का ऑपरेशन है। इसलिए, हैश टेबल के लिए एक ऑपरेशन का औसत ओवरहेड केवल कुंजी के हैश की गणना है, जो सरणी के भीतर संबंधित बकेट तक पहुंचने के साथ संयुक्त है। जैसे, हैश टेबल आमतौर पर ओ (1) समय में प्रदर्शन करते हैं, और अधिकांश स्थितियों में बेहतर प्रदर्शन करते हैं।
[[File:Hash table average insertion time.png|thumb|right|362px|यह ग्राफ बड़े हैश टेबल (कैश के आकार से कहीं अधिक) में तत्वों को देखने के लिए आवश्यक [[सीपीयू कैश]] मिस की औसत संख्या की तुलना चेनिंग और [[रैखिक जांच]] के साथ करता है। संदर्भ की बेहतर स्थानीयता के कारण रेखीय जांच बेहतर प्रदर्शन करती है, हालाँकि जैसे-जैसे सारणी भर जाती है, इसका प्रदर्शन बहुत कम हो जाता है।]]एक साहचर्य सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन एक हैश सारणी के साथ होता है: एक [[हैश फंकशन]] के साथ संयुक्त एक सरणी डेटा संरचना जो प्रत्येक कुंजी को सरणी की एक अलग बाल्टी में अलग करती है। हैश सारणी के पीछे मूल विचार यह है कि किसी सरणी के किसी तत्व को उसके सूचकांक के माध्यम से एक्सेस करना एक सरल, निरंतर-समय का ऑपरेशन है। इसलिए, हैश टेबल के लिए एक ऑपरेशन का औसत ओवरहेड केवल कुंजी के हैश की गणना है, जो सरणी के भीतर संबंधित बकेट तक पहुंचने के साथ संयुक्त है। जैसे, हैश टेबल आमतौर पर ओ (1) समय में प्रदर्शन करते हैं, और अधिकांश स्थितियों में बेहतर प्रदर्शन करते हैं।


हैश टेबल को हैश टकराव को संभालने में सक्षम होना चाहिए: जब हैश फलन  दो अलग-अलग कुंजियों को सरणी की एक ही बाल्टी में मैप करता है। इस समस्या के दो सबसे व्यापक दृष्टिकोण अलग-अलग चेनिंग और [[खुला संबोधन]] हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs"/><ref name="fklm">{{citation|contribution=Pathfinders for associative maps|title=Ext. Abstracts GIS-l 2006|last1=Klammer|first1=F.|author1-link=F. Klammer|last2=Mazzolini|first2=L.|author2-link=L. Mazzolini|publisher=GIS-I|year=2006|pages=71–74}}.</ref> अलग-अलग श्रंखला में, सरणी स्वयं मान को संग्रहीत नहीं करती है, लेकिन एक [[सूचक (कंप्यूटर प्रोग्रामिंग)]] को दूसरे कंटेनर में संग्रहीत करती है, आमतौर पर एक एसोसिएशन सूची, जो हैश से मेल खाने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर, खुले पते में, यदि कोई हैश टकराव पाया जाता है, तो तालिका एक नियतात्मक तरीके से मूल्य को संग्रहीत करने के लिए एक सरणी में एक खाली स्थान की तलाश करती है, आमतौर पर सरणी में अगली तत्काल स्थिति को देखते हुए।
हैश टेबल को हैश टकराव को संभालने में सक्षम होना चाहिए: जब हैश फलन  दो अलग-अलग कुंजियों को सरणी की एक ही बाल्टी में मैप करता है। इस समस्या के दो सबसे व्यापक दृष्टिकोण अलग-अलग चेनिंग और [[खुला संबोधन]] हैं।<ref name="gt"/><ref name="ms"/><ref name="clrs"/><ref name="fklm">{{citation|contribution=Pathfinders for associative maps|title=Ext. Abstracts GIS-l 2006|last1=Klammer|first1=F.|author1-link=F. Klammer|last2=Mazzolini|first2=L.|author2-link=L. Mazzolini|publisher=GIS-I|year=2006|pages=71–74}}.</ref> अलग-अलग श्रंखला में, सरणी स्वयं मान को संग्रहीत नहीं करती है, लेकिन एक [[सूचक (कंप्यूटर प्रोग्रामिंग)]] को दूसरे कंटेनर में संग्रहीत करती है, आमतौर पर एक एसोसिएशन सूची, जो हैश से मेल खाने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर, खुले पते में, यदि कोई हैश टकराव पाया जाता है, तो सारणी एक नियतात्मक तरीके से मूल्य को संग्रहीत करने के लिए एक सरणी में एक खाली स्थान की तलाश करती है, आमतौर पर सरणी में अगली तत्काल स्थिति को देखते हुए।


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


=== वृक्ष कार्यान्वयन ===
=== वृक्ष कार्यान्वयन ===
Line 82: Line 79:


==== सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री ====
==== सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री ====
एक अन्य सामान्य दृष्टिकोण एक [[स्व-संतुलन बाइनरी सर्च ट्री]] के साथ एक साहचर्य सरणी को लागू करना है, जैसे कि [[एवीएल का पेड़]] या रेड-ब्लैक ट्री।<ref>
एक अन्य सामान्य दृष्टिकोण एक [[स्व-संतुलन बाइनरी सर्च ट्री]] के साथ एक साहचर्य सरणी को प्रयुक्त करना है, जैसे कि [[एवीएल का पेड़]] या रेड-ब्लैक ट्री।<ref>
Joel Adams and Larry Nyhoff.
Joel Adams and Larry Nyhoff.
[http://cs.calvin.edu/books/c++/intro/3e/WebItems/Ch15-Web/STL-Trees.pdf "Trees in STL"].
[http://cs.calvin.edu/books/c++/intro/3e/WebItems/Ch15-Web/STL-Trees.pdf "Trees in STL"].
Line 89: Line 86:
"The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of ''self-balancing binary search tree'' called a ''red–black tree''."
"The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of ''self-balancing binary search tree'' called a ''red–black tree''."
</ref>
</ref>
हैश टेबल की तुलना में, इन संरचनाओं के फायदे और कमजोरियां दोनों हैं। सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का सबसे खराब प्रदर्शन हैश टेबल की तुलना में काफी बेहतर है, ओ (लॉग एन) के [[बिग ओ नोटेशन]] में समय की जटिलता के साथ। यह हैश टेबल के विपरीत है, जिसके सबसे खराब प्रदर्शन में सभी तत्व एक ही बकेट साझा करते हैं, जिसके परिणामस्वरूप O(n) समय जटिलता होती है। इसके अलावा, और सभी बाइनरी सर्च ट्री की तरह, सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री अपने तत्वों को क्रम में रखते हैं। इस प्रकार, इसके तत्वों को कम से कम-से-महानतम पैटर्न का पालन करना, जबकि एक हैश तालिका को घुमाने के परिणामस्वरूप तत्वों को यादृच्छिक क्रम में हो सकता है। क्योंकि वे इन-ऑर्डर हैं, वृक्ष-आधारित मानचित्र श्रेणी के प्रश्नों को भी संतुष्ट कर सकते हैं (दो सीमाओं के बीच सभी मान प्राप्त करें) जबकि एक हैशपैप केवल सटीक मान प्राप्त कर सकता है। हालांकि, हैश टेबल में O(1) के सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में बेहतर औसत-केस टाइम जटिलता है, और जब एक अच्छे हैश फलन  का उपयोग किया जाता है तो उनका सबसे खराब प्रदर्शन बहुत कम होता है।
हैश टेबल की तुलना में, इन संरचनाओं के फायदे और कमजोरियां दोनों हैं। सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का सबसे खराब प्रदर्शन हैश टेबल की तुलना में काफी बेहतर है, ओ (लॉग एन) के [[बिग ओ नोटेशन]] में समय की जटिलता के साथ। यह हैश टेबल के विपरीत है, जिसके सबसे खराब प्रदर्शन में सभी तत्व एक ही बकेट साझा करते हैं, जिसके परिणामस्वरूप O(n) समय जटिलता होती है। इसके अलावा, और सभी बाइनरी सर्च ट्री की तरह, सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री अपने तत्वों को क्रम में रखते हैं। इस प्रकार, इसके तत्वों को कम से कम-से-महानतम पैटर्न का पालन करना, जबकि एक हैश सारणी को घुमाने के परिणामस्वरूप तत्वों को यादृच्छिक क्रम में हो सकता है। क्योंकि वे इन-ऑर्डर हैं, वृक्ष-आधारित मानचित्र श्रेणी के प्रश्नों को भी संतुष्ट कर सकते हैं (दो सीमाओं के बीच सभी मान प्राप्त करें) जबकि एक हैशपैप केवल सटीक मान प्राप्त कर सकता है। हालांकि, हैश टेबल में O(1) के सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में बेहतर औसत-केस टाइम जटिलता है, और जब एक अच्छे हैश फलन  का उपयोग किया जाता है तो उनका सबसे खराब प्रदर्शन बहुत कम होता है।


यह ध्यान देने योग्य है कि एक हैश टेबल के लिए बकेट को लागू करने के लिए एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जा सकता है जो अलग-अलग चेनिंग का उपयोग करता है। यह औसत-केस निरंतर लुकअप की अनुमति देता है, लेकिन ओ (लॉग एन) के सबसे खराब-केस प्रदर्शन का आश्वासन देता है। हालांकि, यह कार्यान्वयन में अतिरिक्त जटिलता का परिचय देता है और छोटे हैश तालिकाओं के लिए और भी खराब प्रदर्शन का कारण बन सकता है, जहां पेड़ को सम्मिलित करने और संतुलित करने में लगने वाला समय लिंक की गई सूची के सभी तत्वों पर एक [[रैखिक खोज]] करने के लिए आवश्यक समय से अधिक है। या समान डेटा संरचना।<ref name="knuth">{{cite book| first=Donald |last=Knuth |author1-link=Donald Knuth| title = The Art of Computer Programming| volume = 3: ''Sorting and Searching''| edition = 2nd| publisher = Addison-Wesley| year = 1998| isbn = 0-201-89685-0| pages = 513–558}}</ref><ref>{{cite web |url=https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/ |title=Linear vs Binary Search |last=Probst |first=Mark |date=2010-04-30 |access-date=2016-11-20 }}</ref>
यह ध्यान देने योग्य है कि एक हैश टेबल के लिए बकेट को प्रयुक्त करने के लिए एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जा सकता है जो अलग-अलग चेनिंग का उपयोग करता है। यह औसत-केस निरंतर लुकअप की अनुमति देता है, लेकिन ओ (लॉग एन) के सबसे खराब-केस प्रदर्शन का आश्वासन देता है। हालांकि, यह कार्यान्वयन में अतिरिक्त जटिलता का परिचय देता है और छोटे हैश सारणियों के लिए और भी खराब प्रदर्शन का कारण बन सकता है, जहां पेड़ को सम्मिलित करने और संतुलित करने में लगने वाला समय लिंक की गई सूची के सभी तत्वों पर एक [[रैखिक खोज]] करने के लिए आवश्यक समय से अधिक है। या समान डेटा संरचना।<ref name="knuth">{{cite book| first=Donald |last=Knuth |author1-link=Donald Knuth| title = The Art of Computer Programming| volume = 3: ''Sorting and Searching''| edition = 2nd| publisher = Addison-Wesley| year = 1998| isbn = 0-201-89685-0| pages = 513–558}}</ref><ref>{{cite web |url=https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/ |title=Linear vs Binary Search |last=Probst |first=Mark |date=2010-04-30 |access-date=2016-11-20 }}</ref>




Line 148: Line 145:
== भाषा समर्थन ==
== भाषा समर्थन ==
{{Main|Comparison of programming languages (associative array)}}
{{Main|Comparison of programming languages (associative array)}}
साहचर्य सरणियों को किसी [[जाओ (प्रोग्रामिंग भाषा)]] में एक पैकेज के रूप में लागू किया जा सकता है और कई भाषा प्रणालियाँ उन्हें अपने मानक पुस्तकालय के हिस्से के रूप में प्रदान करती हैं। कुछ भाषाओं में, वे न केवल मानक प्रणाली में निर्मित होते हैं, बल्कि विशेष सिंटैक्स होते हैं, जो अक्सर सरणी-जैसी सबस्क्रिप्टिंग का उपयोग करते हैं।
साहचर्य सरणियों को किसी [[जाओ (प्रोग्रामिंग भाषा)]] में एक पैकेज के रूप में प्रयुक्त किया जा सकता है और कई भाषा प्रणालियाँ उन्हें अपने मानक पुस्तकालय के हिस्से के रूप में प्रदान करती हैं। कुछ भाषाओं में, वे न केवल मानक प्रणाली में निर्मित होते हैं, किन्तु विशेष सिंटैक्स होते हैं, जो अक्सर सरणी-जैसी सबस्क्रिप्टिंग का उपयोग करते हैं।


साहचर्य सरणियों के लिए अंतर्निहित सिंटैक्टिक समर्थन 1969 में [[SNOBOL]] द्वारा नाम तालिका के तहत पेश किया गया था। TMG (भाषा) ने स्ट्रिंग कुंजियों और पूर्णांक मानों के साथ तालिकाओं की पेशकश की। [[MUMPS]] ने बहु-आयामी साहचर्य सरणियाँ बनाईं, वैकल्पिक रूप से लगातार, इसकी प्रमुख डेटा संरचना। [[SETL]] ने उन्हें सेट और मैप्स के एक संभावित कार्यान्वयन के रूप में समर्थन दिया। [[AWK]] से शुरू होने वाली और [[Rexx]], [[Perl]], [[PHP]], [[Tcl]], [[JavaScript]], Maple (सॉफ्टवेयर), Python (प्रोग्रामिंग लैंग्वेज), Ruby (प्रोग्रामिंग लैंग्वेज), [[Wolfram Language]], Go (प्रोग्रामिंग लैंग्वेज), और Lua (प्रोग्रामिंग) सहित अधिकांश आधुनिक स्क्रिप्टिंग भाषाएँ भाषा), एक प्राथमिक कंटेनर प्रकार के रूप में साहचर्य सरणियों का समर्थन करता है। कई और भाषाओं में, वे विशेष सिंटैक्स के बिना पुस्तकालय कार्यों के रूप में उपलब्ध हैं।
साहचर्य सरणियों के लिए अंतर्निहित सिंटैक्टिक समर्थन 1969 में [[SNOBOL]] द्वारा नाम सारणी के तहत पेश किया गया था। TMG (भाषा) ने स्ट्रिंग कुंजियों और पूर्णांक मानों के साथ सारणियों की पेशकश की। [[MUMPS]] ने बहु-आयामी साहचर्य सरणियाँ बनाईं, वैकल्पिक रूप से लगातार, इसकी प्रमुख डेटा संरचना। [[SETL]] ने उन्हें सेट और मैप्स के एक संभावित कार्यान्वयन के रूप में समर्थन दिया। [[AWK]] से शुरू होने वाली और [[Rexx]], [[Perl]], [[PHP]], [[Tcl]], [[JavaScript]], Maple (सॉफ्टवेयर), Python (प्रोग्रामिंग लैंग्वेज), Ruby (प्रोग्रामिंग लैंग्वेज), [[Wolfram Language]], Go (प्रोग्रामिंग लैंग्वेज), और Lua (प्रोग्रामिंग) सहित अधिकांश आधुनिक स्क्रिप्टिंग भाषाएँ भाषा), एक प्राथमिक कंटेनर प्रकार के रूप में साहचर्य सरणियों का समर्थन करता है। कई और भाषाओं में, वे विशेष सिंटैक्स के बिना पुस्तकालय कार्यों के रूप में उपलब्ध हैं।


स्मॉलटॉक में, [[Objective-C]], .NET Framework|.NET,<ref>{{cite web |url=http://msdn.microsoft.com/en-us/library/xfhwa508.aspx |title=Dictionary<TKey, TValue> Class |publisher=MSDN}}</ref> पायथन (प्रोग्रामिंग लैंग्वेज), [[असली बुनियादी]], [[स्विफ्ट (प्रोग्रामिंग भाषा)]], एप्लिकेशन और डेल्फी के लिए विजुअल बेसिक (प्रोग्रामिंग लैंग्वेज)<ref>{{Cite web|url=http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TDictionary|title=System.Generics.Collections.TDictionary - RAD Studio API Documentation|website=docwiki.embarcadero.com|language=en|access-date=2017-04-18}}</ref> उन्हें शब्दकोश कहा जाता है; पर्ल, रूबी (प्रोग्रामिंग भाषा) और बीज7 में उन्हें हैश कहा जाता है; [[C++]], Java (प्रोग्रामिंग लैंग्वेज), गो (प्रोग्रामिंग लैंग्वेज), [[क्लोजर]], [[स्काला (प्रोग्रामिंग भाषा)]], [[OCaml]], Haskell (प्रोग्रामिंग लैंग्वेज) में उन्हें मैप्स कहा जाता है (मैप देखें (C++), unordered_[[map (C++)]], और {{Javadoc:SE|java/util|Map}}); [[सामान्य लिस्प]] और [[विंडोज पॉवरशेल]] में, उन्हें हैश टेबल कहा जाता है (चूंकि दोनों आमतौर पर इस कार्यान्वयन का उपयोग करते हैं); मेपल (सॉफ्टवेयर) और लुआ में, उन्हें टेबल कहा जाता है। PHP में, सभी सरणियाँ साहचर्य हो सकती हैं, सिवाय इसके कि कुंजियाँ पूर्णांकों और स्ट्रिंग्स तक सीमित हैं। जावास्क्रिप्ट में (JSON भी देखें), सभी ऑब्जेक्ट स्ट्रिंग-वैल्यू कुंजियों के साथ साहचर्य सरणियों के रूप में व्यवहार करते हैं, जबकि मानचित्र और WeakMap प्रकार मनमाना वस्तुओं को कुंजियों के रूप में लेते हैं। लुआ में, वे सभी डेटा संरचनाओं के लिए आदिम बिल्डिंग ब्लॉक के रूप में उपयोग किए जाते हैं। [[विजुअल फॉक्सप्रो]] में, उन्हें संग्रह कहा जाता है। D (प्रोग्रामिंग लैंग्वेज) में साहचर्य सरणियों के लिए भी समर्थन है।<ref>{{cite web |url=http://dlang.org/hash-map.html|title=Associative Arrays, the D programming language|publisher=Digital Mars}}</ref>
स्मॉलटॉक में, [[Objective-C]], .NET Framework|.NET,<ref>{{cite web |url=http://msdn.microsoft.com/en-us/library/xfhwa508.aspx |title=Dictionary<TKey, TValue> Class |publisher=MSDN}}</ref> पायथन (प्रोग्रामिंग लैंग्वेज), [[असली बुनियादी]], [[स्विफ्ट (प्रोग्रामिंग भाषा)]], एप्लिकेशन और डेल्फी के लिए विजुअल बेसिक (प्रोग्रामिंग लैंग्वेज)<ref>{{Cite web|url=http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TDictionary|title=System.Generics.Collections.TDictionary - RAD Studio API Documentation|website=docwiki.embarcadero.com|language=en|access-date=2017-04-18}}</ref> उन्हें शब्दकोश कहा जाता है; पर्ल, रूबी (प्रोग्रामिंग भाषा) और बीज7 में उन्हें हैश कहा जाता है; [[C++]], Java (प्रोग्रामिंग लैंग्वेज), गो (प्रोग्रामिंग लैंग्वेज), [[क्लोजर]], [[स्काला (प्रोग्रामिंग भाषा)]], [[OCaml]], Haskell (प्रोग्रामिंग लैंग्वेज) में उन्हें मैप्स कहा जाता है (मैप देखें (C++), unordered_[[map (C++)]], और {{Javadoc:SE|java/util|Map}}); [[सामान्य लिस्प]] और [[विंडोज पॉवरशेल]] में, उन्हें हैश टेबल कहा जाता है (चूंकि दोनों आमतौर पर इस कार्यान्वयन का उपयोग करते हैं); मेपल (सॉफ्टवेयर) और लुआ में, उन्हें टेबल कहा जाता है। PHP में, सभी सरणियाँ साहचर्य हो सकती हैं, सिवाय इसके कि कुंजियाँ पूर्णांकों और स्ट्रिंग्स तक सीमित हैं। जावास्क्रिप्ट में (JSON भी देखें), सभी ऑब्जेक्ट स्ट्रिंग-वैल्यू कुंजियों के साथ साहचर्य सरणियों के रूप में व्यवहार करते हैं, जबकि मानचित्र और WeakMap प्रकार मनमाना वस्तुओं को कुंजियों के रूप में लेते हैं। लुआ में, वे सभी डेटा संरचनाओं के लिए आदिम बिल्डिंग ब्लॉक के रूप में उपयोग किए जाते हैं। [[विजुअल फॉक्सप्रो]] में, उन्हें संग्रह कहा जाता है। D (प्रोग्रामिंग लैंग्वेज) में साहचर्य सरणियों के लिए भी समर्थन है।<ref>{{cite web |url=http://dlang.org/hash-map.html|title=Associative Arrays, the D programming language|publisher=Digital Mars}}</ref>
Line 157: Line 154:
== स्थायी भंडारण ==
== स्थायी भंडारण ==
{{Main|Key–value store}}
{{Main|Key–value store}}
साहचर्य सरणियों का उपयोग करने वाले कई कार्यक्रमों को किसी बिंदु पर उस डेटा को अधिक स्थायी रूप में संग्रहीत करने की आवश्यकता होगी, जैसे [[कम्प्यूटर फाइल]] में। इस समस्या का एक सामान्य समाधान एक सामान्यीकृत अवधारणा है जिसे संग्रह या क्रमांकन के रूप में जाना जाता है, जो मूल वस्तुओं का एक पाठ या द्विआधारी प्रतिनिधित्व उत्पन्न करता है जिसे सीधे फ़ाइल में लिखा जा सकता है। यह आमतौर पर अंतर्निहित ऑब्जेक्ट मॉडल में लागू किया जाता है, जैसे .नेट या कोको, जिसमें मानक फलन  शामिल होते हैं जो आंतरिक डेटा को टेक्स्ट फॉर्म में परिवर्तित करते हैं। कार्यक्रम इन विधियों को कॉल करके वस्तुओं के किसी भी समूह का एक पूर्ण पाठ प्रतिनिधित्व बना सकता है, जो लगभग हमेशा आधार साहचर्य सरणी वर्ग में लागू होते हैं।<ref>[https://developer.apple.com/library/prerelease/ios/documentation/Cocoa/Conceptual/Archiving/Archiving.html#//apple_ref/doc/uid/10000047i "Archives and Serializations Programming Guide"], Apple Inc., 2012</ref>
साहचर्य सरणियों का उपयोग करने वाले कई कार्यक्रमों को किसी बिंदु पर उस डेटा को अधिक स्थायी रूप में संग्रहीत करने की आवश्यकता होगी, जैसे [[कम्प्यूटर फाइल]] में। इस समस्या का एक सामान्य समाधान एक सामान्यीकृत अवधारणा है जिसे संग्रह या क्रमांकन के रूप में जाना जाता है, जो मूल वस्तुओं का एक पाठ या द्विआधारी प्रतिनिधित्व उत्पन्न करता है जिसे सीधे फ़ाइल में लिखा जा सकता है। यह आमतौर पर अंतर्निहित ऑब्जेक्ट मॉडल में प्रयुक्त किया जाता है, जैसे .नेट या कोको, जिसमें मानक फलन  सम्मिलित होते हैं जो आंतरिक डेटा को टेक्स्ट फॉर्म में परिवर्तित करते हैं। कार्यक्रम इन विधियों को कॉल करके वस्तुओं के किसी भी समूह का एक पूर्ण पाठ प्रतिनिधित्व बना सकता है, जो लगभग हमेशा आधार साहचर्य सरणी वर्ग में प्रयुक्त होते हैं।<ref>[https://developer.apple.com/library/prerelease/ios/documentation/Cocoa/Conceptual/Archiving/Archiving.html#//apple_ref/doc/uid/10000047i "Archives and Serializations Programming Guide"], Apple Inc., 2012</ref>
उन प्रोग्रामों के लिए जो बहुत बड़े डेटा सेट का उपयोग करते हैं, इस प्रकार का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है, और एक [[डेटाबेस प्रबंधन प्रणाली]] (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सरणियों को संग्रहीत करते हैं। व्यक्तिगत सरणियों को फिर से संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। ये की-वैल्यू डेटाबेस | की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है जब तक कि अधिक सामान्य [[संबंध का डेटाबेस]] (RDBs) के रूप में, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, कुछ विशिष्ट आला तक उनके उपयोग को सीमित कर दिया। भूमिकाएँ। ज्यादातर मामलों में इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था, हालांकि वस्तुओं को आरडीबी में सहेजना जटिल हो सकता है, एक समस्या जिसे [[वस्तु-संबंधपरक प्रतिबाधा बेमेल]] के रूप में जाना जाता है।
उन प्रोग्रामों के लिए जो बहुत बड़े डेटा सेट का उपयोग करते हैं, इस प्रकार का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है, और एक [[डेटाबेस प्रबंधन प्रणाली]] (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सरणियों को संग्रहीत करते हैं। व्यक्तिगत सरणियों को फिर से संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। ये की-वैल्यू डेटाबेस | की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है जब तक कि अधिक सामान्य [[संबंध का डेटाबेस]] (RDBs) के रूप में, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, कुछ विशिष्ट आला तक उनके उपयोग को सीमित कर दिया। भूमिकाएँ। ज्यादातर स्थितियों में इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था, हालांकि वस्तुओं को आरडीबी में सहेजना जटिल हो सकता है, एक समस्या जिसे [[वस्तु-संबंधपरक प्रतिबाधा बेमेल]] के रूप में जाना जाता है।


बाद {{circa|2010}}, [[क्लाउड कम्प्यूटिंग]] के लिए उपयुक्त उच्च-प्रदर्शन डेटाबेस की आवश्यकता और उनके उपयोग से कार्यक्रमों की आंतरिक संरचना से अधिक निकटता से मिलान करने से की-वैल्यू स्टोर बाजार में पुनर्जागरण हुआ। ये प्रणालियां मूल रूप से साहचर्य सरणियों को संग्रहीत और पुनः प्राप्त कर सकती हैं, जो सामान्य वेब-संबंधित वर्कफ़्लोज़ में प्रदर्शन में बहुत सुधार कर सकती हैं।
बाद {{circa|2010}}, [[क्लाउड कम्प्यूटिंग]] के लिए उपयुक्त उच्च-प्रदर्शन डेटाबेस की आवश्यकता और उनके उपयोग से कार्यक्रमों की आंतरिक संरचना से अधिक निकटता से मिलान करने से की-वैल्यू स्टोर बाजार में पुनर्जागरण हुआ। ये प्रणालियां मूल रूप से साहचर्य सरणियों को संग्रहीत और पुनः प्राप्त कर सकती हैं, जो सामान्य वेब-संबंधित वर्कफ़्लोज़ में प्रदर्शन में बहुत सुधार कर सकती हैं।

Revision as of 09:22, 27 February 2023

"शब्दकोश (डेटा संरचना)" redirects here. Not to be confused with डेटा शब्दकोश.
"सहयोगी कंटेनर" redirects here. For सी ++ प्रोग्रामिंग भाषा के मानक पुस्तकालय में आदेशित साहचर्य सरणियों का कार्यान्वयन, see सहयोगी कंटेनर.
"मानचित्र (कंप्यूटर विज्ञान)" redirects here. For उच्च-क्रम समारोह, see मानचित्र (उच्च क्रम समारोह). For अन्य प्रयोग, see मानचित्र (बहुविकल्पी).

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

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

कई प्रोग्रामिंग भाषाओं में प्रथम डेटा प्रकारों के रूप में साहचर्य सरणियाँ सम्मिलित हैं और वे कई अन्य लोगों के लिए सॉफ्टवेयर पुस्तकालय में उपलब्ध हैं। सामग्री-पता योग्य मेमोरी सहयोगी सरणियों के लिए प्रत्यक्ष हार्डवेयर-स्तर समर्थन का एक रूप है।

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

संचालन

एक साहचर्य सरणी में, विशेषता-मूल्य जोड़ी के बीच संबंध को अक्सर मैपिंग के रूप में जाना जाता है, और एक ही शब्द मैपिंग का उपयोग एक नया संघ बनाने की प्रक्रिया को संदर्भित करने के लिए भी किया जा सकता है।

आमतौर पर एक साहचर्य सरणी के लिए परिभाषित किए जाने वाले ऑपरेशन हैं:[3][4][8]

  • डालें या डालें: एक नया जोड़ें कुंजी को उसके नए मान से मैप करते हुए संग्रह से जोड़े। कोई भी मौजूदा मैपिंग अधिलेखित है। इस ऑपरेशन के तर्क कुंजी और मान हैं।
  • हटाएं या हटाएं: हटाएं ए संग्रह से जोड़ी, किसी दिए गए कुंजी को उसके मूल्य से अनमैप करना। इस ऑपरेशन का तर्क कुंजी है।
  • लुकअप, फाइंड, या गेट: वह मान (यदि कोई हो) खोजें जो किसी दिए गए कुंजी से जुड़ा हो। इस ऑपरेशन का तर्क कुंजी है, और ऑपरेशन से मान वापस किया जाता है। यदि कोई मान नहीं मिलता है, तो कुछ लुकअप फलन अपवाद हैंडलिंग बढ़ाते हैं, जबकि अन्य डिफ़ॉल्ट मान (शून्य, शून्य, विशिष्ट मान निर्माता को दिए गए ...) लौटाते हैं।

इसके अलावा, साहचर्य सरणियों में अन्य ऑपरेशन भी सम्मिलित हो सकते हैं जैसे मैपिंग की संख्या निर्धारित करना या सभी मैपिंग पर लूप करने के लिए एक इटरेटर का निर्माण करना। आमतौर पर, इस तरह के ऑपरेशन के लिए, जिस क्रम में मैपिंग लौटाई जाती है, वह कार्यान्वयन-परिभाषित हो सकता है।

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

गुण

साहचर्य सरणी के संचालन को विभिन्न गुणों को पूरा करना चाहिए:[8]

  • lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
  • lookup(k, new()) = fail, कहाँ fail एक अपवाद या डिफ़ॉल्ट मान है
  • remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))
  • remove(k, new()) = new()

कहाँ k और j चाबियाँ हैं, v एक मूल्य है, D एक सहयोगी सरणी है, और new() एक नया, खाली साहचर्य सरणी बनाता है।

उदाहरण

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

<वाक्यविन्यास प्रकाश लैंग = जावास्क्रिप्ट> { 

    गर्व और पूर्वाग्रह: ऐलिस,
    वुथरिंग हाइट्स: ऐलिस,
    ग्रेट एक्सपेक्टेशंस: जॉन

}</syntaxhighlight>

प्रमुख ग्रेट एक्सपेक्टेशंस पर एक लुकअप ऑपरेशन जॉन को लौटाएगा। यदि जॉन अपनी पुस्तक लौटाता है, तो यह हटाने की कार्रवाई का कारण बनेगा, और यदि पैट एक पुस्तक की जांच करता है, तो यह एक सम्मिलन कार्रवाई का कारण बनेगा, जिससे एक अलग स्थिति होगी:

<वाक्यविन्यास प्रकाश लैंग = जावास्क्रिप्ट> { 

    गर्व और पूर्वाग्रह: ऐलिस,
    द ब्रदर्स करमाज़ोव: पैट,
    वुथरिंग हाइट्स: ऐलिस

}</syntaxhighlight>

कार्यान्वयन

मैपिंग की बहुत कम संख्या वाले शब्दकोशों के लिए, संघ सूची, मैपिंग की एक लिंक्ड सूची का उपयोग करके शब्दकोश को प्रयुक्त करना समझ में आ सकता है। इस कार्यान्वयन के साथ, बुनियादी शब्दकोश संचालन करने का समय मैपिंग की कुल संख्या में रैखिक है; हालाँकि, इसे प्रयुक्त करना आसान है और इसके चलने के समय में स्थिर कारक छोटे हैं।[3][10] एक अन्य बहुत ही सरल कार्यान्वयन तकनीक, जब कुंजियों को एक संकीर्ण सीमा तक सीमित किया जाता है, तो एक सरणी में सीधे संबोधित किया जाता है: किसी दिए गए कुंजी k के मान को सरणी सेल A [k] में संग्रहीत किया जाता है, या यदि k के लिए कोई मैपिंग नहीं है तब सेल एक विशेष प्रहरी मान संग्रहीत करता है जो मैपिंग की अनुपस्थिति को इंगित करता है। सरल होने के साथ-साथ, यह तकनीक तेज़ है: प्रत्येक शब्दकोश संक्रिया में निरंतर समय लगता है। हालाँकि, इस संरचना के लिए स्थान की आवश्यकता पूरे कीस्पेस का आकार है, जब तक कि कीस्पेस छोटा न हो, यह अव्यावहारिक है।[5]

शब्दकोशों को प्रयुक्त करने के दो प्रमुख तरीके हैश टेबल या सर्च ट्री हैं।[3][4][5][6]


हैश सारणी कार्यान्वयन

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

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

हैश टेबल को हैश टकराव को संभालने में सक्षम होना चाहिए: जब हैश फलन दो अलग-अलग कुंजियों को सरणी की एक ही बाल्टी में मैप करता है। इस समस्या के दो सबसे व्यापक दृष्टिकोण अलग-अलग चेनिंग और खुला संबोधन हैं।[3][4][5][11] अलग-अलग श्रंखला में, सरणी स्वयं मान को संग्रहीत नहीं करती है, लेकिन एक सूचक (कंप्यूटर प्रोग्रामिंग) को दूसरे कंटेनर में संग्रहीत करती है, आमतौर पर एक एसोसिएशन सूची, जो हैश से मेल खाने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर, खुले पते में, यदि कोई हैश टकराव पाया जाता है, तो सारणी एक नियतात्मक तरीके से मूल्य को संग्रहीत करने के लिए एक सरणी में एक खाली स्थान की तलाश करती है, आमतौर पर सरणी में अगली तत्काल स्थिति को देखते हुए।

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

वृक्ष कार्यान्वयन

Main article: Search tree


सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री

एक अन्य सामान्य दृष्टिकोण एक स्व-संतुलन बाइनरी सर्च ट्री के साथ एक साहचर्य सरणी को प्रयुक्त करना है, जैसे कि एवीएल का पेड़ या रेड-ब्लैक ट्री।[12] हैश टेबल की तुलना में, इन संरचनाओं के फायदे और कमजोरियां दोनों हैं। सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का सबसे खराब प्रदर्शन हैश टेबल की तुलना में काफी बेहतर है, ओ (लॉग एन) के बिग ओ नोटेशन में समय की जटिलता के साथ। यह हैश टेबल के विपरीत है, जिसके सबसे खराब प्रदर्शन में सभी तत्व एक ही बकेट साझा करते हैं, जिसके परिणामस्वरूप O(n) समय जटिलता होती है। इसके अलावा, और सभी बाइनरी सर्च ट्री की तरह, सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री अपने तत्वों को क्रम में रखते हैं। इस प्रकार, इसके तत्वों को कम से कम-से-महानतम पैटर्न का पालन करना, जबकि एक हैश सारणी को घुमाने के परिणामस्वरूप तत्वों को यादृच्छिक क्रम में हो सकता है। क्योंकि वे इन-ऑर्डर हैं, वृक्ष-आधारित मानचित्र श्रेणी के प्रश्नों को भी संतुष्ट कर सकते हैं (दो सीमाओं के बीच सभी मान प्राप्त करें) जबकि एक हैशपैप केवल सटीक मान प्राप्त कर सकता है। हालांकि, हैश टेबल में O(1) के सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में बेहतर औसत-केस टाइम जटिलता है, और जब एक अच्छे हैश फलन का उपयोग किया जाता है तो उनका सबसे खराब प्रदर्शन बहुत कम होता है।

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


अन्य पेड़

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

तुलना

Underlying data structure Lookup or Removal Insertion Ordered
average worst case average worst case
Hash table O(1) O(n) O(1) O(n) No
Self-balancing binary search tree O(log n) O(log n) O(log n) O(log n) Yes
unbalanced binary search tree O(log n) O(n) O(log n) O(n) Yes
Sequential container of key–value pairs
(e.g. association list) 		O(n) O(n) O(1) O(1) No


क्रमित शब्दकोश

शब्दकोश की मूल परिभाषा में एक आदेश अनिवार्य नहीं है। गणना के एक निश्चित क्रम की गारंटी के लिए, साहचर्य सरणी के आदेशित संस्करण अक्सर उपयोग किए जाते हैं। आदेशित शब्दकोश की दो भावनाएँ हैं:

  • छँटाई के द्वारा चाबियों के दिए गए सेट के लिए गणना का क्रम हमेशा नियतात्मक होता है। यह वृक्ष-आधारित कार्यान्वयन का मामला है, एक प्रतिनिधि <map> सी ++ का कंटेनर।[16]
  • गणना का क्रम कुंजी-स्वतंत्र है और इसके बजाय सम्मिलन के क्रम पर आधारित है। यह .NET फ्रेमवर्क, Java के LinkedHashMap (प्रोग्रामिंग लैंग्वेज) और Python (प्रोग्रामिंग लैंग्वेज) में ऑर्डर किए गए डिक्शनरी के मामले में है।[17][18][19]

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

भाषा समर्थन

Main article: Comparison of programming languages (associative array)

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

साहचर्य सरणियों के लिए अंतर्निहित सिंटैक्टिक समर्थन 1969 में SNOBOL द्वारा नाम सारणी के तहत पेश किया गया था। TMG (भाषा) ने स्ट्रिंग कुंजियों और पूर्णांक मानों के साथ सारणियों की पेशकश की। MUMPS ने बहु-आयामी साहचर्य सरणियाँ बनाईं, वैकल्पिक रूप से लगातार, इसकी प्रमुख डेटा संरचना। SETL ने उन्हें सेट और मैप्स के एक संभावित कार्यान्वयन के रूप में समर्थन दिया। AWK से शुरू होने वाली और Rexx, Perl, PHP, Tcl, JavaScript, Maple (सॉफ्टवेयर), Python (प्रोग्रामिंग लैंग्वेज), Ruby (प्रोग्रामिंग लैंग्वेज), Wolfram Language, Go (प्रोग्रामिंग लैंग्वेज), और Lua (प्रोग्रामिंग) सहित अधिकांश आधुनिक स्क्रिप्टिंग भाषाएँ भाषा), एक प्राथमिक कंटेनर प्रकार के रूप में साहचर्य सरणियों का समर्थन करता है। कई और भाषाओं में, वे विशेष सिंटैक्स के बिना पुस्तकालय कार्यों के रूप में उपलब्ध हैं।

स्मॉलटॉक में, Objective-C, .NET Framework|.NET,[20] पायथन (प्रोग्रामिंग लैंग्वेज), असली बुनियादी, स्विफ्ट (प्रोग्रामिंग भाषा), एप्लिकेशन और डेल्फी के लिए विजुअल बेसिक (प्रोग्रामिंग लैंग्वेज)[21] उन्हें शब्दकोश कहा जाता है; पर्ल, रूबी (प्रोग्रामिंग भाषा) और बीज7 में उन्हें हैश कहा जाता है; C++, Java (प्रोग्रामिंग लैंग्वेज), गो (प्रोग्रामिंग लैंग्वेज), क्लोजर, स्काला (प्रोग्रामिंग भाषा), OCaml, Haskell (प्रोग्रामिंग लैंग्वेज) में उन्हें मैप्स कहा जाता है (मैप देखें (C++), unordered_map (C++), और Map); सामान्य लिस्प और विंडोज पॉवरशेल में, उन्हें हैश टेबल कहा जाता है (चूंकि दोनों आमतौर पर इस कार्यान्वयन का उपयोग करते हैं); मेपल (सॉफ्टवेयर) और लुआ में, उन्हें टेबल कहा जाता है। PHP में, सभी सरणियाँ साहचर्य हो सकती हैं, सिवाय इसके कि कुंजियाँ पूर्णांकों और स्ट्रिंग्स तक सीमित हैं। जावास्क्रिप्ट में (JSON भी देखें), सभी ऑब्जेक्ट स्ट्रिंग-वैल्यू कुंजियों के साथ साहचर्य सरणियों के रूप में व्यवहार करते हैं, जबकि मानचित्र और WeakMap प्रकार मनमाना वस्तुओं को कुंजियों के रूप में लेते हैं। लुआ में, वे सभी डेटा संरचनाओं के लिए आदिम बिल्डिंग ब्लॉक के रूप में उपयोग किए जाते हैं। विजुअल फॉक्सप्रो में, उन्हें संग्रह कहा जाता है। D (प्रोग्रामिंग लैंग्वेज) में साहचर्य सरणियों के लिए भी समर्थन है।[22]


स्थायी भंडारण

Main article: Key–value store

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

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

यह भी देखें

  • की-वैल्यू डेटाबेस
  • टपल
  • समारोह (गणित)
  • जेएसओएन

संदर्भ

  1. ↑ Collins, Graham; Syme, Donald (1995). "A theory of finite maps". Higher Order Logic Theorem Proving and Its Applications. Lecture Notes in Computer Science. 971: 122–137. doi:10.1007/3-540-60275-5_61. ISBN 978-3-540-60275-0.
  2. ↑ Andersson, Arne (1989). "Optimal Bounds on the Dictionary Problem". Proc. Symposium on Optimal Algorithms. Lecture Notes in Computer Science. Springer Verlag. 401: 106–114. doi:10.1007/3-540-51859-2_10. ISBN 978-3-540-51859-4.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Goodrich, Michael T.; Tamassia, Roberto (2006), "9.1 The Map Abstract Data Type", Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371
  4. ↑ 4.0 4.1 4.2 4.3 Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98, archived (PDF) from the original on 2014-08-02
  5. ↑ 5.0 5.1 5.2 5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.
  6. ↑ 6.0 6.1 Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. "Dynamic Perfect Hashing: Upper and Lower Bounds" Archived 2016-03-04 at the Wayback Machine. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094
  7. ↑ Goodrich & Tamassia (2006), pp. 597–599.
  8. ↑ 8.0 8.1 Black, Paul E.; Stewart, Rob (2 November 2020). "dictionary". Dictionary of Algorithms and Data Structures. Retrieved 26 January 2022.
  9. ↑ Goodrich & Tamassia (2006), pp. 389–397.
  10. ↑ "When should I use a hash table instead of an association list?". lisp-faq/part2. 1996-02-20.
  11. ↑ Klammer, F.; Mazzolini, L. (2006), "Pathfinders for associative maps", Ext. Abstracts GIS-l 2006, GIS-I, pp. 71–74.
  12. ↑ Joel Adams and Larry Nyhoff. "Trees in STL". Quote: "The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of self-balancing binary search tree called a red–black tree."
  13. ↑ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.
  14. ↑ Probst, Mark (2010-04-30). "Linear vs Binary Search". Retrieved 2016-11-20.
  15. ↑ Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (April 2015). "A comparison of adaptive radix trees and hash tables". 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea: IEEE: 1227–1238. doi:10.1109/ICDE.2015.7113370. ISBN 978-1-4799-7964-6. S2CID 17170456.
  16. ↑ "std::map". en.cppreference.com.
  17. ↑ "OrderedDictionary Class (System.Collections.Specialized)". MS Docs (in English).
  18. ↑ "LinkedHashMap".
  19. ↑ "collections — Container datatypes — Python 3.9.0a3 documentation". docs.python.org.
  20. ↑ "Dictionary<TKey, TValue> Class". MSDN.
  21. ↑ "System.Generics.Collections.TDictionary - RAD Studio API Documentation". docwiki.embarcadero.com (in English). Retrieved 2017-04-18.
  22. ↑ "Associative Arrays, the D programming language". Digital Mars.
  23. ↑ "Archives and Serializations Programming Guide", Apple Inc., 2012


बाहरी संबंध

Look up associative array in Wiktionary, the free dictionary.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=साहचर्य_सरणी&oldid=104297’