unordered_map - हैश फ़ंक्शन का कोई प्रभाव नहीं है

Question

निम्नलिखित हैश फ़ंक्शन (जो निरंतर 0 देता है) में कोई प्रभाव नहीं पड़ता है?

के बाद से हैश फंक्शन निरंतर लौटा रहा है, मैं के रूप में उत्पादन सभी मूल्यों 3. होने के लिए हालांकि, यह विशिष्ट, एक अनूठा मूल्य के लिए std::vector मान मैप करने के लिए अपने हैश समारोह निरंतर किया जा रहा है की परवाह किए बिना लगता है उम्मीद कर रहा था।

#include <iostream> 
#include <map> 
#include <unordered_map> 
#include <vector> 


// Hash returning always zero. 
class TVectorHash { 
public: 
    std::size_t operator()(const std::vector<int> &p) const { 
    return 0; 
    } 
}; 

int main() 
{ 
    std::unordered_map<std::vector<int> ,int, TVectorHash> table; 

    std::vector<int> value1({0,1}); 
    std::vector<int> value2({1,0}); 
    std::vector<int> value3({1,1}); 

    table[value1]=1; 
    table[value2]=2; 
    table[value3]=3; 

    std::cout << "\n1=" << table[value1]; 
    std::cout << "\n2=" << table[value2]; 
    std::cout << "\n3=" << table[value3]; 

    return 0; 
} 

प्राप्त उत्पादन:

1=1 
2=2 
3=3 

अपेक्षित उत्पादन:

1=3 
2=3 
3=3 

मैं हैश के बारे में क्या याद आ रही है?

Answer 1

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

template< 
    class Key, 
    class T, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator< std::pair<const Key, T> > 
> class unordered_map; 

क़मी बनाने की मशीन के बाद अगले टेम्पलेट पैरामीटर कुंजी तुलनित्र है। व्यवहार कि आप उम्मीद कर पाने के लिए आपको कुछ इस तरह करना है जाएगा:

class TVectorEquals { 
public: 
    bool operator()(const std::vector<int>& lhs, const std::vector<int>& rhs) const { 
     return true; 
    } 
}; 

std::unordered_map<std::vector<int> ,int, TVectorHash, TVectorEquals> table; 

अब अपने नक्शे एक भी तत्व होगा और अपने सभी परिणामों 3 हो जाएगा।

Answer 2

एक साईं हैश तालिका कार्यान्वयन को हैश टकराव की उपस्थिति में भी जानकारी खोना नहीं चाहिए। ऐसी कई तकनीकें हैं जो टकराव के संकल्प की अनुमति देती हैं (आमतौर पर डेटा अखंडता पर रनटाइम प्रदर्शन को बंद कर देती हैं)। जाहिर है, std::unordered_map इसे लागू करता है।

देखें: Hash Collision Resolution

Answer 3

एक अनुमानित कुंजी तुलनात्मक वर्ग जोड़ें।

class TComparer { 
public: 
    bool operator()(const std::vector<int> &a, const std::vector<int> &b) const { 
     return true; // this means that all keys are considered equal 
    } 
}; 

इस तरह यह प्रयोग करें:

std::unordered_map<std::vector<int> ,int, TVectorHash, TComparer> table; 

फिर अपने कोड के बाकी अपेक्षा के अनुरूप काम करेंगे।