Java – Is throwing an exception an anti-pattern here

I just had a discussion over a design choice after a code review. I wonder what your opinions are.

There's this Preferences class, which is a bucket for key-value pairs. Null values are legal (that's important). We expect that certain values may not be saved yet, and we want to handle these cases automatically by initializing them with predefined default value when requested.

The discussed solution used following pattern (NOTE: this is not the actual code, obviously – it's simplified for illustrative purposes):

public class Preferences {
    // null values are legal
    private Map<String, String> valuesFromDatabase;

    private static Map<String, String> defaultValues;

    class KeyNotFoundException extends Exception {
    }

    public String getByKey(String key) {
        try {
            return getValueByKey(key);
        } catch (KeyNotFoundException e) {
            String defaultValue = defaultValues.get(key);
            valuesFromDatabase.put(key, defaultvalue);
            return defaultValue;
        }
    }

    private String getValueByKey(String key) throws KeyNotFoundException {
        if (valuesFromDatabase.containsKey(key)) {
            return valuesFromDatabase.get(key);
        } else {
            throw new KeyNotFoundException();
        }
    }
}

It was criticized as an anti-pattern – abusing exceptions to control the flow. KeyNotFoundException – brought to life for that one use case only – is never going to be seen out of the scope of this class.

It's essentially two methods playing fetch with it merely to communicate something to each other.

The key not being present in the database isn't something alarming, or exceptional – we expect this to occur whenever a new preference setting is added, hence the mechanism that gracefully initializes it with a default value if needed.

The counterargument was that getValueByKey – the private method – as defined right now has no natural way of informing the public method about both the value, and whether the key was there. (If it wasn't, it has to be added so that the value can be updated).

Returning null would be ambiguous, since null is a perfectly legal value, so there's no telling whether it meant that the key wasn't there, or if there was a null.

getValueByKey would have to return some sort of a Tuple<Boolean, String>, the bool set to true if the key is already there, so that we can distinguish between (true, null) and (false, null). (An out parameter could be used in C#, but that's Java).

Is this a nicer alternative? Yes, you'd have to define some single-use class to the effect of Tuple<Boolean, String>, but then we're getting rid of KeyNotFoundException, so that kind of balances out. We're also avoiding the overhead of handling an exception, although it's not significant in practical terms – there are no performance considerations to speak of, it's a client app and it's not like user preferences will be retrieved millions of times per second.

A variation of this approach could use Guava's Optional<String> (Guava is already used throughout the project) instead of some custom Tuple<Boolean, String>, and then we can differentiate between Optional.<String>absent() and "proper" null. It still feels hackish, though, for reasons that are easy to see – introducing two levels of "nullness" seem to abuse the concept that stood behind creating Optionals in the first place.

Another option would be to explicitly check whether the key exists (add a boolean containsKey(String key) method and call getValueByKey only if we have already asserted that it exists).

Finally, one could also inline the private method, but the actual getByKey is somewhat more complex than my code sample, thus inlining would make it look quite nasty.

I may be splitting hairs here, but I'm curious what you would bet on to be closest to best practice in this case. I didn't find an answer in Oracle's or Google's style guides.

Is using exceptions like in the code sample an anti-pattern, or is it acceptable given that alternatives aren't very clean, either? If it is, under what circumstances would it be fine? And vice versa?