What is increased cost of TreeSet vs LinkedHashSet and TreeMap over LinkedHashMap?

Question

LinkedHashSet - This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet.

Same is said about LinkedHashMap vs TreeMap

What is this increased cost (LinkedHashMap vs TreeMap) exactly?

Does that mean that TreeSet needs more memory per element? LinkedHashSet needs more memory for two additional links, but TreeSet needs additional memory to store Map.Entry pair of elements (because implicitly based on TreeMap), besides LinkedHashSet is based on HashMap which also has Map.Entry pair of elements overhead...

So the difference is how fast a new element is added (in case of TreeSet it takes longer due to some "sorting").

What are other significant increased costs?

Answer 1

TreeSet/TreeMap have a higher time complexity for operations such ass add(), contains() (for TreeSet), put(), containsKey() (for TreeMap), etc... since they require logarithmic time to locate elements in the tree (or add elements to the tree), while LinkedHashSet/LinkedHashMap require expected constant time for those operations.

In terms of memory requirements, there's a very small difference:

• TreeMap entries hold key, value, 3 Entry references (left, right, parent) and a boolean.

• LinkedHashMap entries hold key, value, 3 Entry references (next, before, after) and an int.

Answer 2

When iterating a HashSet, the iteration order is generally the order of the hash of the object, which is generally not too useful if you want a predictable order.

If sane ordering is important you would generally need to use a TreeSet which iterates in sorted order but at a cost because maintaining the sorted order adds to the complexity of the process.

A LinkedHashSet can be used as a middle-ground solution to the seemingly insane ordering of a HashSet by ensuring that the iteration order is at least consistent by using the insertion order.