Java collections supporting insertion order

Question

Why don't some data collection data structures support insertion order? What feature is achieved compared to maintaining the insertion order? Do we get something if we don’t maintain order?

Answer 1

Performance. If you want to have the original insertion order, there are LinkedXXX classes that support an additional linked list in placement order. In most cases, you don't care, so you use HashXXX or want a natural order, so you use TreeXXX. In any of these cases, why should you pay the extra cost of a linked list?

Answer 2

Collections do not support insertion order. Some simply added a new value at the end by default. Maintaining the insertion order is only useful if you prioritize objects or use them to sort objects in any way.

As to why some collections support it by default, while others do not, it is mainly related to the implementation and only sometimes part of the definition of collections.

• Lists maintain the insertion order, since simply adding a new record at the end or at the beginning is the fastest implementation of the add (Object) method.

• The HashSet and TreeSet Implementation Kits do not support insertion order, because objects are sorted for quick search and additional memory is required to maintain the insertion order. This leads to increased performance, since the insertion order is almost never interesting for Sets.

• ArrayDeque Deque can be used for simple que and stack, so you want to have “first in first” or “first in last” mode, both require ArrayDeque to support insertion order. In this case, the insertion order is maintained as the central part of the class contract.

Answer 3

• The insertion order is essentially not supported in hash tables - this is how they work (read the article related to details to understand the details). You can add logic to maintain the insertion order (as in LinkedHashMap ), but it takes more code and working time more memory and more time. Loss of performance is usually small, but it can be.
• For TreeSet/Map main reason for using them is the natural iteration order and other functionality added to the SortedSet/Map interface.

Answer 4

Depends on what you need to implement. The insertion order is usually not interesting, so there is no need to maintain it so you can tune in to get better performance.

Maps usually use HashMap and TreeMap. Using hash codes, entries can be placed in small groups that can be easily found. TreeMap supports the sorted order of inserted records due to a slower search, but is easier to sort than a HashMap.

Answer 5

When you use HashSet (or HashMap) data, the data is stored in buckets based on the hash of your object. Thus, your data is easier to access, because you do not need to look for this data in the entire set, you just need to look in the right bucket.

In this way, you can increase productivity at specific points.

Each implementation of Collection has its own peculiarity to make it better to use it in a certain state. Each of these features has a cost. Therefore, if you really do not need it (for example, the insertion order), you are better off using an implementation that does not offer it and better suits your requirements.

Answer 6

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

Answer 7

Theres the "Cookie" section of "O'Reilly Java" titled "Avoid the urge for sorting." The question you should ask is actually the opposite of your original question ... "Are we getting something by sorting?" It takes a lot of effort to sort and maintain this order. Sorting is simple, of course, but it usually doesn't scale in most programs. If you are going to process thousands or tens of thousands of queries (insrt, del, get, etc.) per second, will you seriously use a sorted or unsorted data structure.

Answer 8

Some collections do not maintain order because they compute a hash code for the content and store it accordingly in the appropriate bucket.

Answer 9

I can’t link to the link, but the design of the List and Set implementations of the Collection interface is mostly extensible Array s. Since Collections by default, offers methods for dynamically adding and deleting items at any point where there is no Array , the insertion order may not be preserved. Thus, since there are many methods for manipulating content, there is a need for special implementations that preserve order.

Another point is performance, since the most effective Collection may not be the one that maintains its insertion order. However, I'm not sure exactly how Collections manage their content to improve performance.

So, in short, there are two main reasons why I can think about why there are Collection implementations that preserve order:

• Class Architecture
• Performance

Answer 10

Ok ... that's why these messages are old compared to now, but the insertion order is necessary depending on your needs or application requirements, so just use the correct collection type. In most cases, this is not necessary, but in a situation where you need to use objects in the order in which they were saved, I see a certain need. I think that order matters when you create, for example, a wizard or a stream engine or something like that, where you need to switch from state to state or something like that. In this sense, you can read material from a list without tracking what you need, or go through the list to find what you need. It helps in performance in that sense. It matters, or these collections do not make much sense.