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

डेटा संरचना में असममित हैशिंग (Asymmetric Hashing)


इस अनुभाग में हम देखेंगे कि असममित हैशिंग तकनीक (Asymmetric Hashing) क्या है। इस तकनीक में, हैश टेबल को d संख्या के ब्लॉकों में विभाजित किया जाता है। प्रत्येक विभाजन की लंबाई n/d होती है। प्रोब मान xᵢ, 0 ≤ i ≤ d, को $$\left\{\frac{i*n}{d},...,\frac{(i+1)*n}{d-1}\right\}$$ से समान रूप से लिया जाता है। मल्टीपल चॉइस हैशिंग की तरह, x सम्मिलित करने के लिए, एल्गोरिदम सूची A[x₀], A[x₁], …, A[x_{d-1}] की लंबाई की जांच करता है। फिर x को इन सूचियों में सबसे छोटी सूची में जोड़ता है। यदि टाई (tie) है, तो यह x को सबसे छोटे इंडेक्स वाली सूची में सम्मिलित करता है।

वॉकिंग (Vocking) के अनुसार, असममित हैशिंग के लिए सबसे लंबी सूची की अपेक्षित लंबाई है:

$$E[W]\leq\frac{\ln\ln n}{d\ln\phi_{2}}+O(1)$$

फ़ंक्शन φ_d स्वर्ण अनुपात का सामान्यीकरण है, इसलिए $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$


  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