Find the total number of probes that occur while hashing five strings using linear probing.

Consider the following, five binary strings of length 8.
01010010, 11011011, 10011010, 11111011, 01110010
A hash table of size M = 8 (0 to 7) is using open addressing for hashing the
binary strings. Assume finding an empty slot directly without collision or after
collision is also a probe. The total number of probes that occur while hashing
five strings using linear probing are ______.

2Comments
shivani @shivani1234
24 Jul 2017 04:46 pm
  • for linear hashing of given binary strings look for last 3 bits as hash table is of size 8 which can be written as 1000
  • 01010010 should be alloted block no. 2, 11011011should be alloted block no. 3, 10011010 should be alloted block no. 2, 11111011 should be alloted block no. 3, 01110010 should be alloted block no. 2
  1. but while doing hashing following things will happen 01010010 will go to block no.2 without any conflict so its probe is 1
  2. 11011011 will go to block no.3 without any conflict so its probe is 1
  3. 10011010 should go to block no. 2 but due to conflict there will be 3 probes(2 for conflict and 1 for placing in block no. 4)
  4. 11111011 should go to block no. 3 but due to conflict there will be 3 probes(2 for conflict and 1 for placing in block no. 5)
  5.  01110010 should go to block no. 2 but due to conflict there will be 5 probes(4 for conflict and 1 for placing in block no. 6)
  • So overall there will be =1+1+3+3+5=13 probes
Akanksha Bhardwaj @akanksha13
24 Jul 2017 07:23 pm

Thank you! :)

I was trying to convert binary string to decimal and then solving it :P :D