How to Insert Keys in a Hashtable Using Different Collision Resolution Methods?

  • Topic:
  • Thread starter evinda
  • Start date
3 replies · 2K views · last reply
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Smile)

There are given three elements with keys $22, 15, 8$. Insert them in the given order in a hashtable of $7$ positions given that as method of treatement of the collisions we use:

  • hashing that follows the method coalesced chaining with the hash fuction $h(k)=k \mod m$
  • ordered hashing with open addressing strategies with the primary hash function $h_1(x)=x \mod m$ and the secondary hash function $h_2(x)=(x^2+1) \mod{7}$

That's what I have tried:

For the first case:

View attachment 3894

For the second case:

View attachment 3895Could you tell me if it is right? (Thinking)
 
Attachments
  • Hash table diagram with rows labelled 0 to 6 in a single column; row 0 holds 15, row 1 holds 22 and 0, row 2 holds 8, rows 3 to 6 are empty.
    hash1.png
    1.2 KB · Views: 154
  • Vertical table of seven empty-or-filled slots numbered 0 to 6; slot 1 holds 8, slot 2 holds 22, slot 3 holds 15, and slots 0, 4, 5 and 6 are empty.
    hash2.png
    1.1 KB · Views: 154

Discussion

Hey! (Wasntme)

I believe the first case is right. (Nod)

In the second case, the first value of 22 would still be inserted in slot 1 (using the primary hash function), so I think 22 should be there instead of 8. (Shake)
 
I like Serena said:
Did you figure it out? (Wondering)

Yes, I did.. Thanks for your answer! (Smile)