चार हस्ताक्षरित पूर्णांक (सी ++)

Question

के लिए हैशिंग फ़ंक्शन मैं अभी एक प्रोग्राम लिख रहा हूं जो एक निश्चित फ़ंक्शन से आउटपुट के रूप में चार हस्ताक्षरित 32-बिट पूर्णांक उत्पन्न करता है। मैं इन चार पूर्णांकों को हैश करना चाहता हूं, इसलिए मैं इस फ़ंक्शन के आउटपुट की तुलना भविष्य के आउटपुट से कर सकता हूं।

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

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

क्या कोई मुझे गुणवत्ता हैश फ़ंक्शन लिखने का तरीका जानने में मदद कर सकता है?

Answer 1

आप चार पूर्णांक को उपयुक्त डेटा संरचना में क्यों स्टोर नहीं करते हैं और उन सभी की तुलना करते हैं? इस मामले में उन्हें धोखा देने का लाभ मेरे लिए संदिग्ध प्रतीत होता है, जब तक भंडारण कोई समस्या न हो।

यदि संग्रहण समस्या है, तो आप here का विश्लेषण किए गए हैश फ़ंक्शंस में से एक का उपयोग कर सकते हैं।

Answer 2

क्योंकि हैशिंग टकराव उत्पन्न कर सकती है, इसलिए आपको इन टकरावों को खोजने के लिए कुंजी को स्मृति में रखना होगा। हैशमैप्स और अन्य मानक डेटास्ट्रक्चर अपने आंतरिक बहीखाता में ऐसा करते हैं।

चूंकि कुंजी बहुत छोटी है, तो हैशिंग के बजाय सीधे कुंजी का उपयोग करें। यह तेज़ होगा और कोई टकराव सुनिश्चित नहीं करेगा।

Answer 3

क्यों हैश? ऐसा लगता है कि एक std :: set या std :: बहु सेट इस प्रकार के आउटपुट को स्टोर करने के लिए बेहतर होगा। आपको बस एक स्ट्रक्चर में चार पूर्णांक लपेटना होगा और एक साधारण तुलना फ़ंक्शन लिखना होगा।

Answer 4

CRC या FNV का उपयोग करने का प्रयास करें। एफएनवी अच्छा है क्योंकि यह तेज़ है और "छोटे" हैश मान प्राप्त करने के लिए बिट्स को फोल्ड करने की परिभाषित विधि है (यानी 12-बिट/24-बिट/आदि)।

128-बिट (4 एक्स 32-बिट) संख्या से 64-बिट हैश उत्पन्न करने का लाभ थोड़ा संदिग्ध है क्योंकि अन्य लोगों ने सुझाव दिया है कि आप मूल मूल्य को केवल एक कुंजी के रूप में उपयोग कर सकते हैं सेट। आप वास्तव में हैश में बिट्स की संख्या को मूल रूप से आपके मूल्यों की संख्या का प्रतिनिधित्व करना चाहते हैं। उदाहरण के लिए, यदि आपके डेटासेट में 100,000 4X32-bit मान हैं, तो शायद आप 17-बिट या 18-बिट हैश मान चाहते हैं, 64-बिट हैश नहीं।

Answer 5

थोड़ा अधिक हो सकता है, लेकिन Boost.Hash पर विचार करें। बहुत सरल कोड और अच्छे मूल्य उत्पन्न करता है।

Answer 6

मैं पूरी तरह से विंको से सहमत हूं - बस उन सभी की तुलना करें। यदि आप अभी भी एक अच्छा हैशिंग फ़ंक्शन चाहते हैं, तो आपको अपने 4 असंगत पूर्णांक के वितरण का विश्लेषण करने की आवश्यकता है। फिर आपको अपने हैशिंग फ़ंक्शन को एक तरह से तैयार करना होगा, परिणाम 32 बिट हैशिंग मान की पूरी श्रृंखला पर भी वितरित किया जाएगा।

एक साधारण उदाहरण - आइए बस मान लें कि अधिकांश समय, प्रत्येक फ़ंक्शन का परिणाम 0 से 255 तक होता है। फिर आप आसानी से प्रत्येक फ़ंक्शन से निम्न 8 बिट्स को अपने हैश में मिश्रित कर सकते हैं। अधिकांश समय, आप सीधे परिणाम प्राप्त करेंगे, कभी-कभी (जब एक फ़ंक्शन एक बड़ा परिणाम देता है) तो आपको टकराव होता है।

इसे समेटने के लिए - बिना किसी जानकारी के 4 कार्यों के परिणाम कैसे वितरित किए जाते हैं, हम एक अच्छे हैशिंग फ़ंक्शन के साथ आपकी सहायता नहीं कर सकते हैं।

Answer 7

यहाँ 4 पूर्णांकों से 1 पूर्णांक के लिए एक काफी उचित हैश समारोह है:

unsigned int hash = in[0]; 
hash *= 37; 
hash += in[1]; 
hash *= 37; 
hash += in[2]; 
hash *= 37; 
hash += in[3]; 

समान रूप से वितरित इनपुट के साथ

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

अन्य विशेषताओं के साथ अन्य हैंश हैं, लेकिन गुणा-द्वारा-गुणा-द्वारा-प्राइम अन्यथा साबित होने तक एक अच्छी शुरुआत है। यदि आप चाहें तो अतिरिक्त के बजाय आप xor के साथ जमा करने का प्रयास कर सकते हैं। किसी भी तरह से, टकराव उत्पन्न करना आसान है (उदाहरण के लिए {1, 0, ए, बी} सभी के लिए {0, 37, ए, बी} के साथ टकराता है, इसलिए आप एक ऐसा प्राइम चुनना चाहेंगे जो आपको लगता है आपके फ़ंक्शन में किसी भी व्यावहारिक कार्यान्वयन बग के साथ कुछ भी नहीं करना है। तो यदि आपके फ़ंक्शन में बहुत से मॉड्यूलो-37 अंकगणित हैं, तो इसके बजाय शायद 1000003 का उपयोग करें।