Map implementation with duplicate keys

Question

I want to have a map with duplicate keys   I know there are many map implementations  Eclipse shows me about 50   so I bet there must be one that allows this  I know it s easy to write your own map that does this  but I would rather use some existing solution   Maybe something in commons-collections or google-collections

User · Answer

Learn from my mistakes   please don t implement this on your own  Guava multimap is the way to go   A common enhancement required in multimaps is to disallow duplicate keys-value pairs   Implementing changing this in a your implementation can be annoying   In Guava its as simple as   HashMultimap lt String  Integer gt  no dupe key plus val   HashMultimap create     ArrayListMultimap lt String  Integer gt  allow dupe key plus val   ArrayListMultimap create

User · Answer

You are searching for a multimap  and indeed both commons-collections and Guava have several implementations for that  Multimaps allow for multiple keys by maintaining a collection of values per key  i e  you can put a single object into the map  but you retrieve a collection   If you can use Java 5  I would prefer Guava s Multimap as it is generics-aware

User · Answer

We don t need to depend on the Google Collections external library  You can simply implement the following Map   Map lt String  ArrayList lt String gt  gt  hashMap   new HashMap lt String  ArrayList gt      public static void main String    arg          Add data with duplicate keys    addValues  A    a1       addValues  A    a2       addValues  B    b          View data     Iterator it   hashMap keySet   iterator       ArrayList tempList   null      while  it hasNext            String key   it next   toString                       tempList   hashMap get key         if  tempList    null             for  String value  tempList                System out println  Key     key      Value     value                              private void addValues String key  String value       ArrayList tempList   null     if  hashMap containsKey key           tempList   hashMap get key         if tempList    null           tempList   new ArrayList          tempList add value          else         tempList   new ArrayList          tempList add value                          hashMap put key tempList       Please make sure to fine tune the code

User · Answer

I used this   java util List lt java util Map Entry lt String Integer gt  gt  pairList  new java util ArrayList lt  gt

User · Answer

If there are duplicate keys then a key may correspond to more than one value  The obvious solution is to map the key to a list of these values    For example in Python   map   dict   map  driver     list   map  driver   append  john   map  driver   append  mike   print map  driver              It shows john and mike print map  driver   0          It shows john print map  driver   1          It shows mike

User · Answer

Multimap lt Integer  String gt  multimap   ArrayListMultimap create     multimap put 1   A    multimap put 1   B    multimap put 1   C    multimap put 1   A     multimap put 2   A    multimap put 2   B    multimap put 2   C     multimap put 3   A     System out println multimap get 1    System out println multimap get 2           System out println multimap get 3      Output is      A B C A   A B C   A    Note  we need to import library files   http   www java2s com Code Jar g Downloadgooglecollectionsjar htm  import com google common collect ArrayListMultimap  import com google common collect Multimap    or https   commons apache org proper commons-collections download collections cgi  import org apache commons collections MultiMap  import org apache commons collections map MultiValueMap

User · Answer

Could you also explain the context for which you are trying to implement a map with duplicate keys  I am sure there could be a better solution  Maps are intended to keep unique keys for good reason  Though if you really wanted to do it  you can always extend the class write a simple custom map class which has a collision mitigation function and would enable you to keep multiple entries with same keys    Note  You must implement collision mitigation function such that  colliding keys are converted to unique set  always   Something simple like  appending key with object hashcode or something

User · Answer

You could simply pass an array of values for the value in a regular HashMap  thus simulating duplicate keys  and it would be up to you to decide what data to use   You may also just use a MultiMap  although I do not like the idea of duplicate keys myself

User · Answer

1  Map lt String  List lt String gt  gt  map   new HashMap lt  gt          this verbose solution has multiple drawbacks and is prone to errors  It        implies that we need to instantiate a Collection for every value  check for        its presence before adding or removing a value  delete it manually when no        values are left  etcetera    2  org apache commons collections4 MultiMap interface 3  com google common collect Multimap interface    java-map-duplicate-keys

User · Answer

If you want iterate about a list of key-value-pairs  as you wrote in the comment   then a List or an array should be better  First combine your keys and values   public class Pair      public Class1 key     public Class2 value      public Pair Class1 key  Class2 value             this key   key        this value   value            Replace Class1 and Class2 with the types you want to use for keys and values   Now you can put them into an array or a list and iterate over them   Pair   pairs   new Pair 10       for  Pair pair   pairs

User · Answer

commons apache org  MultiValueMap class

User · Answer

This problem can be solved with a list of map entry List lt Map Entry lt K V gt  gt   We don t need to use neither external libraries nor new implementation of Map  A map entry can be created like this      Map Entry lt String  Integer gt  entry   new AbstractMap SimpleEntry lt String  Integer gt   key   1

User · Answer

just to be complete  Apache Commons Collections also has a MultiMap  The downside of course is that Apache Commons does not use Generics

User · Answer

what about such a MultiMap impl   public class MultiMap lt K  V gt  extends HashMap lt K  Set lt V gt  gt      private static final long serialVersionUID   1L    private Map lt K  Set lt V gt  gt  innerMap   new HashMap lt  gt        public Set lt V gt  put K key  V value        Set lt V gt  valuesOld   this innerMap get key       HashSet lt V gt  valuesNewTotal   new HashSet lt  gt         if  valuesOld    null          valuesNewTotal addAll valuesOld             valuesNewTotal add value       this innerMap put key  valuesNewTotal       return valuesOld         public void putAll K key  Set lt V gt  values        for  V value   values          put key  value                 Override   public Set lt V gt  put K key  Set lt V gt  value        Set lt V gt  valuesOld   this innerMap get key       putAll key  value       return valuesOld          Override   public void putAll Map lt   extends K    extends Set lt V gt  gt  mapOfValues        for  Map Entry lt   extends K    extends Set lt V gt  gt  valueEntry   mapOfValues entrySet            K key   valueEntry getKey          Set lt V gt  value   valueEntry getValue          putAll key  value                 Override   public Set lt V gt  putIfAbsent K key  Set lt V gt  value        Set lt V gt  valueOld   this innerMap get key       if  valueOld    null          putAll key  value             return valueOld          Override   public Set lt V gt  get Object key        return this innerMap get key           Override   etc  etc  override all public methods size    clear

User · Answer

No fancy libs required  Maps are defined by a unique key  so dont bend them  use a list  Streams are mighty   import java util AbstractMap SimpleImmutableEntry   List lt SimpleImmutableEntry lt String  String gt  gt  nameToLocationMap   Arrays asList      new SimpleImmutableEntry lt  gt   A    A1        new SimpleImmutableEntry lt  gt   A    A2        new SimpleImmutableEntry lt  gt   B    B1        new SimpleImmutableEntry lt  gt   B    B1         And thats it   Usage examples   List lt String gt  allBsLocations   nameToLocationMap stream            filter x - gt  x getKey   equals  B             map x - gt  x getValue             collect Collectors toList      nameToLocationMap stream   forEach x - gt   do stuff with  x getKey     x getValue

User · Answer

class  DuplicateMap lt K  V gt         enum MapType               Hash LinkedHash            int HashCode   0      Map lt Key lt K gt  V gt  map   null       DuplicateMap                 map   new HashMap lt Key lt K gt  V gt                DuplicateMap  MapType maptype                 if   maptype    MapType Hash                 map   new HashMap lt Key lt K gt  V gt                       else if   maptype    MapType LinkedHash                 map   new LinkedHashMap lt Key lt K gt  V gt                       else             map   new HashMap lt Key lt K gt  V gt                V put  K key  V value                   return map put  new Key lt K gt   key   HashCode      value               void putAll  Map lt K  V gt  map1                 Map lt Key lt K gt  V gt  map2   new LinkedHashMap lt Key lt K gt  V gt              for   Entry lt K  V gt  entry   map1 entrySet                   map2 put  new Key lt K gt   entry getKey     HashCode      entry getValue                       map putAll map2              Set lt Entry lt K  V gt  gt  entrySet                 Set lt Entry lt K  V gt  gt  entry   new LinkedHashSet lt Map Entry lt K V gt  gt             for   final Entry lt Key lt K gt   V gt  entry1   map entrySet                   entry add  new Entry lt K  V gt                     private K Key   entry1 getKey   Key                    private V Value   entry1 getValue                      Override                 public K getKey                         return Key                                      Override                 public V getValue                         return Value                                      Override                 public V setValue V value                        return null                                          return entry              Override     public String toString             StringBuilder builder   new  StringBuilder            builder append               boolean FirstIteration   true          for   Entry lt K  V gt  entry   entrySet                   builder append     FirstIteration                  entry getKey    null    null  entry getKey   toString               entry getValue    null    null  entry getValue   toString                     FirstIteration   false                    builder append               return builder toString               class Key lt K1 gt                K1 Key          int HashCode           public Key K1 key  int hashCode                super                Key   key              HashCode   hashCode                     public K1 Key                 return Key                      Override         public String toString                 return  Key toString                         Override         public int hashCode                  return HashCode

User · Answer

I had a slightly different variant of this issue  It was required to associate two different values with same key  Just posting it here in case it helps others  I have introduced a HashMap as the value       param frameTypeHash  Key - gt  Integer  frameID   Value - gt  HashMap  innerMap      param innerMap  Key - gt  String  extIP   Value - gt  String    If the key exists  retrieve the stored HashMap innerMap     and put the constructed key  value pair      if  frameTypeHash containsKey frameID                  Key exists  add the key value to innerHashMap             HashMap innerMap    HashMap frameTypeHash get frameID               innerMap put extIP  connName     frameType     interfaceName              else               HashMap lt String  String gt  innerMap   new HashMap lt String  String gt                 innerMap put extIP  connName     frameType     interfaceName                  This means the key doesn t exists  adding it for the first time             frameTypeHash put frameID  innerMap                  In the above code the key frameID is read from a input file s first string in each line  the value for frameTypeHash is constructed by splitting the remaining line and was stored as String object originally  over a period of time the file started having multiple lines  with different values  associated with same frameID key  so frameTypeHash was overwritten with last line as the value  I replaced the String object with another HashMap object as the value field  this helped in maintaining single key to different value mapping

User · Answer

With a bit hack you can use HashSet with duplicate keys  WARNING  this is heavily HashSet implementation dependant    class MultiKeyPair       Object key      Object value       public MultiKeyPair Object key  Object value            this key   key          this value   value              Override     public int hashCode             return key hashCode             class MultiKeyList extends MultiKeyPair       ArrayList lt MultiKeyPair gt  list   new ArrayList lt MultiKeyPair gt          public MultiKeyList Object key            super key  null               Override     public boolean equals Object obj            list add  MultiKeyPair  obj           return false           public static void main String   args        HashSet lt MultiKeyPair gt  set   new HashSet lt MultiKeyPair gt         set add new MultiKeyPair  A   a1         set add new MultiKeyPair  A   a2         set add new MultiKeyPair  B   b1         set add new MultiKeyPair  A   a3          MultiKeyList o   new MultiKeyList  A        set contains o        for  MultiKeyPair pair   o list            System out println pair value

[java] Map implementation with duplicate keys

Examples related to java

Examples related to duplicates

Examples related to guava

Examples related to multimap