Solved

Hashmap entrySet complexity

Posted on 2009-06-29
3
808 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

Migrating Your Company's PCs

To keep pace with competitors, businesses must keep employees productive, and that means providing them with the latest technology. This document provides the tips and tricks you need to help you migrate an outdated PC fleet to new desktops, laptops, and tablets.

Question has a verified solution.

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

Suggested Solutions

What is Waterfall Model? Waterfall model is the classic Software Development Life Cycle method practiced in software development process. As the name "waterfall" describes, this development is flowing downwards steadily like waterfall, i.e., procee…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…

773 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