How iteration ordering in LinkHashMap/LinkedHashSet leads to a bit low performance than HashMap

Question

As LinkedHashMap/Set keeps the order of entry in the Collection so it leads to a little lower performance. I want to know why this happens.

Answer 1

LinkedHash[Map/Set] use doubly linked lists to keep track of the order of entries. So whenever an element is added, a new DLL node must be created. The allocation takes time, and several extra pointers need to be set.

Answer 2

The question is making the invalid assumption that LinkedHash[Map/Set]s always perform worse than their non-linked counterparts.

The LinkedHash[Map/Set] has the additional task of maintaining the pointers used to form the linked list which means slightly worse (although still constant time) performance than Hash[Map/Set] when performing add or remove.

However, when iterating over a LinkedHash[Map/Set] the performance is proportional to the size of the set whereas the non-linked counterpart is proportional to the capacity of the set. When iterating over a Hash[Map/Set] the best case scenario is when the capacity is just big enough to fit all the elements (ie capacity=size) and in such a case it has the same performance. Also keep in mind that unless you have a very static set/map and you set the capacity it's unlikely that capacity will equal size.

So if you're more concerned with the performance of building your map/set then you should choose a HashMap or HashSet but if you're more concerned with iterating over that map/set choose a LinkedHashMap or LinkedHashSet.

See also: http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

Answer 3

LinkedHashMap/Set contains two data structures: hash table and linked list, so that insertion and deleting operations cause modification of two data structures, while the same operations on simple HashMap touch only one data structure (hash table). That is why LinkedHashMap/Set is slower and consume more memory.