TreeMap that allows you to sort based on key AND value :3. Validate is for the gorgeous InvalidArgumentException, replacing them should be a breeze.

KVTreeMap.java

import lombok.Delegate;
import org.apache.commons.lang.Validate;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author DarkSeraphim
 */
public class ValueSortingTreeMap<K, V extends Comparable<V>> implements Map
{


    // The following code prints out:
    // c => 1
    // a => 2
    // b => 3
    public static void main(String[] args)
    {
        ValueSortingTreeMap<String, Integer> kills = new ValueSortingTreeMap<String, Integer>(String.class, Integer.class);
        kills.put("a", 2);
        kills.put("b", 3);
        kills.put("c", 1);
        for(Entry entry : kills.entrySet())
            System.out.println(entry.getKey() + " => " + entry.getValue());
    }

    private interface Exclude<K, V>
    {
        public V put(K key, V value);

        public V get(Object key);

        public V remove(Object key);

        public Set<Map.Entry<K, V>> entrySet();
    }

    // Basically, you need to implement all methods and forward them to Map.
    @Delegate(types = Map.class, excludes = Exclude.class)
    private final TreeMap<K, V> map;

    private final Map<K, V> unsorted = new HashMap<K, V>();

    private final Class<K> k;

    private final Class<V> v;

    private final Comparator<K> comparator = new Comparator<K>()
    {
        /**
         * In the case that this is invoked thanks to a 
         * {@link ValueSortingTreeMap#put(Object key, Object value)},
         * then newKey is the newly inserted key
         * @param newKey
         * @param oldKey
         * @return
         */
        @Override
        public int compare(K newKey, K oldKey)
        {

            Comparable<V> newValue = (Comparable<V>)ValueSortingTreeMap.this.getSort(newKey);
            V oldValue = ValueSortingTreeMap.this.getSort(oldKey);
            // Good luck here :3
            return newValue.compareTo(oldValue);
        }
    };

    /**
     * Blame type erasure for removing the 
     * @param k
     * @param v
     */
    public ValueSortingTreeMap(Class<K> k, Class<V> v)
    {
        this.k = k;
        this.v = v;
        this.map = new TreeMap<K, V>(this.comparator);
    }

    @Override
    public V put(Object key, Object value)
    {
        Validate.notNull(key, "This mapping does not support null keys");
        Validate.isTrue(this.k.equals(key.getClass()), String.format("The key must be of type '%s'", this.k.getName()));
        Validate.isTrue(value == null || this.v.equals(value.getClass()), String.format("The value must be of type '%s' (or null)", this.v.getName()));
        this.unsorted.put((K)key, (V)value);
        return this.map.put((K)key, (V)value);
    }

    /**
     * Since {@link java.util.TreeMap#get(Object key)} uses the sort,
     * getting the key from the TreeMap could result into infinite
     * recursion. To prevent that, we keep a regular HashMap as
     * unsorted (but still O(1)) access point for values
     * <p>
     * Since we store this value before we store it in the TreeMap and remove
     * it after we remove it from the TreeMap, we can use this during all 
     * {@link Comparable#compareTo(java.lang.Object other)} calls.
     * @param key
     * @return
     */
    private V getSort(K key)
    {
        return this.unsorted.get(key);
    }

    @Override
    public V get(Object key)
    {
        return this.map.get(key);
    }

    @Override
    public V remove(Object key)
    {
        V value = this.map.remove(key);
        this.unsorted.remove(key);
        return value;
    }

    public Set<Entry<K, V>> entrySet()
    {
        return this.map.entrySet();
    }
}