Whenever the exception can be anticipated but not avoided.
Say, if you are relying on an external API of some sort to parse data, and that API offers parse methods but nothing to tell whether a given input can be parsed or not (or if whether the parse can succeed or not depends on factors out of your control, but the API doesn’t provide appropriate function calls), and the parsing method throws an exception when the input cannot be parsed.
With a properly designed API, this should boil down to a quantity somewhere in the range “virtually never” to “never”.
I can see absolutely no reason to use exception handling as a means of normal flow control in code. It’s expensive, it’s hard to read (just look at your own first example; I realize it was probably written very quickly, but when _map hasn’t been initialized, what you end up with is an empty map, throwing away the entry you were trying to add), and it litters the code with largely useless try-catch blocks, which can very well hide real problems. Again taking your own example, what if the call to _map.add() were to throw a NullPointerException for some reason other than _map being null? Suddenly, you are silently recreating an empty map rather than adding an entry to it. Which I’m sure I don’t really have to say can lead to any number of bugs in completely unrelated places in the code because of unexpected state…
Edit: Just to be clear, the above answer is written in the context of Java. Other languages may (and apparently, do) differ in the implementation expense of exceptions, but other points should still hold.