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



hash set (1)

शून्य पीरियस के दूसरे प्रश्न के उत्तर को देखते हुए , हमारे पास यह है

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

हैश यादृच्छिकता सक्षम के साथ 85% समय प्रिंट प्रिंट करता है। 85% क्यों?


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

  • शून्य पीरियस का जवाब और

  • सीपीथन के शब्दकोशों की मेरी व्याख्या ।

ध्यान देने वाली पहली बात यह है कि हैश यादृच्छिकता दुभाषिया स्टार्ट-अप पर तय की जाती है।

प्रत्येक पत्र का हैश दोनों सेटों के लिए समान होगा, इसलिए केवल एक चीज जो मायने रखती है वह टक्कर है (जहां ऑर्डर प्रभावित होगा)।

उस दूसरे लिंक की कटौती से हम जानते हैं कि इन सेटों के लिए बैकिंग सरणी लंबाई 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
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

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

Β का मौका यह मौका है कि 5 अक्षरों में से कोई भी हैश 1 से 8 मॉड्यूल और हैश 1 मॉड्यूल 32 होगा।

चूंकि जो कुछ भी है जो 1 मॉड्यूल 32 तक है, वह भी 1 मॉड्यूल 8 है, हम 32 स्लॉट्स का मौका ढूंढना चाहते हैं, पांच में से एक स्लॉट में है 1:

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

5/32 0.15625 है, इसलिए दो सेट निर्माण के बीच आदेशों का 15.625% मौका अलग है

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

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





python-internals