Hashing

Question

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.

Answer 1

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

Comments

how u have decided the no. of probes at each slot please explain??

---

We are doing "linear probing" in question. So, if a slot is full we do a linear probe to find an empty slot. Explanation is now added in answer.

---

Thank u so much Sir.