Java Map Value Comparator, sort while inserting

Question

I would like to insert items into a HashMap, TreeMap or SortedMap (you may suggest some other api) using a value Comparator.

I Have read many posts including this one, most of the posts suggest to re-insert the HashMap into a SortedMap with a value Comparator after all items have been inserted.

I am not interested to re-insert all values again. Isn't there an option or a Map similar data structure which supports the activation of a value Comparator after each insert?

If there is a duplicate issue i would appreciate a link (I have done some search, although I may have missed some)

Again, I am interested in adding a value to some kind of ordered Map so that all items will be ordered by the value and not the key, after each single insert.

The value in the Map entry is actually a complex Object with some getters, and I want to sort only by a specific getter on the value object.

You could insert the items into a [TreeMap](http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html) and give the TreeMap the required comparator in its constructor? Exactly as shown in the question you've already linked to. — DNA, Oct 28 '12 at 12:48
why don't you like the answer you've by yourself mentioned in the question? You need an ordered map - use TreeMap. You need to compare by specific field in the value - use valuecomparator as was suggested, the implementation will slightly change but the ratio is still the same. — Mark Bramnik, Oct 28 '12 at 12:49
@DNA : TreeMap doesn't take as input a value comperator, but only a key comperator — Michael, Oct 28 '12 at 12:52
@Mark Bramnik: please see the solution again, it requeires to re-insert all items, `sorted_map.putAll(map);` the TreeMap but itself can't recieve a value comperator — Michael, Oct 28 '12 at 12:55
@Michael - the linked example clearly shows a TreeMap being initialised with a Comparator that sorts on values. I'd call that a "value comparator". However, do read the comments about the various problems with that solution. — DNA, Oct 28 '12 at 14:16

score 3 · Answer 1 · edited Jun 20 '20 at 09:12

3

I think what you need is org.apache.commons.collections.bidimap.TreeBidiMap

Red-Black tree-based implementation of BidiMap where all objects added implement the Comparable interface.

This class guarantees that the map will be in both ascending key order and ascending value order, sorted according to the natural order for the key's and value's classes.

edited Jun 20 '20 at 09:12

Community

1
1

answered Oct 28 '12 at 13:05

Amit Deshpande

19,001
4
46
72

Thanks for your solution , i would prefer to not use any external libraries. – Michael Oct 28 '12 at 13:10

score 3 · Accepted Answer · edited Apr 24 '16 at 12:24

3

I have though of a some workaround , it is not perfect and and will use some more memory, but it rather simple.

I may extend the key of the Map to also hold the value returned by the getter of the Value object, Then i will extend the key Comparator to sort by the right tuple of the key.

UPDATE

Worked as a charm with a very good performance.

edited Apr 24 '16 at 12:24

Mifeet

12,949
5
60
108

answered Oct 28 '12 at 13:14

Michael

2,827
4
30
47

If the key holds the value, how do you retrieve values from the map? You need to know the sorting value in order to get the object value? – ygesher Oct 20 '17 at 06:40

score 2 · Answer 3 · answered Oct 28 '12 at 12:54

Maps are all about going from a key to a value. Guava has a concept for bidirectional mappings but you don't really care about going from value to key but rather exposing a sorted iteration of values. What I recommend is a custom container that would house both a HashMap and a Priority Queue.

So, extend the the Map, Collection, and Iterable interfaces and on add insert into both the HashMap and Priority Queue. When you iterate, iterate over the queue, when you search/get go to the map.

score 1 · Answer 4 · answered Dec 06 '16 at 01:44

I was looking for something similar, and wasn't able to use the TreeBidiMap because it requires the Map's Keys to implement the Comparable interface.

So i wrote my own minimalistic ValueTreeMap:

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

public class ValueTreeMap<K, V extends Comparable<V>> implements Iterable<V> {
    private TreeSet<V> tree = new TreeSet<V>();
    private HashMap<K, V> map = new HashMap<K, V>();

    public void put(K key, V value){
        V oldValue = map.get(key);
        if(oldValue != null){
            tree.remove(oldValue);
        }
        tree.add(value);
        map.put(key, value);
    }

    public V get(K key){
        return map.get(key);
    }

    @Override
    public Iterator<V> iterator() {
        return tree.iterator();
    }

}

I extended your solution to build a class that implements `Map`: [github](https://github.com/jegesh/cn1-object-cacher/blob/master/src/net/gesher/cn1/caching/ValueTreeMap.java) — ygesher, Oct 21 '17 at 20:56

Java Map Value Comparator, sort while inserting

4 Answers4

Linked