This discussion is archived
1 2 Previous Next 20 Replies Latest reply: Sep 13, 2010 6:06 AM by 800268 RSS

Possible error in hash-algorithm for HashMap

843793 Newbie
Currently Being Moderated
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 Guru
    Currently Being Moderated
    Maps don't have indexes. What are you talking about exactly?
  • 2. Re: Possible error in hash-algorithm for HashMap
    843793 Newbie
    Currently Being Moderated
    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 Expert
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Guru
    Currently Being Moderated
    You were told that answer above.
  • 12. Re: Possible error in hash-algorithm for HashMap
    791266 Explorer
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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