तारों की तुलना करने वाले फ़ंक्शन के प्रदर्शन में सुधार करने का प्रयास करने के लिए मैंने अपने हैंश की तुलना करके उनकी तुलना करने का निर्णय लिया। तो क्या कोई गारंटी है कि 2 बहुत लंबे तारों का हैश एक दूसरे के बराबर है तो तार एक-दूसरे के बराबर हैं?अपने हैंश द्वारा लंबे तारों की तुलना
हालांकि यह गारंटी है कि 2 समान तार आपको बराबर हैंश प्रदान करेंगे, दूसरी तरफ दौर सत्य नहीं है: दिए गए हैश के लिए, हमेशा एक ही हैश उत्पन्न करने वाले कई संभावित तार होते हैं। यह PigeonHole principle के कारण सच है।
कहा जा रहा है कि, एक ही हैश का उत्पादन करने वाले 2 अलग-अलग तारों की संभावनाओं को शून्य के समकक्ष समझा जा सकता है।
ऐसे हैश का एक काफी शास्त्रीय उदाहरण MD5 है, जिसमें लगभग 128 बिट वितरण हैं। जिसका अर्थ है कि आपके पास 2^128 में एक मौका है कि 2 अलग-अलग तार एक ही हैश उत्पन्न करते हैं। खैर, मूल रूप से, लगभग असंभव के समान ही।
दिलचस्प बात यह है कि, एमडी 5 टूटा गया है: एक हमलावर _intentionally_ किसी स्ट्रिंग को बना सकता है जो किसी दिए गए मान को हैश करता है। वहां बस पर्याप्त बिट्स नहीं हैं, यही कारण है कि एसएचए क्रिप्टोग्राफी में वर्तमान मानक बन गया है। –
हां, "यादृच्छिक टकराव" और "जानबूझकर टकराव" प्राप्त करने के बीच यह बहुत बड़ा अंतर है। यादृच्छिक मोर्चे पर, एमडी 5 अभी भी काफी अच्छा है। अब, अगर प्रणाली को जानबूझकर टक्कर (जो हमेशा आवश्यक नहीं है) के जोखिम को ध्यान में रखना चाहिए, तो हाँ, एमडी 5 अब पर्याप्त नहीं है। – Cyan
मूल तारों की तुलना करने से एमडी 5 हैश का उत्पादन और तुलना कैसे तेजी से हो सकती है?! – Aprillion
मुझे यकीन नहीं है, अगर आपका प्रदर्शन बेहतर होगा। दोनों: हैश + बिल्डिंग पूर्णांक की तुलना करना और बराबर का उपयोग करके स्ट्रिंग की तुलना करना एक ही जटिलता है, जो ओ (एन) में रहता है, जहां एन वर्णों की संख्या है।
साधारण सामान्य मामले में जहां दो लंबी तारों की तुलना की जाती है यह निर्धारित करने के लिए की जाती है कि वे समान हैं या नहीं, दो कारणों से एक आसान तुलना हैश पर अधिक पसंद की जाएगी। सबसे पहले, जैसा कि @ विल्डप्लेसर द्वारा इंगित किया गया है, हैश की आवश्यकता है कि दोनों हैंश मानों की गणना करने के लिए दोनों तारों के सभी बाइटों को पार किया जाना चाहिए, जबकि सरल तुलना तेज है, और केवल पहले अंतर मिलने तक केवल बाइट्स को पार करने की आवश्यकता है, जो पूर्ण स्ट्रिंग लंबाई से बहुत कम हो सकता है। और दूसरा, किसी भी अंतर की पहचान करने के लिए एक साधारण तुलना की गारंटी दी जाती है, जबकि हैश केवल एक उच्च संभावना देता है जो वे समान हैं, जैसा कि @AdamLiss और @Cyan द्वारा इंगित किया गया है।
हालांकि, कई दिलचस्प मामले हैं जहां हैश तुलना को बड़े लाभ के लिए नियोजित किया जा सकता है। जैसा कि @Cyan द्वारा उल्लिखित किया गया है यदि तुलना एक से अधिक बार की जानी है, या बाद में उपयोग के लिए संग्रहीत किया जाना चाहिए, तो हैश तेज हो सकता है। दूसरों द्वारा उल्लिखित एक मामला यह नहीं है कि तार स्थानीय नेटवर्क या इंटरनेट से जुड़े विभिन्न मशीनों पर हैं। दो मशीनों के बीच एक छोटी मात्रा में डेटा पास करना आम तौर पर बहुत तेज़ होगा। सबसे सरल पहली जांच दो अलग-अलग आकार की तुलना की जाती है, यदि अलग हो, तो आप कर चुके हैं। अन्यथा, हैश की गणना करें, प्रत्येक अपनी मशीन पर (मान लीजिए कि आप रिमोट मशीन पर प्रक्रिया बनाने में सक्षम हैं) और फिर, यदि आप अलग-अलग हैं। यदि हैश मान समान हैं, और यदि आपके पास पूर्ण निश्चितता होनी चाहिए, तो निश्चितता के लिए कोई आसान शॉर्टकट नहीं है। दोनों सिरों पर लापरवाही संपीड़न का उपयोग करने के लिए कम डेटा को तुलना के लिए स्थानांतरित करने की अनुमति होगी। और आखिरकार, यदि दो तारों को समय के अनुसार अलग किया जाता है, जैसा कि @Cyan द्वारा बताया गया है, यदि आप जानना चाहते हैं कि कल से एक फ़ाइल बदल गई है, और आपने कल के संस्करण से हैश को संग्रहित किया है, तो आप आज के हैश की तुलना कर सकते हैं ।
मुझे आशा है कि इससे किसी के लिए कुछ "बॉक्स के बाहर" विचारों को प्रोत्साहित करने में मदद मिलेगी।
मुझे विश्वास है। हैश उनके डेटा के पूर्ण प्रतिनिधित्व हैं। तो बराबर तारों के बराबर हैश होना चाहिए। – Jeremy1026
स्ट्रिंग्स की पहली जगह की तुलना क्यों नहीं करें। हैश की गणना करने से आप दोनों स्ट्रिंग्स के हर चरित्र का निरीक्षण कर सकते हैं। तो उनकी तुलना करता है (लेकिन यह पहली मेलसमूह पर "असमान" वापस आ सकता है) – wildplasser
@ जेरेमी 1026: यह बस सच नहीं है। मान लीजिए कि आप 4-बिट हैश का उपयोग करते हैं। 4 बिट्स 2^4 = 16 अलग-अलग मान रख सकते हैं, इसलिए आप उस हैश के साथ 16 से अधिक तारों के बीच कभी अंतर नहीं कर सकते। अभ्यास में, हैश आमतौर पर सैकड़ों बिट्स होते हैं, लेकिन उन वस्तुओं की संख्या की सीमा हमेशा होती है जिन्हें वे अलग कर सकते हैं।माना जाता है कि टक्कर पर्याप्त लंबे हैंश के साथ बेहद असंभव हैं, लेकिन कभी गारंटी नहीं है कि विभिन्न तारों में अलग-अलग हैंश होंगे। –