Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा संरचना में गुणन द्वारा हैशिंग (Hashing by Multiplication)


यहाँ हम गुणन विधि (multiplication method) के साथ हैशिंग पर चर्चा करेंगे। इसके लिए हम हैश फ़ंक्शन का उपयोग करते हैं:

h(x) = ⌊m * x * A⌋ mod m

यहाँ A एक वास्तविक-मूल्य स्थिरांक (real-valued constant) है। इस विधि का लाभ यह है कि m का मूल्य इतना महत्वपूर्ण नहीं है। हम m को 2 की घात (power of 2) के रूप में भी ले सकते हैं। यद्यपि A का कोई भी मान हैश फ़ंक्शन देता है, लेकिन A के कुछ मान दूसरों से बेहतर होते हैं।

नुथ (Knuth) के अनुसार, हम A के लिए स्वर्ण अनुपात (golden ratio) का उपयोग कर सकते हैं, इसलिए A होगा:

$$A=\frac{\sqrt5-1}{2}=0.61803398$$

बेशक, A के लिए चाहे कोई भी मान चुना जाए। कबूतर-छेद सिद्धांत (pigeonhole principle) का तात्पर्य है कि यदि u ≥ nm, तो एक हैश मान i और आकार n का कुछ S ⊆ U होगा, जैसे कि सभी x ∈ S के लिए h(x) = i।

इसलिए हम कह सकते हैं कि गुणन द्वारा हैशिंग का सबसे खराब मामला (worst case) विभाजन द्वारा हैशिंग जितना ही बुरा है।


  1. डेटा संरचना में चेनिंग के साथ हैशिंग (Hashing with Chaining) डेटा संरचना में चेनिंग के साथ हैशिंग (Hashing with Chaining)

    इस अनुभाग में हम देखेंगे कि चेनिंग (Chaining) के साथ हैशिंग क्या है। चेनिंग टकराव समाधान (collision resolution) की एक तकनीक है। हम टकराव से बच नहीं सकते, लेकिन हम टकराव को कम करने की कोशिश कर सकते हैं, और एक ही हैश मान के लिए कई तत्वों को संग्रहीत करने का प्रयास कर सकते हैं। इस तकनीक में मान लीजिए

  1. डेटा संरचना में R-ट्री (R-trees) डेटा संरचना में R-ट्री (R-trees)

    यहाँ हम R-ट्री (R-Trees) डेटा संरचना देखेंगे। R-ट्री का उपयोग विशेष डेटा इंडेक्स को कुशलतापूर्वक संग्रहीत करने के लिए किया जाता है। यह संरचना विशेष डेटा क्वेरी और भंडारण को रखने के लिए बहुत उपयोगी है। R-ट्री के कुछ वास्तविक जीवन अनुप्रयोग हैं: बहुआयामी जानकारी इंडेक्स करना गेम डेटा संभालना भू-स्था

  1. हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure) हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure)

    परिचय (Introduction) टेम्पलेट पैरामीटर्स के लिए HDS या हाफएज डेटा स्ट्रक्चर (Halfedge Data Structure - संक्षिप्त HalfedgeDS) को एक एज-केंद्रित डेटा स्ट्रक्चर (Edge-centered Data Structure) के रूप में परिभाषित किया जाता है जो वर्टेक्स, एज और फेसेस (Vertices, Edges and Faces) की घटना जानकारी (Incidenc