हैश फ़ंक्शन मानों के वितरण में सुधार

Question

मान लीजिए कि मेरे पास तारों की एक बड़ी संख्या है (प्रत्येक के 50 वर्णों के 10 अरब तारों का कहना है)। मैं तारों को बिल्कुल 10 बाल्टी में वितरित करना चाहता हूं। प्रत्येक बाल्टी में तारों का लगभग 10% होना चाहिए। हैश फ़ंक्शन एच() के साथ मैं कर सकता हूं:

int bucket_for_s = h(s) % 10 

हालांकि यह वितरण की समानता के बारे में कोई गारंटी नहीं देता है। मान लीजिए कि मैं उपरोक्त सभी तारों के लिए करता हूं और पाते हैं कि 30% बाल्टी 1 पर जाते हैं, 5% बाल्टी 2 पर जाते हैं और इसी तरह। मेरा सवाल है:

एच() वितरण दिया गया है, क्या एक नया हैश फ़ंक्शन h2() उत्पन्न करने का कोई तरीका है जो तारों को समान रूप से वितरित करेगा?

वैकल्पिक रूप से, क्या ऐसी प्रक्रिया है जो हैश फ़ंक्शन h2(), h3() की श्रृंखला उत्पन्न कर सकती है ... ताकि 1: प्रत्येक हैश फ़ंक्शन पिछले एक और 2 से बेहतर हो: मुझे केवल एक उत्पन्न करना होगा हैश कार्यों की उचित संख्या?

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

Answer 1

क्रिप्टोग्राफ़िक रूप से ठोस हैश फ़ंक्शंस पहले से ही हैश आउटपुट के सभी बिट्स में एक बहुत ही वितरण होना चाहिए।

आप जावा के hashCode() जो मेरा मानना ​​है कि लगता है कि कुछ प्रयोग कर रहे हैं

तरह

रों [0] * 31^(n-1) + S 1 * 31^(n-2) + ... + एस [एन -1]

आप आदर्श हैश वितरण से कम देख सकते हैं।

एक क्रिप्टोग्राफ़िक हैश जैसे SHA-256 के आधार पर उपयोग करने का प्रयास करें।

Google का City HashSHA-256 से कम वितरण किया गया है, लेकिन यह बहुत तेज है। यह कम कम्प्यूटेशनल व्यय पर पर्याप्त वितरण प्रदान कर सकता है।

Answer 2

कैसे हल करने के लिए पर एक दिशा यह 10 के बजाय 2 बाल्टी या एन

करने के लिए सरल आप आवंटन बाल्टी 1 के लिए p और बाल्टी 2 के लिए q, और निश्चित रूप p + q = 1 के साथ एक वितरण h() प्राप्त मान लीजिए।

  h()   h2() 

       /bucket1 p*p1 
     bucket1 p - 
    /   \ bucket2 p*q1 
x - 
    \   /bucket1 q*p2 
     bucket2 q - 
       \ bucket2 q*q2 

जहां हमारा लक्ष्य है के लिए भी संभावना: बाल्टी 1 दिए गए यह संभावना p1, q1 (p1+q1=1) और बाल्टी 2 दिया इसे इस्तेमाल करता है संभावना p2, q2 (p2+q2=1) उपयोग करता है:

अब, लक्ष्य है कि मानकों p1, q1, p2, q2 साथ इस तरह के वितरण h2() को मिल रहा है सभी 2 बाल्टी के लिए:

p*q1 + q*p2 = 1/2 (total chances for bucket 1 after h2()) 
p*q2 + q*q2 = 1/2 (total chances for bucket 2 after h2()) 

और पहले की तरह:

p1 + q1 = 1 
p2 + q2 = 1 

यह 4 चर के साथ 4 समीकरणों की रैखिक प्रणाली है (वितरण वितरण h2())।

नोट: 10 बाल्टी के साथ हमारे पास h()p1, p2, ..., p10 के साथ p1 + p2 + ... + p10 = 1 होगा। यदि बाल्टी की संख्या> 2 अज्ञातों की तुलना में कम समीकरण हैं: p1 जैसे प्रत्येक आवंटन के लिए आपको का p11+p12+...+p1_10=1 के साथ एक घटक मिलता है)। इस प्रकार 10 बाल्टी के लिए h2() के 100 अज्ञात पैरामीटर और केवल 20 समीकरण हैं। इसका मतलब है कि कुछ मानदंड (लेकिन व्यवहार्य) मान शेष पैरामीटर के लिए समीकरणों को हल करने से पहले h2() के 80 पैरामीटर को दिए जा सकते हैं। सुंदर नहीं है लेकिन अभी भी एक समाधान है।

Answer 3

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

संभावित उम्मीदवारों

तुम क्या वर्णित से, हैश फंक्शन नियतात्मक होना चाहिए (अपने "हैलो" उदाहरण) - यह सब हैश फंक्शन के लिए सच है - और एक और भी वितरण उत्पन्न करनी चाहिए।

SHA-256 जैसे क्रिप्टोग्राफ़िक हैश को आपकी आवश्यकताओं को पूरा करना चाहिए, क्योंकि यह "हैलो" और "हेलो" जैसे कुछ ही अलग इनपुट के लिए पूरी तरह से अलग हैश का उत्पादन करता है। हैश पर मॉड्यूलो (%) ऑपरेशन का उपयोग करके, तब आप जितनी चाहें उतनी बाल्टी ले सकते हैं (कोर्स की हैश की संख्या से अधिक नहीं)।

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

आप तथाकथित "गैर-क्रिप्टोग्राफ़िक हैश फ़ंक्शंस" देखना चाहते हैं, जिनके पास आराम से गुण हैं और वे लुकअप के लिए अधिक डिज़ाइन किए गए हैं - इसलिए उन्हें गति के लिए अनुकूलित किया गया है। जावा का hashCode(), MurmurHash और पहले से ही उल्लेख किया गया सिटीशैश (Google announcement) एक अच्छी शुरुआत हो सकती है।

हैश फंक्शन बनाम हैश

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

मान लें कि आप वर्कलोड के वितरण के लिए हैश के वितरण का भी उपयोग करना चाहते हैं, इसे निम्न रणनीति का उपयोग करके दूर किया जा सकता है। प्रत्येक बाल्टी को एक कार्य पैकेज या नौकरी के रूप में सोचें जिसे किसी भी उपलब्ध मशीन द्वारा संसाधित किया जा सकता है। यदि आपके पास मशीनों की तुलना में अधिक काम पैकेज हैं (आइए 10 मशीनों के लिए 20 या 30 पैकेज कहें), आप लचीला शेड्यूलिंग के लिए अनुमति देते समय वर्कलोड को समान रूप से वितरित कर सकते हैं। जब मशीन ए को बड़े आकार के पैकेजों में से एक मिलता है और इसे संसाधित करने में कुछ समय लगता है, तो मशीन बी एक ही समय में दो छोटे या मध्यम आकार के पैकेजों को संसाधित कर सकता है, इस प्रकार oversized पैकेज का समग्र प्रदर्शन प्रभाव कम हो जाता है।

Answer 4

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

को देखते हुए यह एक सैद्धांतिक सवाल यह है कि, एक दृष्टिकोण होगा:

रंग का शोर

Whitening आप int bucket_for_s

int bucket_for_s = put_in_bucket(s) 

put_in_bucket: 
    x = h(s) % 10 + 10*((h(s)/10)%10) 
    if(0<=x<=2) return 0 
    if(3<=x<=5) return 1 
    if(6<=x<=9) return 2 
    #The previous bucket_1 (30%) is now split into 3 buckets 
    if(10<=x<=27) return 0 
    #The previous bucket_2 (5%) is now enlarged 
    #to incorporate more of the small old buckets (or parts of buckets) 
    #This bucket is now bucket_4 
    #... more of the same 
    if(83<=x<=99) return 9 

साथ खेल सकते हैं आप जब तक आप एक और अंकों से इस विचार का विस्तार कर सकते आपके "रिज़ॉल्यूशन" से खुश हैं

आप put_in_bucket से तर्क ले सकते हैं और इसे डाल सकते हैं h2(s)h1(s) का उपयोग कर।

इस दृष्टिकोण का उपयोग सफेद शोर (या इस मामले में रंगीन शोर को सफ़ेद करने) के लिए किया जाता है, इसलिए नाम।