Consider the following hashtable: It was created with the hash function H(x) = x

Question

Consider the following hashtable:

It was created with the hash function H(x) = x % 9 and uses a quadratic collision scheme.

Which of the following was the order in which the elements were inserted to produce the table above?

a. All of the insert orders listed here will produce the hashtable shown above.

b. None of the insert orders listed here will produce the hashtable shown above.

c. The insert order: 10, 81, 14, 63, 42 will produce the hashtable shown above.

d. The insert order: 81, 10, 42, 14, 63 will produce the hashtable shown above.

e. The insert order: 14, 42, 10, 81, 63 will produce the hashtable shown above

Explanation / Answer

Option B is correct.

Since hash function is X%9 so the remainder would be the index for that X in the hash table.

Let's take any of the insert order :14,42,10,81,63

14 -> 14%9 = 5 (o.k.)
42 -> 42%9 = 6 (o.k.)
10 -> 10%9 =1 (o.k.)
81 -> 81%9 =0 (o.k.)
63 -> 63%9 =0 (collision occurs)

Here the collision has occurred.
To solve this either list chaining is applied(linked lis/list attached to each index to store elements wit collision)
but here no list has been mentioned.

Other method to overcome collision is "Linear Probing".
In this method When collision is occurred the next closest free(available) index is searched to insert the new element.
In this case 2(closer than 3 from 0) should be the index to insert 63.

So the actual insertion should be like this for any of the insert orders given here.

0 -> 81
1 -> 10
2 -> 63
3 ->
4 ->
5 -> 14
6 -> 42
7 ->
8 ->

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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