CODEWITHSUNDEEP
java
theomega
theomega

Reputation: 32031

Sorted Map with not well-defined Comparators

I'm searching for a Map implementation which can be sorted based on its keys and a Comparator.

I know that TreeMap is the way to go, but I have a huge problem: The comparator is not well defined (which I know is an mistake, but I can not fix it currently) in terms that it returns 0 even for keys which are not equal (in terms of equals() method).

The TreeMap implementation assumes that objects are equal (and therefore overwrites the values) if the comparator returns 0 and does not take the hashCode or the equals method of the object into consideration. This is documented and in most cases the desired behaviour. You can check that the implementation is based on the comparator by looking in the TreeMap.put() method, which contains the following snipset:

        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);

This code walks the tree and if it finds a node in the tree which is equal (using the comparator cpr) to the one which should be inserted (key), the value is overwritten.

But: I'm searching for an implementation of the Map interface which is sorted based on a Comparator but does not use it for detecting which are equal.

Upvotes: 1

Views: 147

Answers (4)

Ian Roberts
Ian Roberts

Reputation: 122364

It'd be rather more housekeeping but it sounds to me like you need some sort of two level structure, a TreeMap<K, LinkedHashMap<K, V>> where the outer map is based on your "faulty" comparator and its values are normal equals-aware maps (whose keys will all be equal according to the comparator, but different according to hashCode and equals).

Upvotes: 0

Deepak Bala
Deepak Bala

Reputation: 11185

I doubt you will find a Map that does that, since it goes against the recommendation of the Comparator interface.

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate the general contract for set (or map), which is defined in terms of equals.

You can always decorate the comparator with your own comparator like so new MyComparator(faultyComparator);

When you deletegate the calls to the faulty comparator, check its return value. If it is 0, make sure the equals() contract of the objects agree. If they don't, rectify the return value. An even better solution is to rewrite the comparator correctly and use a TreeMap, if that option is open.

Upvotes: 2

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 136012

Simply implement a Comparator that never returns 0 and use regular TreeMap.

Upvotes: 0

IndoKnight
IndoKnight

Reputation: 1864

TreeMap should be alright in your case. But, it sounds like you are not using Strings or Wrapper class objects as keys. If you use your own class object as key, you must implement hashcode() and equals() method.

Upvotes: 0

Related Questions