sorted map implementation (ValueComparableMap), sorting not maintained when calling Map.Entry setValue

Question

I've used solution here which describes how to implement a value comparable map in java, and it is working fine for the put method, however, when I try to modify values already in the map through the Map.Entry type, sorting is no longer maintained. Following code exhibits the issue:

TreeMap<Integer, Float> valCompMap = new ValueComparableMap<Integer, Float>(Ordering.natural());
// some code that puts entries in map
Random random = new Random();
for (Map.Entry<Integer, Float> e : valCompMap.entrySet()) {
  e.setValue(e.getValue() + random.nextFloat());
}
//parse keys into list
List<Integer> sorted_keys = new ArrayList<Integer>(valCompMap.keySet()); //here sorted_keys are not sorted according to values in original key value pair in the map

As a work around, I'm re-putting keys with new values as such:

List<Integer> keys = new ArrayList<Integer>(valCompMap.keySet());
for (Integer k : keys) {
  valCompMap.put(k, valCompMap.get(k) + random.nextFloat());
}

Problems with work around:

1. Not straight forward (doesn't express intent clearly)
2. Seem to be in-efficient since looking at the put method in ValueComparableMap, it involves branching, searching, removing and 2x putting.

So what would be an efficient way to modify a value in such ValueComparableMap (while maintaining the live sort property)?

Here is a simple test to demonstrate issue:

TreeMap<Integer, Float> valCompMap = new ValueComparableMap<Integer, Float>(Ordering.natural());

//populate map with random stuff
Random random = new Random();
for (int i = 0; i < 10; ++i) {
  valCompMap.put(i, random.nextFloat());
}

//print
System.out.println("Before modifying, map:");
for (Map.Entry<Integer, Float> e : valCompMap.entrySet()) {
  System.out.println(e.toString());
}

//modify values in map
for (Map.Entry<Integer, Float> e : valCompMap.entrySet()) {
  e.setValue(e.getValue() + random.nextFloat());
}

//print
System.out.println("After modifying, map:");
for (Map.Entry<Integer, Float> e : valCompMap.entrySet()) {
  System.out.println(e.toString());
}

//modify values in work-around way
List<Integer> keys = new ArrayList<Integer>(valCompMap.keySet());
for (Integer k : keys) {
  valCompMap.put(k, valCompMap.get(k) + random.nextFloat());
}

//print
System.out.println("After modifying using work-around, map:");
for (Map.Entry<Integer, Float> e : valCompMap.entrySet()) {
  System.out.println(e.toString());
}

And here is the output:

Before modifying, map:
6=0.05478877
4=0.07464349
1=0.08668131
2=0.0869472
3=0.32622492
8=0.35595274
5=0.3879655
9=0.602066
7=0.7913183
0=0.8479772

After medifying, map:
6=0.9277618
4=0.9426463
1=0.269701
2=0.95250356
3=0.8576952
8=0.547724
5=1.1656129
9=1.3945209
7=1.0475534
0=0.91609937

After modifying using work-around, map:
3=0.96215
6=1.036502
4=1.1082084
1=1.1496286
8=1.2940607
7=1.343531
0=1.4778173
2=1.6039091
5=1.6165544
9=2.1403322