डेटा स्ट्रक्चर में ओवरफ्लो हैंडलिंग

ओवरफ्लो उस समय होता है जब एक नई जोड़ी (Key, Element) के लिए होम बकेट (Home Bucket) भर जाती है।

हम ओवरफ्लो को निम्न तरीकों से संभाल सकते हैं:

• हैश टेबल में किसी व्यवस्थित तरीके से ऐसे बकेट की खोज करें जो भरा न हो।
  • लीनियर प्रोबिंग (Linear Probing / Linear Open Addressing)
  • क्वाड्रेटिक प्रोबिंग (Quadratic Probing)
  • रैंडम प्रोबिंग (Random Probing)
• प्रत्येक बकेट को उन सभी जोड़ियों की सूची रखने की अनुमति देकर ओवरफ्लो को समाप्त करें जिनके लिए यह होम बकेट है।
  • एरे लीनियर लिस्ट (Array Linear List)
  • चेन (Chain)

ओपन एड्रेसिंग (Open Addressing) यह सुनिश्चित करने के लिए की जाती है कि सभी एलिमेंट सीधे हैश टेबल में स्टोर हों, इस प्रकार यह विभिन्न तरीकों को लागू करके टकराव (Collisions) को हल करने का प्रयास करता है।

लीनियर प्रोबिंग (Linear Probing) टकराव को हल करने के लिए डेटा को टेबल में अगले खुले स्लॉट में रखकर किया जाता है।

लीनियर प्रोबिंग का प्रदर्शन (Performance of Linear Probing)

• सबसे खराब स्थिति में फाइंड/इन्सर्ट/इरेज़ समय θ(m) होता है, जहां m को टेबल में जोड़ियों की संख्या माना जाता है।
• यह तब होता है जब सभी जोड़ियाँ एक ही क्लस्टर (Cluster) में होती हैं।

लीनियर प्रोबिंग की समस्या (Problem of Linear Probing)

• आइडेंटिफायर्स का एक साथ क्लस्टर होने की प्रवृत्ति
• आसन्न क्लस्टर्स का विलय (Coalesce) होने की प्रवृत्ति
• खोज समय में वृद्धि या वृद्धि

क्वाड्रेटिक प्रोबिंग (Quadratic Probing)

लीनियर प्रोबिंग बकेट्स (H(x)+i²)%b खोजता है; H(x), x का हैश फंक्शन दर्शाता है।

क्वाड्रेटिक प्रोबिंग, i के क्वाड्रेटिक फंक्शन को इन्क्रीमेंट के रूप में लागू करता है।

बकेट्स H(x), (H(x)+i²)%b, (H(x)-i²)%b की जांच करें, जहां 1 ≤ i ≤ (b-1)/2

b को 4j+3 फॉर्म की एक अभाज्य संख्या (Prime Number) के रूप में दर्शाया गया है, जहां j एक पूर्णांक है।

रैंडम प्रोबिंग (Random Probing)

रैंडम प्रोबिंग रैंडम नंबर्स को शामिल करके की जाती है।

H(x) := (H'(x) + S[i]) % b
S[i] आकार b-1 की एक टेबल है
S[i] को पूर्णांकों [1, b-1] का एक रैंडम परमुटेशन (Random Permutation) दर्शाया गया है।