रैखिक जांच

From Vigyanwiki
Revision as of 15:23, 9 July 2023 by alpha>Saurabh
जॉन स्मिथ और सैंड्रा डी (दोनों सेल 873 पर हैशिंग) के बीच टकराव को सैंड्रा डी को अगले मुक्त स्थान, सेल 874 पर रखकर हल किया जाता है।

लीनियर प्रोबिंग कंप्यूटर प्रोग्रामिंग में हैश तालिकाओं में हैश टकराव को हल करने, विशेषता-मूल्य जोड़ी | कुंजी-मूल्य जोड़े के संग्रह को बनाए रखने और किसी दिए गए कुंजी से जुड़े मूल्य को देखने के लिए डेटा संरचनाओं की योजना है। इसका आविष्कार 1954 में जीन अमडाहल, एलेन एम. मैकग्रा और आर्थर सैमुअल (कंप्यूटर वैज्ञानिक) द्वारा किया गया था और पहली बार 1963 में डोनाल्ड नुथ द्वारा इसका विश्लेषण किया गया था।

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

जैसा थोरुप & जांग (2012) लिखें, हैश टेबल सबसे अधिक उपयोग की जाने वाली गैर-तुच्छ डेटा संरचनाएं हैं, और मानक हार्डवेयर पर सबसे लोकप्रिय कार्यान्वयन लीनियर प्रोबिंग का उपयोग करता है, जो तेज़ और सरल दोनों है।[1] लीनियर प्रोबिंग अपने संदर्भ के अच्छे स्थान के कारण उच्च प्रदर्शन प्रदान कर सकती है, किन्तु कुछ अन्य टकराव समाधान योजनाओं की तुलना में अपने हैश फ़ंक्शन की गुणवत्ता के प्रति अधिक संवेदनशील है। यादृच्छिक हैश फ़ंक्शन, K-स्वतंत्र हैशिंग या 5-स्वतंत्र हैश फ़ंक्शन, या सारणीबद्ध हैशिंग का उपयोग करके कार्यान्वित किए जाने पर प्रति खोज, सम्मिलन या विलोपन में निरंतर अपेक्षित समय लगता है। मर्मुरहैश जैसे अन्य हैश फ़ंक्शंस के साथ अभ्यास में भी अच्छे परिणाम प्राप्त किए जा सकते हैं।[2]

संचालन

सहयोगी सरणी को हल करने के लिए हैश टेबल का उपयोग करने के लिए लीनियर प्रोबिंग ओपन एड्रेसिंग योजनाओं का घटक है। शब्दकोश समस्या में, डेटा संरचना को कुंजी-मूल्य जोड़े का संग्रह बनाए रखना चाहिए जो उन ऑपरेशनों के अधीन है जो संग्रह से जोड़े डालते हैं या हटाते हैं या जो किसी दिए गए कुंजी से जुड़े मूल्य की खोज करते हैं। इस समस्या के खुले समाधान में, डेटा संरचना ऐरे डेटा संरचना है T (हैश तालिका) जिनकी सेल T[i] (जब कोई खाली न हो) प्रत्येक एकल कुंजी-मूल्य जोड़ी संग्रहीत करता है। प्रत्येक कुंजी को सेल में मैप करने के लिए हैश फ़ंक्शन T का उपयोग किया जाता है जहां उस कुंजी को संग्रहीत किया जाना चाहिए, सामान्यतः कुंजियों को स्क्रैम्बल करना जिससे समान मान वाली कुंजियां तालिका में एक-दूसरे के पास न रखी जाती है। हैश टकराव तब होता है जब हैश फ़ंक्शन कुंजी को उस सेल में मैप करता है जो पहले से ही अलग कुंजी द्वारा अभिग्रहण कर लिया गया है। लीनियर प्रोबिंग नई कुंजी को निकटतम खाली सेल में रखकर टकराव को हल करने की रणनीति है।[3][4]

खोज

किसी दी गई कुंजी x को खोजने के लिए , T की सेल जांच की जाती है, जिसकी प्रारंभ इंडेक्स h(x) पर सेल से होती है (जहाँ h हैश फ़ंक्शन है) और आसन्न सेल्स तक जारी है h(x) + 1, h(x) + 2, ..., जब तक कि कोई खाली सेल या वह सेल न मिल जाए जिसकी संग्रहीत कुंजी x है .

यदि कुंजी वाला कोई सेल मिल जाता है, जिससे खोज उस सेल से मान लौटाती है। अन्यथा, यदि कोई खाली सेल पाया जाता है, तो कुंजी तालिका में नहीं हो सकती है, क्योंकि इसे किसी भी बाद के सेल के अतिरिक्त उस सेल में रखा गया होगा जिसे अभी तक खोजा नहीं गया है। इस स्थिति में, खोज के परिणाम के रूप में यह पता चलता है कि कुंजी शब्दकोश में उपस्थित नहीं है।[3][4]

सम्मिलन

कुंजी-मूल्य युग्म सम्मिलित करने के लिए (x,v) तालिका में (संभवतः किसी भी मौजूदा जोड़ी को उसी कुंजी से प्रतिस्थापित करते हुए), सम्मिलन एल्गोरिदम सेल्स के उसी अनुक्रम का अनुसरण करता है जिसे खोज के लिए अनुसरण किया जाएगा, जब तक कि खाली सेल या सेल नहीं मिल जाता जिसकी संग्रहीत कुंजी x है .फिर नई कुंजी-मान जोड़ी को उस सेल में रखा जाता है।[3][4]

यदि सम्मिलन के कारण तालिका का लोड फैक्टर (कंप्यूटर विज्ञान) (उसकी अभिग्रहण वाली सेल्स का अंश) कुछ पूर्व निर्धारित सीमा से ऊपर बढ़ जाएगा, तो पूरी तालिका को नई तालिका से प्रतिस्थापित किया जा सकता है, स्थिर कारक से बड़ा, नए हैश के साथ फ़ंक्शन, गतिशील सरणी की तरह इस सीमा को शून्य के निकट सेट करने और तालिका आकार के लिए उच्च विकास दर का उपयोग करने से हैश तालिका संचालन तेज होता है किन्तु के निकट सीमा मान की तुलना में अधिक मेमोरी उपयोग और कम विकास दर होती है। जब लोड फैक्टर 1/2 से अधिक हो जाएगा तो तालिका का आकार दोगुना करना सामान्य विकल्प होगा, जिससे लोड फैक्टर 1/4 और 1/2 के बीच रहता है।[5]

विलोपन

जब कुंजी-मान युग्म हटा दिया जाता है, तो किसी अन्य युग्म को उसके सेल में पीछे की ओर ले जाना आवश्यक हो सकता है, जिससे स्थानांतरित कुंजी की खोजों को खाली सेल खोजने से रोका जा सके।

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

इसके अतिरिक्त, जब सेल i खाली हो गया है, तालिका के निम्नलिखित कक्षों के माध्यम से आगे खोजना आवश्यक है जब तक कि कोई अन्य खाली कक्ष या कुंजी न मिल जाए जिसे कक्ष में ले जाया जा सके i (अर्थात, कुंजी जिसका हैश मान बराबर या उससे पहले है i). जब कोई खाली सेल मिल जाए, तो सेल खाली करना i सुरक्षित है और हटाने की प्रक्रिया समाप्त हो जाती है। किन्तु, जब खोज में कुंजी मिलती है जिसे सेल में ले जाया जा सकता है i, यह यह चाल निष्पादित करता है. इससे बाद में स्थानांतरित कुंजी की खोज में तेजी आती है, किन्तु यह बाद में अभिग्रहण वाले सेल्स के उसी ब्लॉक में अन्य सेल को भी खाली कर देता है। नई खाली सेल के लिए चल कुंजी की खोज उसी तरह जारी रहती है, जब तक कि यह उस सेल तक पहुंचकर समाप्त नहीं हो जाती जो पहले से ही खाली थी। कुंजियों को पहले वाले सेल में ले जाने की इस प्रक्रिया में, प्रत्येक कुंजी की केवल बार जांच की जाती है। इसलिए, पूरी प्रक्रिया को पूरा करने का समय हटाई गई कुंजी वाले अभिग्रहण वाले कक्षों के ब्लॉक की लंबाई के समानुपाती होता है, जो अन्य हैश तालिका संचालन के चलने के समय से मेल खाता है।[3]

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

गुण

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

विश्लेषण

लीनियर प्रोबिंग का उपयोग करके, शब्दकोश संचालन को निरंतर अपेक्षित समय में कार्यान्वित किया जा सकता है। दूसरे शब्दों में, सम्मिलित करें, हटाएं और खोज संचालन को बिग ओ अंकन में प्रयुक्त किया जा सकता है, जब तक कि हैश तालिका का लोड फैक्टर (कंप्यूटर विज्ञान) से सख्ती से कम स्थिर है।[8] अधिक विस्तार से, किसी विशेष संचालन (खोज, सम्मिलन, या विलोपन) का समय अभिग्रहण वाली सेल्स के सन्निहित ब्लॉक की लंबाई के समानुपाती होता है, जिस पर संचालन प्रारंभ होता है। यदि सभी प्रारंभिक सेल समान रूप से संभावित हैं, तो हैश तालिका में N कोशिकाएं, फिर अधिकतम ब्लॉक k अभिग्रहण वाली सेल्स की संभावना होगी k/N जिसमें खोज का आरंभिक स्थान सम्मिलित है, और इसमें समय लगेगा O(k) जब भी यह प्रारंभिक स्थान हो। इसलिए, किसी संचालन के लिए अपेक्षित समय की गणना इन दो शब्दों के उत्पाद के रूप में की जा सकती है, O(k2/N), तालिका में सन्निहित सेल्स के सभी अधिकतम ब्लॉकों का सारांश दिया गया है। वर्गित ब्लॉक लंबाई का समान योग यादृच्छिक हैश फ़ंक्शन (हैश तालिका की विशिष्ट स्थिति में यादृच्छिक प्रारंभिक स्थान के अतिरिक्त) के लिए अपेक्षित समय सीमा देता है, जो उपस्थित सभी ब्लॉकों को जोड़कर (उन लोगों के अतिरिक्त) वास्तव में तालिका की दी गई स्थिति में उपस्थित है), और प्रत्येक संभावित ब्लॉक के लिए शब्द को इस संभावना से गुणा करना कि ब्लॉक वास्तव में व्याप्त है। वह है,परिभाषित Block(i,k) यह घटना है कि लंबाई की व्याप्त सेल्स का अधिकतम सन्निहित ब्लॉक है k इंडेक्स से प्रारंभ i, प्रति संचालन अपेक्षित समय है

इस सूत्र को प्रतिस्थापित करके सरल बनाया जा सकता है Block(i,k) सरल आवश्यक नियम द्वारा Full(k), वह घटना कम से कम k तत्वों में हैश मान होते हैं जो लंबाई की सेल्स के ब्लॉक k के अन्दर स्थित होते हैं . इस प्रतिस्थापन के बाद, योग के अन्दर का मूल्य अब निर्भर नहीं करता है i, और यह 1/N कारक रद्द कर देता है N बाहरी योग की नियम ये सरलीकरण बंधन की ओर ले जाते हैं

किन्तु चेर्नॉफ़ बाध्य के गुणक रूप से, जब लोड फैक्टर से दूर बाउंड होता है, तो संभावना है कि लंबाई का ब्लॉक k कम से कम सम्मिलित है k हैशेड मान फ़ंक्शन के रूप में तेजी से छोटा है k, जिसके कारण यह योग स्थिर स्वतंत्र n से घिरा हुआ है.[3] किसी ब्लॉक में स्पष्ट रूप से सम्मिलित होने की संभावना का अनुमान लगाने के लिए चेर्नॉफ़ बाउंड के अतिरिक्त स्टर्लिंग के सन्निकटन का उपयोग करके समान विश्लेषण करना भी संभव है k हैश किए गए मान.[4][9] लोड फैक्टर के संदर्भ में α, यादृच्छिक कुंजी पर सफल खोज करने का अपेक्षित समय है O(1 + 1/(1 − α)), और असफल खोज O(1 + 1/(1 − α)2) (या नई कुंजी का सम्मिलन) करने का अपेक्षित समय है .[10] निरंतर लोड कारकों के लिए, उच्च संभावना के साथ, सबसे लंबे जांच अनुक्रम (तालिका में संग्रहीत सभी कुंजियों के लिए जांच अनुक्रमों के बीच) में लॉगरिदमिक लंबाई होती है।[11]

हैश फ़ंक्शन का विकल्प

क्योंकि लीनियर प्रोबिंग असमान रूप से वितरित हैश मानों के प्रति विशेष रूप से संवेदनशील है,[7] इसे उच्च गुणवत्ता वाले हैश फ़ंक्शन के साथ जोड़ना महत्वपूर्ण है जो ऐसी अनियमितताएं उत्पन्न नहीं करता है।

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

यह वर्ग प्रत्येक वस्तु के साथ जो हैश मान जोड़ता है, उसका पहचान हैशकोड, किसी वस्तु के जीवनकाल तक स्थिर रहने की गारंटी देता है किन्तु अन्यथा इच्छानुसार होता है।[13] क्योंकि पहचान हैशकोड प्रति ऑब्जेक्ट केवल बार बनाया जाता है, और इसे ऑब्जेक्ट के पते या मूल्य से संबंधित होना आवश्यक नहीं है, इसके निर्माण में धीमी गणनाएं सम्मिलित हो सकती हैं जैसे कि यादृच्छिक या छद्म यादृच्छिक संख्या जनरेटर को कॉल करना। उदाहरण के लिए, जावा 8 इन मानों के निर्माण के लिए ज़ोरशिफ्ट छद्म यादृच्छिक संख्या जनरेटर का उपयोग करता है।[14] हैशिंग के अधिकांश अनुप्रयोगों के लिए, प्रत्येक मान के लिए हैश फ़ंक्शन की गणना हर बार हैश किए जाने पर करना आवश्यक है, न कि बार जब उसका ऑब्जेक्ट बनाया जाता है। ऐसे अनुप्रयोगों में, यादृच्छिक या छद्म यादृच्छिक संख्याओं को हैश मान के रूप में उपयोग नहीं किया जा सकता है, क्योंकि तब समान मान वाली विभिन्न वस्तुओं में अलग-अलग हैश होंगे। और क्रिप्टोग्राफ़िक हैश फ़ंक्शन (जो वास्तव में यादृच्छिक फ़ंक्शंस से कम्प्यूटेशनल रूप से अप्रभेद्य होने के लिए डिज़ाइन किए गए हैं) सामान्यतः हैश तालिकाओं में उपयोग करने के लिए बहुत धीमे होते हैं।[15] इसके अतिरिक्त, हैश फ़ंक्शन के निर्माण के लिए अन्य विधि तैयार किए गए हैं। ये विधियाँ हैश फ़ंक्शन की शीघ्रता से गणना करती हैं, और लीनियर प्रोबिंग के साथ अच्छी तरह से काम करने के लिए सिद्ध हो सकती हैं। विशेष रूप से, K-स्वतंत्र हैशिंग| के रुपरेखा से लीनियर प्रोबिंग का विश्लेषण किया गया है k-स्वतंत्र हैशिंग, हैश फ़ंक्शंस का वर्ग जो छोटे से यादृच्छिक बीज से आरंभ किया जाता है और जो किसी को भी मैप करने की समान रूप से संभावना रखता है k-किसी के लिए अलग-अलग कुंजियों का समूह k-सूचकांकों का समूह। पैरामीटर k को हैश फ़ंक्शन गुणवत्ता के माप के रूप में सोचा जा सकता है: जितना बड़ा k है, हैश फ़ंक्शन की गणना करने में उतना ही अधिक समय लगेगा किन्तु यह पूरी तरह से यादृच्छिक फ़ंक्शन के समान व्यवहार करेगा।

लीनियर प्रोबिंग के लिए, 5-स्वतंत्रता प्रति संचालन निरंतर अपेक्षित समय की गारंटी देने के लिए पर्याप्त है,[16] जबकि कुछ 4-स्वतंत्र हैश फ़ंक्शन खराब प्रदर्शन करते हैं, जिससे प्रति संचालन लॉगरिदमिक समय लगता है।[6] उच्च गुणवत्ता और व्यावहारिक गति दोनों के साथ हैश फ़ंक्शन के निर्माण का अन्य विधि सारणीकरण हैशिंग है। इस पद्धति में, किसी कुंजी के लिए हैश मान की गणना कुंजी के प्रत्येक बाइट को यादृच्छिक संख्याओं की तालिका में सूचकांक के रूप में उपयोग करके की जाती है (प्रत्येक बाइट स्थिति के लिए अलग तालिका के साथ)। फिर उन तालिका सेल्स की संख्याओं को बिटवाइज़ एकमात्र संचालन द्वारा संयोजित किया जाता है। इस तरह से निर्मित हैश फ़ंक्शन केवल 3-स्वतंत्र हैं। फिर भी, इन हैश फ़ंक्शंस का उपयोग करके लीनियर प्रोबिंग में प्रति संचालन निरंतर अपेक्षित समय लगता है।[4][17] 5-स्वतंत्र हैश फ़ंक्शंस उत्पन्न करने के लिए सारणीकरण हैशिंग और मानक विधियाँ दोनों उन कुंजियों तक सीमित हैं जिनमें बिट्स की निश्चित संख्या होती है। स्ट्रिंग (कंप्यूटर विज्ञान) या अन्य प्रकार की चर-लंबाई कुंजियों को संभालने के लिए, फ़ंक्शन संरचना (कंप्यूटर विज्ञान) सरल सार्वभौमिक हैशिंग तकनीक संभव है जो मध्यवर्ती मूल्यों और उच्च गुणवत्ता (5-स्वतंत्र या सारणीबद्ध) हैश की कुंजी को मैप करती है फ़ंक्शन जो मध्यवर्ती मानों को हैश तालिका सूचकांकों पर मैप करता है।[1][18]

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

इतिहास

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

नुथ (1963) लीनियर प्रोबिंग के प्रारंभिक इतिहास का सारांश प्रस्तुत करता है। यह पहली ओपन एड्रेसिंग विधि थी, और मूल रूप से ओपन एड्रेसिंग का पर्याय थी। नुथ के अनुसार, इसका उपयोग पहली बार 1954 में आईबीएम 701 कंप्यूटर के लिए असेंबली भाषा कार्यक्रम में जीन अमडाहल, एलेन एम. मैकग्रा (नी बोहेम) और आर्थर सैमुअल (कंप्यूटर वैज्ञानिक) द्वारा किया गया था।[8] लीनियर प्रोबिंग का पहला प्रकाशित विवरण किसके द्वारा है? Peterson (1957),[8] जो सैमुअल, अमदहल और बोहमे को भी श्रेय देते हैं, किन्तु यह भी जोड़ते हैं कि यह प्रणाली इतनी प्राकृतिक है कि इसकी बहुत संभावना है कि उस समय से पहले या उसके बाद दूसरों द्वारा स्वतंत्र रूप से इसकी कल्पना की गई होगी।[21] इस पद्धति का और प्रारंभिक प्रकाशन 1958 में सोवियत शोधकर्ता एंड्री एर्शोव द्वारा किया गया था।[22]

लीनियर प्रोबिंग का पहला सैद्धांतिक विश्लेषण, यह दर्शाता है कि यादृच्छिक हैश फ़ंक्शन के साथ प्रति संचालन में निरंतर अपेक्षित समय लगता है, नथ द्वारा दिया गया था।[8] रॉबर्ट सेडगेविक (कंप्यूटर वैज्ञानिक) नुथ के काम को एल्गोरिदम के विश्लेषण में मील का पत्थर कहते हैं।[10] बाद के महत्वपूर्ण विकासों में चालू समय की संभाव्यता वितरण का अधिक विस्तृत विश्लेषण सम्मिलित है,[23][24] और यह प्रमाण कि लीनियर प्रोबिंग प्रति संचालन निरंतर समय में व्यावहारिक रूप से प्रयोग करने योग्य हैश फ़ंक्शन के साथ चलती है, न कि पहले के विश्लेषण द्वारा ग्रहण किए गए आदर्श यादृच्छिक कार्यों के साथ किया जाता है।[16][17]

संदर्भ

  1. ↑ 1.0 1.1 Thorup, Mikkel; Zhang, Yin (2012), "Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation", SIAM Journal on Computing, 41 (2): 293–331, doi:10.1137/100800774, MR 2914329
  2. ↑ 2.0 2.1 Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015), "A seven-dimensional analysis of hashing methods and its implications on query processing" (PDF), Proceedings of the VLDB Endowment, 9 (3): 293–331, doi:10.14778/2850583.2850585
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 6.3.3: Linear Probing", Algorithm Design and Applications, Wiley, pp. 200–203
  4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 Morin, Pat (February 22, 2014), "Section 5.2: LinearHashTable: Linear Probing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 108–116, retrieved 2016-01-15
  5. ↑ Sedgewick, Robert; Wayne, Kevin (2011), Algorithms (4th ed.), Addison-Wesley Professional, p. 471, ISBN 9780321573513. Sedgewick and Wayne also halve the table size when a deletion would cause the load factor to become too low, causing them to use a wider range [1/8,1/2] in the possible values of the load factor.
  6. ↑ 6.0 6.1 Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k[[Category: Templates Vigyan Ready]]-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715–726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60 {{citation}}: URL–wikilink conflict (help)
  7. ↑ 7.0 7.1 Heileman, Gregory L.; Luo, Wenbin (2005), "How caching affects hashing" (PDF), Seventh Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 141–154
  8. ↑ 8.0 8.1 8.2 8.3 Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03
  9. ↑ Eppstein, David (October 13, 2011), "Linear probing made easy", 0xDE
  10. ↑ 10.0 10.1 Sedgewick, Robert (2003), "Section 14.3: Linear Probing", Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.), Addison Wesley, pp. 615–620, ISBN 9780321623973
  11. ↑ Pittel, B. (1987), "Linear probing: the probable largest search time grows logarithmically with the number of records", Journal of Algorithms, 8 (2): 236–249, doi:10.1016/0196-6774(87)90040-X, MR 0890874
  12. ↑ "IdentityHashMap", Java SE 7 Documentation, Oracle, retrieved 2016-01-15
  13. ↑ Friesen, Jeff (2012), Beginning Java 7, Expert's voice in Java, Apress, p. 376, ISBN 9781430239109
  14. ↑ Kabutz, Heinz M. (September 9, 2014), "Identity Crisis", The Java Specialists' Newsletter, 222
  15. ↑ Weiss, Mark Allen (2014), "Chapter 3: Data Structures", in Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (eds.), Computing Handbook, vol. 1 (3rd ed.), CRC Press, p. 3-11, ISBN 9781439898536.
  16. ↑ 16.0 16.1 Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, arXiv:cs/0612055, doi:10.1137/070702278, MR 2538852
  17. ↑ 17.0 17.1 Pătraşcu, Mihai; Thorup, Mikkel (2011), "The power of simple tabulation hashing", Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC '11), pp. 1–10, arXiv:1011.5200, doi:10.1145/1993636.1993638, S2CID 195776653
  18. ↑ Thorup, Mikkel (2009), "String hashing for linear probing", Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 655–664, CiteSeerX 10.1.1.215.4253, doi:10.1137/1.9781611973068.72, MR 2809270
  19. ↑ Parhami, Behrooz (2006), Introduction to Parallel Processing: Algorithms and Architectures, Series in Computer Science, Springer, 4.1 Development of early models, p. 67, ISBN 9780306469640
  20. ↑ Morin, Pat (2004), "Hash tables", in Mehta, Dinesh P.; Sahni, Sartaj (eds.), Handbook of Data Structures and Applications, Chapman & Hall / CRC, p. 9-15, ISBN 9781420035179.
  21. ↑ Peterson, W. W. (April 1957), "Addressing for random-access storage", IBM Journal of Research and Development, Riverton, NJ, USA: IBM Corp., 1 (2): 130–146, doi:10.1147/rd.12.0130
  22. ↑ Ershov, A. P. (1958), "On Programming of Arithmetic Operations", Communications of the ACM, 1 (8): 3–6, doi:10.1145/368892.368907, S2CID 15986378. Translated from Doklady AN USSR 118 (3): 427–430, 1958, by Morris D. Friedman. Linear probing is described as algorithm A2.
  23. ↑ Flajolet, P.; Poblete, P.; Viola, A. (1998), "On the analysis of linear probing hashing" (PDF), Algorithmica, 22 (4): 490–515, doi:10.1007/PL00009236, MR 1701625, S2CID 5436036
  24. ↑ Knuth, D. E. (1998), "Linear probing and graphs", Algorithmica, 22 (4): 561–568, arXiv:cs/9801103, doi:10.1007/PL00009240, MR 1701629, S2CID 12254909
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=रैखिक_जांच&oldid=235364’