(Hash Tables) Insert the keys E A S Y Q U T I O N in that order into an initiall

Question

(Hash Tables) Insert the keys E A S Y Q U T I O N in that order into an initially empty table of size m = 16 using linear probing. Use the hash function 11 * k % m to transform the kth letter of the alphabet into a table index. Redo this exercise for m = 10.

(Hash Tables) Insert the keys E A S Y R U T I O N in that order into an initially empty table of size m 16 using linear probing. Use the hash function 11xk m to transform the Ath letter of the alphabet into a table index. Redo this exercise for m 10.

Explanation / Answer

Solution:

for m= 16

the hash function will be H(x)= 11*k%16

Now let's start inserting the keys into the hash table using the given hash function:

for E, H(x)= 11*5%16= 7, no collision

for A, H(x)= 11*1%16= 11, no collision

for S, H(x)= 1, no collision

for Y, H(x)= 3, no collision

for Q, H(x)= 11, collision now since A is already there Q will take next slot using linear probing, i.e. 12

for U, H(x)= 7, collision now since E is already there Q will take next slot using linear probing, i.e. 8

for T, H(x)= 12, collision now since Q is already there T will take next slot using linear probing, i.e. 13

for I, H(x)= 3, collision now since Y is already there I will take next slot using linear probing, i.e. 4

for O, H(x)= 5, no collision

for N, H(x)= 10, no collision

Using m= 16, number of collisions are= 4

Now for m= 10 the hash function will be

H(x)= 11*k%10

Now let's start inserting the keys into the hash table using the given hash function:

for E, H(x)= 11*5%10= 5, no collision

for A, H(x)= 11*1%10= 1, no collision

for S, H(x)= 9, no collision

for Y, H(x)= 5, collision now since E is already there Y will take next slot using linear probing, i.e. 6

for Q, H(x)= 7, no collision

for U, H(x)= 1, collision now since S is already there U will take next slot using linear probing, i.e. 2

for T, H(x)= 0, no collision

for I, H(x)= 9, collision now since S is already there I will seek for place at 0, 1, and 2 but T, S, and U are already there so , I will be at 3

for O, H(x)= 5, collision, and take place at 8

for N, H(x)= 4, no collision

Using m= 10, the number of collsions are= 4

I hope this helps. Don't forget to give a thumbs up if you like this

0 1 S 2 3 Y 4 I 5 O 6 7 E 8 U 9 10 N 11 A 12 Q 13 T 14 15

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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