Implementación de mapas con claves duplicadas

Quiero tener un mapa con claves duplicadas.

Sé que hay muchas implementaciones de mapas (Eclipse me muestra unas 50), así que apuesto a que debe haber una que lo permita. Sé que es fácil escribir tu propio mapa que haga esto, pero prefiero usar alguna solución existente.

¿Quizás algo en colecciones comunes o colecciones de Google?

Está buscando un multimapa y, de hecho, tanto commons-collections como Guava tienen varias implementaciones para eso. Los multimapas permiten múltiples claves manteniendo una colección de valores por clave, es decir, puede poner un solo objeto en el mapa, pero recupera una colección.

Si puede usar Java 5, preferiría el de Guava, Multimapya que es compatible con los genéricos.

No necesitamos depender de la biblioteca externa de Colecciones de Google. Simplemente puede implementar el siguiente mapa:

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);
}

Asegúrese de ajustar el código.

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));

La salida es:

[A,B,C,A]
[A,B,C]
[A]

Nota: necesitamos importar archivos de biblioteca.

http://www.java2s.com/Code/Jar/g/Downloadgooglecollectionsjar.htm

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

o https://commons.apache.org/proper/commons-collections/download_collections.cgi

import org.apache.commons.collections.MultiMap;
import org.apache.commons.collections.map.MultiValueMap;

Simplemente podría pasar una matriz de valores para el valor en un HashMap normal, simulando así claves duplicadas, y dependería de usted decidir qué datos usar.

También puede usar un MultiMap , aunque a mí no me gusta la idea de duplicar claves.

Si desea iterar sobre una lista de pares clave-valor (como escribió en el comentario), entonces una Lista o una matriz deberían ser mejores. Primero combine sus claves y valores:

public class Pair
{
   public Class1 key;
   public Class2 value;

   public Pair(Class1 key, Class2 value)
   {
      this.key = key;
      this.value = value;
   }

}

Reemplace Class1 y Class2 con los tipos que desea usar para claves y valores.

Ahora puede ponerlos en una matriz o lista e iterar sobre ellos:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}

Este problema se puede resolver con una lista de entradas de mapa List<Map.Entry<K,V>>. No necesitamos utilizar bibliotecas externas ni una nueva implementación de Map. Se puede crear una entrada de mapa como esta: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

commons.apache.org

MultiValueMap class

Aprenda de mis errores ... por favor, no implemente esto por su cuenta. El multimapa de guayaba es el camino a seguir.

Una mejora común requerida en multimaps es no permitir pares de claves-valor duplicados.

Implementar / cambiar esto en su implementación puede ser molesto.

En Guayaba es tan simple como:

HashMultimap<String, Integer> no_dupe_key_plus_val = HashMultimap.create();

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

Tenía una variante ligeramente diferente de este problema: era necesario asociar dos valores diferentes con la misma clave. Solo publíquelo aquí en caso de que ayude a otros, he introducido un HashMap como valor:

/* @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 );
        }
}

En el código anterior, el key frameID se lee de la primera cadena de un archivo de entrada en cada línea, el valor de frameTypeHash se construye dividiendo la línea restante y se almacenó como objeto String originalmente, durante un período de tiempo el archivo comenzó a tener varias líneas ( con diferentes valores) asociados con la misma clave frameID, por lo que frameTypeHash se sobrescribió con la última línea como valor. Reemplacé el objeto String con otro objeto HashMap como campo de valor, esto ayudó a mantener una clave única para la asignación de diferentes valores.

No se requieren bibliotecas sofisticadas. Los mapas están definidos por una clave única, así que no los doble, use una lista. Los arroyos son poderosos.

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"),
);

Y eso es. Ejemplos de uso:

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()...

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;
        }
    }

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

esta solución detallada tiene múltiples inconvenientes y es propensa a errores. Implica que necesitamos instanciar una Colección para cada valor, verificar su presencia antes de agregar o eliminar un valor, eliminarlo manualmente cuando no quedan valores, etcétera.

2, org.apache.commons.collections4.MultiMap interface
3, com.google.common.collect.Multimap interface 

java-map-duplicate-keys

¿Qué pasa con un impl MultiMap?

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() .....

}

¿Podría también explicar el contexto para el que está intentando implementar un mapa con claves duplicadas? Estoy seguro de que podría haber una solución mejor. Los mapas están destinados a mantener claves únicas por una buena razón. Aunque si realmente quisieras hacerlo; siempre puede extender la clase para escribir una clase de mapa personalizada simple que tenga una función de mitigación de colisiones y le permita mantener múltiples entradas con las mismas claves.

Nota: Debe implementar la función de mitigación de colisiones de modo que las claves en colisión se conviertan en un conjunto único "siempre". ¿Algo simple como agregar la clave con el código hash del objeto o algo así?

solo para estar completo, Apache Commons Collections también tiene un MultiMap . La desventaja, por supuesto, es que Apache Commons no usa Generics.

Con un pequeño truco puedes usar HashSet con claves duplicadas. ADVERTENCIA: esto depende en gran medida de la implementación de HashSet.

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);
    }
}

Si hay claves duplicadas, una clave puede corresponder a más de un valor. La solución obvia es asignar la clave a una lista de estos valores.

Por ejemplo en 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

Usé esto:

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