How to create a List from Map and List of keys?

Question

Using Java 8 lambdas, what's the "best" way to effectively create a new List<T> given a List<K> of possible keys and a Map<K,V>? This is the scenario where you are given a List of possible Map keys and are expected to generate a List<T> where T is some type that is constructed based on some aspect of V, the map value types.

I've explored a few and don't feel comfortable claiming one way is better than another (with maybe one exception -- see code). I'll clarify "best" as a combination of code clarity and runtime efficiency. These are what I came up with. I'm sure someone can do better, which is one aspect of this question. I don't like the filter aspect of most as it means needing to create intermediate structures and multiple passes over the names List. Right now, I'm opting for Example 6 -- a plain 'ol loop. (NOTE: Some cryptic thoughts are in the code comments, especially "need to reference externally..." This means external from the lambda.)

public class Java8Mapping {
    private final Map<String,Wongo> nameToWongoMap = new HashMap<>();
    public Java8Mapping(){
        List<String> names = Arrays.asList("abbey","normal","hans","delbrook");
        List<String> types = Arrays.asList("crazy","boring","shocking","dead");
        for(int i=0; i<names.size(); i++){
            nameToWongoMap.put(names.get(i),new Wongo(names.get(i),types.get(i)));
        }
    }

    public static void main(String[] args) {
        System.out.println("in main");
        Java8Mapping j = new Java8Mapping();
        List<String> testNames = Arrays.asList("abbey", "froderick","igor");
        System.out.println(j.getBongosExample1(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
        System.out.println(j.getBongosExample2(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
        System.out.println(j.getBongosExample3(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
        System.out.println(j.getBongosExample4(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
        System.out.println(j.getBongosExample5(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
        System.out.println(j.getBongosExample6(testNames).stream().map(Bongo::toString).collect(Collectors.joining(", ")));
    }

    private static class Wongo{
        String name;
        String type;
        public Wongo(String s, String t){name=s;type=t;}
        @Override public String toString(){return "Wongo{name="+name+", type="+type+"}";}
    }

    private static class Bongo{
        Wongo wongo;
        public Bongo(Wongo w){wongo = w;}
        @Override public String toString(){ return "Bongo{wongo="+wongo+"}";}
    }

    // 1:  Create a list externally and add items inside 'forEach'.
    //     Needs to externally reference Map and List
    public List<Bongo> getBongosExample1(List<String> names){
        final List<Bongo> listOne = new ArrayList<>();
        names.forEach(s -> {
                  Wongo w = nameToWongoMap.get(s);
                  if(w != null) {
                      listOne.add(new Bongo(nameToWongoMap.get(s)));
                  }
              });
        return listOne;
    }

    // 2: Use stream().map().collect()
    //    Needs to externally reference Map
    public List<Bongo> getBongosExample2(List<String> names){
        return names.stream()
              .filter(s -> nameToWongoMap.get(s) != null)
              .map(s -> new Bongo(nameToWongoMap.get(s)))
              .collect(Collectors.toList());
    }

    // 3: Create custom Collector
    //    Needs to externally reference Map
    public List<Bongo> getBongosExample3(List<String> names){
        Function<List<Wongo>,List<Bongo>> finisher = list -> list.stream().map(Bongo::new).collect(Collectors.toList());
        Collector<String,List<Wongo>,List<Bongo>> bongoCollector =
              Collector.of(ArrayList::new,getAccumulator(),getCombiner(),finisher, Characteristics.UNORDERED);

        return names.stream().collect(bongoCollector);
    }
    // example 3 helper code
    private BiConsumer<List<Wongo>,String> getAccumulator(){
        return (list,string) -> {
            Wongo w = nameToWongoMap.get(string);
            if(w != null){
                list.add(w);
            }
        };
    }
    // example 3 helper code
    private BinaryOperator<List<Wongo>> getCombiner(){
        return (l1,l2) -> {
            l1.addAll(l2);
            return l1;
        };
    }

    // 4: Use internal Bongo creation facility
    public List<Bongo> getBongosExample4(List<String> names){
        return names.stream().filter(s->nameToWongoMap.get(s) != null).map(s-> new Bongo(nameToWongoMap.get(s))).collect(Collectors.toList());
    }

    // 5: Stream the Map EntrySet.  This avoids referring to anything outside of the stream, 
    // but bypasses the lookup benefit from Map.
    public List<Bongo> getBongosExample5(List<String> names){
        return nameToWongoMap.entrySet().stream().filter(e->names.contains(e.getKey())).map(e -> new Bongo(e.getValue())).collect(Collectors.toList());
    }

    // 6: Plain-ol-java loop
    public List<Bongo> getBongosExample6(List<String> names){
        List<Bongo> bongos = new ArrayList<>();
        for(String s : names){
            Wongo w = nameToWongoMap.get(s);
            if(w != null){
                bongos.add(new Bongo(w));
            }
        }
        return bongos;
    }
}

Answer 1

If namesToWongoMap is an instance variable, you can't really avoid a capturing lambda.

You can clean up the stream by splitting up the operations a little more:

return names.stream()
    .map(n -> namesToWongoMap.get(n))
    .filter(w -> w != null)
    .map(w -> new Bongo(w))
    .collect(toList());

return names.stream()
    .map(namesToWongoMap::get)
    .filter(Objects::nonNull)
    .map(Bongo::new)
    .collect(toList());

That way you don't call get twice.

This is very much like the for loop, except, for example, it could theoretically be parallelized if namesToWongoMap can't be mutated concurrently.

I don't like the filter aspect of most as it means needing to create intermediate structures and multiple passes over the names List.

There are no intermediate structures and there is only one pass over the List. A stream pipeline says "for each element...do this sequence of operations". Each element is visited once and the pipeline is applied.

Here are some relevant quotes from the java.util.stream package description:

A stream is not a data structure that stores elements; instead, it conveys elements from a source such as a data structure, an array, a generator function, or an I/O channel, through a pipeline of computational operations.

Processing streams lazily allows for significant efficiencies; in a pipeline such as the filter-map-sum example above, filtering, mapping, and summing can be fused into a single pass on the data, with minimal intermediate state.

Answer 2

Radiodef's answer pretty much nailed it, I think. The solution given there:

return names.stream()
    .map(namesToWongoMap::get)
    .filter(Objects::nonNull)
    .map(Bongo::new)
    .collect(toList());

is probably about the best that can be done in Java 8.

I did want to mention a small wrinkle in this, though. The Map.get call returns null if the name isn't present in the map, and this is subsequently filtered out. There's nothing wrong with this per se, though it does bake null-means-not-present semantics into the pipeline structure.

In some sense we'd want a mapper pipeline operation that has a choice of returning zero or one elements. A way to do this with streams is with flatMap. The flatmapper function can return an arbitrary number of elements into the stream, but in this case we want just zero or one. Here's how to do that:

return names.stream()
    .flatMap(name -> {
        Wongo w = nameToWongoMap.get(name);
        return w == null ? Stream.empty() : Stream.of(w);
    })
    .map(Bongo::new)
    .collect(toList());

I admit this is pretty clunky and so I wouldn't recommend doing this. A slightly better but somewhat obscure approach is this:

return names.stream()
    .flatMap(name -> Optional.ofNullable(nameToWongoMap.get(name))
                             .map(Stream::of).orElseGet(Stream::empty))
    .map(Bongo::new)
    .collect(toList());

but I'm still not sure I'd recommend this as it stands.

The use of flatMap does point to another approach, though. If you have a more complicated policy of how to deal with the not-present case, you could refactor this into a helper function that returns a Stream containing the result or an empty Stream if there's no result.

Finally, JDK 9 -- still under development as of this writing -- has added Stream.ofNullable which is useful in exactly these situations:

return names.stream()
    .flatMap(name -> Stream.ofNullable(nameToWongoMap.get(name)))
    .map(Bongo::new)
    .collect(toList());

As an aside, JDK 9 has also added Optional.stream which creates a zero-or-one stream from an Optional. This is useful in cases where you want to call an Optional-returning function from within flatMap. See this answer and this answer for more discussion.

Answer 3

One approach I didn't see is retainAll:

public List<Bongo> getBongos(List<String> names) {
    Map<String, Wongo> copy = new HashMap<>(nameToWongoMap);
    copy.keySet().retainAll(names);

    return copy.values().stream().map(Bongo::new).collect(
        Collectors.toList());
}

The extra Map is a minimal performance hit, since it's just copying pointers to objects, not the objects themselves.