Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

entrySet and keySet in a Map

 
praveen oruganti
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Whether there is any performance increase by using entrySet compared to keySet for a Hashmap.
When i run the findbugs plugins, it is showing use entrySet rather going for keySet in the performance category.

Anyone experience these kind of performance issues...
 
Tim Holloway
Saloon Keeper
Pie
Posts: 18212
53
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The keyset is a core part of the HashMap data structure. The entryset has to be constructed by enumerating through the HashMap element by element, which is an extra layer of code. So yes, it's true that a keyset is slightly more efficient in most cases. However, how you use the data may nullify that advantage.

The final determinant, as always, is to measure. And, since there are so many things you can measure in a typical all, I'd only bother worrying about it if there were actual performance problems and the global measurements indicated that this was a bottleneck.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Tim]: The keyset is a core part of the HashMap data structure. The entryset has to be constructed by enumerating through the HashMap element by element, which is an extra layer of code. So yes, it's true that a keyset is slightly more efficient in most cases.

I don't agree. An EntrySet is just a thin wrapper providing a view of objects that already exist inside the HashMap. Specifically, there is an array of HashMap.Entry obects, which implement Map.Entry. The EntrySet just provides access. There's no need to iterate through the whole map just to construct an EntrySet.

The reason FindBugs points out a possible performance issue is that, if you need to access every key and value, there is absolutely no reason to call get() on each key. Each key and value are already stored right next to each other anyway, internally, in a HashMap.Entry instance. So when you iterate an EntrySet, you're just accessing these elements directly. If instead you call get(), you're invoking hashCode() and causing the HashMap to do a lookup in its internal array. Admittedly this is an O(1) operation, but it's always going to take a bit longer than simply using Entry.getValue(), and there's no reason to make such a call when the key and value are stored next to each other in the first place.

I agree with the points about measuring performance, though, and in many, many applications, the difference will be insignificant. It's not likely to be worth your time to change your existing code for this. But I think it's perfectly sensible to get in the habit of iterating using entrySet() in the first place, for all new code.
[ October 31, 2008: Message edited by: Mike Simmons ]
 
Norman Larson
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Depending on the size of your map, I've found you can also get a performance boost by converting the entrySet to an array via the toArray() function, and then iterating through that with a for loop (not for-each loop). But then again, I'm talking like a 3% total improvement, and it really depends on how often your function is called and how large the map is.
 
Jackie Li
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the findbug, or sonar, is referring the case, as instead of using keySet to get the key first, then using getValue from the key to get the value; using entry set can directly get the value intended.
 
Girish K Kumar
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Both keySet & entrySet does a O(n) walk through on the the underlying map entries as we move forward. So in theory they all have same effect of traversal.

But if you are iterating through the map to get the key and values then using entrySet would be preferred option when compared to keySet. As in keySet we need an additional get(key) to retrieve the value. For HashMap() even though the operation of get is O(1), we need to consider the time taken for the computation of hash index and the time taken to resolve collisions.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic