Associative array
कंप्यूटर विज्ञान में, एक सहयोगी सरणी, मानचित्र, प्रतीक तालिका या शब्दकोश एक अमूर्त डेटा प्रकार है जो (कुंजी, मूल्य) जोड़े के संग्रह को संग्रहीत करता है, जैसे कि प्रत्येक संभावित कुंजी संग्रह में अधिक से अधिक एक बार दिखाई देती है। गणितीय शब्दों में, एक सहयोगी सरणी परिमित क्षेत्र के साथ एक फलन है। यह 'लुकअप', 'रिमूव' और 'इन्सर्ट' संचालन का समर्थन करता है। शब्दकोश समस्या कुशल डेटा संरचनाओं को डिजाइन करने की क्लासिक समस्या है जो सहयोगी सरणियों को लागू करती है। शब्दकोश समस्या के दो प्रमुख समाधान हैश टेबल और सर्च ट्री हैं। कभी-कभी सीधे संबोधित सरणियों, द्विआधारी खोज पेड़ों, या अन्य अधिक विशेष संरचनाओं का उपयोग करके समस्या को हल करना भी संभव है। कई प्रोग्रामिंग भाषाओं में आदिम डेटा प्रकारों के रूप में सहयोगी सरणियाँ शामिल हैं, जबकि कई अन्य भाषाएँ सॉफ्टवेयर पुस्तकालय प्रदान करती हैं जो सहयोगी श्रेणियों का समर्थन करती हैं। सामग्री-पता करने योग्य स्मृति सहयोगी सरणियों के लिए प्रत्यक्ष हार्डवेयर-स्तर समर्थन का एक रूप है। सहयोगी सरणियों में कई अनुप्रयोग होते हैं जिनमें ज्ञापन और सज्जाकार पैटर्न जैसे मौलिक प्रोग्रामिंग पैटर्न शामिल हैं। यह नाम गणित में ज्ञात सहयोगी गुण से नहीं आया है। बल्कि, यह कुंजी के साथ मूल्यों के जुड़ाव से उत्पन्न होता है। इसे सहयोगी प्रोसेसर के साथ भ्रमित नहीं होना चाहिए। एक सहयोगी सरणी में, एक कुंजी और एक मूल्य के बीच संबंध को अक्सर "मानचित्रण" के रूप में जाना जाता है; एक ही शब्द का उपयोग एक नया संबंध बनाने की प्रक्रिया को संदर्भित करने के लिए भी किया जा सकता है। आमतौर पर एक सहयोगी सरणी के लिए परिभाषित किए जाने वाले संचालन हैंः सम्मिलित करें या डालेंः संग्रह में एक नई जोड़ी जोड़ें, अपने नए मूल्य के लिए कुंजी का मानचित्रण करें। किसी भी मौजूदा मानचित्रण को अधिलेखित किया जाता है। इस ऑपरेशन के तर्क कुंजी और मूल्य हैं। हटाएँ या हटाएँः संग्रह से एक जोड़ी को हटा दें, किसी दिए गए कुंजी को उसके मूल्य से अनमैप करें। इस ऑपरेशन का तर्क महत्वपूर्ण है। ढूँढें, खोजें या प्राप्त करें-उस मूल्य (यदि कोई हो) को ढूंढें जो किसी दिए गए कुंजी से बंधा हो। इस ऑपरेशन के लिए तर्क कुंजी है, और ऑपरेशन से मूल्य वापस आ जाता है। यदि कोई मूल्य नहीं मिलता है, तो कुछ खोज कार्य एक अपवाद को बढ़ाते हैं, जबकि अन्य एक डिफ़ॉल्ट मूल्य (जैसे शून्य, शून्य, या निर्माता को पारित एक विशिष्ट मूल्य) लौटाते हैं। सहयोगी सरणियों में अन्य संचालन भी शामिल हो सकते हैं जैसे कि मानचित्रण की संख्या निर्धारित करना या सभी मानचित्रणों पर लूप करने के लिए एक पुनरावृत्ति का निर्माण करना। इस तरह के संचालन के लिए, जिस क्रम में मानचित्रण वापस किए जाते हैं, वह आमतौर पर कार्यान्वयन-परिभाषित होता है। एक मल्टीमैप एक एकल कुंजी के साथ कई मूल्यों को संबद्ध करने की अनुमति देकर एक सहयोगी सरणी को सामान्यीकृत करता है। एक द्विदिश मानचित्र एक संबंधित अमूर्त डेटा प्रकार है जिसमें मानचित्रण दोनों दिशाओं में काम करते हैंः प्रत्येक मूल्य एक अद्वितीय कुंजी के साथ जुड़ा होना चाहिए, और एक दूसरा खोज संचालन एक तर्क के रूप में एक मूल्य लेता है और उस मूल्य से जुड़ी कुंजी को देखता है। गुण सहयोगी सरणी के संचालन को विभिन्न गुणों को संतुष्ट करना चाहिएः लुकअप (के, इन्सर्ट (जे, वी, डी)) = यदि के = = जे तो अन्य लुकअप (के, डी) लुकअप (के, नया ()) = विफल, जहां फेल एक अपवाद या डिफ़ॉल्ट मान है रिमूव (के, इन्सर्ट (जे, वी, डी)) = यदि के = = जे तो हटा दें (के, डी) अन्यथा इन्सर्ट (जे, वी, रिमूव (के, डी)) हटा दें (के, नया () = नया () जहां के और जे कुंजी हैं, वी एक मूल्य है, डी एक सहयोगी सरणी है, और नया () एक नया, खाली सहयोगी सरणी बनाता है। उदाहरण मान लीजिए कि एक पुस्तकालय द्वारा दिए गए ऋणों का समूह एक डेटा संरचना में दर्शाया गया है। पुस्तकालय में प्रत्येक पुस्तक को एक बार में केवल एक ही पुस्तकालय संरक्षक द्वारा देखा जा सकता है। हालाँकि, एक एकल संरक्षक कई पुस्तकों को देखने में सक्षम हो सकता है। इसलिए, किन पुस्तकों के बारे में जानकारी की जाँच की जाती है कि किन संरक्षकों को एक सहयोगी सरणी द्वारा दर्शाया जा सकता है, जिसमें पुस्तकें कुंजी हैं और संरक्षक मूल्य हैं। पायथन या जे. एस. ओ. एन. से संकेतन का उपयोग करते हुए, डेटा संरचना होगीः {"प्राइड एंड प्रेजुडिस": "एलिस", "वुथरिंग हाइट्स": "एलिस", "ग्रेट एक्सपेक्टेशंस": "जॉन"} कुंजी "ग्रेट एक्सपेक्टेशंस" पर एक लुकअप ऑपरेशन "जॉन" वापस करेगा। यदि जॉन अपनी पुस्तक लौटाता है, तो यह एक विलोपन ऑपरेशन का कारण बन सकता है, और यदि पैट एक पुस्तक की जांच करता है, जो एक सम्मिलन ऑपरेशन का कारण बन सकती है, जिससे एक अलग स्थिति हो सकती हैः {"प्राइड एंड प्रेजुडिस": "एलिस", "द ब्रदर्स करामाज़ोव": "पैट", "वुथरिंग हाइट्स": "एलिस"} कार्यान्वयन बहुत कम मानचित्रण वाले शब्दकोशों के लिए, एक संघ सूची, मानचित्रण की एक जुड़ी सूची का उपयोग करके शब्दकोश को लागू करना समझदारी हो सकती है। इस कार्यान्वयन के साथ, मूल शब्दकोश संचालन करने का समय मानचित्रण की कुल संख्या में रैखिक है; हालाँकि, इसे लागू करना आसान है और इसके चलने के समय में स्थिर कारक कम हैं। एक अन्य बहुत ही सरल कार्यान्वयन तकनीक, जब कुंजी एक संकीर्ण सीमा तक सीमित होती है, तो उपयोग करने योग्य होती है, एक सरणी में सीधे संबोधित करनाः किसी दिए गए कुंजी के लिए मान सरणी कक्ष ए [के] में संग्रहीत किया जाता है, या यदि के के लिए कोई मानचित्रण नहीं है तो कक्ष एक विशेष प्रहरी मूल्य संग्रहीत करता है जो एक मानचित्रण की कमी को इंगित करता है। यह तकनीक सरल और तेज़ है, जिसमें प्रत्येक शब्दकोश संचालन में लगातार समय लगता है। हालाँकि, इस संरचना के लिए स्थान की आवश्यकता पूरे कीस्पेस का आकार है, जिससे यह अव्यावहारिक हो जाता है जब तक कि कीस्पेस छोटा न हो। शब्दकोशों को लागू करने के दो प्रमुख तरीके हैश टेबल या सर्च ट्री हैं। हैश टेबल कार्यान्वयन एक सहयोगी सरणी का सबसे अधिक उपयोग किया जाने वाला सामान्य-उद्देश्य कार्यान्वयन हैश टेबल के साथ होता हैः हैश फ़ंक्शन के साथ संयुक्त एक सरणी जो प्रत्येक कुंजी को सरणी की एक अलग "बाल्टी" में अलग करती है। हैश टेबल के पीछे मूल विचार यह है कि एक सरणी के एक तत्व को उसके सूचकांक के माध्यम से प्राप्त करना एक सरल, निरंतर-समय संचालन है। इसलिए, हैश टेबल के लिए एक ऑपरेशन का औसत ओवरहेड केवल कुंजी के हैश की गणना है, जो सरणी के भीतर संबंधित बाल्टी तक पहुंचने के साथ संयुक्त है। जैसे, हैश टेबल आमतौर पर ओ (1) समय में प्रदर्शन करते हैं, और आमतौर पर वैकल्पिक कार्यान्वयन से बेहतर प्रदर्शन करते हैं। हैश टेबल टकराव को संभालने में सक्षम होना चाहिएः सरणी की एक ही बाल्टी में दो अलग-अलग कुंजियों के हैश फ़ंक्शन द्वारा मानचित्रण। इस समस्या के लिए दो सबसे व्यापक दृष्टिकोण अलग-अलग चेन और ओपन एड्रेसिंग हैं। अलग-अलग श्रृंखला में, सरणी स्वयं मूल्य को संग्रहीत नहीं करती है, लेकिन एक सूचक को दूसरे पात्र में संग्रहीत करती है, आमतौर पर एक संघ सूची, जो हैश से मेल खाने वाले सभी मूल्यों को संग्रहीत करती है। इसके विपरीत, खुले पते में, यदि एक हैश टक्कर पाई जाती है, तो तालिका एक निर्धारित तरीके से मूल्य को संग्रहीत करने के लिए एक सरणी में एक खाली स्थान की तलाश करती है, आमतौर पर सरणी में अगली तत्काल स्थिति को देखकर। जब मेज ज्यादातर खाली होती है तो खुले पते में अलग-अलग श्रृंखला की तुलना में कैश मिस अनुपात कम होता है। हालाँकि, जैसे-जैसे टेबल अधिक तत्वों से भर जाता है, खुले संबोधन का प्रदर्शन तेजी से कम हो जाता है। इसके अतिरिक्त, अलग-अलग श्रृंखला ज्यादातर मामलों में कम स्मृति का उपयोग करती है, जब तक कि प्रविष्टियाँ बहुत छोटी न हों (एक सूचक के आकार से चार गुना से कम)। वृक्ष कार्यान्वयन स्व-संतुलित द्विआधारी खोज वृक्ष एक अन्य सामान्य दृष्टिकोण स्व-संतुलित द्विआधारी खोज वृक्ष के साथ एक सहयोगी सरणी को लागू करना है, जैसे कि ए. वी. एल. वृक्ष या लाल-काला वृक्ष। हैश टेबल की तुलना में, इन संरचनाओं में ताकत और कमजोरी दोनों हैं। ओ (लॉग एन) के बड़े ओ संकेतन में समय जटिलता के साथ, आत्म-संतुलन द्विआधारी खोज पेड़ों का सबसे खराब स्थिति प्रदर्शन हैश टेबल की तुलना में काफी बेहतर है। यह हैश टेबल के विपरीत है, जिसके सबसे खराब प्रदर्शन में सभी तत्व एक बाल्टी साझा करते हैं, जिसके परिणामस्वरूप ओ (एन) समय जटिलता होती है। इसके अलावा, और सभी द्विआधारी खोज पेड़ों की तरह, आत्म-संतुलन द्विआधारी खोज पेड़ अपने तत्वों को क्रम में रखते हैं। इस प्रकार, इसके तत्वों को पार करना कम से कम सबसे बड़े पैटर्न का अनुसरण करता है, जबकि हैश टेबल को पार करने के परिणामस्वरूप तत्व यादृच्छिक क्रम में प्रतीत हो सकते हैं। क्योंकि वे क्रम में हैं, वृक्ष-आधारित मानचित्र भी सीमा प्रश्नों को संतुष्ट कर सकते हैं (दो सीमाओं के बीच सभी मूल्यों का पता लगा सकते हैं) जबकि एक हैशमैप केवल सटीक मूल्यों का पता लगा सकता है। हालांकि, हैश टेबल में ओ (1) के स्व-संतुलन द्विआधारी खोज पेड़ों की तुलना में बहुत बेहतर औसत-केस समय जटिलता होती है, और जब एक अच्छे हैश फ़ंक्शन का उपयोग किया जाता है तो उनके सबसे खराब स्थिति प्रदर्शन की संभावना बहुत कम होती है। यह ध्यान देने योग्य है कि एक हैश टेबल के लिए बाल्टियों को लागू करने के लिए एक स्व-संतुलित द्विआधारी खोज वृक्ष का उपयोग किया जा सकता है जो अलग-अलग श्रृंखला का उपयोग करता है। यह औसत-मामले की निरंतर खोज की अनुमति देता है, लेकिन ओ (लॉग एन) के सबसे खराब स्थिति प्रदर्शन का आश्वासन देता है। हालांकि, यह कार्यान्वयन में अतिरिक्त जटिलता का परिचय देता है और छोटे हैश टेबल के लिए और भी खराब प्रदर्शन का कारण बन सकता है, जहां पेड़ को डालने और संतुलित करने में बिताया गया समय एक जुड़ी सूची या समान डेटा संरचना के सभी तत्वों पर एक रैखिक खोज करने के लिए आवश्यक समय से अधिक है। अन्य ट्रीज़ एसोसिएटिव ऐरेज़ को असंतुलित द्विआधारी खोज ट्रीज़ में या किसी विशेष प्रकार की कुंजी जैसे रेडिक्स ट्रीज़, ट्राइज़, जूडी ऐरेज़ या वैन एम्डे बोस ट्रीज़ के लिए विशिष्ट डेटा संरचनाओं में भी संग्रहीत किया जा सकता है, हालांकि इन कार्यान्वयनों का सापेक्ष प्रदर्शन भिन्न होता है। उदाहरण के लिए, जूडी ट्री को हैश टेबल की तुलना में कम कुशलता से प्रदर्शन करने के लिए संकेत दिया जाता है, जबकि सावधानीपूर्वक चयनित हैश टेबल आम तौर पर अनुकूली रेडिक्स ट्री की तुलना में अधिक कुशलता से प्रदर्शन करते हैं, जिसमें संभावित रूप से डेटा प्रकारों पर अधिक प्रतिबंध होते हैं जिन्हें वे संभाल सकते हैं। इन वैकल्पिक संरचनाओं के फायदे अतिरिक्त सहयोगी सरणी संचालन को संभालने की उनकी क्षमता से आते हैं, जैसे कि मानचित्रण का पता लगाना जिसकी कुंजी एक पूछताछ की गई कुंजी के सबसे करीब है जब प्रश्न मानचित्रण के सेट में अनुपस्थित है। एक शब्दकोश की मूल परिभाषा एक क्रम को अनिवार्य नहीं करती है। गणना के एक निश्चित क्रम की गारंटी के लिए, सहयोगी सरणी के क्रमबद्ध संस्करणों का अक्सर उपयोग किया जाता है। एक क्रमबद्ध शब्दकोश की दो इंद्रियां होती हैंः गणना का क्रम हमेशा श्रेणिबद्ध करके कुंजी के दिए गए समूह के लिए निर्धारक होता है। यह वृक्ष-आधारित कार्यान्वयन के लिए मामला है, एक प्रतिनिधि सी + + का पात्र है। गणना का क्रम प्रमुख-स्वतंत्र है और इसके बजाय सम्मिलन के क्रम पर आधारित है। यह. NET फ्रेमवर्क, जावा और पायथन के लिंक्डइनहैशमैप में "ऑर्डर किए गए शब्दकोश" का मामला है। बाद वाला अधिक आम है। इस तरह के आदेशित शब्दकोशों को एक संघ सूची का उपयोग करके, एक सामान्य शब्दकोश के शीर्ष पर एक दोगुनी जुड़ी सूची को ओवरले करके, या वास्तविक डेटा को विरल (अनियमित) सरणी से बाहर निकालकर और एक घने सम्मिलन-आदेशित में लागू किया जा सकता है। भाषा समर्थन सहयोगी सरणियों को किसी भी प्रोग्रामिंग भाषा में एक पैकेज के रूप में लागू किया जा सकता है और कई भाषा प्रणालियाँ उन्हें अपने मानक पुस्तकालय के हिस्से के रूप में प्रदान करती हैं। कुछ भाषाओं में, वे न केवल मानक प्रणाली में निर्मित होते हैं, बल्कि विशेष वाक्यविन्यास होते हैं, जो अक्सर सरणी जैसी सदस्यता का उपयोग करते हैं। सहयोगी सरणियों के लिए अंतर्निहित वाक्य रचना समर्थन 1969 में एस. एन. ओ. बी. ओ. एल. 4 द्वारा "टेबल" नाम के तहत पेश किया गया था। टी. एम. जी. ने स्ट्रिंग कुंजियों और पूर्णांक मूल्यों के साथ तालिकाओं की पेशकश की। एम. यू. एम. पी. एस. ने बहु-आयामी सहयोगी सरणियों को बनाया, वैकल्पिक रूप से लगातार, इसकी प्रमुख डेटा संरचना। एस. ई. टी. एल. ने सेट और मानचित्रों के एक संभावित कार्यान्वयन के रूप में उनका समर्थन किया। ए. डब्ल्यू. के. से शुरू होने वाली और रेक्स, पर्ल, पी. एच. पी., टी. सी. एल., जावास्क्रिप्ट, मेपल, पायथन, रूबी, वोल्फ्राम लैंग्वेज, गो और लुआ सहित अधिकांश आधुनिक स्क्रिप्टिंग भाषाएँ प्राथमिक कंटेनर प्रकार के रूप में सहयोगी सरणियों का समर्थन करती हैं। कई और भाषाओं में, वे विशेष वाक्यविन्यास के बिना पुस्तकालय कार्यों के रूप में उपलब्ध हैं। स्मॉलटॉक, ऑब्जेक्टिव-सी,. नेट, पायथन, रियलबेसिक, स्विफ्ट, वीबीए और डेल्फी में उन्हें शब्दकोश कहा जाता है; पर्ल, रूबी और सीड 7 में उन्हें हैश कहा जाता है; सी + +, जावा, गो, क्लोजर, स्काला, ओसीएएमएल, हास्केल में उन्हें मानचित्र कहा जाता है (मानचित्र (सी + +), अनऑर्डर्ड _ मैप (सी + +), और देखें); कॉमन लिस्प और विंडोज पावरशेल में, उन्हें हैश टेबल कहा जाता है (क्योंकि दोनों आमतौर पर इस कार्यान्वयन का उपयोग करते हैं); मेपल और लुआ में, उन्हें टेबल कहा जाता है। पी. एच. पी. में, सभी सरणियाँ सहयोगी हो सकती हैं, सिवाय इसके कि कुंजी पूर्णांक और स्ट्रिंग तक सीमित हैं। जावास्क्रिप्ट में (जे. एस. ओ. एन. भी देखें), सभी वस्तुएं स्ट्रिंग-मूल्यवान कुंजियों के साथ सहयोगी सरणी के रूप में व्यवहार करती हैं, जबकि मानचित्र और कमजोर मानचित्र प्रकार मनमाने ढंग से वस्तुओं को कुंजियों के रूप में लेते हैं। लुआ में, उनका उपयोग सभी डेटा संरचनाओं के लिए आदिम निर्माण खंड के रूप में किया जाता है। विजुअल फॉक्सप्रो में, उन्हें संग्रह कहा जाता है। डी भाषा सहयोगी सरणियों का भी समर्थन करती है। स्थायी भंडारण सहयोगी सरणी का उपयोग करने वाले कई कार्यक्रमों को उस डेटा को अधिक स्थायी रूप में संग्रहीत करने की आवश्यकता होगी, जैसे कि कंप्यूटर फ़ाइल। इस समस्या का एक सामान्य समाधान एक सामान्यीकृत अवधारणा है जिसे संग्रह या क्रमिककरण के रूप में जाना जाता है, जो मूल वस्तुओं का एक पाठ या द्विआधारी प्रतिनिधित्व उत्पन्न करता है जिसे सीधे किसी फ़ाइल पर लिखा जा सकता है। यह आम तौर पर अंतर्निहित ऑब्जेक्ट मॉडल में लागू किया जाता है, जैसे. नेट या कोकोआ, जिसमें मानक कार्य शामिल हैं जो आंतरिक डेटा को पाठ में परिवर्तित करते हैं। प्रोग्राम इन विधियों को कॉल करके वस्तुओं के किसी भी समूह का एक पूर्ण पाठ प्रतिनिधित्व बना सकता है, जो लगभग हमेशा पहले से ही आधार सहयोगी सरणी वर्ग में लागू होते हैं। बहुत बड़े डेटा सेट का उपयोग करने वाले कार्यक्रमों के लिए, इस प्रकार का व्यक्तिगत फ़ाइल भंडारण उपयुक्त नहीं है, और एक डेटाबेस प्रबंधन प्रणाली (डी. बी.) की आवश्यकता है। कुछ डी. बी. प्रणालियाँ मूल रूप से डेटा को क्रमबद्ध करके और फिर उस क्रमबद्ध डेटा और कुंजी को संग्रहीत करके सहयोगी सरणियों को संग्रहीत करती हैं। अलग-अलग सरणियों को फिर उन्हें संदर्भित करने के लिए कुंजी का उपयोग करके डेटाबेस से लोड या सहेजा जा सकता है। इन प्रमुख-मूल्य भंडारों का उपयोग कई वर्षों से किया जा रहा है और इनका इतिहास अधिक सामान्य संबंधपरक डेटाबेस (आर. डी. बी.) तक लंबा है, लेकिन मानकीकरण की कमी, अन्य कारणों के साथ, उनका उपयोग कुछ विशिष्ट भूमिकाओं तक सीमित है। आर. डी. बी. का उपयोग ज्यादातर मामलों में इन भूमिकाओं के लिए किया जाता था, हालांकि आर. डी. बी. में वस्तुओं को सहेजना जटिल हो सकता है, एक समस्या जिसे वस्तु-संबंध प्रतिबाधा बेमेल के रूप में जाना जाता है। इसके बाद, क्लाउड कंप्यूटिंग के लिए उपयुक्त उच्च-प्रदर्शन डेटाबेस की आवश्यकता और उनका उपयोग करने वाले कार्यक्रमों की आंतरिक संरचना से अधिक निकटता से मेल खाने से प्रमुख-मूल्य वाले स्टोर बाजार में एक पुनर्जागरण हुआ। ये प्रणालियाँ मूल रूप से सहयोगी सरणियों को संग्रहीत और पुनर्प्राप्त कर सकती हैं, जो सामान्य वेब-संबंधित कार्यप्रवाहों में प्रदर्शन में बहुत सुधार कर सकती हैं। की-वैल्यू डेटाबेस टुपल फंक्शन (गणित) जे. एस. ओ. एन. संदर्भ बाहरी लिंक एन. आई. एस. टी. का एल्गोरिदम और डेटा संरचनाओं का शब्दकोशः सहयोगी सरणी सार डेटा प्रकार समग्र डेटा प्रकार डेटा प्रकार