9

I'd like to do the following functionality:

if (!map.contains(key)) {
  map.put(key, val);
}

Update: Let's assume it's not HashMap so the map is implemented as a tree of some kind.

However note that it's a little inefficient, since if we get into the if we actually search the map twice. I'd actually like to do something like that:

map.put_if_new_key(key, val);

Any idea how to do it in Java?

informatik01
  • 16,038
  • 10
  • 74
  • 104
Drakosha
  • 11,925
  • 4
  • 39
  • 52

4 Answers4

8

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.

om-nom-nom
  • 62,329
  • 13
  • 183
  • 228
Sign
  • 1,919
  • 18
  • 33
  • 2
    One warning regarding your first approach: There are two situations where null can be returned. Either the key was missing, or the key was present and associated with the value null. You can't tell which it was with this method. – Mark Byers Dec 09 '11 at 20:30
  • same with contains(key), because essentially it checks to see if that key is null, so if you set a key to null, and then check it to see if it exists it would return false, so there is really no way to tell no matter the method if the key was set or not. – D3_JMultiply Dec 09 '11 at 20:57
  • 1
    @D3_JMultiply Huh what? That's not how it works. `contains()` will only return true if you really added they key (**CAN** be null) to the map not otherwise - that's how it's documented, but if you don't believe the documentation you can look at the implementation.. straight forward really. – Voo Dec 09 '11 at 21:04
5

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>.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
  • 2
    +1 for noting (in code) that this implementation is no more efficient than the one the OP offered – G. Bach Dec 09 '11 at 20:20
  • 3
    Note however - If the OP is worried about the slight increase in two look-ups of the map, the synchronization cost will be far worse. – John Vint Dec 09 '11 at 20:20
  • 1
    @JohnVint: True. But ***if*** he's using ConcurrentMap it's presumably because he *needs* the synchronization. It'll be expensive either way: either `putIfAbsent` or `contains` then `put` in a synchronized block. And I expect that `putIfAbsent` is slightly faster. – Mark Byers Dec 09 '11 at 20:47
  • 1
    @John Vint by far worse, do you mean the 1/10'th or so of a millisecond? – D3_JMultiply Dec 09 '11 at 20:53
1

I don't think your proposed code is inefficient. See if key is already there in Map then its a single map look-up. And even for the cases when key is not found there are not 2 searches. Only 1 search and 1 insert into Map.

anubhava
  • 761,203
  • 64
  • 569
  • 643
  • Insert is going down the tree exactly to the same place as search. – Drakosha Dec 09 '11 at 20:21
  • 1
    @Drakosha: Tree? What tree? The Map interface doesn't guarantee that the keys are stored in a tree - that's an implementation detail for *some* implementations. What implementation of Map are you using? From your question it could just as easily be a `HashMap` in which case there is no tree and key lookups will be extremely fast (on average). – Mark Byers Dec 09 '11 at 20:32
  • @MarkByers thanks, i updated the question. What if it's not `HashMap` – Drakosha Dec 09 '11 at 20:34
  • using your "inefficient" method will lose you fractions of milliseconds, unfortunately, no matter what type of map you use, any way that an implementation would be added would be no slower than checking outside, as seeing it's almost guaranteed that the method they'd use to check if the key didn't exist would probably be the same as what you would do to create the functionality. If you made a Map, had the functionality to check if a key exists, and then you made a more efficient method for checking it to prevent overwrites, wouldn't you update the check method to the more efficient method too? – D3_JMultiply Dec 09 '11 at 20:50
0

I don't think there's any way around checking "contains()" to see whether or not the key exists or not.

Look here to see if this might be an alternative for you:

What happens when a duplicate key is put into a HashMap?

Community
  • 1
  • 1
paulsm4
  • 114,292
  • 17
  • 138
  • 190