अनॉर्डर्ड मल्टीसेट

Question

के हैश/सीआरसी के लिए एल्गोरिदम मान लें कि मैं बिना हस्ताक्षरित int के अनियंत्रित मल्टीसेट्स का एक अनियमित सेट बनाना चाहता हूं। इसके लिए, मुझे अनियंत्रित मल्टीसेट के हैश की गणना करने के लिए हैश फ़ंक्शन बनाना होगा। वास्तव में, यह सीआरसी के लिए भी अच्छा होना चाहिए।

एक स्पष्ट समाधान है कि वेक्टर में आइटम डालें, उन्हें सॉर्ट करें और परिणाम का हैश वापस करें। ऐसा लगता है, लेकिन यह महंगा है।

एक और तरीका मूल्यों को xor करना है, लेकिन जाहिर है कि यदि मेरे पास एक आइटम दो बार है या कोई भी परिणाम समान नहीं होगा - जो अच्छा नहीं है।

कोई विचार यह है कि मैं इस सस्ता को कैसे कार्यान्वित कर सकता हूं - मेरे पास एक ऐसा एप्लिकेशन है जो हजारों सेटों और अपेक्षाकृत बड़े लोगों के लिए यह हजारों करेगा।

Answer 1

आंतरिक बहुआयामी को मूल्य-> गिनती हैश मानचित्र के रूप में कार्यान्वित करें।

यह आपको समस्या से बचने की अनुमति देगा कि तत्वों की संख्या भी निम्न तरीके से xor के माध्यम से रद्द हो जाती है: प्रत्येक तत्व को xor-ing करने के बजाय, आप गिनती और मान से एक नया नंबर बनाते हैं (उदाहरण के लिए उन्हें गुणा करना), और फिर आप xor का उपयोग कर पूर्ण हैश बना सकते हैं।

Answer 2

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

एक ऑपरेशन जो अंतिम मानदंडों के अलावा सभी को पूरा करता है, अतिरिक्त है। बस तत्वों को योग करें। राशि को बाध्य रखने के लिए, अपने हैश मान का आकार योग मॉड्यूल करें। (E.g. modulo 2 64-बिट हैश के लिए।) यह सुनिश्चित करने के लिए कि शून्य मान डालने या हटाने से हैश बदल जाता है, पहले प्रत्येक मान में एक जोड़ें।

योग की कमी यह है कि दो परिवर्तन आसानी से रद्द कर सकते हैं। जैसे 1 3 के साथ 1 3 को प्रतिस्थापित करना 2. इसे संबोधित करने के लिए, आप एक ही दृष्टिकोण का उपयोग कर सकते हैं और प्रविष्टियों के बहुपद को जोड़ सकते हैं, फिर भी कम्यूटिटीविटी को बनाए रखते हैं। जैसे x + 1 को सारांशित करने के बजाय, आप x + x + 1 जोड़ सकते हैं। अब एक ही राशि के साथ परिवर्तनों के सेट को संकुचित करना अधिक कठिन है।

Answer 3

std::unordered_multiset<int> के लिए एक उचित हैश फ़ंक्शन यहां है यदि कंप्यूटेशंस को एक बड़ा प्राइम मोड ले लिया गया तो बेहतर होगा लेकिन विचार खड़ा है।

#include <iostream> 
#include <unordered_set> 

namespace std { 
    template<> 
    struct hash<unordered_multiset<int>> { 
     typedef unordered_multiset<int> argument_type; 
     typedef std::size_t result_type; 

     const result_type BASE = static_cast<result_type>(0xA67); 

     result_type log_pow(result_type ex) const { 
      result_type res = 1; 
      result_type base = BASE; 
      while (ex > 0) { 
       if (ex % 2) { 
        res = res * base; 
       } 
       base *= base; 
       ex /= 2; 
      } 
      return res; 
     } 

     result_type operator()(argument_type const & val) const { 
      result_type h = 0; 
      for (const int& el : val) { 
       h += log_pow(el); 
      } 
      return h; 
     } 
    }; 
}; 

int main() { 
    std::unordered_set<std::unordered_multiset<int>> mySet; 
    std::unordered_multiset<int> set1{1,2,3,4}; 
    std::unordered_multiset<int> set2{1,1,2,2,3,3,4,4}; 
    std::cout << "Hash 1: " << std::hash<std::unordered_multiset<int>>()(set1) 
       << std::endl; 
    std::cout << "Hash 2: " << std::hash<std::unordered_multiset<int>>()(set2) 
       << std::endl; 
    return 0; 
} 

Output:

Hash 1: 2290886192 
Hash 2: 286805088 

यह एक प्रमुख पी होता है, टकराव की संख्या 1/p के लिए आनुपातिक है। मुझे यकीन नहीं है कि विश्लेषण दो की शक्तियों के लिए क्या है। जब आप पूर्णांक x डालें/हटाते हैं तो आप बेस^x जोड़कर/घटाकर हैश कुशल को अपडेट कर सकते हैं।