O que acontece quando uma chave duplicada é colocada em um HashMap?

276

Se eu passar a mesma chave várias vezes para HashMapo putmétodo, o que acontece com o valor original? E se o valor se repetir? Não encontrei nenhuma documentação sobre isso.

Caso 1: Valores sobrescritos para uma chave

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
System.out.println(mymap.get("1"));

Nós recebemos surely not one.

Caso 2: valor duplicado

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
// The following line was added:
mymap.put("1","one");
System.out.println(mymap.get("1"));

Nós recebemos one.

Mas o que acontece com os outros valores? Eu estava ensinando básico a um aluno e me perguntaram isso. É Mapcomo um balde em que o último valor é referenciado (mas na memória)?

boodieye
fonte
7
BTW, esta é uma excelente oportunidade para mostrar o multi-hashmap que faz parte das classes de coleções de Jacarta ( commons.apache.org/collections ). Isso permitirá que você tenha qualquer número de valores associados à mesma chave nos momentos em que você precisar.
314 John Munsch
possível duplicata de HashMap com vários valores sob a mesma chave
Muhammed Refaat

Respostas:

303

Por definição, o putcomando substitui o valor anterior associado à chave fornecida no mapa (conceitualmente como uma operação de indexação de matriz para tipos primitivos).

O mapa simplesmente elimina sua referência ao valor. Se nada mais contiver uma referência ao objeto, esse objeto se tornará elegível para a coleta de lixo. Além disso, Java retorna qualquer valor anterior associado à chave fornecida (ou nullse não houver nenhum), para que você possa determinar o que estava lá e manter uma referência, se necessário.

Mais informações aqui: HashMap Doc

casamentos
fonte
Obrigado por isso. Lendo através da documentação Java, isso não é mencionado claramente. Suponho que o autor do documento tenha assumido que essa é uma suposição tácita de todas as implementações de mapa de hash.
Andrew S
77

Você pode encontrar sua resposta no javadoc do Mapa # put (K, V) (que realmente retorna algo):

public V put(K key,
             V value)

Associa o valor especificado à chave especificada neste mapa (operação opcional). Se o mapa continha anteriormente um mapeamento para essa chave, o valor antigo será substituído pelo valor especificado. ( mDiz-se que um mapa contém um mapeamento para uma chave kse, e somente se m.containsKey(k), retornaria true.)

Parâmetros:
key - chave à qual o valor especificado deve ser associado.
value- valor a ser associado à chave especificada.

Retorna:
valor anterior associado à chave especificada ou nullse não houve mapeamento para key. (Um nullretorno também pode indicar que o mapa anteriormente associado nullao especificado key, se a implementação suportar nullvalores.)

Portanto, se você não atribuir o valor retornado ao chamar mymap.put("1", "a string"), ele se tornará não referenciado e, portanto, elegível para a coleta de lixo.

Pascal Thivent
fonte
3
O valor retornado é o valor anterior (ou null), conforme documentado logo acima no javadoc, portanto, sim, é isso que eu quero dizer. Pode realmente ser mal interpretado?
288 Pascal Thivent
isso é muito útil.
roottraveller
18

O valor anterior da chave é descartado e substituído pelo novo.

Se você deseja manter todos os valores fornecidos por uma chave, considere implementar algo como isto:

import org.apache.commons.collections.MultiHashMap;
import java.util.Set;
import java.util.Map;
import java.util.Iterator;
import java.util.List;
public class MultiMapExample {

   public static void main(String[] args) {
      MultiHashMap mp=new MultiHashMap();
      mp.put("a", 10);
      mp.put("a", 11);
      mp.put("a", 12);
      mp.put("b", 13);
      mp.put("c", 14);
      mp.put("e", 15);
      List list = null;

      Set set = mp.entrySet();
      Iterator i = set.iterator();
      while(i.hasNext()) {
         Map.Entry me = (Map.Entry)i.next();
         list=(List)mp.get(me.getKey());

         for(int j=0;j<list.size();j++)
         {
          System.out.println(me.getKey()+": value :"+list.get(j));
         }
      }
   }
}
kamlesh0606
fonte
1
Esta solução está obsoleta. O MultiHashMap faz parte de apache.commons.collections e não java.
Wikimix 3/11
17

é o recurso Chave / Valor e você não pode ter uma chave duplicada para vários valores, porque quando você deseja obter o valor real de qual um dos valores pertence à chave inserida
no seu exemplo, quando deseja obter o valor "1", qual é isto ?!
é por isso que temos uma chave exclusiva para cada valor, mas você pode ter um truque usando a java standard lib:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class DuplicateMap<K, V> {

    private Map<K, ArrayList<V>> m = new HashMap<>();

    public void put(K k, V v) {
        if (m.containsKey(k)) {
            m.get(k).add(v);
        } else {
            ArrayList<V> arr = new ArrayList<>();
            arr.add(v);
            m.put(k, arr);
        }
    }

     public ArrayList<V> get(K k) {
        return m.get(k);
    }

    public V get(K k, int index) {
        return m.get(k).size()-1 < index ? null : m.get(k).get(index);
    }
}


e você poderia usá-lo desta maneira:

    public static void main(String[] args) {
    DuplicateMap<String,String> dm=new DuplicateMap<>();
    dm.put("1", "one");
    dm.put("1", "not one");
    dm.put("1", "surely not one");
    System.out.println(dm.get("1"));
    System.out.println(dm.get("1",1));
    System.out.println(dm.get("1", 5));
}

e o resultado das impressões são:

[one, not one, surely not one]
not one
null
java acm
fonte
Ótima resposta! bom trabalho. Você literalmente salva minha vida de programação :).
Subin Babu
Obrigado de mim também! Eu tive que adicionar um método "remove" para executar a mesma funcionalidade que um mapa normal, mas funcionou muito bem!
JGlass # 16/18
1
@JGlass seu bem-vindo cara, mas esta não é uma solução técnica, é isso que você pode fazer pela java standard lib, tecnicamente no problema, você deve estar atento ao seu problema, se você precisa ter esse comportamento, tenho certeza que não é solução porque do conceito Chave / Valor, e deve pensar no problema e encontrar uma maneira lógica de resolver. de qualquer maneira, meus detalhes são apenas uma maneira divertida de fazer java e na produção, os problemas e o caminho da resolução são muito diferentes do trabalho divertido! mas você pode usá-lo quando o comportamento Chave / Valor não for problema seu e descobrir que possui uma estrutura de dados assim.
java acm
13

Associa o valor especificado à chave especificada neste mapa. Se o mapa continha anteriormente um mapeamento para a chave, o valor antigo será substituído.

Diego Alejandro
fonte
12

Ele substitui o valor existente no mapa pela respectiva chave. E se nenhuma chave existir com o mesmo nome, ela criará uma chave com o valor fornecido. por exemplo:

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","two");

Tecla OUTPUT = "1", valor = "dois"

Portanto, o valor anterior é substituído.

Bishal Jaiswal
fonte
4

Para sua pergunta se o mapa era como um balde: não.

É como uma lista com name=valuepares, embora namenão precise ser uma String (pode).

Para obter um elemento, você passa sua chave para o método get () - que fornece o objeto atribuído em troca.

E um mapa Hash significa que, se você estiver tentando recuperar seu objeto usando o método get, ele não comparará o objeto real com o que você forneceu, porque precisaria percorrer sua lista e comparar () a chave você forneceu o elemento atual.

Isso seria ineficiente. Em vez disso, não importa em que consiste seu objeto, ele calcula o chamado código hash dos dois objetos e os compara. É mais fácil comparar dois ints em vez de dois objetos inteiros (possivelmente profundamente complexos). Você pode imaginar o código de hash como um resumo com um comprimento predefinido (int); portanto, ele não é único e possui colisões. Você encontra as regras para o hashcode na documentação na qual inseri o link.

Se você quiser saber mais sobre isso, consulte os artigos em javapractices.com e technofundo.com

Saudações

Atmocreations
fonte
3

Eu sempre usei:

HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();

se eu quisesse aplicar várias coisas a uma chave de identificação.

public void MultiHash(){
    HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();
    String key = "Your key";

    ArrayList<String> yourarraylist = hashy.get(key);

    for(String valuessaved2key : yourarraylist){
        System.out.println(valuessaved2key);
    }

}

você sempre pode fazer algo assim e criar um labirinto!

public void LOOK_AT_ALL_THESE_HASHMAPS(){
    HashMap<String, HashMap<String, HashMap<String, HashMap<String, String>>>> theultimatehashmap = new HashMap <String, HashMap<String, HashMap<String, HashMap<String, String>>>>();
    String ballsdeep_into_the_hashmap = theultimatehashmap.get("firststring").get("secondstring").get("thirdstring").get("forthstring");
}
sheepiiHD
fonte
2

Os mapas do JDK não se destinam ao armazenamento de dados sob chaves duplicadas.

  • Na melhor das hipóteses, o novo valor substituirá os anteriores.

  • O pior cenário é a exceção (por exemplo, quando você tenta coletá-lo como um fluxo):

Sem duplicatas:

Stream.of("one").collect(Collectors.toMap(x -> x, x -> x))

Está bem. Você receberá: $ 2 ==> {one = one}

Fluxo duplicado:

Stream.of("one", "not one", "surely not one").collect(Collectors.toMap(x -> 1, x -> x))

Exceção java.lang.IllegalStateException: Chave duplicada 1 (tentativa de mesclar valores um e não um) | em Collectors.duplicateKeyException (Collectors.java:133) | em Collectors.lambda $ uniqKeysMapAccumulator $ 1 (Collectors.java:180) | em ReduceOps $ 3ReducingSink.accept (ReduceOps.java:169) | em Spliterators $ ArraySpliterator.forEachRemaining (Spliterators.java:948) | em AbstractPipeline.copyInto (AbstractPipeline.java:484) | em AbstractPipeline.wrapAndCopyInto (AbstractPipeline.java:474) | em ReduceOps $ ReduceOp.evaluateSequential (ReduceOps.java:913) | em AbstractPipeline.evaluate (AbstractPipeline.java:234) | em ReferencePipeline.collect (ReferencePipeline.java:578) | em (# 4: 1)

Para lidar com chaves duplicadas - use outro pacote, por exemplo: https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html

Existem muitas outras implementações que lidam com chaves duplicadas. Eles são necessários para a web (por exemplo, chaves de cookies duplicadas, cabeçalhos de HTTP podem ter os mesmos campos, ...)

Boa sorte! :)

Witold Kaczurba
fonte
a operação de "substituição" é cara?
gaurav
Ele pode ser resolvido usando apenas o JDK. Collectors.toMap()possui o terceiro argumento - função de mesclagem. Se queremos simplesmente substituir último elemento duplicado: Stream.of("one", "two", "one").collect(Collectors.toMap(x -> x, x -> x, (key1, key2) -> key2)). link
stand alone
Além disso, seu segundo exemplo de código não está correto. Esta entrada: "one", "not one", "surely not one"não produzirá nenhum erro de chave duplicado devido a todas as strings diferentes.
stand alone
Oi @ stand sozinho. Por favor, leia atentamente a função de mapeamento (toMap).
Witold Kaczurba 28/10/19
Olá, @WitoldKaczurba. Compile seu código antes de postar.
stand alone
1

Sim, isso significa que todas as 1 chaves com valor são substituídas pelo último valor adicionado e aqui você adiciona "certamente não uma", para exibir apenas "certamente não uma".

Mesmo se você estiver tentando exibir com um loop, ele também exibirá apenas uma chave e valor com a mesma chave.

ajaynakrani
fonte
0
         HashMap<Emp, Emp> empHashMap = new HashMap<Emp, Emp>();

         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp());
         empHashMap.put(new Emp(1), new Emp());
         System.out.println(empHashMap.size());
    }
}

class Emp{
    public Emp(){   
    }
    public Emp(int id){
        this.id = id;
    }
    public int id;
    @Override
    public boolean equals(Object obj) {
        return this.id == ((Emp)obj).id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}


OUTPUT : is 1

Significa que o mapa de hash não permitirá duplicatas, se você tiver substituído corretamente os métodos equals e hashCode ().

O HashSet também usa o HashMap internamente, consulte o documento de origem

public class HashSet{
public HashSet() {
        map = new HashMap<>();
    }
}
SatyaS
fonte