What are the differences between Treeset, Hashset and Linkedhashset?

Question

The idea of Set is to not allow repeated elements, in java there are three implementations TreeSet, HashSet and LinkedHashSet found some differences in that reply, would like to know in detail if there are others and in which case/scenario each collection stands out.

Answer 1

What changes are the internal structures. Some give more guarantees than others.

I won’t go into details of what a Set, does not seem to be the purpose of the question.

TreeSet

Only applies to elements with absolute ordering. If they are not comparable (Comparable), you can teach with a comparator (Comparator).

Underneath the cloths, it uses a balanced search tree (I think binary tree, red-black, but I don’t remember the source of this information nor whether the internal details have changed).

As it is a balanced tree, all operations are done in O(lg(n)). Has guarantees that you will iterate different from the order in which the elements were inserted.

HashSet

Underneath, it uses a scatter table that points to a linked list of nodes. When there is collision, it is inserted at the beginning of the linked list.

Only applicable for objects having a function of hash. In Java, all objects have this function (Object.hashCode()), then everyone is a candidate for this =D collection

If you wish to use a scattering number of your own, as if a IntFunction<T> to generate the number, then you need to create your own collection or make a HashSet<MyHashWrapper<T>>, where MyHashWrapper<T> would be a container containing an object T and a function of hash own.

In the ideal world, operations in O(1), but can degrade to O(n).

No iteration order guarantee.

LinkedHashSet

Ditto to the HashSet, but the nodes on the collision list have an extra connection. This link ensures that it is possible to iterate in the insertion order. Hence, you have the guarantee that iterates in the same order of insertion.

When to use each?

In general, the HashSet you would use for sloth. Reasonably good performance in most cases. It is hardly necessary to access in the same order of insertion.

The LinkedHashSet cost two cents extra memory and one processing, should be used to extract in insert order.

Already the TreeMap would have two possible uses:

• prevent the degradation of hash
• always iterate in the ascending order

If your application needs to go through these values many and many times in ascending order, then it may make sense to use the TreeMap to this end. If you do not need to make this iteration constantly, but only once in a while, turn from the Set for a List and order will not be a great overhead. Then the sloth speaks louder and I would use HashSet =)