[java] Structural modification ook voor updaten values?

[flowerp]

Ik heb een HashMap waar values in zitten die ik soms moet updaten. De eigenlijke situatie is iets complexer, maar vereenvoudigt komt het er op neer dat ik over alle keys van de map ittereer. Als de value dan een bepaalde waarde heeft verander ik deze in een andere value.

Je mag volgende de API tijdens het itereren over een HashMap geen "structural modification" doen, behalve door gebruik te maken van de add en remove methods van de iterator.

Nu vroeg ik me af of het updaten van een value ook onder een structural modification valt. Aan de ene kant zou je zeggen van wel, namelijk het is een add. Aan de andere kant, als de key hetzelfde is als de huidige key, zal de value dus ook in exact dezelfde bucket moeten vallen. De plek in de bucket kan natuurlijk wel verschillen als er al collisions zijn.

Het gaat om deze pseudo code (generic data en methods etc even weggehaald):

Java:

// Change every 3 in the map into a 4
for ( Map.Entry entry : myMap.entrySet ) {
   if (myMap.key == 3 ) {
       map.add(myMap.key, 4);  
   }
}

Als ik dit test met een groot aantal waardes komt er nooit een ConcurrentModificationException, maar dat zegt natuurlijk niets over het feit of dit stukje code theoretisch unsafe is.

Wat denken jullie?

[Verwijderd]

Aan het begin van de for-loop haal je eenmalig een entrySet() op. Daar itereer je vervolgens over. Je itereert dus feitelijk niet over de HashMap zelf, maar over een snapshot van zijn entries voordat je begon met loopen. Daarom zou dit volgens mij geen probleem moeten zijn.

Edit: dit is dus onjuist. Zie documentatie bij entrySet():

public Set<Map.Entry<K,V>> entrySet():

Returns a collection view of the mappings contained in this map. Each element in the returned collection is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

[ Voor 50% gewijzigd door Verwijderd op 21-01-2007 16:37 . Reden: t klopt niet ]

[flowerp]

Verwijderd schreef op zondag 21 januari 2007 @ 16:34:
Aan het begin van de for-loop haal je eenmalig een entrySet() op. Daar itereer je vervolgens over. Je itereert dus feitelijk niet over de HashMap zelf, maar over een snapshot van zijn entries voordat je begon met loopen. Daarom zou dit volgens mij geen probleem moeten zijn.

Zo simpel is het nou ook weer niet De entryset is geen snapshot maar een view.

code:

entrySet

public Set<Map.Entry<K,V>> entrySet()

Returns a collection view of the mappings contained in this map.
Each element in the returned collection is a Map.Entry.
The collection is backed by the map, so changes to the map are
reflected in the collection, and vice-versa

[Verwijderd]

inderdaad flowerp, dat zag ik ook al

Maar in de API staat ook:

If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)

Dus kennelijk is jouw aanpak wel safe..

Verder heb ik de indruk dat de info die jij noemt over structural modification en add/remove methode van de iterator op een map slaat die gewrapped is met Collections.synchronizedMap (of heb je dat ook gedaan?).

[Robtimus]

Waarom verander je niet gewoon de value van je Map.Entry?

[flowerp]

IceManX schreef op zondag 21 januari 2007 @ 17:02:
Waarom verander je niet gewoon de value van je Map.Entry?

Dat is waarschijnlijk idd de beste aanpak

Ik had deze method nog niet eerder gezien. In de API stond namelijk dat bij de iterator behorende bij de entry collection, add niet supported was. Dat slaat natuurlijk op een gehele entry.

Stomme is dat ik nog wilde kijken wat een Entry precies allemaal kon (via method completion in Eclipse), maar dat ik dacht dat ik beter eerst even de API van HashMap kon gaan lezen.

Een andere methode die ik bedacht had was trouwens om eerst alle geupdate keys in een andere Map te storen, en dan na de iteratie weer terug in de originele Map te zetten. Die Entry.setValue lijkt me echter veel beter.

[Robtimus]

Er is trouwens ook een reden dat er geen setKey() method is. Zodra voor een key in een HashMap de hash code verandert kan dat object niet meer teruggevonden worden. Hetzelfde geldt voor de compareTo method returnwaarde met TreeMaps.

[flowerp]

IceManX schreef op zondag 21 januari 2007 @ 17:40:
Er is trouwens ook een reden dat er geen setKey() method is. Zodra voor een key in een HashMap de hash code verandert kan dat object niet meer teruggevonden worden.

ja, dat zou gelden als je voor die specificieke entry opeens de key zou veranderen. Een entry komt namelijk overeen met een exacte plek in de interne storage van de Map, en die exacte plek komt in eerste instantie overeen met de hash code. De value van een entry is pas echt nodig om een object te vinden, als er meerdere objecten in de Map gestopt worden met dezelfde hash code. Al deze objecten worden dan sequentieel doorzocht, totdat er een hit is.

Een setKey in een entryset iterator zou in theorie wel kunnen. De iterator weet via via vanaf welke Map hij kwam, en kan dus op de achtergrond een remove van de entry doen en een re-insert. Tegelijkertijd kan ie dan deze entry op een speciale interne lijst zetten, zodat bij een next() deze entry niet meer langskomt.

Waarschijnlijk komen bij deze laatste aanpak nog wel een aantal tricky corner cases om de hoek kijken, zeker voor verschillende soorten Maps, en hebben ze het daarom maar niet gedaan.