1 2 Previous Next 20 Replies Latest reply: Sep 13, 2010 8:06 AM by 800268 RSS

    Possible error in hash-algorithm for HashMap

    843793
      Hi, I have a problem with hash map, java 1.6. It is easy to reproduce.

      These three lines:

      java.util.Map<String, String> m = new java.util.HashMap <String, String>();
      m.put("/", "value1");
      m.put("/types[at0001]/items[at10004]/value", "value2");

      Both entries with different keys get the same index: 13 in my code.

      Is this an error do I misunderstand something?

      Thanks for any anwser
        • 1. Re: Possible error in hash-algorithm for HashMap
          EJP
          Maps don't have indexes. What are you talking about exactly?
          • 2. Re: Possible error in hash-algorithm for HashMap
            843793
            Sorry for not well expalining my question, I am talking about this function in HashMap.class

            Both keys as represented in my previous message return the same return value from function indexFor(..,..) which is called at the 4th line of function put(..,..) below. Which is in java.util.HashMap.class

            In this way, the previous key and value are overwritten by the next.

            I hope my question can be understood now.
            Thanks
            Bert Verhees
            public V put(K key, V value) {
                    if (key == null)
                        return putForNullKey(value);
                    int hash = hash(key.hashCode());
                    int i = indexFor(hash, table.length);
                    for (Entry<K,V> e = table; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
            }
            }

            modCount++;
            addEntry(hash, key, value, i);
            return null;
            }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
            • 3. Re: Possible error in hash-algorithm for HashMap
              800268
              Read up on [how hash tables work|http://en.wikipedia.org/wiki/Hash_table#Collision_resolution] and check the result of "/".equals("/types[at0001]/items[at10004]/value").
              • 4. Re: Possible error in hash-algorithm for HashMap
                3004
                BertVerhees wrote:
                In this way, the previous key and value are overwritten by the next.
                Really?

                Check your assumptions at the door and, since you're digging into HashMap's source code, look into its addEntry() method, which is the next step.

                I'm also on 1.6, and when I put those two keys and values, and print out the map I get
                <{/types[at0001]/items[at10004]/value=value2, /=value1}
                as expected.
                • 5. Re: Possible error in hash-algorithm for HashMap
                  EJP
                  Both keys as represented in my previous message return the same return value from function indexFor(..,..)
                  That's called a 'collision'.

                  What do you think the following 'for' loop is there for?
                  • 6. Re: Possible error in hash-algorithm for HashMap
                    843793
                    Check your assumptions at the door and, since you're digging into HashMap's source code, look into its addEntry() method, which is the next step.

                    I'm also on 1.6, and when I put those two keys and values, and print out the map I get
                    <{/types[at0001]/items[at10004]/value=value2, /=value1}
                    as expected.
                    Thanks, jverd, for your reply.How do you think that this is possible? That on my computer two keys collide and not on yours.

                    About the addEntry-method, I don't think it is relevant, because it is called after the indexFor() method, which assigns the index-number in the internal hash tale. Also the for loop which checks the existence of the key is before the addEntry-method
                    • 7. Re: Possible error in hash-algorithm for HashMap
                      843793
                      Hint: a single bucket can hold more than one entry in this implementation (and most other sane implementations).
                      • 8. Re: Possible error in hash-algorithm for HashMap
                        843793
                        Thanks all, for your answers.

                        Please let me explain my problem, because I get all kind of explanations. and I know how a hashmap works (more or less).

                        First I put: key "/" and some value
                        In function put()
                        I get hash 45
                        This results in indexFor(): 13
                        The entry is added. Good

                        Second I put key "/types[at0001]/items[at10004]/value" and some other value
                        In function put()
                        I get hash -2082588691
                        This also results in indexFor(): 13

                        It enters as it should the for-loop in the put() function.
                        The condition:
                        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                        evaluates to false
                        because
                        if (45 == -2082588691 && ( false || false))

                        So the entry is added to, on exact the same location as the previous, the previous is overwritten.
                        There is no warning, there is no way to check easy that this has happened


                        To me this feels like a bug. Please advise me how to handle this problem. I need to trust the hashmap, or at least, if it cannot be trusted, that it gives me a warning.
                        But even with a warning, or maybe I could overwrite the put() function but I don't know if that is the right solution.
                        Because, if the collision happens, what am i to do? I cannot change my key, because it is generated.

                        Thanks,
                        Bert Verhees
                        • 9. Re: Possible error in hash-algorithm for HashMap
                          EJP
                          You are wrong about all this. If two keys have the same hash code a list is formed. Thats what all that code you quoted does. The only way one can overwrite the other is if they are equal, which would indicate a bug in the equals() method concerned.

                          What is the actual problem you are trying to solve?
                          • 10. Re: Possible error in hash-algorithm for HashMap
                            843793
                            Don't bother anymore, I found the answer.

                            It ca have more values at one bucket.

                            Thanks for thinking with me.

                            Bert Verhees
                            • 11. Re: Possible error in hash-algorithm for HashMap
                              EJP
                              You were told that answer above.
                              • 12. Re: Possible error in hash-algorithm for HashMap
                                791266
                                BertVerhees wrote:
                                Please let me explain my problem, because I get all kind of explanations. and I know how a hashmap works (more or less).
                                Looks like you didn't know how they work. I think that most books on datastructures describes how hash collisions usually are handled.

                                Kaj
                                • 13. Re: Possible error in hash-algorithm for HashMap
                                  3004
                                  BertVerhees wrote:
                                  Check your assumptions at the door and, since you're digging into HashMap's source code, look into its addEntry() method, which is the next step.

                                  I'm also on 1.6, and when I put those two keys and values, and print out the map I get
                                  <{/types[at0001]/items[at10004]/value=value2, /=value1}
                                  as expected.
                                  Thanks, jverd, for your reply.How do you think that this is possible? That on my computer two keys collide and not on yours.
                                  They do collide on mine. And you'll get the same output I do, if you'll bother to try it.

                                  >
                                  About the addEntry-method, I don't think it is relevant,
                                  Of course it's relevant! Even if you think it's not, how could you go this far, with something this important and confusing, and not bother to at least check it out?

                                  Jeez, learn to check your assumptions. I shoved you through the door into the room where the answer is displayed on a big flashing neon sign, and you closed your eyes, turned around, and walked out saying, "The answer is not in here."
                                  • 14. Re: Possible error in hash-algorithm for HashMap
                                    3004
                                    BertVerhees wrote:
                                    I know how a hashmap works (more or less).
                                    Less, it would seem.
                                    To me this feels like a bug.
                                    Stop feeling and start thinking. Take the hints you were given, set aside your assumptions, take off the blinders, and rigorously investigate what's actually happening!

                                    Also try a bit of common sense: Would an API that's been around for a dozen or so years get a GA release with such a huge, glaring bug? Or is it more likely that you're just misunderstanding something?
                                    1 2 Previous Next