1

Suppose we have a hash table with 10 buckets and the symbols S1 to S7 are intially entered using a hashing function using linear probing. What can be the maximum number of comparisions needed in searching an item that is not present? The hashing diagram can be explained as:

Index KEY

  • 0 - - S7

  • 1 - - S1

  • 2 - - Empty

  • 3 - - S4

  • 4 - - S2

  • 5 - - Empty

  • 6 - - S5

  • 7 - - Empty

  • 8 - - S6

  • 9 - - S3

Suppose I want to find an element S8(which is obviously not present) ..On Calculating the hash function for S8 suppose it jumps to index 8. Not finding the element at index 8, by linear probing it checks the next index and so on .. Now, the number of comparisons should come out to be total length of the array because by linear probing it should try to look in every index...but the actual answer is 5! :| Please anyone explain!!

Improve this question

1 Answer 1

Reset to default
4

Linear probing will look for an element until it hits an empty hash bucket. In this case, it will examine 8, 9, 0, 1 and 2; at 2 it will stop because the bucket is empty.

Note that deletion is handled by replacing a bucket with a special "tombstone" value which marks the element as deleted but avoids breaking a linear probe chain. Therefore, the linear probe still works correctly in the event of empty elements.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

So, if suppose i delete S3 from the array and as a result index 9 gets empty .. then index 9 will be a tombstone value. Now int the search operation, it will look beyond index 9 or stop at index 8 ?
okay .. thanks a lot!! Just one more question :P the same will be valid if i use quadratic probing ?
Yes. This is a general feature of hash tables which use open addressing.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.