The solution is pretty easy - instead of a HashMap<K,V>, where K is the key type and V is the value type, use a HashMap<K,List<V>> or a HashMap<K,Set<V>>. The insertion is also pretty easy:
- first get the value for the key which is a List<V> or Set<V>.
- if that does not exist, create a new one and add that to the map for the key.
- add to the List / Set.