साहचर्य सरणी: Difference between revisions
No edit summary |
No edit summary |
||
| Line 70: | Line 70: | ||
=== हैश सारणी कार्यान्वयन === | === हैश सारणी कार्यान्वयन === | ||
{{main |हैश टेबल}} | {{main |हैश टेबल}} | ||
[[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> अलग-अलग श्रंखला में सरणी स्वयं मान को संग्रहीत नहीं करती है। किन्तु एक [[सूचक (कंप्यूटर प्रोग्रामिंग)]] को दूसरे कंटेनर में संग्रहीत करती है। सामान्यतः एक एसोसिएशन सूची, जो हैश से मिलान होने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर खुले पते में यदि कोई हैश टकराव पाया जाता है। तो सामान्यतः सरणी में अगलली स्थिति को देखते हुए सारणी एक नियतात्मक प्रकार से मूल्य को संग्रहीत करने के लिए एक सरणी में एक रिक्त स्थान की खोज करती है। | ||
ओपन एड्रेसिंग में अलग-अलग चेनिंग की तुलना में [[कैश मिस]] अनुपात कम होता | ओपन एड्रेसिंग में अलग-अलग चेनिंग की तुलना में [[कैश मिस]] अनुपात कम होता है। जब सारणी प्रायः खाली होती है। चूंकि जैसे ही सारणी अधिक तत्वों से भर जाती है। वैसे ही खुले पते का प्रदर्शन तेजी से घटता है। इसके अतिरिक्त प्रायः स्थितियों में अलग-अलग श्रृखंला कम मेमोरी का उपयोग करती है। जब तक कि प्रविष्टियां बहुत छोटी न हों (एक सूचक के आकार के चार गुना से कम)। | ||
=== वृक्ष कार्यान्वयन === | === वृक्ष कार्यान्वयन === | ||
{{main | | {{main |खोज पेड़}} | ||
==== सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री ==== | ==== सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री ==== | ||
अन्य सामान्य दृष्टिकोण [[स्व-संतुलन बाइनरी सर्च ट्री]] के साथ साहचर्य सरणी को प्रयुक्त करना है। जैसे कि [[एवीएल का पेड़]] या रेड-ब्लैक ट्री।<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 87: | Line 87: | ||
"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) के सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में उत्तम औसत-केस टाइम जटिलता है और जब एक अच्छे हैश फलन का उपयोग किया जाता है। तो उनका सबसे खराब प्रदर्शन बहुत कम होता है। | ||
हैश सारणी की तुलना में | |||
यह ध्यान देने योग्य है कि एक हैश सारणी के लिए बकेट को प्रयुक्त करने के लिए एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जा सकता | यह ध्यान देने योग्य है कि एक हैश सारणी के लिए बकेट को प्रयुक्त करने के लिए एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जा सकता है। जो अलग-अलग चेनिंग का उपयोग करता है। यह औसत-केस निरंतर लुकअप की अनुमति देता है। किन्तु O(n) के सबसे खराब-केस प्रदर्शन का आश्वासन देता है। चूंकि यह कार्यान्वयन में अतिरिक्त जटिलता का परिचय देता है और छोटे हैश सारणियों के लिए और भी खराब प्रदर्शन का कारण बन सकता है। जहां पेड़ को सम्मिलित करने और संतुलित करने में लगने वाला समय लिंक की गई सूची के सभी तत्वों पर एक [[रैखिक खोज]] करने के लिए आवश्यक समय से अधिक है।<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>{{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 157: | Line 156: | ||
{{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 10:01, 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() एक नया खाली साहचर्य सरणी बनाता है।
उदाहरण
माना कि एक पुस्तकालय द्वारा किए गए ऋणों के समूह को डेटा संरचना में दर्शाया गया है। एक पुस्तकालय में प्रत्येक पुस्तक को एक समय में केवल एक ही पुस्तकालय संरक्षक द्वारा चेक आउट किया जा सकता है। चूंकि एक संरक्षक कई पुस्तकों की जाँच करने में सक्षम हो सकता है। इसलिए कौन कौन सी पुस्तकों के बारे में जानकारी की जाँच की जाती है। जिसके लिए संरक्षक एक साहचर्य सरणी द्वारा दर्शाए जा सकते हैं। जिसमें पुस्तकें कुंजी हैं और संरक्षक मूल्य हैं। पायथन (प्रोग्रामिंग लैंग्वेज) या जेएसओएन से संकेतन का उपयोग करते हुए डेटा संरचना होगी।
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
प्रमुख ग्रेट एक्सपेक्टेशंस पर एक लुकअप संचालन जॉन को वापस करेगा। यदि जॉन अपनी पुस्तक लौटाता है। तो यह कार्रवाई को हटाने का कारण बनेगा और यदि पैट एक पुस्तक की जांच करता है। तो यह एक सम्मिलन कार्रवाई का कारण बनेगा। जिससे एक अलग स्थिति होगी:
{
"Pride and Prejudice": "Alice",
"The Brothers Karamazov": "Pat",
"Wuthering Heights": "Alice"
}
कार्यान्वयन
मैपिंग की बहुत कम संख्या वाले शब्दकोशों के लिए संघ सूची मैपिंग की एक लिंक्ड सूची का उपयोग करके शब्दकोश को प्रयुक्त करना आ सकता है। इस कार्यान्वयन के साथ मूलभूत शब्दकोश संचालन करने का समय मैपिंग की कुल संख्या में रैखिक है। चूंकि इसे प्रयुक्त करना सरल है और इसके चलने के समय में स्थिर कारक छोटे हैं।[3][10] एक अन्य बहुत ही सरल कार्यान्वयन तन्त्र, जब कुंजियों को एक संकीर्ण सीमा तक सीमित किया जाता है। तो एक सरणी में सीधे संबोधित किया जाता है। किसी दिए गए कुंजी k के मान को सरणी सेल A [k] में संग्रहीत किया जाता है या यदि k के लिए कोई मैपिंग नहीं है। तब सेल एक विशेष प्रहरी मान संग्रहीत करता है। जो मैपिंग की अनुपस्थिति को निर्देशित करता है। सरल होने के साथ-साथ यह तन्त्र तेज है। प्रत्येक शब्दकोश संक्रिया में निरंतर समय लगता है। चूंकि इस संरचना के लिए स्थान की आवश्यकता पूरे की-स्पेस का आकार है। जब तक कि की-स्पेस छोटा न हो। यह अव्यावहारिक है।[5]
शब्दकोशों को प्रयुक्त करने के दो प्रमुख प्रकार हैश सारणी या सर्च ट्री हैं।[3][4][5][6]
हैश सारणी कार्यान्वयन
साहचर्य सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन हैश सारणी के साथ होता है। हैश फलन के साथ संयुक्त एक सरणी डेटा संरचना, जो प्रत्येक कुंजी को सरणी की अलग रिक्त स्थानों में अलग करती है। हैश सारणी के पीछे मूल विचार यह है कि किसी सरणी के किसी तत्व को उसके सूचकांक के माध्यम से एक्सेस करना सरल, निरंतर-समय का संचालन है। इसलिए हैश सारणी के लिए एक संचालन का औसत ओवरहेड केवल कुंजी के हैश की गणना है। जो सरणी के अन्दर संबंधित बकेट तक पहुंचने के साथ संयुक्त है। जैसे हैश सारणी सामान्यतः ओ (1) समय में प्रदर्शन करते हैं और अधिकांश स्थितियों में अच्छा प्रदर्शन करते हैं।
हैश सारणी को हैश टकराव से संभालने में सक्षम होना चाहिए। जब हैश फलन दो अलग-अलग कुंजियों को सरणी की एक ही बाल्टी में मैप करता है। इस समस्या के दो सबसे व्यापक दृष्टिकोण अलग-अलग चेनिंग और खुला संबोधन हैं।[3][4][5][11] अलग-अलग श्रंखला में सरणी स्वयं मान को संग्रहीत नहीं करती है। किन्तु एक सूचक (कंप्यूटर प्रोग्रामिंग) को दूसरे कंटेनर में संग्रहीत करती है। सामान्यतः एक एसोसिएशन सूची, जो हैश से मिलान होने वाले सभी मानों को संग्रहीत करती है। दूसरी ओर खुले पते में यदि कोई हैश टकराव पाया जाता है। तो सामान्यतः सरणी में अगलली स्थिति को देखते हुए सारणी एक नियतात्मक प्रकार से मूल्य को संग्रहीत करने के लिए एक सरणी में एक रिक्त स्थान की खोज करती है।
ओपन एड्रेसिंग में अलग-अलग चेनिंग की तुलना में कैश मिस अनुपात कम होता है। जब सारणी प्रायः खाली होती है। चूंकि जैसे ही सारणी अधिक तत्वों से भर जाती है। वैसे ही खुले पते का प्रदर्शन तेजी से घटता है। इसके अतिरिक्त प्रायः स्थितियों में अलग-अलग श्रृखंला कम मेमोरी का उपयोग करती है। जब तक कि प्रविष्टियां बहुत छोटी न हों (एक सूचक के आकार के चार गुना से कम)।
वृक्ष कार्यान्वयन
सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री
अन्य सामान्य दृष्टिकोण स्व-संतुलन बाइनरी सर्च ट्री के साथ साहचर्य सरणी को प्रयुक्त करना है। जैसे कि एवीएल का पेड़ या रेड-ब्लैक ट्री।[12] हैश सारणी की तुलना में इन संरचनाओं के लाभ और कमजोरियां दोनों हैं। सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का सबसे खराब प्रदर्शन हैश सारणी की तुलना में अधिक उत्तम है। O(n) के बिग ओ नोटेशन में समय की जटिलता के साथ यह हैश सारणी के विपरीत है। जिसके सबसे खराब प्रदर्शन में सभी तत्व एक ही बकेट साझा करते हैं। जिसके परिणामस्वरूप O(n) समय जटिलता होती है। इसके अतिरिक्त और सभी बाइनरी सर्च ट्री प्रकार सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री अपने तत्वों को क्रम में रखते हैं। इस प्रकार इसके तत्वों को कम से कम से अधिकतम पैटर्न का पालन करना। जबकि एक हैश सारणी को घुमाने के परिणामस्वरूप तत्वों को यादृच्छिक क्रम में हो सकता है क्योंकि वे इन-ऑर्डर हैं। वृक्ष-आधारित मानचित्र श्रेणी के प्रश्नों को भी संतुष्ट कर सकते हैं (दो सीमाओं के बीच सभी मान प्राप्त करें) जबकि एक हैशपैप केवल त्रुटिहीन मान प्राप्त कर सकता है। चूंकि हैश सारणी में O(1) के सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री की तुलना में उत्तम औसत-केस टाइम जटिलता है और जब एक अच्छे हैश फलन का उपयोग किया जाता है। तो उनका सबसे खराब प्रदर्शन बहुत कम होता है।
यह ध्यान देने योग्य है कि एक हैश सारणी के लिए बकेट को प्रयुक्त करने के लिए एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जा सकता है। जो अलग-अलग चेनिंग का उपयोग करता है। यह औसत-केस निरंतर लुकअप की अनुमति देता है। किन्तु O(n) के सबसे खराब-केस प्रदर्शन का आश्वासन देता है। चूंकि यह कार्यान्वयन में अतिरिक्त जटिलता का परिचय देता है और छोटे हैश सारणियों के लिए और भी खराब प्रदर्शन का कारण बन सकता है। जहां पेड़ को सम्मिलित करने और संतुलित करने में लगने वाला समय लिंक की गई सूची के सभी तत्वों पर एक रैखिक खोज करने के लिए आवश्यक समय से अधिक है।[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
बाहरी संबंध
