none
Collision Resolution in the Dictionary Class RRS feed

  • Question

  • Hi,

    Have a question about collision resolution in dictionary. Would you go here and scroll down towards the bottom there is an image showing how the dictionary deals with collision resolution with something like linked lists.

    http://msdn.microsoft.com/en-US/library/ms379571(v=VS.80).aspx

    Question I have is how does the right value get returned when the dictionary is looked up again?

    So say three items are added to a dictionary and due to some bizarre coincidence they are have the same hash and collide. The linked list is created as in the diagram but how then is the right value accessed.

    Collision resolution works during inserting so what I'm asking is how does collision resolution work during getting.

     

     

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    • Edited by Derek Smyth Wednesday, November 23, 2011 1:36 PM
    Wednesday, November 23, 2011 1:34 PM

Answers

  • "So say three items are added to a dictionary and due to some bizarre coincidence they are have the same hash and collide. The linked list is created as in the diagram but how then is the right value accessed."

    It goes through the list searching for one element that has a hash and a key equal to the one you asked for. IEqualityComparere.Equals is used for this.


    • Edited by Mike DanesModerator Wednesday, November 23, 2011 2:06 PM forgot to say that the has is compared for equality too
    • Marked as answer by Derek Smyth Wednesday, November 23, 2011 3:42 PM
    Wednesday, November 23, 2011 1:50 PM
    Moderator

All replies

  • "So say three items are added to a dictionary and due to some bizarre coincidence they are have the same hash and collide. The linked list is created as in the diagram but how then is the right value accessed."

    It goes through the list searching for one element that has a hash and a key equal to the one you asked for. IEqualityComparere.Equals is used for this.


    • Edited by Mike DanesModerator Wednesday, November 23, 2011 2:06 PM forgot to say that the has is compared for equality too
    • Marked as answer by Derek Smyth Wednesday, November 23, 2011 3:42 PM
    Wednesday, November 23, 2011 1:50 PM
    Moderator
  • Hi,

    So the key is still used for the look up. Is the hash value just used as an initial 'ball park' area to start the search from?

    Ah that's how the hashtable works, gets the starting point from the hash and then if not found ... ok think I've got it. Cheers.

     


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    Wednesday, November 23, 2011 3:42 PM
  • "Is the hash value just used as an initial 'ball park' area to start the search from?"

    Exactly!

    Wednesday, November 23, 2011 3:46 PM
    Moderator
  • Nice one! Thanks Mike.


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    Wednesday, November 23, 2011 4:05 PM