Search code examples
javasortinghashmapsortedmap

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

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?

Solution

  • 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)