सी

Question

में एक सरणी (बनाम लिंक्ड सूची) हैशटेबल कार्यान्वयन की तलाश में है, मैं सी में हैशटेबल कार्यान्वयन की तलाश में हूं जो लिंक की सूचियों के बजाय अपनी वस्तुओं को (twodimensional) arrays में संग्रहीत करता है। यानी अगर टकराव होता है, तो टक्कर पैदा करने वाली वस्तु को सिर पर धक्का देने और लिंक की गई सूची के पहले तत्व की बजाय अगली मुक्त पंक्ति अनुक्रमणिका में संग्रहीत किया जाएगा।

प्लस, ऑब्जेक्ट्स को पॉइंटर्स द्वारा संदर्भित करने के बजाय, हैशटेबल में कॉपी किया जाना चाहिए। (वस्तुएं कार्यक्रम के पूरे जीवनकाल के लिए नहीं रहती हैं लेकिन तालिका करता है)।

मुझे पता है कि इस तरह के कार्यान्वयन में गंभीर दक्षता की कमी हो सकती है और यह "हैशिंग का मानक तरीका" नहीं है, लेकिन जैसा कि मैं एक बहुत ही विशेष प्रणाली-वास्तुकला पर काम करता हूं, मुझे उन विशेषताओं की आवश्यकता होती है।

धन्यवाद

Answer 1

एक सुपर सरल कार्यान्वयन:

char hashtable[MAX_KEY][MAX_MEMORY]; 
int counts[MAX_KEY] = {0}; 

/* Inserting something into the table */ 
SomeStruct* some_struct; 
int hashcode = compute_code(some_struct); 
int size = sizeof(SomeStruct); 
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size); 
++counts[hashcode]; 

MAX_MEMORY के खिलाफ जांच करने के लिए मत भूलना।

Answer 2

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

Answer 3

यह सी में नहीं है लेकिन सी ++ में है, लेकिन Google Sparse Hash पर एक नज़र डालें - आपको कुछ विचार दे सकते हैं। मुख्य आवश्यकता यह है कि संग्रहीत वस्तु null होने का एक तरीका है।