क्या 32-बिट हैश बनाम दो 16 बिट हैंश के बीच टकराव दर अंतर है?

Question

मैं एक ऐसे सिस्टम पर काम कर रहा हूं जहां हैश टकराव एक समस्या होगी। अनिवार्य रूप से एक ऐसी प्रणाली है जो हैश-टेबल + वृक्ष संरचना में वस्तुओं का संदर्भ देती है। हालांकि सवाल में सिस्टम पहले टेक्स्ट-फाइलों को संकलित करता है जिसमें ढांचे में पथ शामिल होते हैं जिसमें बाइनरी फाइल होती है जिसमें इसके बजाय हैश वैल्यू होते हैं। यह प्रदर्शन कारणों से किया जाता है। हालांकि इस टकराव की वजह से बहुत खराब है क्योंकि संरचना एक ही हैश मान के साथ 2 आइटमों को स्टोर नहीं कर सकती है; किसी आइटम के लिए पूछने वाले भाग में यह जानने के लिए पर्याप्त जानकारी नहीं होगी कि उसे किसकी आवश्यकता है।

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

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

मुझे पता है कि दो 32-बिट हैंश पर स्विचिंग अधिक टक्कर प्रतिरोधी होगी, लेकिन मुझे आश्चर्य है कि अगर 2 16-बिट हैश पर स्विच करना कम से कम कुछ है एक 32-बिट हैश पर लाभ? मैं सबसे गणितीय इच्छुक व्यक्ति नहीं हूँ, इसलिए मैं भी कैसे सुचना यह बल के अलावा अन्य एक जवाब के लिए जाँच शुरू करने के लिए नहीं पता ...

सिस्टम पर कुछ पृष्ठभूमि:

द्वारा

आइटम दिया जाता है नाम इंसान, वे यादृच्छिक तार नहीं हैं, और आम तौर पर शब्दों, अक्षरों और संख्याओं से बने होते हैं जिनमें कोई सफेद जगह नहीं होती है। यह एक नेस्टेड हैश संरचना है, इसलिए यदि आपके पास {a => {b => {c => 'blah'}}} जैसा कुछ था, तो आपको ए/बी/सी के मूल्य प्राप्त करके 'blah' मान प्राप्त होगा, संकलित अनुरोध तत्काल अनुक्रम में 3 हैश मान होंगे, ए, बी, और फिर सी के हैंश मान।

किसी दिए गए स्तर पर टकराव होने पर केवल एक समस्या है। शीर्ष स्तर और निचले स्तर पर किसी आइटम के बीच टक्कर ठीक है। आपके पास {a => {a => {...}}} हो सकता है, जो कि विभिन्न स्तरों पर टकराव की गारंटी देता है (कोई समस्या नहीं)।

अभ्यास में किसी भी दिए गए स्तर की संभावना हैश के लिए 100 से कम मूल्य होंगे, और कोई भी स्तर पर डुप्लीकेट नहीं होगा।

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

Answer 1

यदि आपके पास 2 16 बिट हैंश हैं, जो असंबद्ध मूल्यों का उत्पादन कर रहे हैं, तो आपने अभी 32-बिट हैश एल्गोरिदम लिखा है। यह किसी अन्य 32-बिट हैश एल्गोरिदम से बेहतर या बदतर नहीं होगा।

यदि आप टकराव के बारे में चिंतित हैं, तो सुनिश्चित करें कि आप एक हैश एल्गोरिदम का उपयोग कर रहे हैं जो आपके डेटा को हैश करने का अच्छा काम करता है (कुछ केवल गणना करने के लिए तेज़ होते हैं, यह वही नहीं है जो आप चाहते हैं), और वृद्धि जब तक आप आरामदायक न हों तब तक अपने हैश का आकार।

इससे टकराव की संभावना का सवाल उठता है। यह पता चला है कि अगर आपके संग्रह में n चीजें हैं, तो n * (n-1)/2 चीजें हैं जो टकरा सकती हैं। यदि आप k बिट हैश का उपयोग कर रहे हैं, तो एक जोड़ी टकराव की बाधा 2-k है। यदि आपके पास बहुत सी चीजें हैं, तो अलग-अलग जोड़ों की बाधाएं लगभग असंबंधित हैं।यह वास्तव में स्थिति है कि Poisson distribution वर्णन करता है।

इस प्रकार टकराव की संख्या जो आप देखेंगे, लगभग λ = n * (n-1) * 2-k-1 के साथ पोइसन वितरण का पालन करना चाहिए। इससे कोई हैश टकराव की संभावना e-λ है। 32 बिट्स और 100 आइटमों के साथ, एक स्तर में टकराव की बाधाएं लगभग एक लाख में 1.1525 हैं। यदि आप पर्याप्त समय के साथ डेटा के पर्याप्त सेट के साथ ऐसा करते हैं, तो आखिरकार उन लाखों मौकों में से एक को जोड़ दिया जाएगा।

लेकिन ध्यान दें कि आपके पास कई सामान्य आकार के स्तर और कुछ बड़े हैं, बड़े लोगों के टकराव के आपके जोखिम पर असरदार असर होगा। ऐसा इसलिए है क्योंकि आप जो भी चीज संग्रह में जोड़ते हैं, वह किसी भी पूर्ववर्ती चीजों से टकरा सकती है - अधिक चीजें टक्कर के उच्च जोखिम के बराबर होती हैं। इसलिए, उदाहरण के लिए, 1000 डेटा आइटम्स वाले एक स्तर में 10,000 विफल होने में लगभग 1 मौका है - जो 100 डेटा आइटम्स के साथ 100 स्तरों के समान जोखिम के बारे में है।

यदि हैशिंग एल्गोरिदम ठीक से अपना काम नहीं कर रहा है, तो टकराव का आपका जोखिम तेजी से बढ़ जाएगा। असफलता की प्रकृति पर कितनी तेजी से निर्भर करता है।

उन तथ्यों का उपयोग करना और आपके आवेदन के उपयोग के लिए आपके अनुमानों का उपयोग करना, आपको यह तय करने में सक्षम होना चाहिए कि क्या आप 32-बिट हैश से जोखिम के साथ सहज हैं या आप किसी बड़े चीज़ पर आगे बढ़ना चाहते हैं या नहीं।