हैश टेबल/हैश फ़ंक्शन का निर्माण

Question

मैं एक हैश तालिका बनाना चाहता हूं जो कि 1 से 15 बाइट्स तक के बाइट्स के अनुक्रम (स्ट्रिंग्स) में कुंजियों को देखता है।

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

किसी भी सहायता को बहुत अधिक सराहना की जाएगी।

हैश में प्रविष्टियों की अधिकतम संख्या है: 4081 * 15 + 4081 * 14 + ... 4081 = 4081 ((15 * (16))/2) = 489720.

उदाहरण के लिए

तो:

int table[489720]; 

int lookup(unsigned char *key) 
{ 
    int index = hash(key); 
    return table[index]; 
} 

हैश फ़ंक्शन के लिए कुछ अच्छे विकल्प क्या हैं, या मैं एक बनाने के बारे में कैसे जाऊं?

धन्यवाद।

Answer 1

यदि आप एक परिपूर्ण हैश चाहते हैं, तो आप perfect hashing पर विकिपीडिया लेख पढ़कर शुरू कर सकते हैं। यदि आप स्नैग में भागते हैं, तो आप यहां मदद मांग सकते हैं।

Answer 2

यदि तालिका में निवासी स्ट्रिंग्स की औसत संख्या कम है - 10,000 प्रविष्टियों के तहत - एक एसोसिएटिव सरणी एक उचित दृष्टिकोण होगी, यहां तक ​​कि एक आधुनिक सीपीयू आर्किटेक्चर पर एक रैखिक खोज का उपयोग कर भी।

अन्यथा, "सही हैश" बनाने के लिए स्ट्रिंग के प्रत्येक वर्ण का निरीक्षण करने और संभावित सीमा के आधार पर एक अद्वितीय मूल्य की गणना करने की आवश्यकता होती है। उदाहरण के लिए, केवल 26 वर्ण A..Z कुंजी में अनुमति दी जाती है, इस काम करेगा:

int 
hash (const char *key) 
{ 
    int h = 0; 
    while (key && *key) 
     h = h * 26 + (*key++ - 'A'); 
    return h; 
} 

Answer 3

आपका कुंजी अंतरिक्ष बड़े (लगभग 2^(8 * 15)), इसलिए अगर आप चाहते हैं एक है सही हैश, आपको यह जानना होगा कि 489720 वास्तविक कुंजी पहले से दिखाई देगी। फिर भी, उन चाबियों के लिए एक आदर्श हैश ढूंढना व्यावहारिक रूप से असंभव है, भले ही आपने बहुत बड़ी तालिका (ए.के.ए. बहुत कम लोड फैक्टर) की अनुमति दी हो। एकदम सही हैश ढूंढने का एकमात्र तरीका परीक्षण और त्रुटि से है, और एक यादृच्छिक हैश विफल होने की संभावना है जब तक आपकी तालिका 489720^2 प्रविष्टियों के करीब न हो।

मैं अत्यधिक regular (non-perfect) hash और deal with collisions appropriately का उपयोग करने की अत्यधिक अनुशंसा करता हूं, उदा। साथ चेनिंग:

struct entry { 
    unsigned char *key; 
    int value; 
    struct entry *next; 
} *table[1<<20]; 
int lookup(unsigned char *key) { 
    int index = hash(key) % (1<<20); 
    for (struct entry *e = table[index]; e != NULL; e = e->next) { 
    if (!strcmp(key, e->key)) return e->value; 
    } 
    // not found 
} 

मैं भी सुझाव है कि आप इस खुद को लागू नहीं करते - एक c++ hashmap की तरह एक मानक पुस्तकालय का उपयोग करें।

Answer 4

सी तार हैश, मैं हमेशा इस समारोह का उपयोग किया है (% परिणाम अपने हैश तालिका के आकार लेने के लिए):

int hashstring(const char* s) { 
    int key = 0; 
    while (*s) { 
    key = key*37 + *s++; 
    } 
    return key; 
} 

मुझे याद नहीं है जहाँ मैं इसे शुरू से है, लेकिन कई वर्षों में उसने मुझे नीचे जाने नहीं दिया है।