गतिशील पूर्ण हैशिंग और सार्वभौमिक हैश फ़ंक्शन - स्पष्टीकरण कृपया?

Question

तो मैं हैश टेबल, हैश फ़ंक्शंस इत्यादि के बारे में पढ़ रहा हूं। मैं विकिपीडिया पर पढ़ने के लिए चिंतित था कि "गतिशील पूर्ण हैशिंग" में एक दूसरी हैश तालिका का उपयोग करना शामिल है क्योंकि डेटा संरचना एक विशेष बाल्टी के भीतर कई मानों को स्टोर करने के लिए होती है।

जहां मैं खो जाता हूं, तब यह होता है कि उस दूसरी हैश तालिका के लिए हैशिंग करने के लिए सार्वभौमिक हैश फ़ंक्शन का चयन कैसे किया जाता है। क्या कोई यह समझा सकता है कि बाल्टी में संग्रहीत मूल्यों से यह सार्वभौमिक हैश फ़ंक्शन कैसे निर्धारित किया जाता है? मैं विकिपीडिया के "सार्वभौमिक हैश फ़ंक्शन" पृष्ठ में तर्क और तर्क का अस्पष्टता से पालन करता हूं, लेकिन इस पर कोई अंतर्ज्ञान करने के लिए संघर्ष कर रहा हूं। विशेष रूप से, इन कार्यों को कोई संघर्ष की गारंटी कैसे देती है? या कम से कम, अगर उनका निपटारा किया जाता है और एक संघर्ष उत्पन्न होता है तो एक नया उत्पन्न होता है, तो हम कैसे जानते हैं कि यह वास्तव में यथार्थवादी समय में किया जा सकता है?

लेडीबर्ड पुस्तक स्पष्टीकरण कृपया?

Answer 1

बिल्कुल सही हैशिंग का अर्थ है कि पढ़ने का उपयोग सबसे खराब मामले में भी स्थिर समय लेता है।

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

प्रविष्टि को तेजी से पर्याप्त बनाने के लिए कुंजी की संख्या (के) के लिए दूसरी स्तर हैश तालिका को बहुत बड़ा चुना जाता है, ताकि पर्याप्त रूप से पर्याप्त टकराव हो सके। यह कोई समस्या नहीं है w.r.t. आकार क्योंकि पहले स्तर हैश समान रूप से कुंजी वितरित करता है ताकि औसत दूसरे स्तर पर हैश टेबल अभी भी छोटे हों।

दूसरे स्तर तालिकाओं के लिए हैश फंक्शन पैरामिट्रीकृत हैश फंक्शन का एक सेट से यादृच्छिक पर चुना जाता है।

Answer 2

कुछ एमआईटी व्याख्यान कैसे देख रहे हैं? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing