my dog learned polymorphism*
The moose likes Java in General and the fly likes Behaviour HashMap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Behaviour HashMap" Watch "Behaviour HashMap" New topic
Author

Behaviour HashMap

Sandeep Jindal
Ranch Hand

Joined: Aug 25, 2003
Posts: 180
Hi All,

I was trying to do the following thing with HashMap.

I create a Map<Key, String>


Idea of this key class is that the object of Key is same if value in i is same.

Now, I created the following Map.



Now, I change the Key Key(2) such that value of i in it is 1 which is same as of the Key(1).



Now, the Map has two key which actually equals, which is not possible if we add the keys using Put method.
Also, on getting previous one is generated.

This is fine.

But the interesting part is that when i remove the key

only one key is lost.

Also, if I removed once, I cannot retrieve the re

That means the Key whose value was 2 is lost (another memory leak in Java). Can anybody explain/put his thoughts on this behavior?
Or can anybody answer the followings?
1. Why only first object is returned and not second (always) when there are two keys.
2. When removing the key, why did not it remove both?
3. Why did map.containsValue("2") returned true, even when after removed the key?




SCJP 5.0
http://sites.google.com/site/duddlutechnologies/home
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38513
    
  23
That sounds like the typical behaviour of a hash-based class. If the hash code of the key changes, the hash-based class will assume you now have a different key.

Yes, there is a possible memory leak, but that is because you have not followed the advice in the Map interface. You have used a mutable class, which by the way has a poorly-designed equals() method. [Using instanceof in an equals method can cause incorrect behaviour if an instance of a subclass is submitted for equals().]

This is what happens with a hash-based Map (which I shall call HM because there are other classes besides HashMap which show the same behaviour):
  • Key and Value are passed, and put somewhere (eg an array) depending on the hash code of the key.
  • The HM keeps references to key and value until the HM is garbage-collected, or the key and value are removed with the remove() method.
  • The HM keeps the references in the same place unless it is full and re-hashing occurs.
  • If you change the state of your object, you will look in the wrong place if you try to retrieve the value. If the hash code is different, the HM will look in the wrong location for the key.
  • If you try to get() from the wrong location, you won't find anything.
  • If you try to remove from the wrong location, you won't find anything to remove.

  • So, your problem is typical of what happens if you try using a mutable object as the Key for an HM.
    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    Hi Campbell,

    Thanks for the Quick and detailed reply.

    I understand the issue. The issue was the original Key have id as 2 had hashCode as 2 and they key is stored with this hashCode in Map.
    Now I change the value of key to 1. Thus when i try to remove key(1), it removed the key whose hashCode is 1 and value is 1 (as implemented in the code), thus key(2) whose hash code was 2 is never removed. Please correct if my understanding is wrong.


    On the side note, can you please comment on why the equals method is poorly designed? (I might be missing some basic design principle)

    Thanks
    Sandeep Jindal
    Jesper de Jong
    Java Cowboy
    Saloon Keeper

    Joined: Aug 16, 2005
    Posts: 14117
        
      16

    Sandeep Jindal wrote:Now, I change the Key Key(2) such that value of i in it is 1 which is same as of the Key(1).

    If you do that while you've used that Key object in the map, then that's a problem. The Map doesn't know that the value of the key has changed and gets confused, and the behaviour of the map will become unpredictable. You should only use immutable classes a keys in a map.

    Sandeep Jindal wrote:Now I change the value of key to 1. Thus when i try to remove key(1), it removed the key whose hashCode is 1 and value is 1 (as implemented in the code), thus key(2) whose hash code was 2 is never removed. Please correct if my understanding is wrong.

    It doesn't make much sense to try to reason what will happen in this case - the behaviour is undefined, so in principle anything can happen. It depends on how HashMap is implemented internally. What happens may be different on different versions of Java.


    Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
    Scala Notes - My blog about Scala
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38513
        
      23
    The instanceof keyword/oparator doesn't do what you think it does.

    Imagine this classand thisas well as your previous Key class. Now k.equals(kk) and kk.equals(k) should give the same result. Compile those classes, correct any spelling errors, and see what happens.

    Look for the appropriate chapter in Bloch's Effective Java (it used to be possible to find that part of the 1st edition as a sample chapter online) or Google for Angelika Langer Java equals for lots more information.

    In your case, the best design is to change your Key class to an immutable class. Change public class Key to public final class Key and change int i to final int i. In a final class, the instanceof keyword/operator does exactly what you think it does, so making the class final allows you to get correct results without changing the equals() method.
    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    Thanks for your answers.
    Understand the contract of HashMap which says do not play with keys, or never play with keys atleast when iterating (correct?)

    but what if I have a requirement in such a way that I need to update my keys based on some operations and that is my requirement.
    Can you please suggest what to do in that case.

    Example of my requirement is:
    I maintain No of Order and the residuals of that orders.
    While doing some operations, I need to modify the No Of orders.

    Also, I need to maintain Map whose key is No Of orders because I frequently require to get the residuals for a particular no of orders (in short, I need some value based on some key(no of orders) and that key needs to be modifiable).
    What do the experts suggest in this case?

    Regards
    Sandeep Jindal
    Jesper de Jong
    Java Cowboy
    Saloon Keeper

    Joined: Aug 16, 2005
    Posts: 14117
        
      16

    Sandeep Jindal wrote:but what if I have a requirement in such a way that I need to update my keys based on some operations and that is my requirement.
    Can you please suggest what to do in that case.

    The only thing that works is: remove the element from the map, change the key, and put it back in the map. There's no way to make it work while leaving the key in the map.
    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    Thanks Jesper!

    What I have done is (even before your reply) following:

    I have taken all the key and put that into an ArrayList.
    Now, I iterated the arraylist and changed the values of the keys (and since its refences, it has changed the corrospding keys)

    Ofcourse, I have taken care that the hashcode for all these key is same(which was very important).

    Please comment on this, if you think this is not the correct or not the best approach.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38513
        
      23
    I don't understand your approach with a List. It seems to confuse things even more. How can you change the values of the keys without changing the hash code? That looks like a poorly designed hashCode method; you should attempt to return different results from objects which are not "equal()" to each other.

    Jesper has already told you only to use immutable objects as keys in a Map.
    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    Hi Campbell,

    Thanks for your answer.
    To explain you the scenario:
    I have Order ID and Number of Orders. For this I store some information.
    e.g.
    (OID: 1, NO 2 AND OID: 2, NO. 3 ) is one key
    (OID: 2, NO 3 AND OID: 4, NO. 3 ) is another key


    Now, I as part of my algoirthm, I need to store and get Information for this Key (OrderID, Number).

    Also, in some process of my algorithm, say I got I more order and I need to add this in each key.
    Say I got another OID:6, No.1. I need to add this into each key and my keys wills be
    (OID: 1, NO 2 AND OID: 2, NO. 3, OID:6, No.1 ) is one key
    (OID: 2, NO 3 AND OID: 4, NO. 3, OID:6, No.1 ) is another key


    I could have used different approach, but I frequency need Values based on the keys mentioned above.

    This is my scenario and I need to update keys for some operation.

    I totally agree with you that they List approach I mentioned is very bad in term of HashCode, but this is the best I could think of.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38513
        
      23
    Don't understand the problem. Sorry.

    I think you will have to write it with a pencil and paper, going from OID: 1, No 2 and OID: 2, No 3 to a particular product ordered, and similarly for the other numbers. Then write down how you would change the order number for that product.
    Patricia Samuel
    Ranch Hand

    Joined: Sep 12, 2007
    Posts: 300
    It took me a long time to understand this post

    I think what Jesper has suggested is the way it can work. You should remove the key and then add new key. I hope you don't want to keep the previous key as well.

    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    I am sorry, I might have confused you.

    I put it another way. I have Orders and Order's Residuals.
    Since I need to get Residuals for a particular type of order, I am strong it in a Map<Orders, Residuals> Is that fine?

    Now, Orders which is a key, is a Map<ID[Integer], Number[Integer]> (this map is not a problem).
    Say my Initial state is this.
    Order<{1,1}>, Residual1
    Order<{1,2}>, Residual2
    Order<{2,2}>, Residual3


    Now, for each of entry in this Map, I need to add one more Order <{1,1}> which shall result the following:
    Order<{1,2}>, Residual1
    Order<{1,3}>, Residual2
    Order<{2,2}, {1,1}>, Residual3



    I understood what Jesper said and one of the right ways but it would work for me, unless I remove all and then start adding and for this, I am temporary saving the keys in list.
    Patricia Samuel
    Ranch Hand

    Joined: Sep 12, 2007
    Posts: 300
    Great Confusion

    Well, giving it a try what i understood from the last post -

    You want your map like this after adding {1,1}

    Order<{1,2}>, Residual1
    Order<{1,3}>, Residual2
    Order<{2,2}>, Residual3
    Order<{1,1}>, Residual3



    Please confirm.
    Sandeep Jindal
    Ranch Hand

    Joined: Aug 25, 2003
    Posts: 180
    Yes Patricia , exactly!

    And since {1,1} is {Order ID, No Of Orders}, thus
    adding {1,1} into {1,2} shall result in {1,3} and
    adding {1,1} into {2,2} shall result in {2,2}, {1,1}

    Hope that solved confusion
    Patricia Samuel
    Ranch Hand

    Joined: Sep 12, 2007
    Posts: 300
    No
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: Behaviour HashMap