मिश्रित संख्यात्मक और शाब्दिक पहचानकर्ताओं के लिए सर्वश्रेष्ठ हैश फ़ंक्शन

Question

प्रदर्शन कारणों से मुझे समूहों में स्ट्रिंग द्वारा पहचाने गए ऑब्जेक्ट्स के सेट को विभाजित करने की आवश्यकता है। वस्तुओं या तो एक संख्या से या डॉट्स पहचानकर्ता के कुछ हिस्सों को अलग करने के साथ उपसर्ग (योग्य) के रूप में एक स्ट्रिंग से पहचाना जा सकता है:

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

संख्यात्मक पहचानकर्ता 1 से कई लाखों लोगों के लिए कर रहे हैं। पाठ पहचानकर्ताओं के पास समान नाम स्पेस उपसर्ग (एनएस 1 :) और उसी पथ उपसर्ग (edit.box।) के साथ बहुत से प्रारंभ होने की संभावना है।

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

ऐसे लाखों ऐसे पहचानकर्ता हैं, लेकिन इसका उद्देश्य हैश फ़ंक्शन के आधार पर 1-2 हजार समूहों के समूहों में विभाजित करना है।

Answer 1

दो अच्छे हैश फ़ंक्शंस दोनों को मूल्यों के समान स्थान में मैप किया जा सकता है, और आम तौर पर उन्हें संयोजित करने के परिणामस्वरूप कोई नई समस्या नहीं होती है।

तो अपने हैश समारोह इस तरह दिख सकता है: अपने पूर्णांक में से किसी का एकत्रीकरण के आसपास निश्चित मूल्यों सापेक्ष एन, जहां एन बकेट की संभावित संख्या है वहाँ जब तक

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

, तो int_hash सिर्फ अपने इनपुट लौट सकते हैं।

एक स्ट्रिंग हैश चुनना एक उपन्यास समस्या नहीं है। "Djb2" (http://www.cse.yorku.ca/~oz/hash.html) या इसी तरह की कोशिश करें, जब तक कि आपके पास अश्लील प्रदर्शन की आवश्यकता न हो।

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

यदि आप ऐसा करते हैं, और हैश अप्रत्याशित रूप से खराब प्रदर्शन नहीं करता है, और आपने अपने लाखों हैश मूल्यों को कुछ हज़ार बाल्टी में डाल दिया है, तो बाल्टी आबादी सामान्य रूप से वितरित की जाएगी, जिसका मतलब है (कई मिलियन/कुछ हजार) और भिन्नता 1/12 (कुछ हज़ार)^2

प्रति बाल्टी की औसत 1500 प्रविष्टियों के साथ, जो मानक विचलन को लगभग 430 के आसपास बनाता है। सामान्य वितरण का 9 5% मतलब के 2 मानक विचलन के भीतर होता है , इसलिए आपकी 9 5% बाल्टी में 640-2360 प्रविष्टियां होंगी, जब तक कि मैंने अपनी रकम गलत नहीं की है। क्या यह पर्याप्त है, या क्या आपको बाल्टी को अधिक बारीकी से समान आकार की आवश्यकता है?

Answer 2

आप शायद sha1 के साथ सुरक्षित रहेंगे और जो भी आकार आप चाहते हैं उसे छोटा कर देंगे।

यह बेहद कुशल नहीं होगा, लेकिन शायद हैश फ़ंक्शन एक बाधा नहीं होगी?

Answer 3

मुझे लगता है कि सीआरसी 16 इन तारों पर उपयोग करने के लिए एक उचित हैश होगा, और समूहों को 1-2 हजार से बड़ा नहीं जाना चाहिए।

यह हैश तालिका को लगभग 1 एमबी + बनाना चाहिए, लेकिन आपके पास * 4 बाइट्स हैं, इसलिए हम 50 एमबी बोल रहे हैं, और फिर आपके पास सभी वास्तविक डेटा भी संग्रहीत किए जा रहे हैं, जो बहुत छोटे थे।