1,057 views
0 votes
0 votes

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. Calculate the total number of probes that occur while hashing five strings using linear probing.

    1 Answer

    Best answer
    5 votes
    5 votes
    In linear probing if the hashed location is not empty, a linear probe is done to find an empty slot.

    Assuming mod 8 function for hashing

    01010010 mod 8 = 010 = 2 (1 probe, goes to slot 2)

    11011011 mod 8 = 011 = 3 (1 probe, goes to slot 3)

    10011010 mod 8 = 010 = 2 (3 probes, goes to slot 4, unsuccessful probes at slots 2 and 3)

    11111011 mod 8 = 011 = 3 (3 probes, goes to slot 5, unsuccessful probes at slots 3 and 4)

    01110010 mod 8 = 010 = 2 (5 probes, goes to slot 6, unsuccessful probes at slots 2, 3, 4, and 5)

    So, total number of probes = 13

    http://webdocs.cs.ualberta.ca/~holte/T26/open-addr.html
    selected by

    Related questions

    1 votes
    1 votes
    1 answer
    1
    s_dr_13 asked Mar 6, 2019
    959 views
    Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful se...
    0 votes
    0 votes
    0 answers
    3
    HeadShot asked Nov 30, 2018
    811 views
    Anyone please give a solution to solve such question as it is difficult in one go.
    0 votes
    0 votes
    2 answers
    4
    altamash asked Nov 5, 2018
    2,549 views
    can any one explain double hashing example