This is a good article. Click here for more information.

रैखिक जांच

From Vigyanwiki
Revision as of 14:57, 25 June 2023 by alpha>Indicwiki (Created page with "{{Short description|Computer programming method for hashing}} {{good article}} File:HASHTB12.svg|thumb|upright=1.35|जॉन स्मिथ और सैंड्रा...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

जॉन स्मिथ और सैंड्रा डी (दोनों सेल 873 पर हैशिंग) के बीच टकराव को सैंड्रा डी को अगले मुक्त स्थान, सेल 874 पर रखकर हल किया जाता है।

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

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

जैसा Thorup & Zhang (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]


विश्लेषण

रैखिक जांच का उपयोग करके, शब्दकोश संचालन को निरंतर अपेक्षित समय में कार्यान्वित किया जा सकता है। दूसरे शब्दों में, सम्मिलित करें, हटाएं और खोज संचालन को बिग ओ अंकन |ओ(1) में लागू किया जा सकता है, जब तक कि हैश तालिका का लोड फैक्टर (कंप्यूटर विज्ञान) एक से सख्ती से कम स्थिर है।[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]इसे उच्च गुणवत्ता वाले हैश फ़ंक्शन के साथ जोड़ना महत्वपूर्ण है जो ऐसी अनियमितताएं उत्पन्न नहीं करता है।

उपरोक्त विश्लेषण मानता है कि प्रत्येक कुंजी का हैश अन्य सभी कुंजियों के हैश से स्वतंत्र एक यादृच्छिक संख्या है। हैशिंग के अधिकांश अनुप्रयोगों के लिए यह धारणा अवास्तविक है। हालाँकि, वस्तुओं को उनके मूल्य के बजाय उनकी पहचान के आधार पर हैश करते समय यादृच्छिक या छद्म यादृच्छिक हैश मानों का उपयोग किया जा सकता है। उदाहरण के लिए, यह जावा संग्रह ढांचे के IdentityHashMap वर्ग द्वारा रैखिक जांच का उपयोग करके किया जाता है।[12] यह वर्ग प्रत्येक वस्तु के साथ जो हैश मान जोड़ता है, उसका पहचान हैशकोड, किसी वस्तु के जीवनकाल तक स्थिर रहने की गारंटी देता है लेकिन अन्यथा मनमाना होता है।[13] क्योंकि पहचान हैशकोड प्रति ऑब्जेक्ट केवल एक बार बनाया जाता है, और इसे ऑब्जेक्ट के पते या मूल्य से संबंधित होना आवश्यक नहीं है, इसके निर्माण में धीमी गणनाएं शामिल हो सकती हैं जैसे कि यादृच्छिक या छद्म यादृच्छिक संख्या जनरेटर को कॉल करना। उदाहरण के लिए, जावा 8 इन मानों के निर्माण के लिए एक Xorshift छद्म यादृच्छिक संख्या जनरेटर का उपयोग करता है।[14] हैशिंग के अधिकांश अनुप्रयोगों के लिए, प्रत्येक मान के लिए हैश फ़ंक्शन की गणना हर बार हैश किए जाने पर करना आवश्यक है, न कि एक बार जब उसका ऑब्जेक्ट बनाया जाता है। ऐसे अनुप्रयोगों में, यादृच्छिक या छद्म यादृच्छिक संख्याओं को हैश मान के रूप में उपयोग नहीं किया जा सकता है, क्योंकि तब समान मान वाली विभिन्न वस्तुओं में अलग-अलग हैश होंगे। और क्रिप्टोग्राफ़िक हैश फ़ंक्शन (जो वास्तव में यादृच्छिक फ़ंक्शंस से कम्प्यूटेशनल रूप से अप्रभेद्य होने के लिए डिज़ाइन किए गए हैं) आमतौर पर हैश तालिकाओं में उपयोग करने के लिए बहुत धीमे होते हैं।[15] इसके बजाय, हैश फ़ंक्शन के निर्माण के लिए अन्य तरीके तैयार किए गए हैं। ये विधियाँ हैश फ़ंक्शन की शीघ्रता से गणना करती हैं, और रैखिक जांच के साथ अच्छी तरह से काम करने के लिए सिद्ध हो सकती हैं। विशेष रूप से, K-स्वतंत्र हैशिंग| के ढांचे से रैखिक जांच का विश्लेषण किया गया हैk-स्वतंत्र हैशिंग, हैश फ़ंक्शंस का एक वर्ग जो एक छोटे से यादृच्छिक बीज से आरंभ किया जाता है और जो किसी को भी मैप करने की समान रूप से संभावना रखता है k-किसी के लिए अलग-अलग कुंजियों का समूह k-सूचकांकों का समूह। पैरामीटर k को हैश फ़ंक्शन गुणवत्ता के माप के रूप में सोचा जा सकता है: जितना बड़ा k है, हैश फ़ंक्शन की गणना करने में उतना ही अधिक समय लगेगा लेकिन यह पूरी तरह से यादृच्छिक फ़ंक्शन के समान व्यवहार करेगा। रैखिक जांच के लिए, 5-स्वतंत्रता प्रति ऑपरेशन निरंतर अपेक्षित समय की गारंटी देने के लिए पर्याप्त है,[16] जबकि कुछ 4-स्वतंत्र हैश फ़ंक्शन खराब प्रदर्शन करते हैं, जिससे प्रति ऑपरेशन लॉगरिदमिक समय लगता है।[6] उच्च गुणवत्ता और व्यावहारिक गति दोनों के साथ हैश फ़ंक्शन के निर्माण का एक अन्य तरीका सारणीकरण हैशिंग है। इस पद्धति में, किसी कुंजी के लिए हैश मान की गणना कुंजी के प्रत्येक बाइट को यादृच्छिक संख्याओं की तालिका में एक सूचकांक के रूप में उपयोग करके की जाती है (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ)। फिर उन तालिका कोशिकाओं की संख्याओं को बिटवाइज़ एकमात्र ऑपरेशन द्वारा संयोजित किया जाता है। इस तरह से निर्मित हैश फ़ंक्शन केवल 3-स्वतंत्र हैं। फिर भी, इन हैश फ़ंक्शंस का उपयोग करके रैखिक जांच में प्रति ऑपरेशन लगातार अपेक्षित समय लगता है।[4][17] 5-स्वतंत्र हैश फ़ंक्शंस उत्पन्न करने के लिए सारणीकरण हैशिंग और मानक विधियाँ दोनों उन कुंजियों तक सीमित हैं जिनमें बिट्स की एक निश्चित संख्या होती है। स्ट्रिंग (कंप्यूटर विज्ञान) या अन्य प्रकार की चर-लंबाई कुंजियों को संभालने के लिए, फ़ंक्शन संरचना (कंप्यूटर विज्ञान) एक सरल सार्वभौमिक हैशिंग तकनीक संभव है जो मध्यवर्ती मूल्यों और उच्च गुणवत्ता (5-स्वतंत्र या सारणीबद्ध) हैश की कुंजी को मैप करती है फ़ंक्शन जो मध्यवर्ती मानों को हैश तालिका सूचकांकों पर मैप करता है।[1][18] एक प्रायोगिक तुलना में, रिक्टर एट अल। पाया गया कि हैश फ़ंक्शंस के मल्टीप्लाई-शिफ्ट परिवार (के रूप में परिभाषित) ) सभी हैशिंग योजनाओं के साथ एकीकृत होने पर सबसे तेज़ हैश फ़ंक्शन था, यानी, उच्चतम थ्रूपुट और अच्छी गुणवत्ता का उत्पादन करता था जबकि सारणीकरण हैशिंग ने सबसे कम थ्रूपुट का उत्पादन किया था।[2] वे बताते हैं कि प्रत्येक तालिका लुक-अप के लिए कई चक्रों की आवश्यकता होती है, जो साधारण अंकगणितीय परिचालनों की तुलना में अधिक महंगा होता है। उन्होंने मुरमुरहैश को सारणीकरण हैशिंग से बेहतर पाया: मल्टी और मुरमुर द्वारा प्रदान किए गए परिणामों का अध्ययन करके, हम सोचते हैं कि सारणीकरण (...) के लिए व्यापार-बंद व्यवहार में कम आकर्षक है।

इतिहास

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

Knuth (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=235361’