Behaviour HashMap

[Sandeep Jindal]

Hi All,

I was trying to do the following thing with HashMap.

I create a Map<Key, String>

  

public class Key {
	public int i;
	
	public Key(int _i){
		this.i = _i;
	}
	
	@Override
	public boolean equals(Object o){
		
		if (o instanceof Key){
			Key k = (Key)o;
			if (k.i == this.i){
				return true;
			}
		}
		return false;
	}
	
	@Override
	public int hashCode(){
		return i;
	}
	
	public String toString(){
		return " Key:" + i;
	}
}

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.

    
HashMap<Key, String> map = new HashMap<Key, String>();
map.put(new Key(1), "1");
map.put(new Key(2), "2");

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

    
Iterator it = map.keySet().iterator();
  while(it.hasNext()){
  Key k = (Key)it.next();
  if(map.get(k).equals("2")){
     k.i--;
}

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

   map.get(new Key(1)) 

previous one is generated.

This is fine.

But the interesting part is that when i remove the key

   map.remove(new Key(1)) 

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?

[Campbell Ritchie]

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]

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]

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.

[Campbell Ritchie]

The instanceof keyword/oparator doesn't do what you think it does.

Imagine this class

public class SkeletonKey extends Key
{
    private int j;

    public SkeletonKey(int i, int j)
    {
        super(i);
        this.j = j;
    }

    @Override
    public int hashCode()
    {
       return super.hashCode() * 31 + j;
    }

    @Override
    public boolean equals(Object obj)
    {
        return obj instanceof SkeletonKey &&
                        ((SkeletonKey)obj).i == this.i &&
                        ((SkeletonKey)obj).j == this.j;
    }
/*
 *   Other methods maybe
 */
}

and this

public class KeyedUp
{
    public static void main(String[] args)
    {
       Key k = new Key(123);
       Key kk = new SkeletonKey(123, 456);
       System.out.printf("k.equals(kk): %b and kk.equals(k): %b%n",
                     k.equals(kk), kk.equals(k));
    }
}

as 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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

No