CODEWITHSUNDEEP
javaduplicatesguavamultimap
IAdapter
IAdapter

Reputation: 64777

Map implementation with duplicate keys

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?

Upvotes: 141

Views: 330844

Answers (22)

Vova
Vova

Reputation: 1

We could extend HashMap introducing another method to do what we need for key duplication:

import java.util.*;

class MyMap<K, S> extends HashMap<K, List<S>> {
    //Introducing another method into HashMap
    public List<S> putValue(K key, S value) {
        List<S> list = containsKey(key) ? get(key) : new ArrayList<>();
        list.add(value);
        put(key, list);
        return list;
    }

}

And than we could could do:

public class Main{
  public static void main(String[] args) {
    //Map with duplicate keys

    MyMap<Integer, String> myMap = new MyMap<>();
    myMap.putValue(1, "A");
    myMap.putValue(1, "B");
    myMap.putValue(1, "C");
    myMap.putValue(1, "D");

    myMap.putValue(2, "A");
    myMap.putValue(2, "B");
    myMap.putValue(2, "C");

    myMap.putValue(3, "A");
    myMap.putValue(3, "AA");
    myMap.putValue(3, "AAA");

    myMap.put(4, List.of("1", "2", "3"));
  
    System.out.println(myMap.get(1));
    System.out.println(myMap.get(2));
    System.out.println(myMap.get(3));
    System.out.println(myMap.get(4));
  }
}

Upvotes: 0

Alex
Alex

Reputation: 627

To handle a map with duplicate keys, you can use a Multimap implementation from Google Guava or Apache Commons Collections. Both provide elegant solutions for this use case.

1. Google Guava's Multimap

The Multimap interface allows you to map a key to multiple values. It provides several implementations like ArrayListMultimap, HashMultimap, etc., where each key can map to a collection of values. Example with Guava:

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

public class MultimapExample {
    public static void main(String[] args) {
        Multimap<String, String> multimap = ArrayListMultimap.create();

        multimap.put("key1", "value1");
        multimap.put("key1", "value2");
        multimap.put("key2", "value3");

        System.out.println(multimap);
        // Output: {key1=[value1, value2], key2=[value3]}
    }
}

Here, you can add multiple values to the same key. The Multimap stores a collection of values for each key.

To include Google Guava in your project, add the following Maven dependency:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>32.1.2-jre</version>
</dependency>

2. Apache Commons Collections MultiValuedMap

Another alternative is to use MultiValuedMap from Apache Commons Collections. This interface also allows you to map a key to multiple values. Example with Apache Commons Collections:

import org.apache.commons.collections4.MultiValuedMap;
import org.apache.commons.collections4.multimap.ArrayListValuedHashMap;

public class MultiValuedMapExample {
    public static void main(String[] args) {
        MultiValuedMap<String, String> multiValuedMap = new ArrayListValuedHashMap<>();

        multiValuedMap.put("key1", "value1");
        multiValuedMap.put("key1", "value2");
        multiValuedMap.put("key2", "value3");

        System.out.println(multiValuedMap);
        // Output: {key1=[value1, value2], key2=[value3]}
    }
}

To include Apache Commons Collections in your project, add the following Maven dependency:

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.4</version>
</dependency>

Conclusion

If you're already using Guava, I would recommend Multimap from Google Guava. Otherwise, if you're familiar with Apache Commons Collections, the MultiValuedMap would work just as well.

Upvotes: 0

Prilaga
Prilaga

Reputation: 857

Just use simple Set with Pair. This Set will exclude pairs with the same key-value. Also you can iterate it.

val set = hashSetOf<Pair<String, String>>()
set.add(Pair("1", "a"))
set.add(Pair("1", "b"))
set.add(Pair("1", "b")) // Duplicate
set.add(Pair("2", "a"))
set.add(Pair("2", "b"))
set.forEach { pair -> println(pair) }

result: (1, a),(2, b),(1, b),(2, a)

Upvotes: 0

Ravi Parekh
Ravi Parekh

Reputation: 5604

[June, 2021]

  1. org.springframework.util.MultiValueMap

  2. commons.apache.org - org.apache.commons.collections4

Upvotes: 7

Mayank
Mayank

Reputation: 89

You can use a TreeMap with a custom Comparator in order to treat each key as unequal to the others. It would also preserve the insertion order in your map, just like a LinkedHashMap. So, the net result would be like a LinkedHashMap which allows duplicate keys!

This is a very simple implementation without the need of any third party dependencies or complications of MultiMaps.

import java.util.Map;
import java.util.TreeMap;

...
...

//Define a TreeMap with a custom Comparator
Map<Integer, String> map = new TreeMap<>((a, b) -> 1); // See notes 1 and 2

//Populate the map
map.put(1, "One");
map.put(3, "Three");
map.put(1, "One One");
map.put(7, "Seven");
map.put(2, "Two");
map.put(1, "One One One");
    
//Display the map entries:
map.entrySet().forEach(System.out::println);

//See note number 3 for the following:
Map<Integer, String> sortedTreeMap = map.entrySet().stream()
            .sorted(Map.Entry.comparingByKey())
            .collect(Collectors.toMap(
                Map.Entry::getKey, Map.Entry::getValue,
                (x, y) -> x, () -> new TreeMap<>((a, b) -> 1)
             ));
//Display the entries of this sorted TreeMap: 
sortedTreeMap.entrySet().forEach(System.out::println);

    
...

Notes:

  1. You can also use any positive integer in place of 1 in the comparator's definition here.
  2. If you use any negative integer instead, then it will reverse the insertion order in your map.
  3. If you also want to sort this map based on the keys (which is the default behavior of a TreeMap), then you may do this operation on the current map.

Upvotes: 4

BiggDatta
BiggDatta

Reputation: 41

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<SimpleImmutableEntry<String, String>> nameToLocationMap = Arrays.asList(
    new SimpleImmutableEntry<>("A", "A1"),
    new SimpleImmutableEntry<>("A", "A2"),
    new SimpleImmutableEntry<>("B", "B1"),
    new SimpleImmutableEntry<>("B", "B1"),
);

And thats it. Usage examples:

List<String> allBsLocations = nameToLocationMap.stream()
        .filter(x -> x.getKey().equals("B"))
        .map(x -> x.getValue())
        .collect(Collectors.toList());

nameToLocationMap.stream().forEach(x -> 
do stuff with: x.getKey()...x.getValue()...

Upvotes: 4

george
george

Reputation: 19

what about such a MultiMap impl?

public class MultiMap<K, V> extends HashMap<K, Set<V>> {
  private static final long serialVersionUID = 1L;
  private Map<K, Set<V>> innerMap = new HashMap<>();

  public Set<V> put(K key, V value) {
    Set<V> valuesOld = this.innerMap.get(key);
    HashSet<V> valuesNewTotal = new HashSet<>();
    if (valuesOld != null) {
      valuesNewTotal.addAll(valuesOld);
    }
    valuesNewTotal.add(value);
    this.innerMap.put(key, valuesNewTotal);
    return valuesOld;
  }

  public void putAll(K key, Set<V> values) {
    for (V value : values) {
      put(key, value);
    }
  }

  @Override
  public Set<V> put(K key, Set<V> value) {
    Set<V> valuesOld = this.innerMap.get(key);
    putAll(key, value);
    return valuesOld;
  }

  @Override
  public void putAll(Map<? extends K, ? extends Set<V>> mapOfValues) {
    for (Map.Entry<? extends K, ? extends Set<V>> valueEntry : mapOfValues.entrySet()) {
      K key = valueEntry.getKey();
      Set<V> value = valueEntry.getValue();
      putAll(key, value);
    }
  }

  @Override
  public Set<V> putIfAbsent(K key, Set<V> value) {
    Set<V> valueOld = this.innerMap.get(key);
    if (valueOld == null) {
      putAll(key, value);
    }
    return valueOld;
  }

  @Override
  public Set<V> get(Object key) {
    return this.innerMap.get(key);
  }

  @Override
  etc. etc. override all public methods size(), clear() .....

}

Upvotes: 1

Vikki
Vikki

Reputation: 2015

 1, Map<String, List<String>> map = new HashMap<>();

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

Upvotes: 1

Issac Balaji
Issac Balaji

Reputation: 1441

Multimap<Integer, String> 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;

Upvotes: 29

Thach Van
Thach Van

Reputation: 1539

This problem can be solved with a list of map entry List<Map.Entry<K,V>>. We don't need to use neither external libraries nor new implementation of Map. A map entry can be created like this: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

Upvotes: 14

nd.
nd.

Reputation: 8932

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.

Upvotes: 96

Gabrial David
Gabrial David

Reputation: 59

class  DuplicateMap<K, V> 
{
    enum MapType
    {
        Hash,LinkedHash
    }

    int HashCode = 0;
    Map<Key<K>,V> map = null;

    DuplicateMap()
    {
        map = new HashMap<Key<K>,V>();
    }

    DuplicateMap( MapType maptype )
    {
        if ( maptype == MapType.Hash ) {
            map = new HashMap<Key<K>,V>();
        }
        else if ( maptype == MapType.LinkedHash ) {
            map = new LinkedHashMap<Key<K>,V>();
        }
        else
            map = new HashMap<Key<K>,V>();
    }

    V put( K key, V value  )
    {

        return map.put( new Key<K>( key , HashCode++ ), value );
    }

    void putAll( Map<K, V> map1 )
    {
        Map<Key<K>,V> map2 = new LinkedHashMap<Key<K>,V>();

        for ( Entry<K, V> entry : map1.entrySet() ) {
            map2.put( new Key<K>( entry.getKey() , HashCode++ ), entry.getValue());
        }
        map.putAll(map2);
    }

    Set<Entry<K, V>> entrySet()
    {
        Set<Entry<K, V>> entry = new LinkedHashSet<Map.Entry<K,V>>();
        for ( final Entry<Key<K>, V> entry1 : map.entrySet() ) {
            entry.add( new Entry<K, V>(){
                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<K, V> 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<K1>
    {
        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;
        }
    }

Upvotes: 1

Alex Arvanitidis
Alex Arvanitidis

Reputation: 4464

I used this:

java.util.List<java.util.Map.Entry<String,Integer>> pairList= new java.util.ArrayList<>();

Upvotes: 0

frostbite
frostbite

Reputation: 648

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<String, Integer> no_dupe_key_plus_val = HashMultimap.create();

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();

Upvotes: 4

cyberthanasis
cyberthanasis

Reputation: 415

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

Upvotes: 0

Erdem
Erdem

Reputation: 974

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<MultiKeyPair> list = new ArrayList<MultiKeyPair>();

    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<MultiKeyPair> set = new HashSet<MultiKeyPair>();
    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);
    }
}

Upvotes: 0

Suresh Vadali
Suresh Vadali

Reputation: 139

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 -> Integer (frameID), Value -> HashMap (innerMap)
   @param innerMap: Key -> String (extIP), Value -> 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<String, String> innerMap = new HashMap<String, String>();
            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.

Upvotes: 2

user668943
user668943

Reputation: 545

We don't need to depend on the Google Collections external library. You can simply implement the following Map:

Map<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList>();

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.

Upvotes: 38

newacct
newacct

Reputation: 122449

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

Upvotes: 0

Mnementh
Mnementh

Reputation: 51311

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)
{
   ...
}

Upvotes: 11

AlbertoPL
AlbertoPL

Reputation: 11519

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.

Upvotes: 19

Priyank
Priyank

Reputation: 14387

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?

Upvotes: 0

Related Questions