क्या हैश टेबल वास्तव में ओ (1) हो सकता है?

Question

ऐसा सामान्य ज्ञान प्रतीत होता है कि हैश टेबल ओ (1) प्राप्त कर सकते हैं, लेकिन इससे मुझे कभी समझ नहीं आया है। क्या कोई इसे समझा सकता है? यहां दो स्थितियां हैं जो ध्यान में आती हैं:

ए मान हैश तालिका के आकार से छोटा छोटा है। इसलिए, मान अपने हैश है, इसलिए कोई हैश तालिका नहीं है। लेकिन अगर वहां था, तो यह ओ (1) होगा और अभी भी अक्षम होगा।

बी आपको मूल्य के हैश की गणना करना है। इस स्थिति में, ऑर्डर डेटा के आकार के लिए ओ (एन) है। ओ (एन) काम करने के बाद लुकअप ओ (1) हो सकता है, लेकिन यह अभी भी मेरी आंखों में ओ (एन) के लिए आता है।

और जब तक कि आपके पास एक परिपूर्ण हैश या बड़ी हैश तालिका न हो, तो प्रति बाल्टी में शायद कई आइटम हैं। तो, यह किसी भी बिंदु पर किसी भी बिंदु पर एक छोटी रैखिक खोज में devolves।

मुझे लगता है कि हैश टेबल बहुत ही अच्छे हैं, लेकिन मुझे ओ (1) पदनाम नहीं मिलता है जब तक कि यह सैद्धांतिक नहीं माना जाता है।

विकिपीडिया का article for hash tables निरंतर निरंतर लुकअप समय का संदर्भ देता है और हैश फ़ंक्शन की लागत को पूरी तरह से अनदेखा करता है। क्या यह वास्तव में एक उचित उपाय है?

---

संपादित करें: मैं क्या सीखा संक्षेप में:

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

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

Answer 1

आपके यहां दो चर हैं, एम और एन, जहां एम इनपुट की लंबाई है और एन हैश में वस्तुओं की संख्या है।

• आपका वस्तुओं हे (1) समय में की तुलना में समानता हो सकता है:

  हे (1) देखने प्रदर्शन दावा कम से कम दो धारणाएं बनाता है।

• कुछ हैश टकराव होंगे।

अपने वस्तुओं चर आकार और एक समानता की जांच कर रहे हैं सभी बिट्स को देखकर की आवश्यकता है तो प्रदर्शन हे (एम) हो जाएगा। हैश फ़ंक्शन हालांकि ओ (एम) होना आवश्यक नहीं है - यह ओ (1) हो सकता है। एक क्रिप्टोग्राफिक हैश के विपरीत, एक शब्दकोश में उपयोग के लिए हैश फ़ंक्शन को हैश की गणना करने के लिए इनपुट में हर बिट को देखने की आवश्यकता नहीं है। कार्यान्वयन केवल बिट्स की एक निश्चित संख्या को देखने के लिए स्वतंत्र हैं।

पर्याप्त मात्रा में आइटमों की संख्या संभावित हैश की संख्या से अधिक हो जाएगी और फिर आप ओ (1) के ऊपर प्रदर्शन वृद्धि के कारण टक्कर प्राप्त करेंगे, उदाहरण के लिए ओ (एन) एक साधारण लिंक्ड सूची ट्रैवर्सल (या ओ (एन * एम) यदि दोनों धारणाएं झूठी हैं)।

व्यवहार में हालांकि हे (1) का दावा है, जबकि तकनीकी रूप से गलत, कई असली दुनिया स्थितियों के लिए लगभग सच है, और विशेष रूप से उन स्थितियों में, जहां ऊपर मान्यताओं पकड़ में है।

Answer 2

हैश निश्चित आकार है - उचित हैश बाल्टी को देख एक निश्चित मूल्य ऑपरेशन है। इसका मतलब है कि यह ओ (1) है।

हैश की गणना करना विशेष रूप से महंगा संचालन नहीं होना चाहिए - हम यहाँ क्रिप्टोग्राफिक हैश फ़ंक्शन नहीं बोल रहे हैं। लेकिन वह इसके द्वारा है। हैश फ़ंक्शन गणना स्वयं तत्वों की संख्या n पर निर्भर नहीं है; जबकि यह किसी तत्व में डेटा के आकार पर निर्भर हो सकता है, यह n का संदर्भ नहीं है। तो हैश की गणना एन पर निर्भर नहीं है और यह ओ (1) भी है।

Answer 3

आपको हैश की गणना करना है, इसलिए डेटा को आकार के आकार के लिए ओ (एन) ऑर्डर करना है। ओ (एन) काम करने के बाद लुकअप ओ (1) हो सकता है, लेकिन यह अभी भी मेरी आंखों में ओ (एन) के लिए आता है।

क्या? हैश के लिए एक तत्व लगातार समय लेता है। यह और कुछ क्यों होगा? आप n तत्वों डालने रहे हैं, तो हां, तो आप n हैश गणना करने के लिए है, और कि रैखिक समय लगता है ... एक तत्व को देखने के लिए, आप के लिए क्या देख रहे हैं की एक एकल हैश की गणना, तो उपयुक्त बाल्टी लगता है उस के साथ। आप हैश टेबल में पहले से मौजूद सब कुछ के हैंश की पुन: गणना नहीं करते हैं।

और जब तक कि आपके पास एक परिपूर्ण हैश या बड़ी हैश तालिका न हो, तो संभवतः प्रति बाल्टी कई आइटम हैं, इसलिए यह किसी भी बिंदु पर एक छोटी रैखिक खोज में घूमती है।

आवश्यक नहीं है। बाल्टी को सूचियों या सरणी होने की आवश्यकता नहीं होती है, वे किसी भी कंटेनर प्रकार, जैसे संतुलित बीएसटी हो सकते हैं। इसका मतलब है O(log n) सबसे खराब मामला। लेकिन यही कारण है कि एक बाल्टी में बहुत से तत्व डालने से बचने के लिए एक अच्छा हैशिंग फ़ंक्शन चुनना महत्वपूर्ण है। जैसा कि केनीटीएम ने इंगित किया है, औसतन, आपको अभी भी O(1) समय मिलेगा, भले ही कभी-कभी आपको बाल्टी से गुजरना पड़े।

व्यापार हैश टेबल के बंद निश्चित रूप से अंतरिक्ष जटिलता है। आप समय के लिए अंतरिक्ष व्यापार कर रहे हैं, जो विज्ञान की गणना में सामान्य मामला प्रतीत होता है।

---

आप अपनी अन्य टिप्पणियों में से एक में तारों के रूप में तारों का उपयोग करने का उल्लेख करते हैं। आप स्ट्रिंग के हैश की गणना करने के लिए कितने समय लेते हैं, इस बारे में चिंतित हैं, क्योंकि इसमें कई वर्ण होते हैं? जैसा कि किसी और ने फिर से बताया, हैश की गणना करने के लिए आपको सभी वर्णों को देखने की आवश्यकता नहीं है, हालांकि यदि आपने किया तो यह बेहतर हैश उत्पन्न कर सकता है। उस मामले में, यदि आपके कुंजी में औसत m वर्ण पर हैं, और आप अपने हैश गणना करने के लिए उन सभी को इस्तेमाल किया है, तो मुझे लगता है कि तुम सही हो, कि लुकअप O(m) ले जाएगा। यदि m >> n तो आपको कोई समस्या हो सकती है। आप उस मामले में बीएसटी के साथ शायद बेहतर हो जाएंगे। या एक सस्ता हैशिंग समारोह का चयन करें।

Answer 4

हैशिंग हे (1) है तभी तालिका में कुंजी और कुछ अन्य मान्यताओं के केवल स्थिर संख्या बने होते हैं। लेकिन ऐसे मामलों में इसका फायदा है।

अपने प्रमुख एक n बिट प्रतिनिधित्व है, तो आपके हैश समारोह का उपयोग कर सकते 1, 2, ... इन बिट्स की एन।एक हैश फ़ंक्शन के बारे में सोचकर 1 बिट का उपयोग करता है। मूल्यांकन निश्चित रूप से ओ (1) है। लेकिन आप केवल कुंजी स्थान को 2 में विभाजित कर रहे हैं। तो आप एक ही बिन में 2^(एन -1) कुंजी को मैप कर रहे हैं। बीएसटी खोज का उपयोग करते हुए यह लगभग एक पूर्ण कुंजी का पता लगाने के लिए एन -1 कदम उठाता है।

आप यह देखने के लिए इसे बढ़ा सकते हैं कि यदि आपका हैश फ़ंक्शन K बिट्स का उपयोग करता है तो आपका बिन आकार 2^(n-k) है।

तो के-बिट हैश फ़ंक्शन ==> 2 से अधिक के^प्रभावी प्रभावी डिब्बे ==> 2^(एनके) एन-बिट कुंजी प्रति बिन ==> (एनके) चरण (बीएसटी) टकराव को हल करने के लिए । असल में अधिकांश हैश फ़ंक्शन बहुत कम "प्रभावी" होते हैं और 2^के डिब्बे बनाने के लिए के बिट्स से अधिक की आवश्यकता होती है। तो यह आशावादी भी है।

आप इसे इस तरह से देख सकते हैं - आपको सबसे खराब मामले में एन बिट्स की चाबियों की एक जोड़ी को विशिष्ट रूप से अलग करने में सक्षम होने के लिए ~ n चरणों की आवश्यकता होगी। इस जानकारी सिद्धांत सीमा, हैश तालिका या नहीं के आसपास वास्तव में कोई रास्ता नहीं है।

हालांकि, यह हैश टेबल का उपयोग कैसे/कब नहीं है!

जटिलता विश्लेषण मानता है कि एन-बिट कुंजी के लिए, आप तालिका में ओ (2^एन) कुंजी (उदाहरण के लिए सभी संभव कुंजी के 1/4) हो सकते हैं। लेकिन अधिकांश समय जब हम हैश टेबल का उपयोग नहीं करते हैं, तो हमारे पास तालिका में केवल n-bit कुंजी की निरंतर संख्या होती है। यदि आप केवल तालिका में निरंतर कुंजी की आवश्यकता चाहते हैं, तो कहें कि सी आपकी अधिकतम संख्या है, तो आप ओ (सी) डिब्बे की हैश तालिका बना सकते हैं, जो अपेक्षित निरंतर टक्कर (एक अच्छे हैश फ़ंक्शन के साथ) की गारंटी देता है; और कुंजी में एन बिट्स के ~ logC का उपयोग कर एक हैश फ़ंक्शन। फिर हर क्वेरी ओ (लॉगसी) = ओ (1) है। इस प्रकार लोगों का दावा है कि "हैश टेबल एक्सेस ओ (1)"/

यहां कुछ कैच हैं - पहले, कह रहे हैं कि आपको सभी बिट्स की आवश्यकता नहीं है केवल बिलिंग चाल हो सकती है। सबसे पहले आप हैश फ़ंक्शन में मुख्य मान को वास्तव में पास नहीं कर सकते हैं, क्योंकि यह ओ (एन) की स्मृति में एन बिट्स को ले जायेगा। तो आपको उदाहरण करने की ज़रूरत है एक संदर्भ गुजर रहा है। लेकिन आपको अभी भी इसे पहले से स्टोर करने की आवश्यकता है जो ओ (एन) ऑपरेशन था; आप इसे हैशिंग के लिए बिल नहीं देते हैं; आप समग्र गणना कार्य इस से बच नहीं सकते हैं। दूसरा, आप हैशिंग करते हैं, बिन ढूंढते हैं, और 1 से अधिक कुंजी पाते हैं; आपकी लागत आपके रिज़ॉल्यूशन विधि पर निर्भर करती है - यदि आप तुलना आधारित (बीएसटी या सूची) करते हैं, तो आपके पास ओ (एन) ऑपरेशन होगा (याद कुंजी एन-बिट है); यदि आप दूसरे हैश करते हैं, तो, यदि आपके पास 2 हैश की टक्कर है तो आपके पास एक ही समस्या है। तो ओ (1) 100% गारंटी नहीं है जब तक कि आपके पास कोई टकराव न हो (आप चाबियों की तुलना में अधिक डिब्बे वाली तालिका रखने का मौका बेहतर कर सकते हैं)।

वैकल्पिक पर विचार करें, उदा। बीएसटी, इस मामले में। सी कुंजी हैं, इसलिए एक संतुलित बीएसटी गहराई में ओ (लॉगसी) होगा, इसलिए एक खोज ओ (लॉगसी) चरणों को लेती है। हालांकि इस मामले की तुलना ओ (एन) ऑपरेशन होगी ... इसलिए ऐसा लगता है कि इस मामले में हैशिंग एक बेहतर विकल्प है।

Answer 5

ऐसी दो सेटिंग्स हैं जिनके तहत आप ओ (1) सबसे खराब-मामले के समय प्राप्त कर सकते हैं।

1. तो अपने सेटअप स्थिर है, तो FKS हैशिंग आप बुरी से बुरी हालत हो जाएगा हे (1) की गारंटी देता है। लेकिन जैसा कि आपने संकेत दिया है, आपकी सेटिंग स्थिर नहीं है।
2. आप कोयल हैशिंग का उपयोग करते हैं, तो प्रश्नों और हटाए गए हैं हे (1) बुरी से बुरी हालत है, लेकिन प्रविष्टि है केवल हे (1) की उम्मीद। यदि आपके पास आवेषण की कुल संख्या पर ऊपरी सीमा है, और तालिका का आकार मोटे तौर पर 25% बड़ा होने के लिए कोयल हैशिंग बहुत अच्छी तरह से काम करता है।

से here