साहचर्य सरणी
कंप्यूटर विज्ञान में साहचर्य सारणी, मानचित्र, प्रतीक सारणी या शब्दकोश सार डेटा विधि है। जो मुख्यतः डेटा का संग्रह (सार डेटा प्रकार) जोडी के रूप में करता है | जैसे कि संग्रह में कुंजी, मान, जोड़े प्रत्येक संभावित कुंजी अधिकतम प्रतीत होती है। गणितीय रूप में साहचर्य सारणी एक फलन (गणित) है। जिसमें एक फलन का 'सीमित' डोमेन होता है।[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] इन वैकल्पिक संरचनाओं के लाभ एक साहचर्य सारणी के मूल से संचालन को संभालने की उनकी क्षमता से आते हैं। जैसे कि मैपिंग को ढूंढना, जिसकी कुंजी क्वेरी कुंजी के सबसे पास है। जब क्वेरी स्वयं मैपिंग के समूह में उपस्थित नहीं होती है।
तुलना
| अंतर्निहित डेटा संरचना | लुकअप या हटाना | प्रविष्टि | आदेश दिया | ||
|---|---|---|---|---|---|
| औसत | सबसे खराब स्थिति | औसत | सबसे खराब स्थिति | ||
| हैश सारणी | O(1) | O(n) | O(1) | O(n) | No |
| सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री | O(log n) | O(log n) | O(log n) | O(log n) | Yes |
| असंतुलित बाइनरी सर्च ट्री | O(log n) | O(n) | O(log n) | O(n) | Yes |
| की-वैल्यू पेयर का सीक्वेंशियल कंटेनर | O(n) | O(n) | O(1) | O(1) | No |
क्रमित शब्दकोश
शब्दकोश की मूल परिभाषा में आदेश अनिवार्य नहीं है। गणना के एक निश्चित क्रम की गारंटी के लिए साहचर्य सारणी के आदेशित संस्करण प्रायः उपयोग किए जाते हैं। आदेशित शब्दकोश की दो भावनाएँ हैं:
- छँटाई के द्वारा चाबियों के दिए गए समूह के लिए गणना का क्रम सदैव नियतात्मक होता है। यह एक प्रतिनिधि
<map>सी ++ का कंटेनर वृक्ष-आधारित कार्यान्वयन का स्थिति है।[16] - गणना का क्रम कुंजी-स्वतंत्र है और इसके अतिरिक्त सम्मिलन के क्रम पर आधारित है। यह .नेट फ्रेमवर्क, जावा के लिंक्ड हैशमैप (प्रोग्रामिंग लैंग्वेज) और पायथन (प्रोग्रामिंग लैंग्वेज) में ऑर्डर किए गए डिक्शनरी के स्थितियों में है।[17][18][19]
आदेशित शब्दकोशों के बाद की भावना अधिक सामान्य रूप से की जाती है। उन्हें एक सामान्य शब्दकोश के शीर्ष पर दोगुनी लिंक की गई सूची को ओवरले करके या वास्तविक डेटा को विरल (अक्रमित) सारणी से बाहर और एक घने सम्मिलन-आदेशित में ले जाकर एसोसिएशन सूची का उपयोग करके कार्यान्वित किया जा सकता है।
भाषा समर्थन
साहचर्य सारणियों को किसी जावा (प्रोग्रामिंग भाषा) में एक पैकेज के रूप में प्रयुक्त किया जा सकता है और कई भाषा प्रणालियाँ उन्हें अपने मानक पुस्तकालय के भाग के रूप में प्रदान करती हैं। कुछ भाषाओं में वे न केवल मानक प्रणाली में निर्मित होते हैं। किन्तु विशेष सिंटैक्स होते हैं। जो प्रायः सारणी-जैसी सबस्क्रिप्टिंग का उपयोग करते हैं।
साहचर्य सारणियों के लिए अंतर्निेहित सिंटैक्टिक समर्थन 1969 में स्नोबोल द्वारा नाम सारणी के अनुसार प्रस्तुत किया गया था। टीएमजी (भाषा) ने स्ट्रिंग कुंजियों और पूर्णांक मानों के साथ सारणियों को प्रस्तुत किया। एमयूएमपीएस ने बहु-आयामी साहचर्य सारणियाँ बनाईं। वैकल्पिक रूप से लगातार इसकी प्रमुख डेटा संरचना एसईटीएल ने उन्हें समूह और मैप्स के संभावित कार्यान्वयन के रूप में समर्थन दिया। एडब्लूके से प्रारम्भ होने वाली और रेक्स, पर्ल, पीएचपी, टीसीएल, जावास्क्रिप्ट, मेपल , पायथन (प्रोग्रामिंग लैंग्वेज), रूबी (प्रोग्रामिंग लैंग्वेज), वूल्फ्रेम लैंग्वेज, गो (प्रोग्रामिंग लैंग्वेज) और लुआ (प्रोग्रामिंग) सहित अधिकांश आधुनिक स्क्रिप्टिंग भाषाएँ (भाषा) प्राथमिक कंटेनर प्रकार के रूप में साहचर्य सारणियों का समर्थन करता है। कई और भाषाओं में वे विशेष सिंटैक्स के बिना पुस्तकालय कार्यों के रूप में उपलब्ध हैं।
स्मॉलटॉक में ऑब्जेक्टिव-सी, .नेट फ्रेमवर्क .नेट,[20] पायथन (प्रोग्रामिंग लैंग्वेज), असली मूलभूत, स्विफ्ट (प्रोग्रामिंग भाषा), एप्लिकेशन और डेल्फी के लिए विजुअल बेसिक (प्रोग्रामिंग लैंग्वेज)[21] उन्हें शब्दकोश कहा जाता है। पर्ल, रूबी (प्रोग्रामिंग भाषा) और बीज-7 में उन्हें हैश कहा जाता है। सी++, जावा (प्रोग्रामिंग लैंग्वेज), गो (प्रोग्रामिंग लैंग्वेज), क्लोजर, स्काला (प्रोग्रामिंग भाषा), ओकाम, हैशकेल (प्रोग्रामिंग लैंग्वेज) में उन्हें मैप्स कहा जाता है। सामान्य लिस्प और विंडोज पॉवरशेल में उन्हें हैश सारणी कहा जाता है। चूंकि दोनों इस कार्यान्वयन का उपयोग करते हैं। मेपल (सॉफ्टवेयर) और लुआ में उन्हें सारणी कहा जाता है। पीएचपी में सभी सारणियाँ साहचर्य हो सकती हैं। इसके लिये कुंजियाँ पूर्णांकों और स्ट्रिंग्स तक सीमित हैं। जावास्क्रिप्ट में सभी ऑब्जेक्ट स्ट्रिंग-वैल्यू कुंजियों के साथ साहचर्य सारणियों के रूप में व्यवहार करते हैं। जबकि मानचित्र और वीकमैप विधि वस्तुओं को कुंजियों के रूप में लेते हैं। लुआ में वे सभी डेटा संरचनाओं के लिए प्रथम बिल्डिंग ब्लॉक के रूप में उपयोग किए जाते हैं। विजुअल फॉक्सप्रो में उन्हें संग्रह कहा जाता है। D (प्रोग्रामिंग लैंग्वेज) में साहचर्य सारणियों के लिए भी समर्थन है।[22]
स्थायी भंडारण
साहचर्य सारणियों का उपयोग करने वाले कई कार्यक्रमों को किसी बिंदु पर उस डेटा को अधिक स्थायी रूप में संग्रहीत करने की आवश्यकता होगी। जैसे कम्प्यूटर फाइल के रूप में। इस समस्या का सामान्य समाधान एक सामान्यीकृत अवधारणा है। जिसे संग्रह या क्रमांकन के रूप में जाना जाता है। जो मूल वस्तुओं का पाठ या द्विआधारी प्रतिनिधित्व उत्पन्न करता है। जिसे सीधे फ़ाइल में लिखा जा सकता है। यह सामान्यतः अंतर्निहित ऑब्जेक्ट मॉडल में प्रयुक्त किया जाता है। जैसे .नेट या कोको, जिसमें मानक फलन सम्मिलित होते हैं। जो आंतरिक डेटा को टेक्स्ट फॉर्म में परिवर्तित करते हैं। कार्यक्रम इन विधियों को कॉल करके वस्तुओं के किसी भी समूह का एक पूर्ण पाठ प्रतिनिधित्व बना सकता है। जो लगभग सदैव आधार साहचर्य सारणी वर्ग में प्रयुक्त होते हैं।[23] उन प्रोग्रामों के लिए जो बहुत बड़े डेटा समूह का उपयोग करते हैं। इस विधि का व्यक्तिगत फ़ाइल संग्रहण उचित नहीं है और एक डेटाबेस प्रबंधन प्रणाली (डीबी) की आवश्यकता होती है। कुछ डीबी सिस्टम मूल रूप से डेटा को क्रमबद्ध करके और उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके साहचर्य सारणियों को संग्रहीत करते हैं। व्यक्तिगत सारणियों को पुनः संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सुरक्षित किया जा सकता है। ये की-वैल्यू डेटाबेस की-वैल्यू स्टोर्स का उपयोग कई वर्षों से किया जा रहा है और इनका एक इतिहास है। जब तक कि अधिक सामान्य संबंध का डेटाबेस (आरडीबीएस) के रूप में, किन्तु मानकीकरण की कमी, अन्य कारणों के साथ कुछ विशिष्ट स्थानों तक उनके उपयोग को सीमित कर दिया। इन भूमिकाओं के लिए आरडीबी का उपयोग किया गया था। चूंकि वस्तुओं को आरडीबी में बनाये रखने में जटिलता हो सकती है। यह एक समस्या है। जिसे वस्तु-संबंधपरक प्रतिबाधा बेमेल के रूप में जाना जाता है।
क्लाउड कम्प्यूटिंग के लिए उपयुक्त उच्च-प्रदर्शन डेटाबेस की आवश्यकता और उनके उपयोग से कार्यक्रमों की आंतरिक संरचना से अधिक निकटता से मिलान करने से की-वैल्यू स्टोर बाजार में पुनर्जागरण हुआ। ये प्रणालियां मूल रूप से साहचर्य सारणियों को संग्रहीत और पुनः प्राप्त कर सकती है। जो सामान्य वेब-संबंधित वर्कफ़्लोज़ में प्रदर्शन में बहुत सुधार कर सकती हैं।
यह भी देखें
- की-वैल्यू डेटाबेस
- टपल
- फलन (गणित)
- जेएसओएन
संदर्भ
- ↑ 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
बाहरी संबंध
