9

Say you have a key class (KeyClass) with overridden equals, hashCode and clone methods. Assume that it has 2 primitive fields, a String (name) and an int (id).

Now you define

KeyClass keyOriginal, keyCopy, keyClone;

keyOriginal = new KeyClass("original", 1);
keyCopy = new KeyClass("original", 1);
keyClone = KeyClass.clone();

Now

keyOriginal.hashCode() == keyCopy.hashCode() == keyClone.hashCode()
keyOriginal.equals(keyCopy) == true
keyCopy.equals(keyClone) == true

So as far as a HashMap is concerned, keyOriginal, keyCopy and keyClone are indistinguishable.

Now if you put an entry into the HashMap using keyOriginal, you can retrieve it back using keyCopy or keyClone, ie

map.put(keyOriginal, valueOriginal);
map.get(keyCopy) will return valueOriginal
map.get(keyClone) will return valueOriginal

Additionally, if you mutate the key after you have put it into the map, you cannot retrieve the original value. So for eg

keyOriginal.name = "mutated";
keyOriginal.id = 1000;

Now map.get(keyOriginal) will return null

So my question is

when you say map.keySet(), it will return back all the keys in the map. How does the HashMap class know what are the complete list of keys, values and entries stored in the map?

EDIT So as I understand it, I think it works by making the Entry key as a final variable. 

static class Entry<K,V> implements Map.Entry<K,V> { 
  final K key;

(docjar.com/html/api/java/util/HashMap.java.html). So even if I mutate the key after putting it into the map, the original key is retained. Is my understanding correct? But even if the original key reference is retained, one can still mutate its contents. So if the contents are mutated, and the K,V is still stored in the original location, how does retrieval work?

EDIT retrieval will fail if you mutate the key after putting into the hashmap. Hence it is not recommended that you have mutable hashmap keys.

Basanth Roy
  • 6,272
  • 5
  • 25
  • 25
  • 2
    why not just look at the source yourself, it is public and easily accessible –  Mar 07 '12 at 14:12
  • if it didn't it wouldn't be much of a data structure now would it? How do you think it's able to lookup the particular key you want? – Nim Mar 07 '12 at 14:13
  • [The source](http://www.docjar.com/html/api/java/util/HashMap.java.html) for the curious. – Alexander Pavlov Mar 07 '12 at 14:20
  • Looking up a single key is just a question of calculating hashCode and then comparing each collided key using equals. But the HashMap needs to be aware of what are all the keys stored in it; without the client passing in a key. So The answer by Louis below looks like how that is happening. – Basanth Roy Mar 07 '12 at 14:21

3 Answers3

9

HashMap maintains a table of entries, with references to the associated keys and values, organized according to their hash code. If you mutate a key, then the hash code will change, but the entry in HashMap is still placed in the hash table according to the original hash code. That's why map.get(keyOriginal) will return null.

map.keySet() just iterates over the hash table, returning the key of each entry it has.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • Thanks. "If you mutate a key, then the hash code will change, but the entry in HashMap is still placed in the hash table according to the original hash code." I read the source code. So as I understand it, I think it works by making the Entry key as a final variable. static class Entry implements Map.Entry { final K key; (http://www.docjar.com/html/api/java/util/HashMap.java.html). So even if I mutate the key after putting it into the map, the original key is retained. Is my understanding correct? – Basanth Roy Mar 07 '12 at 15:41
  • It holds a _reference_ to the key. If you mutate the key, then basically, the `entrySet()` of the `HashMap` will see the modified key, but `get(key)` will be looking in the wrong place, so it'll return `null` when you try `map.get(key)`. Basically, having mutable keys in a `Map` is just asking for trouble, and actually going ahead and mutating keys in a `Map` is like shooting yourself in the kneecaps. – Louis Wasserman Mar 07 '12 at 15:57
  • Thanks again. But what I still haven't understood is this. You have keyOriginal and keyCopy with the same field values within them. Now you put keyOriginal in the map. Say it goes into position 100 in the internal hashmap entry table. Now you mutate keyOriginal. It is still stored in position 100. Now if you say map.get(keyCopy), it does return the original associated value. How is it able to do that if keyOriginal.equals(keyCopy) is false ? – Basanth Roy Mar 07 '12 at 16:12
  • Have you tested that? I would be very surprised if that's true. I would strongly expect `map.get(keyCopy)` to return `null`. – Louis Wasserman Mar 07 '12 at 16:14
  • Yes, I have tested that. I will add the test code in a new question. I can't add it here since it would be too long. – Basanth Roy Mar 07 '12 at 16:15
  • I tested it with https://gist.github.com/1994139, and `map.get(keyCopy)` does indeed return `null`. The problem must be elsewhere. – Louis Wasserman Mar 07 '12 at 16:17
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/8643/discussion-between-louis-wasserman-and-rationalspring) – Louis Wasserman Mar 07 '12 at 16:19
1

If you change the entry but not the hashCode, you are safe. For this reason it is considered best practice to make all fields in the hashCode, equals and compareTo, both final and immutable.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • Thanks. Good info. -- "If you change the entry but not the hashCode, you are safe." -- I would add that you are still not safe since equals will fail. – Basanth Roy Mar 07 '12 at 16:43
  • So I guess it is safe to say that if you mutate the key (hashCode is different and equals is false) after adding to map, then your retrieval will fail. – Basanth Roy Mar 07 '12 at 16:46
  • Unless that is what you intended. ;) If it has to be mutable, you can remove the key, update it and add it back. Its only a problem if you change the key while its a key to a map (or an element of a Set for the same reason) – Peter Lawrey Mar 07 '12 at 16:48
  • Yes true, that was not my intention in this case. – Basanth Roy Mar 07 '12 at 16:51
1

Simply put, the HashMap is an object in your computer's memory that contains keys and values. Each key is unique (read about hashcode), and each key points to a single value.

In your code example, the value coming out of your map in each case is the same because the key is the same. When you changed your key, there is no way to get a value for it because you never added an item to your HashMap with the mutated key.

If you added the line:

map.put("mutated", 2);

Before mutating the key, then you will no longer get a null value.

schottsfired
  • 131
  • 5