क्या हैश एल्गोरिदम पाइथन के शब्दकोश मैपिंग उपयोग करता है?

Question

मैं कमांड लाइन पार्सर बनाने के साथ गड़बड़ कर रहा था और सोच रहा था कि किस प्रकार का हैश एल्गोरिदम पायथन स्कूल का उपयोग है?

जिस तरह से मैंने इसे स्थापित किया है, मेरे पास एक पैटर्न मिलान एल्गोरिदम है जो एक शब्दकोश कुंजी के साथ टोकनयुक्त इनपुट अनुक्रमों से मेल खाता है। कुछ चाबियाँ अपेक्षाकृत लंबी हैं (6-7 वर्ण तारों की लंबाई 5 या 6 टुपल्स)। मैं सोच रहा था कि क्या कोई बिंदु था जिस पर लंबी शब्दकोश कुंजी महत्वपूर्ण पुनर्प्राप्ति की दक्षता को कम करती है।

Answer 1

हैश जो इसका उपयोग करता है उस वस्तु पर निर्भर करता है जो कुंजी के रूप में उपयोग किया जा रहा है - प्रत्येक वर्ग अपनी खुद की __hash __() विधि को परिभाषित कर सकती है, और यह मान जो किसी विशेष उदाहरण के लिए लौटाता है वह शब्दकोश के लिए उपयोग किया जाता है।

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

एक ट्यूपल का हैश इसकी सामग्री के हैंश पर आधारित है। एल्गोरिथ्म अनिवार्य है इस (सरलीकृत थोड़ा):

def hash(tuple): 
    mult = 1000003 
    x = 0x345678 
    for index, item in enumerate(tuple): 
     x = ((x^hash(item)) * mult) & (1<<32) 
     mult += (82520 + (len(tuple)-index)*2) 
    return x + 97531 

तार के लिए, दुभाषिया भी हर चरित्र से अधिक दोहराता, उन्हें इस (फिर से, थोड़ा सरलीकृत) एल्गोरिथ्म के साथ संयोजन:

def hash(string): 
    x = string[0] << 7 
    for chr in string[1:]: 
     x = ((1000003 * x)^chr) & (1<<32) 
    return x 

एक बड़ा मुद्दा हैश टकराव से बचने के बारे में चिंता करने के लिए। हैश कुंजी को टकराने से रैखिक खोज हो जाएगी क्योंकि शब्दकोश नई वस्तु को स्टोर करने के लिए एक जगह खोजने की कोशिश करता है (इसे अब सुरक्षा समस्या के रूप में पहचाना जा रहा है, और यह व्यवहार आगामी पायथन संस्करणों में बदल रहा है)