60

Why do some collection data structures not maintain the order of insertion? What is the special thing achieved compared to maintaining order of insertion? Do we gain something if we don't maintain the order?

3
  • 1
    For instance, Why does a java.util.HashSet need to maintain order of insertion? Sep 12, 2010 at 8:09
  • no .. i am asking ..does we loose anything while maintaining order ..contrary do we gain something if we doesn't maintain the order
    – JavaUser
    Sep 12, 2010 at 8:11
  • eg:LinkedList. Think about it, wouldn't it be easier to append/prepend to a linked list than insert it in the middle?
    – st0le
    Sep 12, 2010 at 9:47

10 Answers 10

88

Performance. If you want the original insertion order there are the LinkedXXX classes, which maintain an additional linked list in insertion order. Most of the time you don't care, so you use a HashXXX, or you want a natural order, so you use TreeXXX. In either of those cases why should you pay the extra cost of the linked list?

4
  • 14
    Where does ArrayList fit in the answer?
    – ADTC
    Sep 26, 2014 at 4:42
  • 1
    @ADTC It doesn't fit in the answer.
    – user207421
    Mar 20, 2015 at 6:32
  • Well, ArrayList maintains insertion order with array backing, but I suppose the performance is worse than LinkedXXX classes?
    – ADTC
    Mar 20, 2015 at 12:50
  • 1
    @ADTC It maintains insertion order if you don't use the indexed insertion methods, or sort it, and so does LinkedList. 'With array backing ' is irrelevant. The performance in both cases is described in the Javadoc.
    – user207421
    Mar 20, 2015 at 15:01
20

The collections don't maintain order of insertion. Some just default to add a new value at the end. Maintaining order of insertion is only useful if you prioritize the objects by it or use it to sort objects in some way.

As for why some collections maintain it by default and others don't, this is mostly caused by the implementation and only sometimes part of the collections definition.

  • Lists maintain insertion order as just adding a new entry at the end or the beginning is the fastest implementation of the add(Object ) method.

  • Sets The HashSet and TreeSet implementations don't maintain insertion order as the objects are sorted for fast lookup and maintaining insertion order would require additional memory. This results in a performance gain since insertion order is almost never interesting for Sets.

  • ArrayDeque a deque can used for simple que and stack so you want to have ''first in first out'' or ''first in last out'' behaviour, both require that the ArrayDeque maintains insertion order. In this case the insertion order is maintained as a central part of the classes contract.

0
7
  • The insertion order is inherently not maintained in hash tables - that's just how they work (read the linked-to article to understand the details). It's possible to add logic to maintain the insertion order (as in the LinkedHashMap), but that takes more code, and at runtime more memory and more time. The performance loss is usually not significant, but it can be.
  • For TreeSet/Map, the main reason to use them is the natural iteration order and other functionality added in the SortedSet/Map interface.
1
  • 1
    Just on a quick side note: strictly speaking Map implementations are not Collections as they do not implement the Collection interface. They do have similar methods, but that's it. Check: download.oracle.com/javase/1.4.2/docs/guide/collections/… (#Collection Interfaces) Most likely the OP's question addresses maps too though.
    – FK82
    Sep 12, 2010 at 13:13
2

Depends on what you need the implementation to do well. Insertion order usually is not interesting so there is no need to maintain it so you can rearrange to get better performance.

For Maps it is usually HashMap and TreeMap that is used. By using hash codes, the entries can be put in small groups easy to search in. The TreeMap maintains a sorted order of the inserted entries at the cost of slower search, but easier to sort than a HashMap.

2

When you use a HashSet (or a HashMap) data are stored in "buckets" based on the hash of your object. This way your data is easier to access because you don't have to look for this particular data in the whole Set, you just have to look in the right bucket.

This way you can increase performances on specific points.

Each Collection implementation have its particularity to make it better to use in a certain condition. Each of those particularities have a cost. So if you don't really need it (for example the insertion order) you better use an implementation which doesn't offer it and fits better to your requirements.

0

Why is it necessary to maintain the order of insertion? If you use HashMap, you can get the entry by key. It does not mean it does not provide classes that do what you want.

0

Theres's a section in the O'Reilly Java Cookbook called "Avoiding the urge to sort" The question you should be asking is actually the opposite of your original question ... "Do we gain something by sorting?" It take a lot of effort to sort and maintain that order. Sure sorting is easy but it usually doesn't scale in most programs. If you're going to be handling thousands or tens of thousands of requests (insrt,del,get,etc) per second whether not you're using a sorted or non sorted data structure is seriously going to matter.

0

Okay ... so these posts are old as compared to now, but insertion order is needed depending on your need or application requirements, so just use the right type of collection. For most part, it is not needed, but in a situation where you need to utilize objects in the order they were stored, I see a definite need. I think order matters when you are creating for instance a wizard or a flow engine or something of that nature where you need to go from state to state or something. In that sense you can read off stuff from the list without having it keep track of what you need next or traverse a list to find what you want. It does help with performance in that sense. It does matter or else these collections would not make much sense.

0

some Collection are not maintain the order because of, they calculate the hashCode of content and store it accordingly in the appropriate bucket.

-1

I can't cite a reference, but by design the List and Set implementations of the Collection interface are basically extendable Arrays. As Collections by default offer methods to dynamically add and remove elements at any point -- which Arrays don't -- insertion order might not be preserved. Thus, as there are more methods for content manipulation, there is a need for special implementations that do preserve order.

Another point is performance, as the most well performing Collection might not be that, which preserves its insertion order. I'm however not sure, how exactly Collections manage their content for performance increases.

So, in short, the two major reasons I can think of why there are order-preserving Collection implementations are:

  1. Class architecture
  2. Performance
7
  • Note that Arrays is an actual class, while arrays are a special type of container objects. I'm also pretty sure LinkedList actually does use a linked list but I haven't read the code. :-)
    – wds
    Sep 12, 2010 at 9:24
  • Ok, point taken, I edited my post. About your LinkedList comment: where is the contradiction to what I posted?
    – FK82
    Sep 12, 2010 at 9:57
  • To clarify: A LinkedList afaik is a List (read extendable Array) whose insertion order is maintained in another List (the two of which are linked, hence the name). Or, am I wrong on that one?
    – FK82
    Sep 12, 2010 at 10:04
  • A very confused and confusing post. A LinkedList is not an extensible array, and neither is a List: it depends on the implementation. Neither of them contains 'another List'. I don't know what you mean by 'which Arrays don't.' Your second paragraph is basically meaningless. Your conclusions don't follow from your premisses.
    – user207421
    Sep 13, 2010 at 10:43
  • 1
    Also, the Array object does not offer methods to dynamically remove and add elements. That's why List exists in the first place. My second paragraph says what you say in your post. Don't flame away on your first impression, buddy.
    – FK82
    Sep 13, 2010 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.