डेटा संरचना में अतिप्रवाह हैंडलिंग

एक नई जोड़ी (कुंजी, तत्व) भर जाने के लिए होम बकेट के समय एक अतिप्रवाह होता है।

हम

एक बाल्टी के लिए कुछ व्यवस्थित तरीके से हैश तालिका खोजें जो भरी नहीं है।

• रैखिक जांच (रैखिक खुला पता)।
• द्विघात जांच।
• यादृच्छिक जांच।

प्रत्येक बकेट को उन सभी युग्मों की सूची रखने की अनुमति देकर अतिप्रवाह को समाप्त करें जिनके लिए वह होम बकेट है।

• सरणी रैखिक सूची।
• श्रृंखला।

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

तालिका में अगले खुले स्लॉट में डेटा रखकर टकरावों को हल करने के लिए रैखिक जांच की जाती है।

रैखिक जांच का प्रदर्शन

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

रैखिक जांच की समस्या

• पहचानकर्ता एक साथ क्लस्टर करने की प्रवृत्ति रखते हैं
• आस-पास के समूह आपस में जुड़ रहे हैं
• खोज समय बढ़ाएं या बढ़ाएं

द्विघात जांच

लीनियर प्रोबिंग सर्च बकेट (H(x)+i2)%b; H(x) x के हैश फ़ंक्शन को इंगित करता है

द्विघात जांच वेतन वृद्धि के रूप में i के द्विघात कार्य को लागू करता है

1<=i<=(b-1)/2

b को 4j+3 के रूप में एक अभाज्य संख्या के रूप में दर्शाया गया है, j एक पूर्णांक है

यादृच्छिक जांच

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

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].