Implementação do mapa com chaves duplicadas

Quero ter um mapa com chaves duplicadas.

Eu sei que existem muitas implementações de mapa (o Eclipse me mostra cerca de 50), então aposto que deve haver uma que permita isso. Sei que é fácil escrever seu próprio mapa que faça isso, mas prefiro usar alguma solução existente.

Talvez algo em coleções comuns ou coleções google?

Você está procurando um multimapa e, de fato, tanto as coleções comuns quanto o Guava têm várias implementações para isso. Multimaps permitem várias chaves, mantendo uma coleção de valores por chave, ou seja, você pode colocar um único objeto no mapa, mas você recupera uma coleção.

Se você puder usar o Java 5, eu preferiria o Guava, Multimappois ele reconhece os genéricos.

Não precisamos depender da biblioteca externa do Google Collections. Você pode simplesmente implementar o seguinte 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);
}

Certifique-se de ajustar o 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));

O resultado é:

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

Nota: precisamos importar arquivos de biblioteca.

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

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

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

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

Você poderia simplesmente passar uma matriz de valores para o valor em um HashMap regular, simulando assim chaves duplicadas, e caberia a você decidir quais dados usar.

Você também pode usar apenas um MultiMap , embora eu não goste da ideia de chaves duplicadas.

Se você quiser iterar sobre uma lista de pares de valores-chave (como você escreveu no comentário), então uma Lista ou uma matriz deve ser melhor. Primeiro combine suas chaves e valores:

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

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

}

Substitua Class1 e Class2 pelos tipos que deseja usar para chaves e valores.

Agora você pode colocá-los em uma matriz ou lista e iterar sobre eles:

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

Este problema pode ser resolvido com uma lista de entradas do mapa List<Map.Entry<K,V>>. Não precisamos usar bibliotecas externas nem novas implementações de Map. Uma entrada de mapa pode ser criada assim: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

commons.apache.org

MultiValueMap class

Aprenda com meus erros ... por favor, não implemente isso sozinho. Guava multimap é o caminho a percorrer.

Um aprimoramento comum exigido em multimaps é proibir pares de chaves-valor duplicados.

Implementar / alterar isso em sua implementação pode ser irritante.

No Goiaba é tão simples como:

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

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

Eu tinha uma variante ligeiramente diferente desse problema: era necessário associar dois valores diferentes à mesma chave. Apenas postando aqui no caso de ajudar outras pessoas, introduzi um HashMap como o 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 );
        }
}

No código acima, a chave frameID é lida a partir da primeira string de um arquivo de entrada em cada linha, o valor para frameTypeHash é construído dividindo a linha restante e foi armazenado como objeto String originalmente, durante um período de tempo em que o arquivo começou a ter várias linhas ( com valores diferentes) associados à mesma chave frameID, então frameTypeHash foi sobrescrito com a última linha como valor. Substituí o objeto String por outro objeto HashMap como o campo de valor, o que ajudou a manter uma chave única para mapeamento de valor diferente.

Não são necessárias bibliotecas sofisticadas. Os mapas são definidos por uma chave única, então não os dobre, use uma lista. Streams são 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"),
);

E é isso. Exemplos 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<>();

essa solução detalhada tem várias desvantagens e está sujeita a erros. Isso implica que precisamos instanciar uma Coleção para cada valor, verificar sua presença antes de adicionar ou remover um valor, excluí-lo manualmente quando nenhum valor for deixado, etc.

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

java-map-duplicate-keys

que tal um 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() .....

}

Você também poderia explicar o contexto para o qual está tentando implementar um mapa com chaves duplicadas? Tenho certeza de que poderia haver uma solução melhor. Os mapas têm como objetivo manter as chaves exclusivas por um bom motivo. Embora se você realmente quisesse fazer; você sempre pode estender a classe, escrever uma classe de mapa personalizado simples que tem uma função de mitigação de colisão e permitiria que você mantenha várias entradas com as mesmas chaves.

Observação: você deve implementar a função de mitigação de colisão de forma que as chaves de colisão sejam convertidas em um conjunto exclusivo "sempre". Algo simples como anexar o código hash do objeto ou algo assim?

só para ficar completo, o Apache Commons Collections também possui um MultiMap . A desvantagem, claro, é que o Apache Commons não usa Genéricos.

Com um pequeno hack, você pode usar o HashSet com chaves duplicadas. AVISO: isso depende muito da implementação do 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);
    }
}

Se houver chaves duplicadas, uma chave pode corresponder a mais de um valor. A solução óbvia é mapear a chave para uma lista desses valores.

Por exemplo em 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

Eu usei este:

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