How do I search a map in Java for a key that matches a predicate?

In a nutshell, it is as simple as:

Predicate<T> predicate = (t -> <your predicate here>);
return myMap.keySet()
    .stream()
    .filter(predicate)
    .findAny()
    .map(myMap::get);

returns an empty Optional if no key matches

(nota: findAny is better than findFirst because it does not prevent parallelization if relevant, and findFirst is useless anyway since the Set of keys is not sorted in any meaningful way, unless your Map is a SortedMap)

I prefer entrySet myself as well. You should find this efficient:

Map<String, Integer> map; //Some example Map
//The map is filled here

List<Integer> valuesOfInterest = map.entrySet()
                                 .stream() //Or parallelStream for big maps
                                 .filter(e -> e.getKey().startsWith("word")) //Or some predicate
                                 .map(Map.Entry::getValue) //Get the values
                                 .collect(Collectors.toList()); //Put them in a list

The list is empty if nothing matched. This is useful if multiple keys match the predicate.

It’s not clear why you are shouting “THEN” so often. It’s the standard way of solving problems, to combine tools designed for broad variety of use cases to get your specific result. There is a built-in capability for traversing a sequence of elements and search for matches, the Stream API. Further, the Map interface provides you with the Collection views, keySet(), entrySet(), and values(), to be able to use arbitrary tools operating on Collections, the bridge to the Stream API being one of them.

So if you have a Map<Key,Value> and are interested in the values, whose keys match a predicate, you may use

List<Value> valuesOfInterest = map.entrySet().stream()
    .filter(e -> e.getKey().fulfillsCondition())
    .map(Map.Entry::getValue)
    .collect(Collectors.toList());

which consists of three main steps, filter to select matches, map to specify whether you are interested in the key, value, entry or a converted value of each matche and collect(Collectors.toList()) to specify that you want to collect the results into a List.

Each of these steps could be replaced by a different choice and the entire stream pipeline could be augmented by additional processing steps. Since you want this specific combination of operations, there is nothing wrong with having to specify exactly these three steps instead of getting a convenience method for your specific use case.

The initial step of entrySet().stream() is required as you have to select the entry set as starting point and switch to the Stream API which is the dedicated API for element processing that doesn’t modify the source. The Collection API, on the other hand, provides you with methods with might mutate the source. If you are willing to use that, the alternative to the code above is

map.keySet().removeIf(key -> !key.fulfillsCondition());
Collection<Value> valuesOfInterest=map.values();

which differs in that the nonmatching entries are indeed removed from the source map. Surely, you don’t want to confuse these two, so it should be understandable, why there is a clear separation between the Collection API and the Stream API.