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




hash dictionary (4)

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

उपयोगकर्ता द्वारा परिभाषित कक्षाओं में डिफ़ॉल्ट रूप से __cmp __ () और __hash __ () विधियां हैं; उनके साथ, सभी वस्तुएं असमान की तुलना करती हैं (स्वयं को छोड़कर) और x .__ हैश __ () आईडी (x) से प्राप्त परिणाम देता है।

तो यदि आपके पास अपनी कक्षा में लगातार __hash__ है, लेकिन कोई __cmp__ या __eq__ विधि प्रदान नहीं कर रहा है, तो आपके सभी उदाहरण शब्दकोश के लिए असमान हैं। दूसरी तरफ, यदि आप कोई __cmp__ या __eq__ विधि प्रदान करते हैं, लेकिन __hash__ प्रदान नहीं करते हैं, तो आपके उदाहरण अभी भी शब्दकोश के संदर्भ में असमान हैं।

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


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

उत्पादन

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}

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

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

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

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


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

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

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

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


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

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


संपादित करें : नीचे दिया गया जवाब हैश टकराव से निपटने के संभावित तरीकों में से एक है, हालांकि यह नहीं है कि पाइथन इसे कैसे करता है। नीचे संदर्भित पायथन की विकी भी गलत है। नीचे @ डंकन द्वारा दिया गया सबसे अच्छा स्रोत कार्यान्वयन है: 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