पायथन dict कार्यान्वयन विवरण

Question

मुझे पाइथन शब्दकोश कार्यान्वयन के बारे में एक प्रश्न है। अजगर की तरह सभी चाबियाँ के लिए एक खोज आदेश, उदा बनाए रखेंगे, तो आप निम्नलिखित आपरेशन

a = {} 
a[3] = 1 
a[0] = 2 

a = {0:2, 3:1} 

अजगर करना स्वतः अपने प्रविष्टि क्रम बदल जाएगा

लग रहा है। जैसा कि पाइथन का दावा है कि निर्देश अनियंत्रित सेट है, मैं काफी समझ नहीं पा रहा हूं कि क्यों पाइथन ऐसे खोज आदेश को बनाए रखेगा। क्या पाइथन एक हैश टेबल द्वारा निर्देशित करता है और इंडेक्स ऑर्डरिंग के लिए सेट स्टोर करता है?

उम्मीद है कि मैं सवाल स्पष्ट कर दूंगा।

धन्यवाद

Answer 1

Dict सूचकांक आदेश कितना dict कार्यान्वित किया जाता है का परिणाम है, और पर भरोसा नहीं किया जाना चाहिए।

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

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

यदि आप पुनरावृत्ति आदेश प्रविष्टि आदेश के समान होना चाहते हैं, तो ordereddict देखें।

Answer 2

एक आदेश का आदेश ऑब्जेक्ट के हैशिंग फ़ंक्शन (और हैश टकराव होने पर सम्मिलन आदेश) द्वारा पूरी तरह से निर्धारित किया जाता है। पूर्णांकों खुद को हैश (कम से कम sys.maxint तक):

>>> hash(1) 
1 

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

>>> d1 = {} 
>>> d1[0] = 'foo' 
>>> d1[8] = 'bar' 
>>> d1 
{0: 'foo', 8: 'bar'} 
>>> 
>>> d2 = {} 
>>> d2[8] = 'bar' 
>>> d2[0] = 'foo' 
>>> d2 
{8: 'bar', 0: 'foo'} 

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

बेशक

, अपने शब्दकोश अधिक है करने के लिए ~ 5 तत्वों से है, यह आकार दिया जाएगा (मैं 16 के लिए लगता है, लेकिन उस पर मुझे बोली नहीं है) और 0 और 8 अब भिड़ना होगा होता है अगर ...

>>> d1 = {x:x for x in range(1, 6)} 
>>> d1[0] = 0 
>>> d1[8] = 8 
>>> d1 
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8} 
>>> d2 = {x:x for x in range(1, 6)} 
>>> d2[8] = 8 
>>> d2[0] = 0 
>>> d2 
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 8: 8} 

ध्यान दें, (क्रमबद्ध) आदेश संरक्षित है (नहीं प्रविष्टि क्रम) जिसका अर्थ है कि हर पूर्णांक यह हैश तालिका (कोई टकराव) में स्थान को प्राथमिकता दी है कर ली। मुझे लगता है कि जब यह लगभग 2/3 पूर्ण होता है तो ताना आकार बदल जाता है।

---

ध्यान दें, यह विशुद्ध रूप से शैक्षिक है - अजगर विनिर्देश यह नहीं कहता है यह कैसे काम करता है और इसलिए यह किसी भी समय सकता है परिवर्तन। कृपया इस व्यवहार पर भरोसा न करें। इनमें से अधिकांश को comments in the source code और से जोड़ा जा सकता है जो इसके आगे बैठता है ...