Java: Iteration through HashMap, which is more efficient?

Question

Given the following code, with two alternative ways to iterate through it,
Is there a performance difference between the two methods?

Map<String, Integer> map = new HashMap<String, Integer>(); //populate map //alt. #1 for (String key : map.keySet()) { Integer value = map.get(key); //use key and value } //alt. #2 for (Map.Entry<String, Integer> entry : map.entrySet()) { String key = entry.getKey(); Integer value = entry.getValue(); //use key and value } 

I tend to think that alt. #2 alt. #2 is a more efficient means of repeating through the whole map (but I could be wrong)

Answer 1

Your second option is definitely more efficient, since you only search once compared to n number of times in the first option.

But nothing is better than trying when you can. So here goes -

(Not perfect, but good enough to test assumptions on my car too)

 public static void main(String args[]) { Map<String, Integer> map = new HashMap<String, Integer>(); // populate map int mapSize = 500000; int strLength = 5; for(int i=0;i<mapSize;i++) map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt()); long start = System.currentTimeMillis(); // alt. #1 for (String key : map.keySet()) { Integer value = map.get(key); // use key and value } System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms"); start = System.currentTimeMillis(); // alt. #2 for (Map.Entry<String, Integer> entry : map.entrySet()) { String key = entry.getKey(); Integer value = entry.getValue(); // use key and value } System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms"); } 

RESULTS (some interesting)

With int mapSize = 5000; int strLength = 5; int mapSize = 5000; int strLength = 5;
Alt # 1 took 26 ms
Alt # 2 took 20 ms

With int mapSize = 50000; int strLength = 5; int mapSize = 50000; int strLength = 5;
Alt # 1 took 32 ms
Alt # 2 took 20 ms

With int mapSize = 50000; int strLength = 50; int mapSize = 50000; int strLength = 50;
Alt # 1 took 22 ms
Alt # 2 took 21 ms

With int mapSize = 50000; int strLength = 500; int mapSize = 50000; int strLength = 500;
Alt # 1 took 28 ms
Alt # 2 took 23 ms

With int mapSize = 500000; int strLength = 5; int mapSize = 500000; int strLength = 5;
Alt # 1 took 92 ms
Alt # 2 took 57 ms

... etc.

Answer 2

The second fragment will be a little faster, since it does not need to search for keys again.

HashMap iterators call the nextEntry method, which returns Entry<K,V> .

Your first fragment discards the value from the record (in KeyIterator ), and then looks for it again in the dictionary.

The second fragment uses the key and value directly (from EntryIterator )

(Both keySet() and entrySet() cheap calls)

Answer 3

The latter is more effective than the first. A tool like FindBugs will actually designate the former and prompt you to do the latter.

Answer 4

Map

Map<String, Integer> map = new HashMap<String, Integer>();

Besides two options, there is one more.

1) keySet () - use it if you need to use only keys

 for ( String k : map.keySet() ) { ... } 

2) entrySet () - use it if you need both: keys and values

 for ( Map.Entry<String, Integer> entry : map.entrySet() ) { String k = entry.getKey(); Integer v = entry.getValue(); ... } 

3) values ​​() - use it if you only need values

 for ( Integer v : map.values() ) { ... } 

Answer 5

bguiz,

I think (I don't know) that the EntrySet iteration (alternative 2) is a little more efficient, simply because it does not have a hash for each key to get its value ... Having said that, computing the hash is O (1) operation for each entry, and therefore we ONLY say O (n) throughout HashMap ... but note that this only applies to HashMap ... other Map implementations may have VERY different performance characteristics.

I really think that you will be pushing to actually NOTICE the difference in performance. If you're interested, why not set up a test script during both iteration methods?

If you don’t have a REAL one reporting a performance problem, then you are really worried about not so much ... A few ticks here and there will not affect the general usability of your program.

I believe that many, many other aspects of the code are generally more important than direct work. Of course, some blocks are "performance critical", and this is known before it is even written, it was tested without problems ... but such cases are quite rare. As a general approach, it’s better to focus on writing complete, correct, flexible, testable, reusable, readable, supported code ... CAN performance can be built later, as needed.

Version 0 should be AS SIMPLE AS POSSIBLE without any "optimizations."

Answer 6

In general, the second will be slightly faster for HashMap. It really matters if you have a lot of hash collisions, since then the get(key) call becomes slower than O(1) - it gets O(k) , and k is the number of records in the same bucket (t .e. The number of keys with the same hash code or another hash code that is still displayed in the same bucket - this depends on the capacity, size and load factor on the map).

The input-iteration option doesn't have to do a search, so here it gets a little faster.

Another note. If the capacity of your map is much larger than the actual size, and you often use iterations, you can use LinkedHashMap instead. It provides O(size) instead of O(size+capacity) complexity for a full iteration (as well as a predictable iteration order). (You should still measure whether this actually provides an improvement, as factors may vary. LinkedHashMap has a large overhead for creating a map.)