Ideally, you should start with a simple synchronized block, identify that it indeed creates a bottle neck, then try to do it lock free. Maybe more complicated solution is not worth the effort or you have a bottle neck elsewhere?
John's solution seems faster but, if this is critical section of your program, you might want to also test the following (using just ConcurrentMap's atomic methods):
ConcurrentMap<Key, Long> map = new ConcurrentHashMap<>();
public boolean putIfGreater(Key key, long value) {
Long boxedValue = Long.valueOf(value);
Long current = map.putIfAbsent(key, boxedValue);
if (current == null) {
return true;
} else {
while (true) {
if (value < current) {
return false;
}
if (map.replace(key, current, boxedValue)) {
return true;
}
current = map.get(key);
}
}
}