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.

If your scope is limited to Java 7 then try changing as below code :

 Map<Integer, List<String>> segList = new HashMap<Integer, List<String>>();
 Iterator<Entry<String, Integer>> i = citiesWithCodes.entrySet().iterator();
            while (i.hasNext()) {
                  Entry<String, Integer> next = i.next();
                  if (segList.get(next.getValue()) != null) {
                       List<String> city= segList.get(next.getValue());
                       city.add(next.getKey());
                       segList.put(next.getValue(), city);
                  }else{
                        List<String> city=new ArrayList<String>();
                        city.add(next.getKey());
                        segList.put(next.getValue(), city);

                  }
            }

Output:

{49=[Frankfurt, Berlin, Hamburg, Cologne], 41=[Bern, Zurich, Interlaken], 43=[Vienna, Salzburg]}