CODEWITHSUNDEEP
javacollectionshashmaptreemaplinkedhashmap
Chris Abbott
Chris Abbott

Reputation: 306

Which data structure should I use to support key-value mappings, reverse iteration and insertion ordering?

Which data structure from Collections can efficiently store key-value mappings, preserve insertion ordering and allow efficient reverse traversal? The data structure must come from the original Java Collections, so using the Apache Commons library is out of the question.

I'm currently using a LinkedHashMap, which is ideal because it preserves insertion order, allows key-value mappings, and has add() and remove() methods that operate in O(1) time. The issue however, is that to reverse the LinkedHashMap, I need to perform a set-copy every time a new key is added: 

List<Integer> reverseKeys = new ArrayList<>(keys);
Collections.reverse(reverseKeys);

which becomes very costly over large key sets (as was mentioned here: Iterating through a LinkedHashMap in reverse order).

Alternatively, I could use a TreeMap with a custom comparator to preserve insertion order, but this seems like a waste because add() and remove() will be running in O(n) time. The benefit of this approach is that the TreeMap has the descendingKeySet() method which would allow efficient reverse traversal.

My only other thought is to use an ArrayList of Entry objects, however I'm unsure how efficient this would be.

Which of these approaches would perform the best overall over a few thousand Key-value mappings? Are there any approaches that I haven't listed that would be a better alternative?

Upvotes: 3

Views: 263

Answers (2)

M. Justin
M. Justin

Reputation: 21132

As of Java 21, LinkedHashMap meets all your requirements, as a reversed method was added to it.

SequencedMap<K, V> map = new LinkedHashMap<>();

// Add elements to the map here

SequencedMap<K, V> reversedMap = map.reversed();

Javadocs

public SequencedMap<K,V> reversed()

Returns a reverse-ordered view of this map. The encounter order of mappings in the returned view is the inverse of the encounter order of mappings in this map. […]

Upvotes: 0

libik
libik

Reputation: 23029

Do you HAVE to have only one variable? It is common approach to have same data multiple-times in different structure, if you want to query them often.

The add/remove costs more, however selecting can cost a lot less.

In your case, you can have LinkedList in reversed order (adding at zero position is O(1) ) and LinkedHashMap.

Ideally you should create your own class with these two variables and methods like "add/remove etc.", to make sure it is consistent.

Upvotes: 2

Related Questions