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.