Solved

Hashmap entrySet complexity

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

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

758 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now