साहचर्य सरणी: Difference between revisions
No edit summary |
No edit summary |
||
| Line 16: | Line 16: | ||
== संचालन == | == संचालन == | ||
एक साहचर्य सरणी में | एक साहचर्य सरणी में विशेषता-मूल्य जोड़ी के बीच संबंध को प्रायः मैपिंग के रूप में जाना जाता है और एक ही शब्द मैपिंग का उपयोग नया संघ बनाने की प्रक्रिया को संदर्भित करने के लिए भी किया जा सकता है। | ||
सामान्यतः एक साहचर्य सरणी के लिए परिभाषित किए जाने वाले संचालन हैं:<ref name="gt">{{citation|contribution=9.1 The Map Abstract Data Type|title=Data Structures & Algorithms in Java|last1=Goodrich|first1=Michael T.|author1-link=Michael T. Goodrich|last2=Tamassia|first2=Roberto|author2-link=Roberto Tamassia|publisher=Wiley|edition=4th|year=2006|pages=368–371}}</ref><ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|pages=81–98 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf |archive-url=https://web.archive.org/web/20140802025330/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf |archive-date=2014-08-02 |url-status=live}}</ref><ref name="Black"/> | |||
* | * डालें: एक नया जोड़ें <math>(key, value)</math> कुंजी को उसके नए मान से मैप करते हुए संग्रह से जोड़े। कोई भी उपस्थित मैपिंग अधिलेखित है। इस संचालन के तर्क कुंजी और मान हैं। | ||
* हटाएं या हटाएं: हटाएं | * हटाएं या हटाएं: हटाएं <math>(key, value)</math> संग्रह से जोड़ी किसी दिए गए कुंजी को उसके मूल्य से अनमैप करना। इस संचालन का तर्क कुंजी है। | ||
* लुकअप, फाइंड, या गेट: वह मान (यदि कोई हो) खोजें जो किसी दिए गए कुंजी से जुड़ा हो। इस | * लुकअप, फाइंड, या गेट: वह मान (यदि कोई हो) खोजें जो किसी दिए गए कुंजी से जुड़ा हो। इस संचालन का तर्क कुंजी है और संचालन से मान वापस किया जाता है। यदि कोई मान नहीं मिलता है। तो कुछ लुकअप फलन अपवाद हैंडलिंग बढ़ाते हैं। जबकि अन्य डिफ़ॉल्ट मान (शून्य, शून्य, विशिष्ट मान निर्माता को दिए गए) लौटाते हैं। | ||
इसके | इसके अतिरिक्त साहचर्य सरणियों में अन्य संचालन भी सम्मिलित हो सकते हैं। जैसे मैपिंग की संख्या निर्धारित करना या सभी मैपिंग पर लूप करने के लिए एक [[इटरेटर]] का निर्माण करना। सामान्यतः इस प्रकार के संचालन के लिए जिस क्रम में मैपिंग लौटाई जाती है। वह कार्यान्वयन-परिभाषित हो सकता है। | ||
एक [[मल्टीमैप]] एक एकल कुंजी के साथ कई मानों को संबद्ध करने की अनुमति देकर एक साहचर्य सरणी का सामान्यीकरण करता है।<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> एक [[द्विदिश नक्शा]] एक संबंधित | एक [[मल्टीमैप]] एक एकल कुंजी के साथ कई मानों को संबद्ध करने की अनुमति देकर एक साहचर्य सरणी का सामान्यीकरण करता है।<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> एक [[द्विदिश नक्शा|द्विदिश मानचित्र]] एक संबंधित सार डेटा प्रकार है। जिसमें मैपिंग दोनों दिशाओं में संचालित होती ह। प्रत्येक मान को एक अलग प्रकार की कुंजी के साथ जोड़ा जाना चाहिए और दूसरा लुकअप संचालन एक मान को एक तर्क के रूप में लेता है और उस मान से जुड़ी कुंजी को देखता है। | ||
=== गुण === | === गुण === | ||
| Line 46: | Line 46: | ||
}</syntaxhighlight> | }</syntaxhighlight> | ||
प्रमुख ग्रेट एक्सपेक्टेशंस पर एक लुकअप | प्रमुख ग्रेट एक्सपेक्टेशंस पर एक लुकअप संचालन जॉन को लौटाएगा। यदि जॉन अपनी पुस्तक लौटाता है, तो यह हटाने की कार्रवाई का कारण बनेगा, और यदि पैट एक पुस्तक की जांच करता है, तो यह एक सम्मिलन कार्रवाई का कारण बनेगा, जिससे एक अलग स्थिति होगी: | ||
<वाक्यविन्यास प्रकाश लैंग = जावास्क्रिप्ट> { | <वाक्यविन्यास प्रकाश लैंग = जावास्क्रिप्ट> { | ||
| Line 68: | Line 68: | ||
=== हैश सारणी कार्यान्वयन === | === हैश सारणी कार्यान्वयन === | ||
{{main | Hash table}} | {{main | Hash table}} | ||
[[File:Hash table average insertion time.png|thumb|right|362px|यह ग्राफ बड़े हैश टेबल (कैश के आकार से कहीं अधिक) में तत्वों को देखने के लिए आवश्यक [[सीपीयू कैश]] मिस की औसत संख्या की तुलना चेनिंग और [[रैखिक जांच]] के साथ करता है। संदर्भ की बेहतर स्थानीयता के कारण रेखीय जांच बेहतर प्रदर्शन करती है, हालाँकि जैसे-जैसे सारणी भर जाती है, इसका प्रदर्शन बहुत कम हो जाता है।]]एक साहचर्य सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन एक हैश सारणी के साथ होता है: एक [[हैश फंकशन]] के साथ संयुक्त एक सरणी डेटा संरचना जो प्रत्येक कुंजी को सरणी की एक अलग बाल्टी में अलग करती है। हैश सारणी के पीछे मूल विचार यह है कि किसी सरणी के किसी तत्व को उसके सूचकांक के माध्यम से एक्सेस करना एक सरल, निरंतर-समय का | [[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 86: | 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(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 92: | Line 92: | ||
==== अन्य पेड़ ==== | ==== अन्य पेड़ ==== | ||
साहचर्य सरणियों को असंतुलित बाइनरी सर्च ट्री में या किसी विशेष प्रकार की चाबियों जैसे [[मूलांक का पेड़]], [[कोशिश करें]], [[जूडी सरणी]] या [[वैन एम्डे बोस कदम]] के लिए विशिष्ट डेटा संरचनाओं में भी संग्रहीत किया जा सकता है, हालांकि हैश टेबल की तुलना में इन कार्यान्वयन विधियों की क्षमता भिन्न होता है; उदाहरण के लिए, जूडी ट्री को हैश टेबल की तुलना में कम मात्रा में दक्षता के साथ प्रदर्शन करने के लिए संकेत दिया जाता है, जबकि सावधानी से चयनित हैश टेबल | साहचर्य सरणियों को असंतुलित बाइनरी सर्च ट्री में या किसी विशेष प्रकार की चाबियों जैसे [[मूलांक का पेड़]], [[कोशिश करें]], [[जूडी सरणी]] या [[वैन एम्डे बोस कदम]] के लिए विशिष्ट डेटा संरचनाओं में भी संग्रहीत किया जा सकता है, हालांकि हैश टेबल की तुलना में इन कार्यान्वयन विधियों की क्षमता भिन्न होता है; उदाहरण के लिए, जूडी ट्री को हैश टेबल की तुलना में कम मात्रा में दक्षता के साथ प्रदर्शन करने के लिए संकेत दिया जाता है, जबकि सावधानी से चयनित हैश टेबल सामान्यतः एडाप्टिव रेडिक्स ट्री की तुलना में बढ़ी हुई दक्षता के साथ प्रदर्शन करते हैं, जिसमें डेटा के प्रकारों पर संभावित अधिक प्रतिबंध होते हैं जिन्हें वे संभाल सकते हैं।<ref>{{Cite journal|last1=Alvarez|first1=Victor|last2=Richter|first2=Stefan|last3=Chen|first3=Xiao|last4=Dittrich|first4=Jens|date=April 2015|title=A comparison of adaptive radix trees and hash tables|journal=2015 IEEE 31st International Conference on Data Engineering|location=Seoul, South Korea|publisher=IEEE|pages=1227–1238|doi=10.1109/ICDE.2015.7113370|isbn=978-1-4799-7964-6|s2cid=17170456}}</ref> इन वैकल्पिक संरचनाओं के फायदे एक साहचर्य सरणी के मूल से परे संचालन को संभालने की उनकी क्षमता से आते हैं, जैसे कि मैपिंग को ढूंढना जिसकी कुंजी क्वेरी कुंजी के सबसे करीब है, जब क्वेरी स्वयं मैपिंग के सेट में मौजूद नहीं होती है। | ||
=== तुलना === | === तुलना === | ||
| Line 137: | Line 137: | ||
== क्रमित शब्दकोश == | == क्रमित शब्दकोश == | ||
शब्दकोश की मूल परिभाषा में एक आदेश अनिवार्य नहीं है। गणना के एक निश्चित क्रम की गारंटी के लिए, साहचर्य सरणी के आदेशित संस्करण | शब्दकोश की मूल परिभाषा में एक आदेश अनिवार्य नहीं है। गणना के एक निश्चित क्रम की गारंटी के लिए, साहचर्य सरणी के आदेशित संस्करण प्रायः उपयोग किए जाते हैं। आदेशित शब्दकोश की दो भावनाएँ हैं: | ||
* छँटाई के द्वारा चाबियों के दिए गए सेट के लिए गणना का क्रम हमेशा नियतात्मक होता है। यह वृक्ष-आधारित कार्यान्वयन का मामला है, एक प्रतिनिधि {{code|<map>}} सी ++ का कंटेनर।<ref>{{cite web |title=std::map |url=https://en.cppreference.com/w/cpp/container/map |website=en.cppreference.com}}</ref> | * छँटाई के द्वारा चाबियों के दिए गए सेट के लिए गणना का क्रम हमेशा नियतात्मक होता है। यह वृक्ष-आधारित कार्यान्वयन का मामला है, एक प्रतिनिधि {{code|<map>}} सी ++ का कंटेनर।<ref>{{cite web |title=std::map |url=https://en.cppreference.com/w/cpp/container/map |website=en.cppreference.com}}</ref> | ||
| Line 145: | 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}}); [[सामान्य लिस्प]] और [[विंडोज पॉवरशेल]] में, उन्हें हैश टेबल कहा जाता है (चूंकि दोनों | स्मॉलटॉक में, [[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> | ||
== स्थायी भंडारण == | == स्थायी भंडारण == | ||
{{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> | ||
उन प्रोग्रामों के लिए जो बहुत बड़े डेटा सेट का उपयोग करते हैं, इस प्रकार का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है, और एक [[डेटाबेस प्रबंधन प्रणाली]] (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सरणियों को संग्रहीत करते हैं। व्यक्तिगत सरणियों को फिर से संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। ये की-वैल्यू डेटाबेस | की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है जब तक कि अधिक सामान्य [[संबंध का डेटाबेस]] (RDBs) के रूप में, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, कुछ विशिष्ट आला तक उनके उपयोग को सीमित कर दिया। भूमिकाएँ। ज्यादातर स्थितियों में इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था, हालांकि वस्तुओं को आरडीबी में सहेजना जटिल हो सकता है, एक समस्या जिसे [[वस्तु-संबंधपरक प्रतिबाधा बेमेल]] के रूप में जाना जाता है। | उन प्रोग्रामों के लिए जो बहुत बड़े डेटा सेट का उपयोग करते हैं, इस प्रकार का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है, और एक [[डेटाबेस प्रबंधन प्रणाली]] (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सरणियों को संग्रहीत करते हैं। व्यक्तिगत सरणियों को फिर से संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। ये की-वैल्यू डेटाबेस | की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है जब तक कि अधिक सामान्य [[संबंध का डेटाबेस]] (RDBs) के रूप में, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, कुछ विशिष्ट आला तक उनके उपयोग को सीमित कर दिया। भूमिकाएँ। ज्यादातर स्थितियों में इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था, हालांकि वस्तुओं को आरडीबी में सहेजना जटिल हो सकता है, एक समस्या जिसे [[वस्तु-संबंधपरक प्रतिबाधा बेमेल]] के रूप में जाना जाता है। | ||
Revision as of 09:31, 27 February 2023
कंप्यूटर विज्ञान में साहचर्य सरणी, मानचित्र, प्रतीक सारणी या शब्दकोश सार डेटा प्रकार है। जो विशेषता-मूल्य जोड़ी का संग्रह (सार डेटा प्रकार) संग्रहीत करता है | एक बार संग्रह में कुंजी, मान जोड़े जैसे कि प्रत्येक संभावित कुंजी अधिकतम दिखाई देती है। गणितीय शब्दों में साहचर्य सरणी एक फलन (गणित) है। जिसमें एक फलन का 'सीमित' डोमेन होता है।[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]
हैश सारणी कार्यान्वयन
एक साहचर्य सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन एक हैश सारणी के साथ होता है: एक हैश फंकशन के साथ संयुक्त एक सरणी डेटा संरचना जो प्रत्येक कुंजी को सरणी की एक अलग बाल्टी में अलग करती है। हैश सारणी के पीछे मूल विचार यह है कि किसी सरणी के किसी तत्व को उसके सूचकांक के माध्यम से एक्सेस करना एक सरल, निरंतर-समय का संचालन है। इसलिए, हैश टेबल के लिए एक संचालन का औसत ओवरहेड केवल कुंजी के हैश की गणना है, जो सरणी के भीतर संबंधित बकेट तक पहुंचने के साथ संयुक्त है। जैसे, हैश टेबल सामान्यतः ओ (1) समय में प्रदर्शन करते हैं, और अधिकांश स्थितियों में बेहतर प्रदर्शन करते हैं।
हैश टेबल को हैश टकराव को संभालने में सक्षम होना चाहिए: जब हैश फलन दो अलग-अलग कुंजियों को सरणी की एक ही बाल्टी में मैप करता है। इस समस्या के दो सबसे व्यापक दृष्टिकोण अलग-अलग चेनिंग और खुला संबोधन हैं।[3][4][5][11] अलग-अलग श्रंखला में, सरणी स्वयं मान को संग्रहीत नहीं करती है, लेकिन एक सूचक (कंप्यूटर प्रोग्रामिंग) को दूसरे कंटेनर में संग्रहीत करती है, सामान्यतः एक एसोसिएशन सूची, जो हैश से मेल खाने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर, खुले पते में, यदि कोई हैश टकराव पाया जाता है, तो सारणी एक नियतात्मक तरीके से मूल्य को संग्रहीत करने के लिए एक सरणी में एक खाली स्थान की तलाश करती है, सामान्यतः सरणी में अगली तत्काल स्थिति को देखते हुए।
ओपन एड्रेसिंग में अलग-अलग चेनिंग की तुलना में कैश मिस अनुपात कम होता है जब टेबल ज्यादातर खाली होती है। हालाँकि, जैसे ही सारणी अधिक तत्वों से भर जाती है, खुले पते का प्रदर्शन तेजी से घटता है। इसके अतिरिक्त, ज्यादातर स्थितियों में अलग-अलग श्रृखंला कम मेमोरी का उपयोग करती है, जब तक कि प्रविष्टियां बहुत छोटी न हों (एक सूचक के आकार के चार गुना से कम)।
वृक्ष कार्यान्वयन
सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री
एक अन्य सामान्य दृष्टिकोण एक स्व-संतुलन बाइनरी सर्च ट्री के साथ एक साहचर्य सरणी को प्रयुक्त करना है, जैसे कि एवीएल का पेड़ या रेड-ब्लैक ट्री।[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]
आदेशित शब्दकोशों की बाद की भावना अधिक सामान्य रूप से सामना की जाती है। उन्हें एक सामान्य शब्दकोश के शीर्ष पर एक दोगुनी लिंक की गई सूची को ओवरले करके, या वास्तविक डेटा को विरल (अक्रमित) सरणी से बाहर और एक घने सम्मिलन-आदेशित एक में ले जाकर, एक एसोसिएशन सूची का उपयोग करके कार्यान्वित किया जा सकता है।
भाषा समर्थन
साहचर्य सरणियों को किसी जाओ (प्रोग्रामिंग भाषा) में एक पैकेज के रूप में प्रयुक्त किया जा सकता है और कई भाषा प्रणालियाँ उन्हें अपने मानक पुस्तकालय के हिस्से के रूप में प्रदान करती हैं। कुछ भाषाओं में, वे न केवल मानक प्रणाली में निर्मित होते हैं, किन्तु विशेष सिंटैक्स होते हैं, जो प्रायः सरणी-जैसी सबस्क्रिप्टिंग का उपयोग करते हैं।
साहचर्य सरणियों के लिए अंतर्निहित सिंटैक्टिक समर्थन 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]
स्थायी भंडारण
साहचर्य सरणियों का उपयोग करने वाले कई कार्यक्रमों को किसी बिंदु पर उस डेटा को अधिक स्थायी रूप में संग्रहीत करने की आवश्यकता होगी, जैसे कम्प्यूटर फाइल में। इस समस्या का एक सामान्य समाधान एक सामान्यीकृत अवधारणा है जिसे संग्रह या क्रमांकन के रूप में जाना जाता है, जो मूल वस्तुओं का एक पाठ या द्विआधारी प्रतिनिधित्व उत्पन्न करता है जिसे सीधे फ़ाइल में लिखा जा सकता है। यह सामान्यतः अंतर्निहित ऑब्जेक्ट मॉडल में प्रयुक्त किया जाता है, जैसे .नेट या कोको, जिसमें मानक फलन सम्मिलित होते हैं जो आंतरिक डेटा को टेक्स्ट फॉर्म में परिवर्तित करते हैं। कार्यक्रम इन विधियों को कॉल करके वस्तुओं के किसी भी समूह का एक पूर्ण पाठ प्रतिनिधित्व बना सकता है, जो लगभग हमेशा आधार साहचर्य सरणी वर्ग में प्रयुक्त होते हैं।[23] उन प्रोग्रामों के लिए जो बहुत बड़े डेटा सेट का उपयोग करते हैं, इस प्रकार का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है, और एक डेटाबेस प्रबंधन प्रणाली (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सरणियों को संग्रहीत करते हैं। व्यक्तिगत सरणियों को फिर से संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। ये की-वैल्यू डेटाबेस | की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है जब तक कि अधिक सामान्य संबंध का डेटाबेस (RDBs) के रूप में, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, कुछ विशिष्ट आला तक उनके उपयोग को सीमित कर दिया। भूमिकाएँ। ज्यादातर स्थितियों में इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था, हालांकि वस्तुओं को आरडीबी में सहेजना जटिल हो सकता है, एक समस्या जिसे वस्तु-संबंधपरक प्रतिबाधा बेमेल के रूप में जाना जाता है।
बाद c. 2010, क्लाउड कम्प्यूटिंग के लिए उपयुक्त उच्च-प्रदर्शन डेटाबेस की आवश्यकता और उनके उपयोग से कार्यक्रमों की आंतरिक संरचना से अधिक निकटता से मिलान करने से की-वैल्यू स्टोर बाजार में पुनर्जागरण हुआ। ये प्रणालियां मूल रूप से साहचर्य सरणियों को संग्रहीत और पुनः प्राप्त कर सकती हैं, जो सामान्य वेब-संबंधित वर्कफ़्लोज़ में प्रदर्शन में बहुत सुधार कर सकती हैं।
यह भी देखें
- की-वैल्यू डेटाबेस
- टपल
- समारोह (गणित)
- जेएसओएन
संदर्भ
- ↑ 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.
- ↑ 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.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.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.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.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
- ↑ Goodrich & Tamassia (2006), pp. 597–599.
- ↑ 8.0 8.1 Black, Paul E.; Stewart, Rob (2 November 2020). "dictionary". Dictionary of Algorithms and Data Structures. Retrieved 26 January 2022.
- ↑ Goodrich & Tamassia (2006), pp. 389–397.
- ↑ "When should I use a hash table instead of an association list?". lisp-faq/part2. 1996-02-20.
- ↑ Klammer, F.; Mazzolini, L. (2006), "Pathfinders for associative maps", Ext. Abstracts GIS-l 2006, GIS-I, pp. 71–74.
- ↑ 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."
- ↑ 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.
- ↑ Probst, Mark (2010-04-30). "Linear vs Binary Search". Retrieved 2016-11-20.
- ↑ 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.
- ↑ "std::map". en.cppreference.com.
- ↑ "OrderedDictionary Class (System.Collections.Specialized)". MS Docs (in English).
- ↑ "LinkedHashMap".
- ↑ "collections — Container datatypes — Python 3.9.0a3 documentation". docs.python.org.
- ↑ "Dictionary<TKey, TValue> Class". MSDN.
- ↑ "System.Generics.Collections.TDictionary - RAD Studio API Documentation". docwiki.embarcadero.com (in English). Retrieved 2017-04-18.
- ↑ "Associative Arrays, the D programming language". Digital Mars.
- ↑ "Archives and Serializations Programming Guide", Apple Inc., 2012
बाहरी संबंध
