Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Performance considerations for keySet() and entrySet() of Map

All,

Can anyone please let me know exactly what are the performance issues between the 2? The site : CodeRanch provides a brief overview of the internal calls that would be needed when using keySet() and get(). But it would be great if anyone can provide exact details about the flow when keySet() and get() methods are used. This would help me understand the performance issues better.

like image 820
name_masked Avatar asked Oct 06 '10 06:10

name_masked


People also ask

What is keySet and entrySet?

Map Interface is present in Java. util package, which provides mainly three methods KeySet(),entrySet() and values(). These methods are used to retrieve the keys of the map, key-value pairs of the map, and values of the map respectively.

What is use of keySet () in map?

keySet() method in Java is used to create a set out of the key elements contained in the hash map. It basically returns a set view of the keys or we can create a new set and store the key elements in them. Parameters: The method does not take any parameter.

What does the map methods returning views entrySet () return?

It basically returns a set view of the hash map or we can create a new set and store the map elements into them.

How does HashMap entrySet work?

Entry<K,V>> entrySet(): This method returns a Set view of the HashMap mappings. This set is backed by the map, so changes to the map are reflected in the set, and vice-versa. public V get(Object key): Returns the value mapped to the specified key, or null if there is no mapping for the key.


2 Answers

The most common case where using entrySet is preferable over keySet is when you are iterating through all of the key/value pairs in a Map.

This is more efficient:

for (Map.Entry entry : map.entrySet()) {     Object key = entry.getKey();     Object value = entry.getValue(); } 

than:

for (Object key : map.keySet()) {     Object value = map.get(key); } 

Because in the second case, for every key in the keySet the map.get() method is called, which - in the case of a HashMap - requires that the hashCode() and equals() methods of the key object be evaluated in order to find the associated value*. In the first case that extra work is eliminated.

Edit: This is even worse if you consider a TreeMap, where a call to get is O(log2(n)), i.e. the comparator for will may need to run log2(n) times (n = size of the Map) before finding the associated value.

*Some Map implementations have internal optimisations that check the objects' identity before the hashCode() and equals() are called.

like image 125
Michael Barker Avatar answered Sep 20 '22 10:09

Michael Barker


First of all, this depends entirely on which type of Map you're using. But since the JavaRanch thread talks about HashMap, I'll assume that that's the implementation you're referring to. And lets assume also that you're talking about the standard API implementation from Sun/Oracle.

Secondly, if you're concerned about performance when iterating through your hash map, I suggest you have a look at LinkedHashMap. From the docs:

Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

HashMap.entrySet()

The source-code for this implementation is available. The implementation basically just returns a new HashMap.EntrySet. A class which looks like this:

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {     public Iterator<Map.Entry<K,V>> iterator() {         return newEntryIterator(); // returns a HashIterator...     }     // ... } 

and a HashIterator looks like

private abstract class HashIterator<E> implements Iterator<E> {     Entry<K,V> next;    // next entry to return     int expectedModCount;   // For fast-fail     int index;      // current slot     Entry<K,V> current; // current entry      HashIterator() {         expectedModCount = modCount;         if (size > 0) { // advance to first entry             Entry[] t = table;             while (index < t.length && (next = t[index++]) == null)                 ;         }     }      final Entry<K,V> nextEntry() {         if (modCount != expectedModCount)             throw new ConcurrentModificationException();         Entry<K,V> e = next;         if (e == null)             throw new NoSuchElementException();          if ((next = e.next) == null) {             Entry[] t = table;             while (index < t.length && (next = t[index++]) == null)                 ;         }     current = e;         return e;     }      // ... } 

So there you have it... Thats the code dictating what will happen when you iterate through an entrySet. It walks through the entire array which is as long as the maps capacity.

HashMap.keySet() and .get()

Here you first need to get hold of the set of keys. This takes time proportional to the capacity of the map (as opposed to size for the LinkedHashMap). After this is done, you call get() once for each key. Sure, in the average case, with a good hashCode-implementation this takes constant time. However, it will inevitably require lots of .hashCode and .equals calls, which will obviously take more time than just doing a entry.value() call.

like image 26
aioobe Avatar answered Sep 22 '22 10:09

aioobe