python पाइथन के निर्देश में एक ही हैश के साथ कई कुंजियां कैसे हो सकती हैं?




hash dictionary (4)

मैं हुड के नीचे पाइथन हैश फ़ंक्शन को समझने की कोशिश कर रहा हूं। मैंने एक कस्टम क्लास बनाया जहां सभी उदाहरण एक ही हैश मान लौटाते हैं।

class C(object):
    def __hash__(self):
        return 42

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

c, d = C(), C()
x = {c: 'c', d: 'd'}
print x
# {<__main__.C object at 0x83e98cc>:'c', <__main__.C object at 0x83e98ec>:'d'}
# note that the dict has 2 elements

मैंने थोड़ा और प्रयोग किया और पाया कि यदि मैं __eq__ विधि को ओवरराइड करता __eq__ जैसे वर्ग के सभी उदाहरण बराबर की तुलना करते हैं, तो सेट केवल एक उदाहरण की अनुमति देता है।

class D(C):
    def __eq__(self, other):
        return hash(self) == hash(other)

p, q = D(), D()
y = {p:'p', q:'q'}
print y
# {<__main__.D object at 0x8817acc>]: 'q'}
# note that the dict has only 1 element

तो मुझे यह जानकर उत्सुकता है कि एक हथियार के पास एक ही हैश के साथ कई तत्व कैसे हो सकते हैं। धन्यवाद!

नोट: प्रश्न (उदाहरण के बजाय) का उदाहरण देने के लिए प्रश्न संपादित किया गया क्योंकि उत्तर में सभी चर्चाएं डिक्ट्स के बारे में हैं। लेकिन यह सेट पर लागू होता है; सेट में एक ही हैश मान के साथ कई तत्व भी हो सकते हैं।


पाइथन के हैशिंग कार्यों के बारे में एक विस्तृत विवरण के लिए मेरा जवाब देखें कि क्यों जल्दी वापसी जल्दी से धीमी है?

मूल रूप से यह तालिका में एक स्लॉट लेने के लिए हैश का उपयोग करता है। यदि स्लॉट और हैश मैचों में कोई मान है, तो यह आइटम को तुलना करने के लिए तुलना करता है कि वे बराबर हैं या नहीं।

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

ध्यान देने योग्य महत्वपूर्ण बात यह है कि कोई सूचियां या बाल्टी नहीं हैं: स्लॉट की एक विशेष संख्या के साथ केवल एक हैश तालिका है, और प्रत्येक हैश का उपयोग उम्मीदवार स्लॉट के अनुक्रम उत्पन्न करने के लिए किया जाता है।


हैश टेबल, आम तौर पर हैश टकराव की अनुमति है! आप दुर्भाग्यपूर्ण हो जाएंगे और अंततः एक ही चीज़ के लिए दो चीजें हैंश। नीचे, वस्तुओं की एक सूची में ऑब्जेक्ट्स का एक सेट है जिसमें एक ही हैश कुंजी है। आम तौर पर, उस सूची में केवल एक चीज होती है, लेकिन इस मामले में, यह उन्हें उसी में ढेर रखेगी। एकमात्र तरीका यह जानता है कि वे अलग हैं ऑपरेटर के बराबर है।

जब ऐसा होता है, तो आपका प्रदर्शन समय के साथ घट जाएगा, यही कारण है कि आप अपने हैश फ़ंक्शन को "जितना संभव हो उतना यादृच्छिक" बनाना चाहते हैं।


यहां पाइथन डिक्ट्स के बारे में सबकुछ है जो मैं एक साथ रख सकता था (शायद किसी से भी ज्यादा जानना चाहूंगा, लेकिन जवाब व्यापक है)। यह इंगित करने के लिए कि पाइथन डिक्ट्स स्लॉट का उपयोग करते हैं और मुझे इस खरगोश छेद को नीचे ले जाते हैं, यह इंगित करने के लिए से चिल्लाना।

  • पायथन शब्दकोश हश टेबल के रूप में लागू किए जाते हैं।
  • हैश टेबल को हैश टकराव के लिए अनुमति देना चाहिए यानी यदि दो कुंजियों के पास हैश मान है, तो तालिका के कार्यान्वयन में कुंजी और मूल्य जोड़े को अनजाने में पुनर्प्राप्त करने और पुनर्प्राप्त करने की रणनीति होनी चाहिए।
  • पाइथन dict हैश टकराव को हल करने के लिए खुले पते का उपयोग करता है (नीचे समझाया गया है) ( dictobject.c:296-297 देखें)।
  • पायथन हैश टेबल मेमोरी का एक आकस्मिक ब्लॉक है (एक सरणी की तरह है, तो आप इंडेक्स द्वारा O(1) लुकअप कर सकते हैं)।
  • तालिका में प्रत्येक स्लॉट एक और केवल एक प्रविष्टि स्टोर कर सकते हैं। यह महत्वपूर्ण है
  • तालिका में प्रत्येक प्रविष्टि वास्तव में तीन मानों का संयोजन है - । इसे एक सी संरचना के रूप में लागू किया गया है ( dictobject.h:51-56 देखें dictobject.h:51-56 )
  • नीचे दिया गया चित्र एक अजगर हैश तालिका का तार्किक प्रतिनिधित्व है। नीचे दिए गए आंकड़े में, 0, 1, ..., i, ... बाईं ओर हैश तालिका में स्लॉट के सूचकांक हैं (वे केवल चित्रकारी उद्देश्यों के लिए हैं और तालिका के साथ स्पष्ट रूप से संग्रहीत नहीं हैं!)।

    # Logical model of Python Hash table
    -+-----------------+
    0| <hash|key|value>|
    -+-----------------+
    1|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    i|      ...        |
    -+-----------------+
    .|      ...        |
    -+-----------------+
    n|      ...        |
    -+-----------------+
    
  • जब एक नया नियम शुरू किया जाता है तो यह 8 स्लॉट के साथ शुरू होता है। ( dictobject.h:51-56 देखें dictobject.h:51-56 )

  • तालिका में प्रविष्टियां जोड़ने पर, हम कुछ स्लॉट से शुरू करते हैं, i कुंजी के हैश पर आधारित होता i । सीपीथन प्रारंभिक i = hash(key) & mask का उपयोग करता है। जहां mask = PyDictMINSIZE - 1 , लेकिन यह वास्तव में महत्वपूर्ण नहीं है)। बस ध्यान दें कि प्रारंभिक स्लॉट, i, जो चेक किया गया है, कुंजी के हैश पर निर्भर करता है।
  • यदि वह स्लॉट खाली है, तो प्रवेश स्लॉट में जोड़ा जाता है (प्रविष्टि से, मेरा मतलब है, <hash|key|value> )। लेकिन क्या होगा अगर उस स्लॉट पर कब्जा कर लिया गया है !? सबसे अधिक संभावना है क्योंकि एक और प्रविष्टि में एक ही हैश हैश (हैश टकराव!)
  • यदि स्लॉट पर कब्जा कर लिया गया है, तो सीपीथॉन (और यहां तक ​​कि पीईपीई) हैश और कुंजी की तुलना करता है (तुलना करके मेरा मतलब है == तुलना की तुलना नहीं is ) वर्तमान प्रविष्टि की कुंजी के खिलाफ स्लॉट में प्रविष्टि की तुलना में ( dictobject.c:296-297 )। यदि दोनों मेल खाते हैं, तो ऐसा लगता है कि प्रविष्टि पहले से मौजूद है, छोड़ देता है और अगली प्रविष्टि को डालने के लिए आगे बढ़ता है। यदि हैश या कुंजी मेल नहीं खाती है, तो यह जांच शुरू कर देता है
  • प्रोबिंग का मतलब है कि यह एक खाली स्लॉट खोजने के लिए स्लॉट द्वारा स्लॉट की खोज करता है। तकनीकी रूप से हम केवल एक-एक करके जा सकते हैं, i + 1, i + 2, ... और पहले उपलब्ध एक (यह रैखिक जांच) का उपयोग करें। लेकिन टिप्पणियों में खूबसूरती से समझाया गया है ( dictobject.c:296-297 देखें), dictobject.c:296-297 यादृच्छिक जांच का उपयोग करता है। यादृच्छिक जांच में, अगला स्लॉट छद्म यादृच्छिक क्रम में चुना जाता है। प्रविष्टि को पहले खाली स्लॉट में जोड़ा गया है। इस चर्चा के लिए, अगला स्लॉट चुनने के लिए उपयोग किया जाने वाला वास्तविक एल्गोरिदम वास्तव में महत्वपूर्ण नहीं है (जांच के लिए एल्गोरिदम के लिए dictobject.c:296-297 देखें)। महत्वपूर्ण बात यह है कि पहले खाली स्लॉट मिलने तक स्लॉट की जांच की जाती है।
  • लुकअप के लिए भी यही बात होती है, बस प्रारंभिक स्लॉट i से शुरू होती है (जहां मैं कुंजी के हैश पर निर्भर करता हूं)। यदि हैश और कुंजी दोनों स्लॉट में प्रविष्टि से मेल नहीं खाते हैं, तो यह जांच शुरू कर देता है, जब तक कि यह एक मैच के साथ स्लॉट नहीं पाता। यदि सभी स्लॉट थक गए हैं, तो यह असफल रिपोर्ट करता है।
  • बीटीडब्लू, यदि दो-तिहाई पूर्ण हो तो ताना का आकार बदल दिया जाएगा। यह लुकअप को धीमा करने से बचाता है। ( dictobject.h:51-56 देखें dictobject.h:51-56 )

तुम वहाँ जाओ! वस्तुओं को डालने पर चाबियों के पाइथन कार्यान्वयन दोनों चाबियों की हैश समानता और चाबियों की सामान्य समानता ( == ) दोनों के लिए जांच करता है। तो संक्षेप में, यदि दो कुंजियां हैं, a और b और hash(a)==hash(b) , लेकिन a!=b , तो दोनों पाइथन स्कूल में सामंजस्यपूर्ण रूप से मौजूद हो सकते हैं। लेकिन अगर hash(a)==hash(b) और a==b , तो वे दोनों एक ही नियम में नहीं हो सकते हैं।

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

मुझे लगता है कि मेरे प्रश्न का संक्षिप्त जवाब यह है, "क्योंकि इस तरह यह स्रोत कोड में लागू किया गया है;)"

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


संपादित करें : नीचे दिया गया जवाब हैश टकराव से निपटने के संभावित तरीकों में से एक है, हालांकि यह नहीं है कि पाइथन इसे कैसे करता है। नीचे संदर्भित पायथन की विकी भी गलत है। नीचे @ डंकन द्वारा दिया गया सबसे अच्छा स्रोत कार्यान्वयन है: http://svn.python.org/projects/python/trunk/Objects/dictobject.c मैं मिश्रण के लिए क्षमा चाहता हूं।

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

यहां आप John Smith और Sandra Dee दोनों को हैश 152 । बाल्टी 152 उनमें से दोनों शामिल हैं। Sandra Dee तलाश करते समय इसे पहली बार बाल्टी 152 में सूची मिलती है, फिर उस सूची के माध्यम से लूप तब तक Sandra Dee पाई जाती है और 521-6955

निम्नलिखित गलत है यह केवल संदर्भ के लिए है: पायथन की विकी पर आप पाइथन लुकअप निष्पादित करते हैं (छद्म?) कोड पा सकते हैं।

वास्तव में इस समस्या के कई संभावित समाधान हैं, एक अच्छा अवलोकन के लिए विकिपीडिया लेख देखें: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution





equality