hashing

Question

Answer 1

For such problems where we have binary key and the table size is the kth power of 2 , the last 'k' bits will decide the hash value i.e. the location where the key will be mapped.

As table size  = 8 which is 2³ , hence the trailing 3 bits will decide the table location of the key..

Hence , 

a) h(01010010)   =  010  =  2 ..

b) h(11011011)    =  011  =  3

c) h(10011010)   =   010  =  2[Collision]

                                    =  3[Collision]

                                    =  4

d) h(11111011)    =  011   = 3[Collision]

                                    = 4[Collision]

                                    = 5

e) h(01110010)   =  010   = 2[Collision]

                                    = 3[Collision]

                                    = 4[Collision]

                                    = 5[Collision]

                                    = 6

Hence total number of probes     =    1 + 1 + 3 + 3 + 5

                                                   =    13

Comments

Hash table size is M ($2^{K}$) then LSB 'K' bits will decide the slot in hash table.

Here Hashtable size=8 ($2^{3}$) so LSB '3' bits will decide the slot .

 01010010 -- it goes to 010 slot without collision.[without collision also one probe]-----${\color{Red} 1}$ probe

11011011---it goes to 011 slot without collision .${\color{Red} 1}$ probe

10011010--it goes to 010 slot but it is already filled so use linear probing and next slot also collision 

it goes to 100 slot .No of probes generated here are ${\color{Red} 3}$

11111011--Same as above it also collide with existing slots and finally allocated in 101 slot.No of probes generated here are ${\color{Red} 3}$

01110010---Same as above it collides and finally allocated in a 110 slot .No of probes generated here are ${\color{Red} 5}$

Finally total no of probes generated are :1+1+3+3+5=13.