क्यों टुपल (सेट ([1, "ए", "बी", "सी", "जेड", "एफ"])) == टुपल (सेट (["ए", "बी", "सी" , "जेड", "एफ", 1])) हैश यादृच्छिकता के साथ 85% समय सक्षम है?

Question

Given Zero Piraeus' answer to another question, हम उस

x = tuple(set([1, "a", "b", "c", "z", "f"])) 
y = tuple(set(["a", "b", "c", "z", "f", 1])) 
print(x == y) 

प्रिंटों Truehash randomization के साथ समय में से 85% सक्षम है। 85% क्यों?

Answer 1

मैं इस सवाल के किसी भी पाठकों को ग्रहण करने के लिए जा रहा हूँ दोनों को पढ़ा है:

• Zero Piraeus' answer और

• My explanation of CPython's dictionaries।

नोट करने के लिए पहली बात यह है कि हैश यादृच्छिकीकरण दुभाषिया शुरू हुआ पर फैसला किया जाता है।

प्रत्येक अक्षर के हैश, दोनों सेट के लिए एक ही हो जाएगा तो केवल बात यह है कि कोई फर्क कर सकते हैं, अगर वहाँ एक टक्कर (जहां क्रम प्रभावित हो जाएगा) है।

---

कि दूसरी कड़ी में हम जानते हैं इन सेटों के लिए समर्थन सरणी लंबाई 8 पर शुरू होता है की कटौती द्वारा:

_ _ _ _ _ _ _ _ 

पहले मामले में, हम 1 सम्मिलित करें:

_ 1 _ _ _ _ _ _ 

और फिर शेष डालें:

α 1 ? ? ? ? ? ? 

तो यह आकार 32 के लिए rehashed है:

1 can't collide with α as α is an even hash 
    ↓ so 1 is inserted at slot 1 first 
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 

दूसरे मामले में, हम बाकी सम्मिलित करें:

? β ? ? ? ? ? ? 

और फिर 1 सम्मिलित करने के लिए प्रयास करें:

Try to insert 1 here, but will 
    ↓ be rehashed if β exists 
? β ? ? ? ? ? ? 

और फिर इसे फिर से हटा दिया जाएगा:

Try to insert 1 here, but will 
    be rehashed if β exists and has 
    ↓ not rehashed somewhere else 
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 

तो क्या पुनरावृत्ति आदेश भिन्न हैं, इस पर निर्भर करता है कि β मौजूद है या नहीं।

---

एक β का मौका मौका 8 और को हैश 1 सापेक्ष 32.

कुछ भी के बाद से है कि करने के लिए 1 सापेक्ष 32 भी हैश हैश कि 5 पत्र के किसी भी 1 सापेक्ष करने के लिए हैश जाएगा सापेक्ष 8 करने के लिए 1, हम मौका लगता है कि 32 स्लॉट की, पांच में से एक स्लॉट 1 में है चाहता हूँ:

5 (number of letters)/32 (number of slots) 

5/32 0,15625 है, इसलिए है एक 15।दो सेट निर्माण के बीच ऑर्डर के 625% मौका अलग-अलग हैं।

---

बिल्कुल अजीब बात नहीं है, यह बिल्कुल शून्य पीरियस मापा गया है।

---

_{¹ तकनीकी रूप से यह भी स्पष्ट नहीं है। हम रीशेशिंग के कारण 5 हेशों में से प्रत्येक का विशिष्ट रूप से नाटक कर सकते हैं, लेकिन रैखिक जांच के कारण यह वास्तव में "बंच किए गए" संरचनाओं के लिए अधिक संभावना है ... लेकिन क्योंकि हम केवल यह देखते हैं कि एक स्लॉट पर कब्जा कर लिया गया है, यह नहीं करता है वास्तव में हमें प्रभावित नहीं करते हैं।}