हैश मैप लुकअप के लिए अनुकूलित

Question

मैं कुछ मानचित्र ढूंढ रहा हूं जिसमें निश्चित कुंजी (प्रारंभिक समय के दौरान तय) है और यह तेज़ी से दिखता है। यह बाद में तत्व जोड़ने/अपडेट करने का समर्थन नहीं कर सकता है। क्या कुछ एल्गोरिदम है जो चाबियों की सूची देखता है और एक फ़ंक्शन तैयार करता है ताकि बाद में देखने के लिए तेज़ हो। मेरे मामले में, चाबियाँ तार हैं।

अद्यतन:

कुंजी संकलन समय पर नहीं जाना जाता है। लेकिन आवेदन के प्रारंभिक समय के दौरान। बाद में कोई और सम्मिलन नहीं होगा लेकिन बहुत सारे लुक-अप होंगे। इसलिए मैं अनुकूलित करने के लिए लुक-अप चाहता हूं।

Answer 1

CMPH आप जो खोज रहे हैं हो सकता है। असल में यह gperf के बिना संकलन-समय पर सेट की आवश्यकता है।

हालांकि std::unordered_map निश्चित रूप से सी ++ 11 के रूप में संभवतः कुछ टकरावों के साथ भी हो सकता है।

जब से तुम तार देखने, तार के लिए, एक Trie (विभिन्न trie जायके, crit-बिट या जो कुछ भी अजीब नामों वे के किसी भी) भी इस पर गौर करना श्रेयस्कर होगा, खासकर यदि आप उनमें से कई है। स्वतंत्र रूप से उपलब्ध कई मुफ्त trie कार्यान्वयन हैं।
प्रयासों का लाभ यह है कि वे तारों को इंडेक्स-संपीड़ित कर सकते हैं, इसलिए वे कम मेमोरी का उपयोग करते हैं, जिसमें कैश में डेटा रखने की उच्च संभावना होती है। इसके अलावा एक्सेस पैटर्न कम यादृच्छिक है, जो कैश-अनुकूल भी है। एक हैश तालिका को मान प्लस हैश, और सूचकांक को कम से कम यादृच्छिक रूप से संग्रहीत करना चाहिए (यादृच्छिक रूप से, लेकिन अप्रत्याशित रूप से) स्मृति में। एक trie/trie-like संरचना आदर्श रूप से केवल एक अतिरिक्त बिट की आवश्यकता होती है जो प्रत्येक नोड में अपने सामान्य उपसर्ग से कुंजी को अलग करता है।

(वैसे ध्यान दें कि हे (लॉग (एन)) बहुत संभव है तेजी से हो सकता है की तुलना में हे (1) इस तरह के एक मामले में, क्योंकि बड़े-ओ कि जैसी चीजों पर विचार नहीं करता।)

Answer 2

कोशिश गूगल-sparsehash: http://code.google.com/p/google-sparsehash/

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed. 

Answer 3

ध्यान दें कि ये अलग-अलग चीजें हैं: क्या आपको ऊपरी सीमा की आवश्यकता है, क्या आपको तेजी से सामान्य दर की आवश्यकता है, या आपको सबसे तेज़ लुकअप की आवश्यकता है, कोई प्रश्न नहीं पूछा गया? आखिरी व्यक्ति आपको खर्च करेगा, पहले दो लोग विवादित लक्ष्य हो सकते हैं।

---

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

इसका एक संशोधन एक सामान्य हैश फ़ंक्शन (जैसे शिफ़्ट-मल्टीप्ली-एड) का उपयोग करेगा और उचित पैरामीटर पर एक ब्रूट फोर्स खोज करेगा।

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

एक और विकल्प दो अलग हैश फ़ंक्शंस का उपयोग करना है - इससे एक लुकअप की लागत बढ़ जाती है लेकिन एलियंस आपके घड़ी के सिलों को चुरा लेने से थोड़ा कम होने की संभावना कम हो जाती है। यह असंभव है कि यह सामान्य तारों और एक सभ्य हैश समारोह के साथ एक समस्या होगी।

Answer 4

एक समान विषय (संकलित समय पर ज्ञात वस्तुओं की संख्या) में, मैंने इसे एक उत्पादित किया: Lookups on known set of integer keys। कम ओवरहेड, सही हैश के लिए कोई ज़रूरत नहीं है। सौभाग्य से, यह सी में है ;-)