This week's book giveaway is in the Android forum.
We're giving away four copies of Head First Android and have David & Dawn Griffiths on-line!
See this thread for details.
Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

Comparison between Collection classes

 
Ranch Hand
Posts: 68
MyEclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi..i have confusion between the Collection classes when i have to choose them for a specific scenario...
like
I read that LinkedHashSet is faster in iteration than HashSet...why??

and HashSet is better in accesing a single element than LinkedHashSet...or are they equal in accesing??

I am facing similar type of problem in List and Map also... and my questions got wrong when i attempted these type of questions..please also provide me a link from where i can understand this...

sumit
 
Saloon Keeper
Posts: 13383
295
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
LinkedHashSet and HashSet both have O(1) time complexity for adding and removing. This means that adding and removing items from either will take a constant amount of time, regardless of their size. LinkedHashSet is still slower than HashSet though, because it has to keep track of the links.

For iteration, LinkedHashSet is faster, because it uses an amount of time proportional to the size of the Set, whereas HashSet uses time proportional to the size of the Set + the capacity of the Set.

I recommend always using LinkedHashSet (for the simple reason that it returns items in the same order as you inserted them), unless you make a lot of changes to the Set (using add and remove). In this case HashSet might be more appropriate. Analogously, use LinkedHashMap in preference to HashMap, unless you make a lot of changes to it and speed matters.

What questions did you have regarding List?
 
Ranch Hand
Posts: 247
Eclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
LinkedHashSet is faster in iteration than HashSet

In HashSet, the entities are not arranged in an order... So its unordered... To fetch an entity, it has to make a vast search for it...

LinkedHashSet arranges the entities in the order they are added into the Set... Comparatively, its quicker to find the entity in it...

You can go through WHAT?

K&B SCJP Exam Guide only... Its a nice one to direct you in the usage of Collections... And please brush up some basic Data Structure concepts to get even more insight of Collections...

Data Structure understanding makes you to win the Collection sort of questions very easily...
 
Bartender
Posts: 6663
5
MyEclipse IDE Firefox Browser Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I recommend always using LinkedHashSet (for the simple reason that it returns items in the same order as you inserted them), unless you make a lot of changes to the Set (using add and remove). In this case HashSet might be more appropriate. Analogously, use LinkedHashMap in preference to HashMap, unless you make a lot of changes to it and speed matters.



You can use a LinkedHashSet if indeed you are very particular about the insertion and traversal orders. The DS to use would of course depend on the situation.

The difference in iteration time comes down to how Map.Entry maintains the link to the next entry. As mentioned by others in this post, a HashMap's implementation of an iterator will go through each Entry in an array and return the one that it finds. That is a costly operation. A LinkedHashMap will return the next ordered Entry that is available and the logic does not have to scan through the entire Entry table. This is a relatively inexpensive traversal.

A HashSet / LinkedHashSet is backed by a HashMap or a LinkedHashMap, just in case you were wondering why discussing Maps came into the picture.
 
Stephan van Hulst
Saloon Keeper
Posts: 13383
295
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ram Narayan.M wrote:LinkedHashSet arranges the entities in the order they are added into the Set... Comparatively, its quicker to find the entity in it...



For iteration, this argument holds no water. Iteration simply goes over all the elements, there is nothing to 'find'.

The fact that the elements in a LinkedHashSet have insertion order, will do nothing to speed up the finding of a particular element. Insertion order is not an order you can base a searching scheme on. The elements are not sorted.
The reason LinkedHashSet iterates faster, is because the elements are linked, i.e., the Set can go directly to the next element. In a HashSet, the Set has to go over the buckets that contain the elements.
 
Sumit Khurana
Ranch Hand
Posts: 68
MyEclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A HashSet / LinkedHashSet is backed by a HashMap or a LinkedHashMap, just in case you were wondering why discussing Maps came into the picture.


and is HashMap backed by Hashtable???

What questions did you have regarding List?



like for searching in list which one is faster??
I think ArrayList,but tell me am i right or wrong??

and do any one have a link where i can find these type of problems??
 
Ram Narayan.M
Ranch Hand
Posts: 247
Eclipse IDE Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Certainly,Its ArrayList... Since all entities are arranged sequentially in contiguous memory locations... Iteration speed is fast in ArrayList...

 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic