How to group the keys from a HashMap using values as a List or an Array

I have created a Map using a String as a key and Integer as a value. So, it is like citiesWithCodes.

I have put the values in Hashmap manually as of now, for the testing purpose. They are:

Map<String, Integer> citiesWithCodes = new HashMap<String, Integer>();
        citiesWithCodes.put("Berlin", 49);
        citiesWithCodes.put("Frankfurt", 49);
        citiesWithCodes.put("Hamburg", 49);
        citiesWithCodes.put("Cologne", 49);
        citiesWithCodes.put("Salzburg", 43);
        citiesWithCodes.put("Vienna", 43);
        citiesWithCodes.put("Zurich", 41);
        citiesWithCodes.put("Bern", 41);
        citiesWithCodes.put("Interlaken", 41);

I want to fetch the cities in a List or an Array format according to their codes. So, for example for a value 43, it should return something like {43=[Vienna, Salzburg]}.

I have tried the following approach. It is a definitely dirty approach and isn't giving the correct reults.

   public static Map<Integer, List<String>> codeCities(Map<String, Integer> citiesWithCodes){
       Map<Integer, List<String>> segList = new HashMap<Integer, List<String>>();
       List<String> city;
       Iterator<Entry<String, Integer>> i = citiesWithCodes.entrySet().iterator();
       while (i.hasNext()) {
           city = new ArrayList<String>();
           Entry<String, Integer> next = i.next();
           i.remove();
           city.add(next.getKey());
           for (Entry<String, Integer> e : citiesWithCodes.entrySet()) {
               if(e.getValue().equals(next.getValue())){
                   city.add(e.getKey());
                   citiesWithCodes.remove(e);
               }
           }
           System.out.println(city);
           segList.put(next.getValue(), city);
       }
       return segList;
   }

The output I am getting is: {49=[Cologne], 41=[Interlaken], 43=[Salzburg]} Could someone tell me, the correct approach to achieve the results?

PS: I know it is possible using MultiMap. But we are limited only to use Java Collection Framework and not Java 8 as well.