Why is TreeMap taking value as key

Question

I have taken a treemap and want to sort it according to its key values which are stored in a hashmap. Whenever I want to update a key-value pair, I remove the key from the tree and add the key value again.

But I discovered that when I insert a key value pair, the key is getting overwritten if I insert a key-value pair where the value is already present. and moreover, the key has multiple occurrences in the treemap which should not happen. Can someone please explain to me what is happening?

class StockPrice {
    HashMap<Integer,Integer> map=new HashMap<>();
    TreeMap<Integer,Integer> treemap=new TreeMap<>((k1,k2)->map.get(k1)-map.get(k2)); //min heap
    int latesttime=-1;
    
    public StockPrice() {
        
    }
    
    public void update(int timestamp, int price) {
        System.out.println(treemap);
        latesttime=Math.max(latesttime,timestamp);
        map.put(timestamp,price);
        if(treemap.containsKey(timestamp)){
            treemap.remove((Integer)timestamp);
        }
        treemap.put(timestamp,price);
    }
    
    public int current() {
        return map.get(latesttime);
    }
    
    public int maximum() {
        return map.get(treemap.lastKey());
    }
    
    public int minimum() {
        return map.get(treemap.firstKey());
    }
}

["StockPrice","update","update","minimum","maximum","update","maximum","maximum","current","update","current","minimum","update","update","minimum","minimum"]
[[],[38,2308],[43,121],[],[],[40,5339],[],[],[],[32,5339],[],[],[43,6414],[49,9369],[],[]]

The output of print statement in the update method.
{}
{38=2308}
{43=121, 38=2308}
{43=121, 38=2308, 40=5339}
{43=121, 38=2308, 32=5339}
{43=121, 38=2308, 32=5339, 43=6414}

I wanted the values to be overwritten and not the key.

Answer 1

Your Comparator compares keys by value from first map, not by their own content

You have specified a Comparator, but apparently misunderstand how that Comparator is being put to work.

Your comparator compares keys of the second map by the value returned from first map — not the content of those keys

Let's look at a simpler example.

We start with three names, each mapped to a number. Notice that two of them map to the same number coincidentally. Both Alice and Carol return 2.

Map < String, Integer > otherMap =
        Map.of(
                "Alice" , 2 ,
                "Bob" , 3 ,
                "Carol" , 2
        );

Let's dump to console with a call the Map#toString. Be aware that Map iterates in an arbitrary order at any random time. By definition, a Map is unsorted.

otherMap.toString() = {Bob=3, Alice=2, Carol=2}

Now we define a second map. But this map is a NavigableMap, so its keys are kept in sorted order. The sorting by default is their natural order. Alternatively, we can specify a Comparator, as done here.

We use TreeMap as the concrete class for our NavigableMap.

NavigableMap < String, Integer > navMap = new TreeMap <>( ( k1 , k2 ) -> otherMap.get( k1 ) - otherMap.get( k2 ) );

By the way, that lambda can be replaced with a method reference passed to Comparator.comparingInt. This is beside the point here, just FYI.

NavigableMap < String, Integer > navMap = new TreeMap <>( Comparator.comparingInt( otherMap :: get ) );

By whichever of the two syntaxes, the effect is the same: 👉 Keys in our second map are judged by the value of the matching entry in the first map.

This means putting "Alice" in our second map has the same effect as putting "Carol" in our second map. Both return a value from the first map of 2. So they are equivalent.

Let's add three entries to our new map.

navMap.put( "Alice" , 100 );
navMap.put( "Bob" , 200 );
navMap.put( "Carol" , 300 );

Apparently you would expect three entries in navMap. But, no, there are two entries in navMap.

navMap = {Alice=300, Bob=200}

You can see that code run live at Ideone.com.

Putting "Carol" updated the entry for "Alice" with the new value of 300, rather than make a new third entry. This is because 👉 you told the TreeMap to compare the two keys based on their coincidentally shared value of 2 as returned by the first Map. You overrode the default behavior of comparing the text of "Alice" and "Carol".

Not a bug, a feature. Working as documented.

Pop quiz: What if we changed the put lines, so that we put Carol before Alice?

navMap.put( "Carol" , 300 );
navMap.put( "Alice" , 100 );
navMap.put( "Bob" , 200 );

Result is Carol=100 rather than Alice=300:

navMap.toString() = {Carol=100, Bob=200}

What happened is:

1. We made a new entry into our empty navigable map for "Carol"+300.
2. We attempted to put "Alice"+100. In doing so, the TreeMap did a lookup on the first map, and retrieved the value 2 for the key Alice. Well, 2 matches the 2 returned by a lookup for our first entry’s key, Carol. So that means Alice & Carol keys are equivalent. So no need for a new entry. The TreeMap updates the existing, singular, entry of "Carol"+300 to be "Carol"+100.
3. We put "Bob"+200, with the key of "Bob" returning a value from the first map of 3. Our TreeMap has not seen a key whose comparator value is 3, meaning it does not equal the 2 of the first and only entry. So the TreeMap makes a new second entry of "Bob"+200. Three is bigger than two, so the Bob entry sorts after the Carol entry.

---

Another issue: Your comparator violates the advice in the TreeMap Javadoc to make the comparator consistent with equals. So you are failing to obey the general contract of the Map interface.

---

I have no idea what you were trying to accomplish in your original effort behind this Question. I suggest you post another Question with your original goal so the community can devise an entirely different approach without what seems like an overly complicated use of double maps.