यह data structure में collision resolution techniques है। Open addressing में, सभी keys जो है वह hash table के अंदर स्टोर रहती है। इसमें hash table के बाहर कोई key स्टोर नहीं रहती है, इसलिए hash table का size हमेशा keys की संख्या से बड़ा या equal होता है। इसे closed hashing भी कहते है।

Open addressing में निन्मलिखित techniques का प्रयोग किया जाता है:-
1. linear probing
2. quadratic probing
3. double hashing

linear probing

इसमें, जब collision होता है तो हम अगले slot के लिए linear prob करते है और तब तक probing की जाती है जब तक कि कोई empty slot ना मिल जाए।

advantage:-
इसे आसानी से compute किया जा सकता है।

disadvantage:-
1. linear probing की मुख्य परेशानी clustering है।
2. empty slot को ढूंडने में समय जयादा लगता है।

time complexity:-
linear probing में किसी element को search करने का worst time O(table size) है।

Quadratic probing

इसमें, जब collision होता है तो हम ith iteration में i2th slot के लिए probe करते है और हम तब तक probing करते है जब तक कि empty slot मिल नहीं जाता।

double hashing

इसमें, हम दूसरे hash function –hash 2(x) का प्रयोग करते है तथा ith iteration में i*hash 2(x) के लिए probe करते है। इसको दो hash functions को compute करने के लिए ज्यादा समय की जरुरत होती है।

conclusion:-

• linear probing जो है वह best cache performance देती है परन्तु इसकी परेशानी clustering है।
• Quadratic probing में cache performance ठीक है परन्तु linear probing से कम best है और इसमें clustering की परेशानी कम होती है।
• .double hashing की cache performance बहुत ही ख़राब है. परन्तु इसमें clustering नहीं होती है।


Leave a Reply