Performance Considerations for Keyset() and Entryset() of Map

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

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 let's 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... That's the code dictating what will happen when you iterate through an entrySet. It walks through the entire array, which is as long as the map's 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.

Performance - Inefficient use of keySet iterator instead of entrySet iterator

This is SonarQube warning coming from FindBugs.

You can rewrite your code like this:

if (docPropertiesMap != null) {
IDocProperty[] docProperties = new IDocProperty[docPropertiesMap.size()];
int iArrIndex = 0;

for (Map.Entry<String, String[]> entry : docPropertiesMap.entrySet()) {
String strPropName = entry.getKey();
String[] propValue = entry.getValue();

IDocProperty docProperty = (IDocProperty) FDMAFactory.getDataObject("DocProperty");
docProperty.setPropertyName(strPropName);
docProperty.setArrPropertyValues(propValue);
docProperties[iArrIndex++] = docProperty;
}
metadata.setArrDocProperties(docProperties);
return metadata;
}

java collections - keyset() vs entrySet() in map

Every call to the Iterator.next() moves the iterator to the next element. If you want to use the current element in more than one statement or expression, you have to store it in a local variable. Or even better, why don't you simply use a for-each loop?

for (String key : map.keySet()) {
System.out.println(key + ":" + map.get(key));
}

Moreover, loop over the entrySet is faster, because you don't query the map twice for each key. Also Map.Entry implementations usually implement the toString() method, so you don't have to print the key-value pair manually.

for (Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry);
}

How do I efficiently iterate over each entry in a Java Map?

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + "/" + entry.getValue());
}

On Java 10+:

for (var entry : map.entrySet()) {
System.out.println(entry.getKey() + "/" + entry.getValue());
}

LinkedHashMap access by index vs Performance

As said by Stephen C, the time complexity is the same, as in either case, you have a linear iteration, but the efficiency still differs, as the second variant will only iterate to the specified element, instead of creating a complete copy.

You could optimize this even further, by not performing an additional lookup after finding the entry. To use the pointer to the actual location within the Map, you have to make the use of its Iterator explicit:

public boolean removeItem(int position) {
if(position >= items.size()) return false;
Iterator<?> it=items.values().iterator();
for(int counter = 0; counter < position; counter++) it.next();
boolean result = it.next() != null;
it.remove();
return result;
}

This follows the logic of your original code to return false if the key was mapped to null. If you never have null values in the map, you could simplify the logic:

public boolean removeItem(int position) {
if(position >= items.size()) return false;
Iterator<?> it=items.entrySet().iterator();
for(int counter = 0; counter <= position; counter++) it.next();
it.remove();
return true;
}

You may retrieve a particular element using the Stream API, but the subsequent remove operation requires a lookup which makes it less efficient as calling remove on an iterator which already has a reference to the position in the map for most implementations.

public boolean removeItem(int position) {

if(position >= items.size() || position < 0)
return false;

Product key = items.keySet().stream()
.skip(position)
.findFirst()
.get();

items.remove(key);
return true;
}

Stream an entrySet to groupingBy instead of keySet

return scores.entrySet().stream()
.collect(Collectors.groupingBy(Map.Entry::getValue,
Collectors.mapping(Map.Entry::getKey,
Collectors.toList())));

parsing on HashMap in Java

Here's how you can get the key set:

Set<A> keys = myMap.keySet();

I don't know what "passing on" means. I don't know what "parsing" means for a HashMap, either. Except for getting the keys out of the Map, this question makes no sense whatsoever. Voting to close.

Getting the key and its specific value from map

You can use propMap.entrySet() method which returns a Map.Entry of key, value, if you want to use every pair of key and value: -

for (Map.Entry<String, String> entry: propMap.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}

Or, if you want to know how to do this with propMap.keySet(), you can iterate over the Set<Key> you obtain, and for each key, use propMap.get(key), to get the value of a particular key: -

Set<String> keySet = propMap2.keySet();

for (String key: keySet) {
System.out.println(propMap.get(key));
}

From an answer from this post: -

With the later approach, if you are regularly accessing the key-value pair, then for each key, 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 (entrySet), that extra work is eliminated.



Related Topics



Leave a reply



Submit