Solved

Hashmap entrySet complexity

Posted on 2009-06-29
3
821 Views
Last Modified: 2013-11-12
What is the complexity of iterating the elements, having them by calling entrySet in the hashmap.

Is it the same as if the elements were in a list?
0
Comment
Question by:romram
3 Comments
 
LVL 26

Expert Comment

by:ksivananth
ID: 24734128
traversing all same...

values() will return a list with values in the map.
entrySet() will return a set with Entry( key, value ) in the map!
0
 

Author Comment

by:romram
ID: 24734140
So, I mean in  this case using hashmap or list is the same in this case, both will give us O(n) complexity, right?
0
 
LVL 22

Accepted Solution

by:
NovaDenizen earned 20 total points
ID: 24750068
I looked at java/util/HashMap.java (dated 2006), and it looks like the Set iterator you get from entrySet() uses just a very thin wrapper around the HashMap.  The HashMap uses an array of linked lists for its data structure.  Iterating through the HashMap takes O(k+n) time, where k is the capacity of the hashmap and n is the count of elements stored in it.  

If you assume the hash table is sized appropriately for the number of objects stored in it (like within a factor of 2 or so), then iterating through it is O(n).
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Software development teams often use in-memory caches to improve performance. They want to speed up access to, or reduce load on, a backing store (database, file system, etc.) by keeping some or all of the data in memory.   You should implement a…
In this post we will learn different types of Android Layout and some basics of an Android App.
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question