Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Hashmap entrySet complexity

Posted on 2009-06-29
3
Medium Priority
?
883 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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 80 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

Tech or Treat!

Submit an article about your scariest tech experience—and the solution—and you’ll be automatically entered to win one of 4 fantastic tech gadgets.

Question has a verified solution.

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

Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Suggested Courses

650 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