HashSet and LinkedHashSet [duplicate]

Question

This question already has answers here:

HashSet vs LinkedHashSet (10 answers)

Closed 8 years ago.

So im developing a program where I need to store unique customer data of primitive types. In this regard, I have been reading a book about datastructures, and came to the conclusion to use a HashSet.

Now this book states, that a HashSet has faster insertion and removal, than a LinkedHashSet. Now this baffles me a bit. I thought that the only difference between the two, was that a LinkedHashSet uses some extra memory, using a LinkedList to keep order.

Can anyone elaborate?

Answer 1

Choose you Data Structure wisely.

You can use Linked Hash Set instead of Hash Set if the order of insertion is important to you. With the additional features the memory or processor cycles might take a hit.

Edit1 : Things to consider other than the insertion order: Because LinkedHashSet maitains a doubly linkedlist, it will be slower for insertion and removing, but will be slightly faster in iteration.

To Quote the java doc:

This class provides all of the optional Set operations, and permits null elements. Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

Answer 2

TreeSet, LinkedHashSet and HashSet in Java are three Set implementation in collection framework and like many others they are also used to store objects. Main feature of TreeSet is sorting, LinkedHashSet is insertion order and HashSet is just general purpose collection for storing object. HashSet is implemented using HashMap in Java while TreeSet is implemented using TreeMap. TreeSet is a SortedSetimplementation which allows it to keep elements in the sorted order defined by either Comparable or Comparator interface. Comparable is used for natural order sorting and Comparator for custom order sorting of objects, which can be provided while creating instance of TreeSet. Anyway before seeing difference between TreeSet, LinkedHashSet and HashSet, let's see some similarities between them:

1) Duplicates : All three implements Set interface means they are not allowed to store duplicates.

2) Thread safety : HashSet, TreeSet and LinkedHashSet are not thread-safe, if you use them in multi-threading environment where at least one Thread modifies Set you need to externally synchronize them.

3) Fail-Fast Iterator : Iterator returned by TreeSet, LinkedHashSet and HashSet are fail-fast Iterator. i.e. If Iterator is modified after its creation by any way other than Iterators remove() method, it will throw ConcurrentModificationException with best of effort. read more about fail-fast vs fail-safe Iterator here

Now let’s see difference between HashSet, LinkedHashSet and TreeSet in Java :

Performance and Speed : First difference between them comes in terms of speed. HashSet is fastest, LinkedHashSet is second on performance or almost similar to HashSet but TreeSet is bit slower because of sorting operation it needs to perform on each insertion. TreeSet provides guaranteed O(log(n)) time for common operations like add, remove and contains, while HashSet and LinkedHashSet offer constant timeperformance e.g. O(1) for add, contains and remove given hash function uniformly distribute elements in bucket.

Ordering : HashSet does not maintain any order while LinkedHashSet maintains insertion order of elements much like List interface and TreeSet maintains sorting order or elements.

Internal Implementation : HashSet is backed by an HashMap instance, LinkedHashSet is implemented using HashSet and LinkedList while TreeSet is backed up by NavigableMap in Java and by default it uses TreeMap.

null : Both HashSet and LinkedHashSet allows null but TreeSet doesn't allow null but TreeSet doesn't allow null and throw java.lang.NullPointerException when you will insert null into TreeSet. Since TreeSet uses compareTo() method of respective elements to compare them which throws NullPointerException while comparing with null, here is an