Como podemos fazer isso com a goiaba? Observe a presença deList<K> no tipo de retorno, pois muitas chaves podem ser mapeadas para o mesmo valor em qualquer mapa normal.

public static <K, V> Map<V, List<K>> inverse(Map<K, V> map){
    Map<V, List<K>> result = new LinkedHashMap<V, List<K>>();
    for (Map.Entry<K, V> entry : map.entrySet()) {
        if(!result.containsKey(entry.getValue())){
            result.put(entry.getValue(), new ArrayList<K>());                
        }
        result.get(entry.getValue()).add(entry.getKey());
    }        
    return result;        
}

BiMap parece insistir na unicidade dos valores, mas não tenho esse luxo.