Que se passe-t-il lorsqu'une clé en double est insérée dans un HashMap?

276

Si je passe plusieurs fois la même clé à HashMapla putméthode de, que se passe-t-il avec la valeur d'origine? Et si même la valeur se répète? Je n'ai trouvé aucune documentation à ce sujet.

Cas 1: valeurs écrasées pour une clé

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

Nous obtenons surely not one.

Cas 2: valeur en double

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

Nous obtenons one.

Mais qu'advient-il des autres valeurs? J'enseignais les bases à un étudiant et on m'a posé cette question. Est-ce Mapcomme un compartiment où la dernière valeur est référencée (mais en mémoire)?

boodieye
la source
7
BTW, c'est une excellente occasion de montrer le multi-hashmap qui fait partie des classes de collections de Jakarta ( commons.apache.org/collections ). Il vous permettra d'avoir un nombre quelconque de valeurs associées à la même clé pour les moments où vous en aurez besoin.
John Munsch
doublon possible de HashMap avec plusieurs valeurs sous la même clé
Muhammed Refaat

Réponses:

303

Par définition, la putcommande remplace la valeur précédente associée à la clé donnée dans la carte (conceptuellement comme une opération d'indexation de tableau pour les types primitifs).

La carte laisse simplement tomber sa référence à la valeur. Si rien d'autre ne contient une référence à l'objet, cet objet devient éligible pour le garbage collection. De plus, Java renvoie toute valeur précédente associée à la clé donnée (ou nulls'il n'y en a aucune), afin que vous puissiez déterminer ce qui s'y trouvait et conserver une référence si nécessaire.

Plus d'informations ici: HashMap Doc

jheddings
la source
Merci pour cela. En lisant la documentation Java, cela n'est pas mentionné clairement. Je suppose que l'auteur du document a supposé que c'était une supposition tacite de toutes les implémentations de cartes de hachage.
Andrew S
77

Vous pouvez trouver votre réponse dans le javadoc de Map # put (K, V) (qui retourne en fait quelque chose):

public V put(K key,
             V value)

Associe la valeur spécifiée à la clé spécifiée dans cette carte (opération facultative). Si la carte contenait auparavant un mappage pour cette clé, l'ancienne valeur est remplacée par la valeur spécifiée. (Une carte mest censée contenir un mappage pour une clé ksi et seulement si m.containsKey(k)reviendrait true.)

Paramètres:
key - clé à laquelle la valeur spécifiée doit être associée.
value- valeur à associer à la clé spécifiée.

Renvoie:
la valeur précédente associée à la clé spécifiée, ou nulls'il n'y avait pas de mappage pour key. (Un nullretour peut également indiquer que la carte précédemment associée nullà la spécifiée key, si l'implémentation prend en charge les nullvaleurs.)

Donc, si vous n'affectez pas la valeur retournée lors de l'appel mymap.put("1", "a string"), elle devient simplement non référencée et donc éligible pour le garbage collection.

Pascal Thivent
la source
3
La valeur retournée est la valeur précédente (ou null) comme documenté juste au-dessus dans le javadoc donc, oui, c'est ce que je veux dire. Peut-il vraiment être mal interprété?
Pascal Thivent
c'est très utile.
roottraveller
18

La valeur précédente de la clé est supprimée et remplacée par la nouvelle.

Si vous souhaitez conserver toutes les valeurs fournies par une clé, vous pouvez envisager d'implémenter quelque chose comme ceci:

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
la source
1
Cette solution est obsolète. MultiHashMap fait partie de apache.commons.collections et non java.
wikimix
17

c'est la fonction Clé / Valeur et vous ne pouvez pas avoir de clé en double pour plusieurs valeurs parce que lorsque vous voulez obtenir la valeur réelle dont l'une des valeurs appartient à la clé entrée
dans votre exemple lorsque vous voulez obtenir la valeur de "1", laquelle est il ?!
c'est des raisons d'avoir une clé unique pour chaque valeur mais vous pourriez avoir un truc par la bibliothèque standard java:

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


et vous pouvez l'utiliser de cette façon:

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

et le résultat des impressions sont:

[one, not one, surely not one]
not one
null
java acm
la source
Très bonne réponse! bon travail. Vous sauvez littéralement ma vie de programmation :).
Subin Babu
Merci aussi de ma part! J'ai dû y ajouter une méthode de "suppression" pour effectuer les mêmes fonctionnalités qu'une carte normale, mais cela a très bien fonctionné!
JGlass
1
@JGlass votre mec bienvenu, mais ce n'est pas une solution technique, c'est ce que vous pouvez faire par java standard lib, en problème technique vous devez être vigilant sur votre problème, si vous avez besoin d'avoir ce comportement je suis sûr que ce n'est pas une solution car du concept clé / valeur, et doit penser au problème et trouver un moyen logique de le résoudre. de toute façon mes détails sont juste une façon amusante de faire avec java et en production, les problèmes et la voie de résolution sont très différents du travail amusant! mais vous pouvez l'utiliser lorsque le comportement clé / valeur n'est pas votre problème et trouver une structure de données comme celle-ci.
java acm
13

Associe la valeur spécifiée à la clé spécifiée dans cette carte. Si la carte contenait précédemment un mappage pour la clé, l'ancienne valeur est remplacée.

Diego Alejandro
la source
12

Il remplace la valeur existante dans la carte pour la clé respective. Et si aucune clé n'existe avec le même nom, elle crée une clé avec la valeur fournie. par exemple:

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

Touche OUTPUT = "1", valeur = "deux"

Ainsi, la valeur précédente est remplacée.

Bishal Jaiswal
la source
4

Pour votre question si la carte était comme un seau: non.

C'est comme une liste avec des name=valuepaires alors qu'il namen'est pas nécessaire que ce soit une chaîne (elle le peut, cependant).

Pour obtenir un élément, vous passez votre clé à la méthode get () - qui vous donne en retour l'objet assigné.

Et une carte de hachage signifie que si vous essayez de récupérer votre objet à l'aide de la méthode get, elle ne comparera pas le véritable objet à celui que vous avez fourni, car il lui faudrait parcourir sa liste et comparer () la clé vous avez fourni avec l'élément courant.

Ce serait inefficace. Au lieu de cela, peu importe la composition de votre objet, il calcule un soi-disant code de hachage à partir des deux objets et les compare. Il est plus facile de comparer deux ints au lieu de deux objets entiers (peut-être profondément complexes). Vous pouvez imaginer le hashcode comme un résumé ayant une longueur prédéfinie (int), il n'est donc pas unique et a des collisions. Vous trouverez les règles du hashcode dans la documentation à laquelle j'ai inséré le lien.

Si vous voulez en savoir plus à ce sujet, vous voudrez peut-être consulter les articles sur javapractices.com et technofundo.com

Cordialement

Atmocréations
la source
3

J'ai toujours utilisé:

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

si je voulais appliquer plusieurs choses à une seule clé d'identification.

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

}

vous pourriez toujours faire quelque chose comme ça et vous créer un labyrinthe!

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");
}
moutonsiiHD
la source
2

Les cartes de JDK ne sont pas destinées à stocker des données sous des clés dupliquées.

  • Au mieux, la nouvelle valeur remplacera les précédentes.

  • Le pire scénario est une exception (par exemple, lorsque vous essayez de le collecter en tant que flux):

Pas de doublons:

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

D'accord. Vous obtiendrez: 2 $ ==> {one = one}

Flux dupliqué:

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

Exception java.lang.IllegalStateException: clé en double 1 (tentative de fusion des valeurs une et non une) | sur Collectors.duplicateKeyException (Collectors.java:133) | chez Collectors.lambda $ uniqKeysMapAccumulator $ 1 (Collectors.java:180) | chez ReduceOps $ 3ReducingSink.accept (ReduceOps.java:169) | chez Spliterators $ ArraySpliterator.forEachRemaining (Spliterators.java:948) | chez AbstractPipeline.copyInto (AbstractPipeline.java:484) | chez AbstractPipeline.wrapAndCopyInto (AbstractPipeline.java:474) | chez ReduceOps $ ReduceOp.evaluateSequential (ReduceOps.java:913) | chez AbstractPipeline.evaluate (AbstractPipeline.java:234) | sur ReferencePipeline.collect (ReferencePipeline.java:578) | à (# 4: 1)

Pour gérer les clés dupliquées - utilisez un autre package, par exemple: https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html

Il existe de nombreuses autres implémentations traitant des clés dupliquées. Celles-ci sont nécessaires pour le Web (par exemple, les clés de cookie dupliquées, les en-têtes Http peuvent avoir les mêmes champs, ...)

Bonne chance! :)

Witold Kaczurba
la source
l'opération de "remplacement" est-elle coûteuse?
gaurav
Il peut être résolu en utilisant JDK uniquement. Collectors.toMap()a le troisième argument - fonction de fusion. Si nous voulons remplacer tout simplement le dernier élément en double: Stream.of("one", "two", "one").collect(Collectors.toMap(x -> x, x -> x, (key1, key2) -> key2)). lien
autonome
De plus, votre deuxième exemple de code n'est pas correct. Cette entrée: "one", "not one", "surely not one"ne produira aucune erreur de clé en double à cause de toutes les chaînes différentes.
autonome
Salut @stand alone. Veuillez lire attentivement la fonction de cartographie (toMap).
Witold Kaczurba
Salut @WitoldKaczurba. Veuillez compiler votre code avant de poster.
autonome
1

Oui, cela signifie que toutes les 1 clés avec valeur sont écrasées avec la dernière valeur ajoutée et ici vous ajoutez "sûrement pas une" donc elle n'affichera que "sûrement pas une".

Même si vous essayez d'afficher avec une boucle, il n'affichera également qu'une seule clé et valeur qui ont la même clé.

ajaynakrani
la source
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

Signifie que la carte de hachage n'autorisera pas les doublons, si vous avez correctement remplacé les méthodes égales et hashCode ().

HashSet utilise également HashMap en interne, voir la doc source

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