To expand my comment on Ernest's correct answer, here is how I could implement the remove -and- put solution:
for (String key : new ArrayList<String>(map.keySet())) { String upper = key.toUpperCase(); for (String value : map.remove(key)) map.add(upper, value); }
source share