I need help to understand the following... Use the hash function hf(x) = x, m =

Question

I need help to understand the following...

Use the hash function hf(x) = x, m = 11 to map an integer value to a hash table index. Insert the data 1, 13, 12,53,77,29,31,22 into the hash table.

(a) Construct the hash table by using linear probe addressing.

(b) Construct the hash table by using chaining with separate lists.

(c) For both techniques, determine the load factor, the average number of probes needed to locate a value in the table, and the average number of probes needed to determine that a value is not in the table. For linears probe addressing, when counting the number of probes needed to locate a value that is not in the table, count the discovery of an empty slot as a probe. For chaining with separate lists, record an encounter with the end of a list as a probe.

Explanation / Answer

a) The hash table is being created by function hf(x) = x, therefore 1 will go in location 1, 2 in location 2 and so on. Also since we are using linear probe, in case of collision, it will search for next empty slot.

therefore hash table will be

77

1

13

12

22

-

-

29

-

53

31

-

-

53

b) in this case linear chains will be created when collision occurs

77 , 22

1 , 12

13

-

-

-

29

-

53 , 31

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.