std :: हैश

Question

के साथ अप्रत्याशित टकराव मुझे पता है कि 32 बी int में स्ट्रिंग की असीमित संख्या टकराव उत्पन्न करनी चाहिए, लेकिन मुझे हैशिंग फ़ंक्शन से कुछ अच्छा वितरण की उम्मीद है।

क्या यह अजीब बात नहीं है कि इन 2 तारों में एक ही हैश है?

size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
//hash0 == hash1 

मैं जानता हूँ कि मैं boost::hash<std::string> या दूसरों का उपयोग कर सकते हैं, लेकिन मैं पता है कि std::hash साथ कुछ गड़बड़ है चाहता हूँ। क्या मैं इसे गलत इस्तेमाल कर रहा हूँ? क्या मुझे किसी भी तरह से "बीज" नहीं करना चाहिए?

Answer 1

std::hash के आपके उपयोग के साथ गलत कुछ भी नहीं है: मैं अलग हैश मान (जीसीसी 4.5) मिलता है। समस्या यह है कि विज़ुअल स्टूडियो 2010 के साथ बंडल किए गए मानक लाइब्रेरी कार्यान्वयन द्वारा प्रदान की गई विशेषज्ञता std::hash<std::string> केवल हैश मान (संभवतः प्रदर्शन कारणों के लिए) निर्धारित करने के लिए स्ट्रिंग के वर्णों का एक सबसेट लेता है। संयोग से 14 वर्णों वाली स्ट्रिंग का अंतिम चरित्र इस सेट का हिस्सा नहीं है, यही कारण है कि दोनों तार एक ही हैश मान उत्पन्न करते हैं।

जहां तक ​​मुझे पता है कि यह व्यवहार मानक के अनुरूप है, की मांग करता है केवल उसी तर्क के साथ हैश फ़ंक्शन पर एकाधिक कॉल हमेशा एक ही मान को वापस करनी चाहिए। हालांकि, हैश टक्कर की संभावना न्यूनतम होना चाहिए। वीएस -2010 कार्यान्वयन अनिवार्य हिस्सा को पूरा करता है, फिर भी वैकल्पिक एक के लिए खाते में विफल रहता है।

विवरण के लिए, हेडर फ़ाइल xfunctional (मेरी प्रतिलिपि में लाइन 869 से शुरू) में कार्यान्वयन देखें और सी ++ मानक (latest public draft) के §17.6.3.4 में कार्यान्वयन देखें।

यदि आपको तारों के लिए बेहतर हैश फ़ंक्शन की आवश्यकता है, तो आपको इसे स्वयं लागू करना चाहिए। यह वास्तव में not that hard है।

Answer 2

आप बीज हैशिंग फ़ंक्शन नहीं करते हैं, आप केवल "उन्हें" नमक कर सकते हैं।

फ़ंक्शन का उपयोग सही तरीके से किया जाता है और यह टकराव केवल भाग्यशाली हो सकता है।

आप यह नहीं बता सकते कि हैशिंग फ़ंक्शन को समान रूप से वितरित नहीं किया जाता है जब तक कि आप यादृच्छिक कुंजी के साथ बड़े पैमाने पर परीक्षण नहीं करते हैं।

Answer 3

टीआर 1 हैश फ़ंक्शन और नवीनतम मानक तारों जैसी चीजों के लिए उचित ओवरलोड को परिभाषित करता है। जब मैं std :: tr1 :: हैश (g ++ 4.1.2) का उपयोग करके यह कोड चलाता हूं, तो मुझे इन दो तारों के लिए अलग हैश मान मिलते हैं।

Answer 4

आपको संभावित हैश मान प्राप्त करना चाहिए।

hashtest.cpp

#include <string> 
#include <iostream> 
#include <functional> 
int main(int argc, char** argv) 
{ 
size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n"; 
return 0; 
} 

आउटपुट

# g++ hashtest.cpp -o hashtest -std=gnu++0x 
# ./hashtest 
16797002355621538189 != 16797001256109909978 

Answer 5

सटीक हैश एल्गोरिदम मानक द्वारा निर्दिष्ट नहीं है, इसलिए परिणाम भिन्न होंगे। वीसी 10 द्वारा उपयोग किया जाने वाला एल्गोरिदम अक्षरों को खाते में नहीं लेता है यदि स्ट्रिंग 10 वर्णों से अधिक है; 1 + s.size()/10 की वृद्धि के साथ अग्रिम। यह कानूनी है, हालांकि क्यूओआई दृष्टिकोण से, बल्कि निराशाजनक है; ऐसे हैश कोड डेटा के कुछ विशिष्ट सेट (जैसे यूआरएल) के लिए बहुत खराब प्रदर्शन करने के लिए जाने जाते हैं।

FNV हैश:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = (16777619 * result) 
        ^static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

Mersenne प्रधानमंत्री हैश:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = 127 * result 
        + static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

(FNV मैं दृढ़ता से आप या तो एक FNV हैश या एक एक Mersenne प्रधानमंत्री के आधार पर के साथ बदलने के सुझाव देंगे हैश माना जाता है कि बेहतर है, लेकिन Mersenne प्रधानमंत्री हैश मशीनों का एक बहुत पर तेजी से हो जाएगा, क्योंकि 127 से गुणा अक्सर काफी तेजी 2166136261. से गुणा करने से है)

+०१२३५१६४१०