Sunday, August 13, 2006

Improved Map Iteration

When some one new to Java comes to play, first thing they do, they re-invent the wheel. Such wheel can be a class that is already implemented in java.util package. Yes! Collections and Maps! Later, as you become a senior Java developer you alredy know the narrow places in the "Utils" valley. And yet we can make mistakes.

Such mistake can be the following implementation of the method that calculates the size of the collection.

private Collection myStuff = ...

public int calculateSize() {
int count = 0;
for (Iterator it = myStuff.iterator(); it.hasNext(); it.next()) {
count++;
}
return count;
}

This can be easily fixed by

public int calculateSize() {
return myStuff.size();
}

Another, more frequent example of bad performance is a condition where one wants to know if there are any objects in the collection, but does not really care how many there are.

if (myStuff.size() == 0) {
// do something
}

Remember size() method may possibly calculate the size and therefore generally is slower than a call to isEmpty() method. Therefore the fix is obvious.

if (myStuff.isEmpty()) {
// do something
}

Could you imagine that I once worked for a company where the senior developers did not know about Iterators? So instead of

for (Iterator it = myStuff.iterator(); it.hasNext();) {
Object item = it.next();
// do something with the item
}

they had

for (int i = 0; i < myStuff.size(); i++) {
Object item = myStuff.get(i);
// do something with the item
}

and on top of that myStuff was a Vector, which is synchronized. Very sloooow code!

Nevertheless my point is: Know your collections!

Now back to the topic of improving the Map iteration. Well, it really depends what we need to do at each step of our iteration.

If you need to iterate over the keys of the Map do this

for (Iterator it = myMap.keySet().iterator(); it.hasNext();) {
Object key = it.next();
// do something with the key
}

And if you need to iterate over the values of the Map do this

for (Iterator it = myMap.values().iterator(); it.hasNext();) {
Object value = it.next();
// do something with the value
}

But what if we need both the key and the value? The usual approach and very bad approach is to get the set of keys, iterate over them and get the value for each key.

for (Iterator it = myMap.keySet().iterator(); it.hasNext();) {
Object key = it.next();
Object value = myMap.get(key);
// do something with the key and the value
}

What is wrong about this? Nothing! You can do it this way and it's perfectly fine. It is just very inefficient as at each iteration a map needs to look up the value for a given key. It is better to iterate over map entries. There is a special interface Map.Entry that can be used to retrieve the key and the value of each entry in the map. So the previous example can be transformed into

for (Iterator it = myMap.entrySet().iterator(); it.hasNext();) {
Map.Entry entry = (Map.Entry) it.next();
Object key = entry.getKey();
Object value = entry.getValue();
// do something with the key and the value
}

Don't forget to change myMap.get(key) to entry.getValue(), otherwise you are not gaining anything from this modification. I did this recently, I omitted to change it, even worse - I changed it to myMap.get(entry.getValue()). As a result the map was not finding anything... Luckily, we had tests around the class I modified and my stupid mistake was caught early.

Have the tests ready before making changes! Even experienced people make mistakes.

13 comments:

Anonymous said...

thank you, this is quite helpful

JAW said...

thanks! this is helpful

Anonymous said...

Thanks!! It has helped me a lot

Anonymous said...

Thanks, very useful.
May be you just should update your samples to Java 5

manuodycpl

naveen said...

I think there is another better way to iterate over key and values of map i.e.

for (Object key:myMap.keySet()) {
// do something with the key
}

for (Object value:myMap.values()) {
// do something with the value
}

Dushan Hanuska said...

True. If you don't need the value (first case) or the key (second case) during the iteration.

Sabri Onur Tüzün said...

The last one is the best way...

Anonymous said...

When using generics and and myMap is of type
Map[String,String]
then you can also use this construct (replace [,] accordingly):

for (Iterator[Map.Entry[String,String]] it = umlautMap.entrySet().iterator(); it.hasNext();) {
Map.Entry[String,String] entry = it.next();
String key = entry.getKey();
Object value = entry.getValue();
// do something with the key and the value
}

silence.is.saftey said...

Why thank you! using this in a school project :D

Anonymous said...

For the record, accessing Vectors outside of an Iterator construct (that is, by the "slow" method of using 'get') is actually faster.

The senior developers were correct in doing what they were doing.

Why? Vector implements RandomAccess (http://java.sun.com/j2se/1.5.0/docs/api/java/util/RandomAccess.html), which specifically states that using the 'get' method is quicker than using an iterator.

Read it.

Anonymous said...

It was really helpful.

Gaurav said...

Couple of more advanced ways to iterate over Map in Java

Santhana m said...

Thanks for you post.and i think this is also one of the best way to iterate map without using iterator,
Map map = ...;
for (Map.Entry entry : map.entrySet()) {
String key = entry.getKey();
Thing thing = entry.getValue();
}


Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.