Уменьшите карту, где ключи являются значениями в некоторых записях

Question

Я пытаюсь создать новую Карту из другой Карты, где некоторые значения являются ключами в других записях.

Пример:

HashMap<String,String> testMap = new HashMap<>();
testMap.put("a","b");
testMap.put("b","d");
testMap.put("d","e");
testMap.put("e","f");
testMap.put("k","r");

Мне нужна новая карта с таким форматом:

a->f
b->f
d->f
e->f
k->r

producedMap.put("a","f");
producedMap.put("b","f");
producedMap.put("d","f");
producedMap.put("e","f");
producedMap.put("k","r");

Мой код таков, но, похоже, не дает истинного результата.

    public HashMap<String,String> getMatched(HashMap<String,String> correpondanceMap){

    Collection<String> correpondanceKeys = correpondanceMap.keySet();
    HashMap<String,String> newCorrepondanceMap= new HashMap<>();
    correpondanceMap.entrySet().forEach(entry->{
        if (correpondanceKeys.contains(entry.getValue())){
            String newValue = entry.getValue();
            String keyOfnewValue = correpondanceMap
                    .entrySet()
                    .stream()
                    .filter(entriii -> newValue.equals(entry.getValue()))
                    .map(Map.Entry::getKey).limit(1).collect(Collectors.joining());


            newCorrepondanceMap.put(keyOfnewValue,correpondanceMap.get(newValue));
        }
        else
        {
            newCorrepondanceMap.put(entry.getKey(),entry.getValue());
        }
    });

    newCorrepondanceMap.entrySet().forEach(entry-> System.out.println(entry.getKey() +"  -- > " +entry.getValue()));

    return newCorrepondanceMap;
}

Answer 1

Этого можно добиться с помощью простой логики рекурсии в вспомогательной функции:

public static String findCorrespondingValue(Map<String, String> map, String key){
    if(map.containsKey(key)){
        return findCorrespondingValue(map, map.get(key));
    }
    return key;
}

Как говорилось, логика очень проста, мы просто проверяем, существует ли для данного key значение в данном map

• если да, то мы снова выполняем функцию, но на этот раз с value в качестве новый key.
• если сопоставления не существует, мы можем с уверенностью сказать, что данный key является последним значение в цепочке

Вы можете вызвать метод следующим образом:

Map<String, String> testMap = ... // setup testMap

Map<String, String> result = new HashMap<>();
for (final Entry<String, String> entry : testMap.entrySet()) {
    result.put(
        entry.getKey(), 
        findCorrespondingValue(testMap, entry.getValue())
    );
}

или если вы использовали java 8:

Map<String, String> result = testMap.entrySet().stream()
    .collect(Collectors.toMap(
        e -> e.getKey(),  // or just Map.Entry::getKey
        e -> findCorrespondingValue(e.getValue())
     ));

---

Вам, конечно, придется реализовать какую-то логику, чтобы выяснить, есть ли у вас циклические ссылки. Например:

a -> b
b -> f
f -> a

Который сейчас просто потерпит неудачу с StackOverflowError.

---

Вы можете сделать это также общим, если вы хотите поддерживать несколько различных типов, а не только String:

public static <T> T findCorrespondingValue(Map<? extends T, ? extends T> map, T key){
    if(map.containsKey(key)){
        return findCorrespondingValue(map, map.get(key));
    }
    return key;
}