The Gateway to Computer Science Excellence

0 votes

+2

Yes I'm getting 1,9

Worst case occurs require N+1 comparision to know the element is not there in the hash table where N is the size of the largest cluster.

Here N is formed of index(7,8,9,10,11,12,0,1)

Worst case occurs require N+1 comparision to know the element is not there in the hash table where N is the size of the largest cluster.

Here N is formed of index(7,8,9,10,11,12,0,1)

0

arrange in the bucket using h(k)

0 | 38 |

1 | 14 |

2 | - |

3 | 42 |

4 | - |

5 | 70 |

6 | - |

7 | 7 |

8 | 8 |

9 | 21 |

10 | 34 |

11 | 11 |

12 | 25 |

check for any x that is not present in bucket.

search for x%13=2 or 4 or 6 ==> blank found

so, 1 key comparison. **Minimum=1**

---------------------------------------------------------------

search for x%13=7 (say, x=20)

not found untill it reaches linearly till key 2. blank found. so, total (8+1)= 9 key comparison.

**maximum=9**

+1 vote

0 | 38 |

1 | 14 |

2 | |

3 | 42 |

4 | |

5 | 70 |

6 | |

7 | 7 |

8 | 8 |

9 | 21 |

10 | 34 |

11 | 11 |

12 | 25 |

This will be the distribution of the Hash Table after all the keys has been inserted in the table.

Minimum no. of key comparison is 1. This happens when either at the location[ key%13 ] key is present or when at the location[ key%13 ] no key is present.

For Maximum Key Comparison consider the largest cluster in the given hash table. The largest cluster in given case consist of location no. {7,8,9,10,11,12,0,1}. The size of largest cluster being 8.

Now suppose you are searching for the key value 72.

Hash Value = 72%13 = 7.

Now the search process will look as of like this.

First value at location[7] will be compared with 72, since 7!=72( No. of comparisons = 1). Since collision resolution technique used is linear probing. Next ,

location[8] will be compared with 72, since 8!=72( No. of comparisons = 2). Since collision resolution technique used is linear probing. Next ,

location[9] will be compared with 72, since 21!=72( No. of comparisons = 3). Since collision resolution technique used is linear probing. Next ,

...

...

...

location[1] will be compared with 72, since 14!=72( No. of comparisons = 8). Since collision resolution technique used is linear probing. Next ,

location[2] will be compared with 72, since null!=72( No. of comparisons = 9).

Since, there is no key present at this location the search process will stop and null (Key not Found) will be returned.

Last comparisons is very important. This is also required along with all the remaining 8 comparisons to stop the algorithm.

52,375 questions

60,582 answers

202,000 comments

95,401 users