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 aHashMap
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
Where Do I Have to Place the Jdbc Driver for Tomcat's Connection Pool
Using Locales with Java's Tolowercase() and Touppercase()
When to Catch the Exception VS When to Throw the Exceptions
Java Change the Document in Documentlistener
How to Get the Real Path of Java Application at Runtime
Difference Between List and Array
Stopping a Window from Displaying Till It Is Fully Drawn
Peer Not Authenticated While Importing Gradle Project in Eclipse
How to See the Source Code of the Sun Jdk
Lambda Expression and Method Overloading Doubts
How to Find Out What Type Each Object Is in a Arraylist<Object>
Why Isn't a Qualified Static Final Variable Allowed in a Static Initialization Block
Generating a Random Number Between 1 and 10 Java
Why Does My Spring Boot App Always Shutdown Immediately After Starting
Correct Way of Throwing Exceptions with Reactor
Is This the Best Way to Rewrite the Content of a File in Java