Pourquoi la méthode get de HashMap a-t-elle une boucle FOR?

Question

Je suis en train de regarder le code source pour HashMap dans Java 7, et je vois que l' put méthode permet de vérifier si une entrée est déjà présente et si elle est présente, alors il sera de remplacer l'ancienne valeur par la nouvelle valeur.

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

Donc, en gros, cela signifie qu'il y aurait toujours une seule entrée pour la clé donnée, j'ai vu cela par le débogage, mais si je me trompe, alors s'il vous plaît me corriger.

Maintenant, puisqu'il y a une seule entrée pour une clé donnée, pourquoi ne l' get méthode d'une boucle FOR, car elle pouvait avoir simplement retourné directement la valeur?

    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

Je me sens au-dessus de la boucle est inutile. Merci de m'aider à comprendre si je me trompe.

Answer 1

table[indexFor(hash, table.length)] est le seau de l' HashMap que peut contenir la clé que nous sommes à la recherche pour le (si il est présent dans l' Map).

Cependant, chaque compartiment peut contenir plusieurs entrées (soit des clés différentes ayant le même hashCode(), ou les différentes touches avec différents hashCode() qui reste encore cartographié le même compartiment), vous devez donc effectuer une itération sur ces entrées jusqu'à ce que vous trouver ce que vous cherchez.

Le nombre d'entrées dans chaque compartiment doit être très petite, cette boucle est toujours exécuté dans attendues O(1) du temps.

Answer 2

Si vous voyez le travail interne de la méthode get de la table de hachage.

public V get(Object key)  {
        if (key == null)
           return getForNullKey();
         int hash = hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
         {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                 return e.value;
         }
             return null;
}

• Tout d'abord, il obtient le code de hachage de l'objet clé, qui est transmis, et trouve le seau emplacement.
• Si le seau est trouvé, il renvoie la valeur (e.valeur)
• Si aucune correspondance n'est trouvée, elle renvoie null.

Quelques fois il peut y avoir des chances de Hashcode de collision et pour la résolution de cette collision Hashmap utilise equals() et ensuite le stocker cet élément dans LinkedList dans le même seau.

Prenons exemple:

Extraire les données pour les principaux vaibahv: carte.get(nouvelle Clé("vaibhav"));

Étapes:

1. Calculer le code de hachage de la Clé {"vaibhav"}.Il sera généré que 118.

2. Calculer l'indice en utilisant la méthode de l'indice, il sera de 6.

3. Aller à l'indice 6 de tableau et de comparer l'élément clé donné clé. Si les deux sont égaux puis retourner la valeur, faute de quoi vérifier à côté de l'élément, s'il existe.

4. Dans notre cas, il n'est pas retrouvé comme premier élément et à côté de l'objet node n'est pas nulle.

5. Si à côté de nœud est nulle alors retourner la valeur null.

6. Si à côté de nœud n'est pas null traverse le deuxième élément et répétez le processus jusqu'à 3 clé n'est pas trouvée ou suivant n'est pas null.

Pour ce processus de récupération pour la boucle sera utilisé. Pour plus d'information, vous pouvez vous référer cette

Answer 3

Pour mémoire, en java-8, cela est également présent (en quelque sorte, car il existe TreeNode s également):

 if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
 

Fondamentalement (pour le cas où le bac n'est pas un Tree ), itérez le bac entier jusqu'à ce que vous trouviez l'entrée recherchée.

En regardant cette implémentation, vous comprendrez peut-être pourquoi il est bon de fournir un hachage correct - de sorte que toutes les entrées ne se retrouvent pas dans le même seau, d'où un délai plus long pour la recherche.

Answer 4

Je pense que @Eran a déjà répondu à votre requête bien et @Prashant a également fait une bonne tentative, le long de avec d'autres personnes qui ont répondu, alors laissez-moi l'expliquer à l'aide d'un exemple, de sorte que le concept est très clair.

Concepts

Fondamentalement, ce que @Eran est en train de dire que dans un seau (essentiellement à l'index du tableau), il est possible qu'il n'y a plus d'une entrée (rien, mais Entry objet) et ce qui est possible lorsque 2 ou plusieurs clés de donner hachage différent, mais donner le même indice de seau/emplacement.

Maintenant, afin de mettre l'entrée dans la table de hachage, c'est ce qui se passe à un niveau élevé (à lire attentivement, car je suis allé le mile supplémentaire pour expliquer quelques bonnes choses qui sont par ailleurs pas partie de votre question):

• Obtenir le hash: ce qui se passe ici est donc que le hash est calculé pour une clé donnée (notez que ce n'est pas hashCode, un hash est calculé à l'aide de l' hashCode et il est de fait que-comme pour atténuer le risque de mal écrite fonction de hachage).
• Obtenir l'index: C'est essentiellement l'index du tableau ou en d'autres termes seau. Maintenant, pourquoi cet indice est calculé au lieu d'utiliser directement la valeur de hachage de l'indice est parce que pour réduire le risque de hachage pourrait plus que la taille de la table de hachage, de sorte que ce calcul de l'indice étape permet de s'assurer que l'indice sera toujours inférieure à la taille de la table de hachage.

Et quand une situation se produit lorsque 2 donner les clés de hachage différent mais le même index, puis celles qui vont dans le même seau, et c'est la raison pour que la boucle FOR est important.

Exemple

Ci-dessous est un exemple simple que j'ai créé pour illustrer le concept pour vous:

public class Person {
    private int id;

    Person(int _id){
        id = _id;
    }

    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }

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

La classe de Test:

import java.util.Map;

public class HashMapHashingTest {
    public static void main(String[] args) {
        Person p1 = new Person(129);
        Person p2 = new Person(133);

        Map<Person, String> hashMap = new MyHashMap<>(2);
        hashMap.put(p1, "p1");
        hashMap.put(p2, "p2");
        System.out.println(hashMap);
    }
}

Debug capture d'écran (cliquez et zoomer car il est à la recherche de petite taille):

Remarquez que dans l'exemple ci-dessus, les deux Person objet donne les différentes valeurs de hachage (136 et 140 respectivement), mais donne le même indice de 0, de sorte que les deux objets sont dans le même seau. Dans la capture d'écran, vous pouvez voir que les deux objets sont à l'index 0 et là vous avez un next aussi peuplée essentiellement de points pour le deuxième objet.

---

Mise à jour:une Autre façon la plus simple de voir que plus de la clé est d'aller dans le même seau

est par la création d'une classe et en remplaçant la hashCode méthode retourne toujours la même valeur int, maintenant ce qui allait se passer, c'est que tous les objets de cette classe donnerait le même index/seau emplacement, mais puisque vous n'avez pas remplacé l' equals méthode de sorte qu'ils ne seraient pas considérés comme identiques et par conséquent la forme d'une liste à l'index/seau emplacement.

Une autre tournure à ce que suppose que vous remplacez l' equals méthode et de comparer tous les objets de l'égalité alors qu'un objet sera présent à l'index/seau emplacement car tous les objets sont égaux.

Answer 5

Tandis que les autres réponses expliquer ce qui se passe, OP commentaires sur les réponses m'amène à penser un angle différent d'explication est nécessaire.

Exemple simplifié

Disons que vous allez jeter de 10 chaînes dans un tableau associatif: "A", "B", "C", "Bonjour", "au Revoir", "Yo", "Yo-yo", "Z", "1", "2"

Vous utilisez HashMap que votre hash map au lieu de faire votre propre carte de hachage (bon choix). Une partie de la substance au-dessous de ne pas utiliser HashMap mise en œuvre directement mais il approche de l'une plus théorique et du point de vue abstrait.

HashMap n'est pas par magie savez que vous allez à ajouter 10 chaînes, et il ne sait quelles chaînes de caractères, vous allez mettre en il plus tard. Elle a à offrir des places de mettre ce que vous pourriez donner à elle... pour tout ce qu'elle sait que vous allez mettre de 100 000 chaînes en elle - peut-être de chaque mot dans le dictionnaire.

Disons que, en raison de l'argument du constructeur que vous avez choisi lors de votre prise de new HashMap(n) que votre hash map a 20 seaux. Nous appelons bucket[0] par bucket[19].

1. map.put("A", value); Disons que la valeur de hachage pour "A" est de 5. Le hachage de la carte peut maintenant faire bucket[5] = new Entry("A", value);

2. map.put("B", value); Supposer de hachage("B") = 3. Donc, bucket[3] = new Entry("B", value);

3. map.put("C"), value); - de hachage("C") = 19 - bucket[19] = new Entry("C", value);

4. map.put("Hi", value); Maintenant, voici où cela devient intéressant. Disons que votre fonction de hachage est telle que de hachage("Bonjour") = 3. Alors maintenant, hash map veut faire bucket[3] = new Entry("Hi", value); Nous avons un problème! bucket[3] est où nous avons mis la touche "B", et "Salut" est certainement une touche autre que "B"... mais ils ont la même valeur de hachage. Nous avons une collision!

En raison de cette possibilité, l' HashMap n'est pas réellement mise en œuvre de cette façon. Un hachage de la carte doit avoir des seaux qui peut contenir plus de 1 entrée en eux. NOTE: je n'ai pas à en dire plus que 1 entrée avec la même clé, comme nous ne peut pas, mais il doit avoir des seaux qui peut contenir plus de 1 entrée de clés différentes. Nous avons besoin d'un seau qui peut contenir à la fois "B" et "Salut".

Afin de ne pas laisser n' bucket[n] = new Entry(key, value);, mais au lieu de cela, nous allons avoir bucket être de type Bucket[] au lieu de Entry[]. Alors maintenant, nous n' bucket[n].add( new Entry(key, value) );

Donc, nous allons changer de...

bucket[3].add("B", value);

et

bucket[3].add("Hi", value);

Comme vous pouvez le voir, nous avons maintenant les entrées pour "B" et "Salut" dans le même seau. Maintenant, lorsque nous voulons obtenir de nouveau, nous avons besoin d'une boucle sur tout dans le seau, par exemple, avec une boucle for.

Donc, la boucle est présent à cause des collisions. Pas de collisions de key, mais les collisions d' hash(key).

Pourquoi utilisons-nous tel un fou de la structure de données?

Vous demandez peut-être à ce stade, "Attendez, QUOI!?! Pourquoi pourrait-on faire une telle chose bizarre comme ça??? Pourquoi sommes-nous à l'aide de ces artificiel, et alambiqué structure de données???" La réponse à cette question serait...

Un hachage carte fonctionne comme ceci en raison des propriétés qu'un tel particulier le programme d'installation fournit pour nous en raison de la façon dont les mathématiques fonctionne. Si vous utilisez une bonne fonction de hachage, ce qui minimise les conflits, et si vous la taille de votre HashMap ont plus de seaux que le nombre d'entrées que vous devinez sera en elle, alors vous avez une optimisation de hachage de la carte qui sera le plus rapide de la structure de données pour les insertions et les requêtes de données complexes.

Votre table de hachage peut être trop petit

Puisque vous dites que vous êtes souvent en voyant cette boucle for être itéré avec plusieurs éléments de votre débogage, ce qui signifie que votre HashMap pourrait être trop petit. Si vous avez un délai raisonnable deviner combien de choses que vous pourriez mettre en elle, essayez de régler la taille plus grande que celle. Avis dans mon exemple ci-dessus que j'ai été insertion de 10 chaînes, mais avait une table de hachage avec carte de 20 seaux. Avec une bonne fonction de hachage, cela vous donnera de très peu de collisions.

Note:

Remarque: l'exemple ci-dessus est une simplification de la question et de ne prendre certains raccourcis pour des raisons de concision. Une explication complète est même un peu plus compliqué, mais tout ce que vous devez savoir pour répondre à la question posée est ici.