• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList v/s HashSet

 
Ranch Hand
Posts: 441
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I understand the set collection doesn't allow duplicates.

In case, we just need unique values, then which would be faster: ArrayList OR HashSet.

Moreover, what would be performance order for following collections:

1. ArrayList
2. LinkedList
3. HashSet
4. LinkedHashSet

 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

The discussion of performance isn't as simply as just an order. It really depends on what you want to do. For example, are you referring to adding elements? removing elements? or iterating through elements? Additionally, depending on the implementation, it also depends on where -- as another example, removing an element from the end of an arraylist, is much faster than removing an element from the middle of the arraylist. etc.

Anyway, assuming that you are an university student (apologies if this is not true), have you learned data structures and algorithms, in your classes yet?
                     
Henry
 
Bartender
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Faster in what sense. Are you interested in the time taken to add, remove or find items in the collection?
Another important factor when talking about performance is the size of the collection as the number of items in your data set can have a major bearing on which collection will perform better for the type of operations you are performing.
 
Vaibhav Gargs
Ranch Hand
Posts: 441
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So, we can consider the performance in terms of following operations:

1. Iteration
2. Addition
3. Removing
4. Searching

Can we identify the sequence of collections performance-wise for above operations? I know it will again depend upon multiple factors such as size of collection, addition at what place, searching in best/worst case etc. But on a high level for best coding practice/guideline to be used.
 
Saloon Keeper
Posts: 15510
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As far as best practices go, you shouldn't worry about performance, but about using the collection that conceptually fits your design. Duplicates are allowed, or elements have a position? Use a List. Elements are unique, and you don't don't care about their position? Use a Set. Elements need to remain sorted? Use a SortedSet. Elements need to go in on one side and come out of the other? Use a Queue. Elements need to be stacked? Use a Deque.

There's no point in comparing an ArrayList to a HashSet, because they perform different jobs. You can compare a LinkedList to an ArrayList, or a HashSet to a TreeSet, but only after you've decided whether you need a List or a Set.

There is usually an implementation for each interface that you should use first, and only change if you have good reasons to believe your application requires another implementation. These are:

InterfaceGoto implementation
ListArrayList
SetLinkedHashSet or EnumSet
SortedSetTreeSet
Queue or DequeArrayDeque
MapLinkedHashMap or EnumMap
SortedMapTreeMap
 
Tony Docherty
Bartender
Posts: 3323
86
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you read the Java API Documentation for each of the classes you should get the information you require.

For example for ArrayList it says

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.



For Hashset it says:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

 
Vaibhav Gargs
Ranch Hand
Posts: 441
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you all for your valuable inputs. Appreciate it!!
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic