Java structure suggestion for a sorted list of pairs with unique keys

Question

A structure k => v (k and v are >=0 ints) where all k are unique while v may be equal (k1 => v and k2 => v) should be sorted in ascending order of v values, for example:

Let we have [35 => 1, 23 => 4, 9 => 9, 2 => 14] and want to insert a new pair 20 => 5, then the result is going to be [35 => 1, 23 => 4, 20 => 5, 9 => 9, 2 => 14].

What is the fastest structure in Java I can use in order to create it based on some input data and further iterate it in a 'one-by-one' fashion from the left. SortedHashMap?

Answer 1

Some time ago I encountered a similar situation; I used a couple of maps in parallel:

• A HashMap<K, P> M, where P is the pair type, to be able to find pairs by their key.

• A TreeMap<P, P> S, with a comparator that sorts first by the value and then by the key, to always have the correct sorting order available.

By maintaining both structures in parallel, it is possible to always have your pairs sorted, without having to use the key as the sorting value.

To add a pair:

M.put(key, pair);
S.put(pair, pair);

To get a pair by key:

M.get(key);

To remove a pair:

P pair = M.get(key);
M.remove(key);
S.remove(pair);

To get a sorted list of pairs:

S.keySet();

The average complexity of the core operations is:

• Add: O(logn) (TreeMap)
• Get: O(1) (HashMap)
• Remove: O(logn) (TreeMap)

Answer 2

I don't think that there is an existing structure for that.

A SortedMap is not the right thing for you because it sorts using the keys and not the values.

I would use a HashMap and implement the sorting in an additional method which copies the entrySet into a list. The list would be sorted using a custom comparator which compares the values.

If performance is a big big point here you should think about implementing an own structure. There are many possibilities to do this and one cannot say what is the fastest. It depends on what operations you want to execute how often.

Answer 3

If you don't need incremental construction, I'd do:

List<Pair> pairs = ...;
Collections.sort(pairs, new Comparator<Pair>() {
    @Override public int compare(Pair p1, Pair p2) {
        return p1.v - p2.v;
    }
}
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.addAll(pairs); // retains insertion order
return map;