Solved

Hashmap entrySet complexity

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
In this post we will learn different types of Android Layout and some basics of an Android App.
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

726 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