Put a value into the map in Java *without* updating existing value if exists

If you expect to be inserting new elements a vast majority of the time.

ValType temp = map.put(key, val);
if(temp != null)
    map.put(key, temp);

I don't think it's a good idea in general, but it is worth considering if you can reason sufficiently about your use case.

Second thought on this if you can use a particular map implementation instead of just the map interface you could do this with a NavigableMap

Map sub = map.subMap(key, true, key, true);
if (!sub.contains(key)) {
  sub.put(key, val);
}

Since the sub tree will be 0 or 1 nodes large there is no repeated work.

If you have a ConcurrentMap<K, V> there is the method putIfAbsent:

If the specified key is not already associated with a value, associate it with the given value. This is equivalent to

if (!map.containsKey(key))
    return map.put(key, value);
else
    return map.get(key);

except that the action is performed atomically.

However this method does not exist on Map<K, V>.