11 Replies Latest reply on Mar 8, 2010 6:42 PM by 796440

    Collision in Java HashMap

    807580
      I am under the expression that if two key-value pairs hash to the same position, both values will be stored at the same hashcode position and no value will be overwritten. However, why is the following code giving me different result? Can anyone explain please

      Thank you

      Xin

      import java.util.HashMap;
      import java.util.Hashtable;


      /**
      *
      * @author xint
      */
      public class Main {

      /**
      * @param args the command line arguments
      */
      public static void main(String[] args) {
      // Test collision in HashMap
      HashMap<String, String> hm = new HashMap<String,String>();

      hm.put("xint", "University of Toronto");
      hm.put("xint", "University of California");

      System.out.println(hm.containsValue("University of Toronto"));

      }

      }
        • 1. Re: Collision in Java HashMap
          796440
          xerox.time wrote:
          I am under the expression that if two key-value pairs hash to the same position, both values will be stored at the same hashcode position and no value will be overwritten. However, why is the following code giving me different result? Can anyone explain please
          Nothing will be overwritten if the keys are not equal.

          Here you have two keys that not only have the same hashCode, but also are equal(). If you had two keys that had the same hashCode but were not equal, then they would hash to the same bucket, but both would be present in the map--neither would overwrite the other.

          In the future, when posting code, use code tags so it will be readable. Copy/paste from your original source in your editor, highlight the code, and click the CODE button.
          • 2. Re: Collision in Java HashMap
            807580
            xerox.time wrote:
            I am under the expression that if two key-value pairs hash to the same position, both values will be stored at the same hashcode position and no value will be overwritten.
            Well, define "position". Two unequals objects with the same hashcode can both be used as keys in a hash table. Two equal objects are considered equal (imagine that) so only one value can be associated with that key.

            So if by "position" you mean "hashcode", what you say is true, but irrelevant. If by "position" you mean "logical position defined by the key", then your expectation is wrong.

            By the way:
            I am under the expression
            I think you mean "under the impression".
            • 3. Re: Collision in Java HashMap
              807580
              xerox.time wrote:
              Can anyone explain please
              What determines whether an entry is already present in a HashMap is the equals method alone.

              The hashCode method is used by the HashMap as an aid to efficiently store entries internally.

              So the methods have two very distinct purposes.
              • 4. Re: Collision in Java HashMap
                796440
                TashaYar wrote:
                xerox.time wrote:
                Can anyone explain please
                What determines whether an entry is already present in a HashMap is the equals method alone.
                No, it is a combination of hashCode() and equals().
                • 5. Re: Collision in Java HashMap
                  YoungWinston
                  jverd wrote:
                  TashaYar wrote:
                  What determines whether an entry is already present in a HashMap is the equals method alone.
                  No, it is a combination of hashCode() and equals().
                  Actually, I've got to go with TashaYar on this one. hashCode() is only used to determine what bucket the entry will go into, not whether it is already present.

                  Anyway, she's a weapons expert, and I wouldn't want to cross her.

                  Winston
                  • 6. Re: Collision in Java HashMap
                    YoungWinston
                    Note to self: check foot before opening mouth.

                    Thought about it in the shower and my apologies jverd, you're absolutely right; equals() is only used after hashCode() has determined the bucket, which is why it's so important to follow the rules.

                    Tasha, you'll have to shoot me.

                    Winston
                    • 7. Re: Collision in Java HashMap
                      807580
                      YoungWinston wrote:
                      Tasha, you'll have to shoot me.
                      No shoot me. My explanation was too simplistic so I put everybody in danger.
                      • 8. Re: Collision in Java HashMap
                        807580
                        You do not have to shoot him now.
                        • 9. Re: Collision in Java HashMap
                          796440
                          paulcw wrote:
                          You do not have to shoot him now.
                          Duck season.
                          • 10. Re: Collision in Java HashMap
                            807580
                            Wabbit season!

                            (nice catch by the way, i was afraid nobody would catch that reference)
                            • 11. Re: Collision in Java HashMap
                              796440
                              paulcw wrote:
                              i was afraid nobody would catch that reference
                              The cultural ignorance of today's youth is indeed shocking.