64 बिट से 10 बिट्स के लिए हैश फ़ंक्शन

Question

मुझे एक हैश फ़ंक्शन चाहिए जो लंबी संख्या (64 बिट्स) लेता है और 10 बिट्स का परिणाम उत्पन्न करता है। इस उद्देश्य के लिए सबसे अच्छा हैश फ़ंक्शन क्या है। इनपुट मूल रूप से चर के पते हैं (पते 64 बिट्स या लिनक्स पर 8 बाइट्स हैं), इसलिए मेरे उद्देश्य फ़ंक्शन को उस उद्देश्य के लिए अनुकूलित किया जाना चाहिए।

Answer 1

मैं इस तरह somethig कहेंगे:

uint32_t hash(uint64_t x) 
{ 
    x >>= 3; 
    return (x^(x>>10)^(x>>20)) & 0x3FF; 
} 

ऐसा न हो कि महत्वपूर्ण 3 बिट्स के रूप में सबसे चर 4 बाइट या 8-बाइट गठबंधन कर रहे हैं, बहुत ही उपयोगी नहीं हैं, इसलिए हम उन्हें निकाल देते। फिर हम अगले 30 बिट्स लेते हैं और 10 बिट्स के ब्लॉक में उन्हें एक साथ (एक्सओआर) मिलाते हैं।

स्वाभाविक रूप से, आप (x>>30)^(x>>40)^(x>>50) भी ले सकते हैं लेकिन मुझे यकीन नहीं है कि वे अभ्यास में कोई फर्क नहीं पड़ेगा।

Answer 2

अधिकांश वितरण के लिए सर्वश्रेष्ठ एक प्राइम द्वारा संशोधित है, 1021 सबसे बड़ा 10-बिट प्राइम है। कम बिट्स को पट्टी करने की कोई ज़रूरत नहीं है।

static inline int hashaddress(void *v) 
{ 
     return (uintptr_t)v % 1021; 
} 

अगर आपको लगता है प्रदर्शन चिंता का विषय हो सकता है, हाथ पर कुछ विकल्पों की है और अपने वास्तविक कार्यक्रम में उन्हें दौड़। Microbenchmarks बर्बाद कर रहे हैं; कुछ चक्रों का अंतर कैश प्रभावों और आकार के मामलों से घिरा हुआ लगभग निश्चित है।

Answer 3

मैंने लिखा एक खिलौना कार्यक्रमके ढेर, डेटा क्षेत्र है, और ढेर पर कुछ वास्तविक पते को देखने। असल में मैंने 4 ग्लोबल्स, 4 स्थानीय लोगों की घोषणा की और 2 mallocs किया। पते को प्रिंट करते समय मैंने पिछले दो बिट्स को गिरा दिया।

20125e8 
20125e6 
20125e7 
20125e4 
3fef2131 
3fef2130 
3fef212f 
3fef212c 
25e4802 
25e4806 

क्या यह मुझसे कहता है:: यहाँ रन में से एक से एक उत्पादन होता है

1. LSB इस निर्गम (पते के 3 बिट) अक्सर 'चालू' है में और 'ऑफ'। तो हैश की गणना करते समय मैं इसे छोड़ नहीं दूँगा। 2 एलएसबी छोड़ना पर्याप्त लगता है।
2. हम यह भी देखते हैं कि निचले 8-10 बिट्स में अधिक एन्ट्रॉपी है। हमें का उपयोग करना चाहिए कि हैश की गणना करते समय।
3. हम जानते हैं कि 64 बिट मशीन पर, virtual addresses are never more than 48 bits wide।

मैं अगले करना होगा क्या:

/* Drop two LSBs. */ 
a >>= 2; 

/* Get rid of the MSBs. Keep 46 bits. */ 
a &= 0x3fffffffffff; 

/* Get the 14 MSBs and fold them in to get a 32 bit integer. 
The MSBs are mostly 0s anyway, so we don't lose much entropy. */ 
msbs = (a >> 32) << 18; 
a ^= msbs; 

अब हम एक decent 'half avalanche' hash function के माध्यम से इस गुजरती हैं, बजाय हमारे अपने रोलिंग की ।

uint32_t half_avalanche(uint32_t a) 
{ 
    a = (a+0x479ab41d) + (a<<8); 
    a = (a^0xe4aa10ce)^(a>>5); 
    a = (a+0x9942f0a6) - (a<<14); 
    a = (a^0x5aedd67d)^(a>>3); 
    a = (a+0x17bea992) + (a<<7); 
    return a; 
} 

एक 10 बिट हैश के लिए, uint32_t लौटे 10 MSBs का उपयोग करें: 'आधा हिमस्खलन' इनपुट के प्रत्येक बिट एक ही स्थान पर बिट्स प्रभावित करने के लिए और मौका उच्च हो जाता है का मतलब है।हैश फ़ंक्शन ठीक काम करता रहता है यदि आप NN बिट हैश के लिए एमएसबी चुनते हैं, जो प्रत्येक अतिरिक्त बिट के साथ बाल्टी गिनती को प्रभावी ढंग से दोगुना करते हैं।

मैं थोड़ा ऊब गया था, इसलिए मैंने इसके लिए एक खिलौना बेंचमार्क लिखा। कुछ भी फैंसी नहीं है, यह ढेर पर स्मृति का एक गुच्छा आवंटित करता है और ऊपर वर्णित हैश की कोशिश करता है। स्रोत here से हो सकता है। एक उदाहरण परिणाम:

1024 बाल्टी, 256 मूल्यों उत्पन्न, 29 collissions
1024 बाल्टी, 512 मूल्यों उत्पन्न, 103 collissions
1024 बाल्टी, 1024 मान उत्पन्न, 370 collissions

अगला: मैंने अन्य दो हैशों का उत्तर यहां दिया। दोनों के पास समान प्रदर्शन है। ऐसा लगता है: बस सबसे तेज़ चुनें;)