हैश एल्गोरिदम 2 बाइट-मूल्यों

Question

मैं एक माइक्रो जो सी

में

प्रोग्राम किया जाता के साथ एक इलेक्ट्रॉनिक परियोजना पर काम कर रहा हूँ करने के लिए 16 बाइट-मान मैप करने के मैं कुछ आईडी और में उसके संबंधित जानकारी स्टोर करने की जरूरत है एक फ्लैश मेमोरी (एसडी)। ये आईडी 16 बाइट लंबी हैं इसलिए 2^128 संभावित मान हैं। हालांकि वे 16 बाइट हैं, केवल 50000 (अद्वितीय) मानों का उपयोग किया जाएगा। एसडी में सभी संभावित (2^128) आईडी स्टोर करना शारीरिक रूप से असंभव है।

मैं केवल 50000 उपयोग किए गए मानों को स्टोर कर सकता हूं लेकिन फिर मुझे उन सभी को खोजने के लिए उन सभी को (सबसे बुरी तरह) पार करना होगा। इसके अलावा, उनमें से प्रत्येक के लिए 16-बाइट मान तुलना की गणना की जानी चाहिए जो इसे धीमा कर देती है।

तो मुझे लगता है कि मुझे किसी प्रकार का (हैश?) फ़ंक्शन चाहिए जो 2^128 मानों को 50000 (मानचित्र 16 बाइट्स से 2 बाइट्स) पर मैप करता है। यह स्पष्ट है कि कुछ मूल मान एक ही मूल्य/अनुक्रमणिका पर मैप करेंगे। विचार यह है कि जब मुझे आईडी मिलती है, तो मैं एक हैश फ़ंक्शन लागू करता हूं जो मुझे 0 और ~ 50000 (0-65535) के बीच एक सूचकांक देता है। उस इंडेक्स के साथ मैं सीधे एसडी सेक्टर तक पहुंच सकता हूं जिसमें आईडी और इसकी संबंधित जानकारी संग्रहीत की जाती है। जैसा कि मैंने इंगित किया है, वह सूचकांक स्मृति की स्थिति को संदर्भित करेगा जहां विभिन्न आईडी एक ही इंडेक्स मूल्य पर मैप किए जाने वाले कुछ अलग-अलग आईडी के कारण सह-अस्तित्व में रहेंगे। मुझे सही आईडी मिलनी होगी, लेकिन 50000 मूल के बजाय इसकी तुलना केवल कुछ ही होगी।

किसी भी विचार/राय की वास्तव में सराहना की जाएगी।

अग्रिम धन्यवाद।

Answer 1

अपने 128 बिट मूल्य में बिट्स Assumign "समान रूप से वितरित" कर रहे हैं, तो आप बस कुछ इस तरह कर सकता है:

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash ^= (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

संभवतः हैं अन्य अधिक चतुर तरीके हैं, लेकिन यह एक बहुत ही सरल है, और काफी अच्छी तरह से काम कर सकते हैं।

Answer 2

बस वास्तविक आईडी के 16 एमएसबी का उपयोग करें। यह गूंगा है लेकिन आपके विवरण के साथ यह काम करेगा।

Answer 3

ज़रूर चटाई का ठीक है, यह हालांकि, एक प्रमुख के उपयोग के द्वारा कम टक्कर में परिणाम चाहिए जहां uuid[x] == uuid[y] (और x!=y)

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    // hash *= 31; //next line does this, note 31 is a prime 
    hash = (hash << 5) - hash; 
    hash += (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

या इस संस्करण भी बेहतर है, क्योंकि यह संघर्ष को कम कर देता है, जहां की XOR पहले 16 बिट्स और दूसरे 16 बिट्स मैच।

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] & 0xffff; 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] >> 16; 
} 

Answer 4

आईडी 16 बाइट लंबा है, इसलिए मुझे लगता है कि यह एक ASCII स्ट्रिंग में संग्रहीत है, इसलिए ELFhash शायद काम करता है।

int ELFhash(char *key) { 
    unsigned long h = 0; 
    while(*key) { 
     h = (h << 4) + *key++; 
     unsigned long g = h & 0xf0000000L; 
     if (g) h ^= g >> 24; 
     h &= -g; 
    } 
    return h & M; 
} 

जहां एम 65536 की तुलना में एक अभाज्य संख्या में छोटा है, या 50000.

यह क्योंकि वे एक विशिष्ट meaaing के लिए प्रतिनिधित्व करते हैं कि कई आईडी तार के उपसर्ग ही के हैं, तो आप होना चाहिए अधिक होने की संभावना है टकराव को रोकने के लिए अधिक सावधान, या लिंक्ड सूची बहुत लंबी होगी।