log(n) "sort by value" Map? I've read so much arguing about "sort by value maps". Well, I wrote the following log(n) sort by value Map . And, by the way, a real Map , does not allow duplicate keys. Many of the maps I googled ignore that annoying problem. I assume this map is still log(n)...:

public static void sortByValue_logN() {

    class MyComp implements Comparator {
        Map&lt;Object, Integer&gt; sharedMap;

        public int compare(Object key1, Object key2) {
            if(key1.equals(key2)) { return 0; }

            Integer val1 = sharedMap.get(key1);
            Integer val2 = sharedMap.get(key2);

            if(val1 &gt; val2) return -1; 
            return 1;
        }     

    }

    class TreeMapByValue&lt;K&gt; extends TreeMap&lt;K, Integer&gt; {
        Map&lt;Object, Integer&gt; sharedMap = new HashMap&lt;Object, Integer&gt;();
        TreeMapByValue(Comparator comp) {
            super(comp);
        }

        @Override
        public Integer put(K key, Integer val) {
            if(sharedMap.containsKey(key)) {
                super.remove(key);
                val += sharedMap.get(key);
            }
            sharedMap.put(key, val);

            super.put(key, val);

            return val;
        }
    }

    MyComp myComp = new MyComp();
    TreeMapByValue&lt;Object&gt; myMap = new TreeMapByValue(myComp);
    myComp.sharedMap = myMap.sharedMap;


    // all the rest is just testing the map
    Random rand = new Random();
    String[] story = { "The", "quick", "brown", "fox", "jumped" };

    for(int repeat = 0; repeat &lt; 3; repeat++) {
        for(int i = 0; i &lt; story.length; i++) {
            String key = story[i];
            int value = rand.nextInt(100);
            myMap.put(key, value);
            System.out.println(key + "--&gt;" + value);
        }
    }

    for(Map.Entry&lt;Object, Integer&gt; entry : myMap.entrySet()) {
        System.out.println("key = " + entry.getKey() + "___value = " + entry.getValue());
    }
} 


Surely (at least stylistically) something is bad about the above code.

I don't understand generics yet, so I am ok with ignoring that for now. I am also ignoring thread-safety issues as well.

My goal is to create a log(n) "sort by value" map that respects the property of not having duplicate keys. So, what is wrong with what I did?
put seems quite broken, which in turn breaks get.

From the documentation,


  V put(K key, V value)
  
  Associates the specified value with the specified key in this map
  (optional operation). If the map previously contained a mapping for
  the key, the old value is replaced by the specified value. (A map m is
  said to contain a mapping for a key k if and only if m.containsKey(k)
  would return true.)
  
  Returns:
  the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key, if the implementation supports null values.)


Let's take this code

  myMap.put("x", 1);
  int oldValue = myMap.put("x", 2);
  System.out.printf("%d %d%n", oldValue, myMap.get("x"));


I would expect it to print 1 2, but it prints 3 3.