Filter the elements of a map based on a subset of its keys without iterating through the entire thing

Just do:

map.keySet().retainAll(set);

As per the javadoc, the changes in the key set are reflected back in the map.

... The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. ...

Here's a demo:

Map<String, String> map = new HashMap<String, String>();
map.put("1", "one");
map.put("2", "two");
map.put("3", "three");

Set<String> set = new HashSet<String>();
set.add("1");
set.add("3");

map.keySet().retainAll(set);

System.out.println(map); // {3=three, 1=one}

Elaborating on BalusC's excellent answer, values() supports retainAll() as well:

Map<String, String> map = new HashMap<String, String>();
map.put("1", "one");
map.put("2", "two");
map.put("3", "three");

Set<String> set = new HashSet<String>();
set.add("one");
set.add("two");

map.values().retainAll(set);

System.out.println(map);   // prints {1=one, 2=two}

retailAll retains duplicate values as well, as you would expect:

Map<String, String> map = new HashMap<String, String>();
map.put("1", "one");
map.put("2", "two");
map.put("3", "three");
map.put("4", "two");

Set<String> set = new HashSet<String>();
set.add("one");
set.add("two");

map.values().retainAll(set);

System.out.println(map);  // prints {1=one, 2=two, 4=two}