Как перебрать все значения Map

Метод values() возвращает представление (Collection<V>) всех значений карты.

for (String value : map.values()) {
    System.out.println(value);
}

Как и keySet(), values() — это view, связанный с картой. Удаление элемента из values() удалит соответствующую запись из Map. Коллекция values() может содержать дубликаты (разные ключи могут иметь одинаковые значения).

На собеседовании: назовите values() и упомяните, что это view-коллекция, а не копия. В отличие от keySet(), values() — это Collection, а не Set (допускает дубликаты).