update/change java.util.Map key in place

[MooMaster]

There's probably a really obvious answer to this question, but my
GoogleFu fails me, and after looking @ (http://java.sun.com/javase/6/
docs/api/), (http://java.sun.com/docs/books/tutorial/collections/
interfaces/map.html), and comp.lang.java and this newsgroup for the
most obvious keywords, nothing came quickly enough.

I have a Map of keys and values. I want to update my map such that I
change the key via an operation on its associated values (for a lousy
example, every time I add a new value to the values list, make the key
the mean value). The Map.Entry Interface only provides a getKey()
method, so the only idiom I've been able to come up with is:

for(Map.Entry<K,V> entry : map.entrySet())
{
newKey = performOperation(entry.getValue());
map.put(newKey, entry.getValue());
map.remove(entry);
}

But the cautionary note in the Map Interface's API : "Note: great care
must be exercised if mutable objects are used as map keys. The
behavior of a map is not specified if the value of an object is
changed in a manner that affects equals comparisons while the object
is a key in the map. A special case of this prohibition is that it is
not permissible for a map to contain itself as a key. While it is
permissible for a map to contain itself as a value, extreme caution is
advised: the equals and hashCode methods are no longer well defined on
such a map."

seems to suggest that there's an in-place, easier way of doing this.
What's the best way?

 

[Lew]

I have a Map of keys and values. I want to update my map such that I
change the key via an operation on its associated values (for a lousy

A key will only have one associated value in a Map.

example, every time I add a new value to the values list, make the key
the mean value). The Map.Entry Interface only provides a getKey()
method, so the only idiom I've been able to come up with is:

for(Map.Entry<K,V> entry : map.entrySet())
{
newKey = performOperation(entry.getValue());
map.put(newKey, entry.getValue());
map.remove(entry);
}

This is likely to throw a ConcurrentModificationException, as the put and
remove operations will conflict with the loop's Iterator.

But the cautionary note in the Map Interface's API : "Note: great care
must be exercised if mutable objects are used as map keys. The

That is not what your example illustrates.

behavior of a map is not specified if the value of an object is
changed in a manner that affects equals comparisons while the object
is a key in the map."

seems to suggest that there's an in-place, easier way of doing this.
What's the best way?

How do you read from the warning that there's an in-place way to do what you
want, or that it would be easier? That warning tells me the exact opposite.

Remove the old key, modify it, then put with the new key. Don't do it inside
an iteration of the Map or you will run into trouble.

 

[MooMaster]

A key will only have one associated value in a Map.



This is likely to throw a ConcurrentModificationException, as the put and
remove operations will conflict with the loop's Iterator.


That is not what your example illustrates.



How do you read from the warning that there's an in-place way to do what you
want, or that it would be easier?  That warning tells me the exact opposite.

Remove the old key, modify it, then put with the new key.  Don't do it inside
an iteration of the Map or you will run into trouble.

(1) Good point, I should've specified the value as a list use-case
sooner
(2) Actually, "Exception in thread "main"
java.lang.ClassCastException: java.util.TreeMap$Entry cannot be cast
to java.lang.Comparable", but the point still stands
(3) That I can use a mutable object as a key, and consequently must
take great care in modifying it, seems to suggest that I can modify
the key while iterating. How is this essentially different from the
example shown in (http://java.sun.com/docs/books/tutorial/collections/
interfaces/map.html)?
"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();"
Aren't you still modifying the underlying data structure by removing
"it" within your loop?

 

[MooMaster]

A key will only have one associated value in a Map.



This is likely to throw a ConcurrentModificationException, as the put and
remove operations will conflict with the loop's Iterator.


That is not what your example illustrates.



How do you read from the warning that there's an in-place way to do what you
want, or that it would be easier?  That warning tells me the exact opposite.

Remove the old key, modify it, then put with the new key.  Don't do it inside
an iteration of the Map or you will run into trouble.

(1) Good point, I should've specified that the values as a list use-
case earlier...
(3) That I can use a mutable object as a key, and must take great care
modifying it, seems to suggest that I can modify it. While I
understand that modifying a data structure as you're iterating over it
is generally unsafe, how is this different from the from the example
shown at http://java.sun.com/docs/books/tutorial/collections/interfaces/map..html:

"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove(); "

Isn't that also removing the object from the Map while iterating over
it?

 

[Mike Schilling]

(3) That I can use a mutable object as a key, and consequently must
take great care in modifying it, seems to suggest that I can modify
the key while iterating. How is this essentially different from the
example shown in
(http://java.sun.com/docs/books/tutorial/collections/
interfaces/map.html)?
"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();"
Aren't you still modifying the underlying data structure by removing
"it" within your loop?

If you modify the key in such a way that the part of it used by the
Map (e.g. the hashCode() for a HashMap key) changes, you've broken the
Map. You must take care to avoid doing this. I suppose that you can
change some inessential part of the key without doing any damage; say,
if you have a "times used" count that isn't used to calcualte
hashCode() or checked as part of equals(), you can increment that
freely.

 

[Volker Borchert]

(3) That I can use a mutable object as a key, and must take great care
modifying it, seems to suggest that I can modify it. While I
understand that modifying a data structure as you're iterating over it
is generally unsafe, how is this different from the from the example
shown at http://java.sun.com/docs/books/tutorial/collections/interfaces/map..html:

"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove(); "

Isn't that also removing the object from the Map while iterating over
it?

Yes, but it is using the Iterator's remove() such that the Iterator
can keep itself consistent, whereas the snippet above used the
Map's remove() and put() bypassing the Iterator. For details, study
the implementations in the JDK sources.

 

[Lew]

(3) That I can use a mutable object as a key, and consequently must
take great care in modifying it, seems to suggest that I can modify
the key while iterating. How is this essentially different from the

That's modifying the key, not removing the entry from the Map. It's
structural modifications that trigger ConcurrentModificationException, i.e.,
insertions and removals, not modifications to entries in place.

example shown in (http://java.sun.com/docs/books/tutorial/collections/
interfaces/map.html)?
"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();"
Aren't you still modifying the underlying data structure by removing
"it" within your loop?

That uses the Iterator to remove the object. It's removal by something other
than the Iterator that causes a fail-fast Iterator to fail fast. Your example
upthread didn't use the Iterator to do the remove().

 

[Lew]

(3) That I can use a mutable object as a key, and must take great care
modifying it, seems to suggest that I can modify it. While I
understand that modifying a data structure as you're iterating over it
is generally unsafe, how is this different from the from the example
shown at http://java.sun.com/docs/books/tutorial/collections/interfaces/map..html:

"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove(); "

Isn't that also removing the object from the Map while iterating over
it?

Answered the first time you posted the question.

 

[MooMaster]

That's modifying the key, not removing the entry from the Map.  It's
structural modifications that trigger ConcurrentModificationException, i.e.,
insertions and removals, not modifications to entries in place.


That uses the Iterator to remove the object.  It's removal by something other
than the Iterator that causes a fail-fast Iterator to fail fast.  Your example
upthread didn't use the Iterator to do the remove().

Wasn't familiar with the concept of a "fail-fast" iterator but this
explained it fairly well
http://www.jguru.com/faq/view.jsp?EID=221988

That's modifying the key, not removing the entry from the Map.

That's the _exact_ point of my question. I don't want to remove the
key, just modify it. The whole reason I did that put/remove thing was
because I couldn't figure out how to modify in place.

After looking at Mike's post it seems that if I had my own user-
defined class as the key, which had a field that wasn't involved in
the hashCode() and equals() calculation, I could modify the key by
modifying the value of that field. However, if I use a class such as
the Double wrapper class as the key, I can't modify that since a new
Double instance would need to be created to encapsulate the resulting
value.

Consequently, the only way to modify something like:

TreeMap<Double /* mean value of list */, ArrayList<Integer> /* list of
numbers */> clusters

when I add more Integers to the ArrayList, would be to compute a new
key, copy ArrayList to the key, mark the old key for deletion, and
then do the Map update in a separate pass. Is that correct?

 

[Daniel Pitts]

(3) That I can use a mutable object as a key, and consequently must
take great care in modifying it, seems to suggest that I can modify
the key while iterating.

It doesn't suggest anything of the sort. What it means is that you can
use a mutable object as the key, as long as you don't mutate it. If you
absolutely must mutate it, you must not change the "key" portion of it
(which is generally either the equals() and hashCode, or the compareTo
ordering)

You must either remove and then add the "new" value, or leave the value
the same.

You can do this instead:

public void updateMap(Map<Foo,Bar> myMap) {
Map<Foo, Bar> newKeys = new HashMap<Foo,Bar>();
for(Iterator<Map.Entry<Foo,Bar>> it = myMap.iterator(); it.hasNext(){
Map.Entry<Foo,Bar> entry = it.next();
Foo changedFoo = calculateFoo(entry.getKey(), entry.getValue());
Bar changedBar = calculateBar(entry.getKey(), entry.getValue());
it.remove();
newKeys.put(changedFoo, changedBar);
}
myMap.putAll(newKeys);
}

 

[Mark Space]

That's the _exact_ point of my question. I don't want to remove the
key, just modify it. The whole reason I did that put/remove thing was
because I couldn't figure out how to modify in place.

You're missing the point. If you modify a key in place, that key will
then be in the wrong spot in the Map, and a look-up won't find it later.

Maps are, basically, ordered. If you have three double keys stored in a
Map like this:

1: 1.112223
2: 2.333444
3: 3.444455

And then you change the last one to, for example, 0.111222, that key
will never be found, because it's out of order. The Map will look in
position 1, find 1.112223 and say "Well, this is bigger than the key, so
it should have been found by now, so I'll stop looking."

Not all maps use linear ordering like this, but they all have some kind
of order, even hash maps (which order on index based on hashcode) and if
you change the key without re-ordering it in the map somehow you'll be SOL.

Consequently, the only way to modify something like:

TreeMap<Double /* mean value of list */, ArrayList<Integer> /* list of
numbers */> clusters

when I add more Integers to the ArrayList, would be to compute a new
key, copy ArrayList to the key, mark the old key for deletion, and
then do the Map update in a separate pass. Is that correct?

??? Why don't you just remove the key-value pair, modify as needed, then
re-add them both? Why do you have to copy the ArrayList?

arrayList = treeMap.get( 1.112223 );
treeMap.remove( 1.112223 );
arrayList.add( 42 );
double newMean = calculateMean( arrayList );
treeMap.put( newMean, arrayList );

 

[Lew]

That's the _exact_ point of my question. I don't want to remove the
key, just modify it. The whole reason I did that put/remove thing was
because I couldn't figure out how to modify in place.

Others addressed the point of modifying the key in place. I was addressing
the points you made about removing keys. Among other things, you asked about
the difference between the two:

(3) That I can use a mutable object as a key, and consequently must
take great care in modifying it, seems to suggest that I can modify
the key while iterating. How is this essentially different from the
example shown in (http://java.sun.com/docs/books/tutorial/collections/
interfaces/map.html)?
"// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();"
Aren't you still modifying the underlying data structure by removing
"it" within your loop?

which AIUI also was asking about the difference between removal via an
Iterator and removal by something other than the Iterator.

You brought up removal from the Map. I was addressing the points you brought
up. That you also brought up modification in place was not for me to address,
except to explain the difference. Don't keep shifting ground. I was
addressing the points you raised.

 

[Tom Anderson]

Consequently, the only way to modify something like:

TreeMap<Double /* mean value of list */, ArrayList<Integer> /* list of
numbers */> clusters

when I add more Integers to the ArrayList, would be to compute a new
key, copy ArrayList to the key, mark the old key for deletion, and then
do the Map update in a separate pass. Is that correct?

Pretty much. As others have said or implied, you can't change the value,
the true value, of the key of an entry that's already in a map.

I'd be tempted to deal with this situation by creating a new map every
time, rather than replacing entries. Then you can just do:

private Map<Double, List<Integer>> clusters ;

double mean(Collection<Integer> values) {
int sum = 0 ;
for (int value: values) sum += value ;
return (double)sum / values.size() ;
}

void updateMap() {
Map newClusters = new HashMap() ;
for (List<Integer> cluster: clusters.values())
newClusters.put(mean(cluster), cluster) ;
clusters = newClusters ;
}

Alternatively, if you don't insist on doing the update in a single pass,
i'd be tempted to wrap the map and the update logic up in a single object
which did the updating on every mutation. Thinking about it, this would be
pretty ghastly to program, but would mean you had a really nice interface:

Map<Double, List<Integer>> clusters = new ClusterMap() ;
List<Integer> cluster = clusters.get(2.4) ;
cluster.add(9) ; // automatically updates the cluster map

You'd need to write a class for the individual cluster, which traps
mutations and triggers the update, and then a class for the whole map.

tom