Comment les HashTables gèrent-ils les collisions?

98

J'ai entendu dans mes classes de diplôme qu'un HashTableplacera une nouvelle entrée dans le seau «prochaine disponible» si la nouvelle entrée de clé entre en collision avec une autre.

Comment le HashTabletoujours renvoie-t-il la valeur correcte si cette collision se produit lors de l'appel d'un retour avec la clé de collision?

Je suppose que le type Keyssont Stringet hashCode()renvoie la valeur par défaut générée par, par exemple, Java.

Si j'implémente ma propre fonction de hachage et que je l'utilise dans le cadre d'une table de consultation (c.-à-d. A HashMapou Dictionary), quelles stratégies existent pour traiter les collisions?

J'ai même vu des notes relatives aux nombres premiers! Informations pas si claires de la recherche Google.

Alex
la source

Réponses:

93

Les tables de hachage traitent les collisions de deux manières.

Option 1: en faisant en sorte que chaque compartiment contienne une liste liée d'éléments qui sont hachés dans ce compartiment. C'est pourquoi une mauvaise fonction de hachage peut rendre les recherches dans les tables de hachage très lentes.

Option 2: Si les entrées de la table de hachage sont toutes pleines, la table de hachage peut augmenter le nombre de compartiments dont elle dispose, puis redistribuer tous les éléments de la table. La fonction de hachage renvoie un entier et la table de hachage doit prendre le résultat de la fonction de hachage et le modifier par rapport à la taille de la table de cette façon, il peut être sûr qu'il arrivera au compartiment. Ainsi, en augmentant la taille, il réorganisera et exécutera les calculs modulo qui, si vous avez de la chance, pourraient envoyer les objets vers différents seaux.

Java utilise à la fois les options 1 et 2 dans ses implémentations de table de hachage.

ams
la source
1
Dans le cas de la première option, y a-t-il une raison pour laquelle une liste chaînée est utilisée au lieu d'un tableau ou même d'un arbre de recherche binaire?
1
l'explication ci-dessus est de haut niveau, je ne pense pas que cela fasse beaucoup de différence entre la liste liée et le tableau. Je pense qu'un arbre de recherche binaire serait excessif. De plus, je pense que si vous creusez dans des choses comme ConcurrentHashMap et d'autres, il y a beaucoup de détails d'implémentation de bas niveau qui peuvent faire une différence de performance, que l'explication de haut niveau ci-dessus ne tient pas compte.
matin
2
Si le chaînage est utilisé, lorsqu'une clé est donnée, comment savoir quel élément récupérer?
ChaoSXDemon
1
@ChaoSXDemon vous pouvez parcourir la liste dans la chaîne par clé, les clés en double ne sont pas le problème, le problème est que deux clés différentes ont le même hashcode.
ams
1
@ams: Lequel est préféré? Y a-t-il une limite pour la collision de hachage, après quoi le 2ème point est exécuté par JAVA?
Shashank Vivek
78

Lorsque vous avez parlé de "La table de hachage placera une nouvelle entrée dans le compartiment" suivant disponible "si la nouvelle entrée de clé entre en collision avec une autre.", Vous parlez de la stratégie d'adressage ouverte de la résolution de collision de la table de hachage.


Il existe plusieurs stratégies de table de hachage pour résoudre les collisions.

Le premier type de grande méthode nécessite que les clés (ou les pointeurs vers elles) soient stockées dans la table, avec les valeurs associées, ce qui comprend en outre:

  • Chaînage séparé

entrez la description de l'image ici

  • Adressage ouvert

entrez la description de l'image ici

  • Hachage coalescent
  • Hachage de coucou
  • Hachage Robin Hood
  • Hachage à 2 choix
  • Hachage à la marelle

Une autre méthode importante pour gérer les collisions est le redimensionnement dynamique , qui a plusieurs façons:

  • Redimensionner en copiant toutes les entrées
  • Redimensionnement incrémentiel
  • Clés monotones

EDIT : les éléments ci-dessus sont empruntés à wiki_hash_table , où vous devriez aller voir pour obtenir plus d'informations.

herohuyongtao
la source
3
"[...] exige que les clés (ou les pointeurs vers elles) soient stockées dans la table, avec les valeurs associées". Merci, c'est le point qui n'est pas toujours immédiatement clair lors de la lecture des mécanismes de stockage des valeurs.
mtone
27

Il existe plusieurs techniques disponibles pour gérer les collisions. Je vais expliquer certains d'entre eux

Chaînage: Dans le chaînage, nous utilisons des index de tableau pour stocker les valeurs. Si le code de hachage de la deuxième valeur pointe également vers le même index, nous remplaçons cette valeur d'index par une liste liée et toutes les valeurs pointant vers cet index sont stockées dans la liste liée et l'index du tableau réel pointe vers la tête de la liste liée. Mais s'il n'y a qu'un seul code de hachage pointant vers un index de tableau, la valeur est directement stockée dans cet index. La même logique est appliquée lors de la récupération des valeurs. Ceci est utilisé dans Java HashMap / Hashtable pour éviter les collisions.

Sondage linéaire: Cette technique est utilisée lorsque nous avons plus d'index dans la table que les valeurs à stocker. La technique de palpage linéaire fonctionne sur le concept de l'incrémentation continue jusqu'à ce que vous trouviez un emplacement vide. Le pseudo code ressemble à ceci:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Technique de double hachage: Dans cette technique, nous utilisons deux fonctions de hachage h1 (k) et h2 (k). Si la fente à h1 (k) est occupée, la deuxième fonction de hachage h2 (k) est utilisée pour incrémenter l'index. Le pseudo-code ressemble à ceci:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Les techniques de sondage linéaire et de double hachage font partie de la technique d'adressage ouvert et ne peuvent être utilisées que si les emplacements disponibles sont supérieurs au nombre d'éléments à ajouter. Cela prend moins de mémoire que le chaînage car il n'y a pas de structure supplémentaire utilisée ici, mais sa lenteur à cause de beaucoup de mouvement se produit jusqu'à ce que nous trouvions un emplacement vide. Toujours dans la technique d'adressage ouvert lorsqu'un élément est supprimé d'un emplacement, nous mettons une pierre tombale pour indiquer que l'élément est supprimé d'ici, c'est pourquoi il est vide.

Pour plus d'informations, consultez ce site .

Jatinder Pal
la source
18

Je vous suggère fortement de lire cet article de blog paru récemment sur HackerNews: Comment HashMap fonctionne en Java

En bref, la réponse est

Que se passe-t-il si deux objets clés HashMap différents ont le même hashcode?

Ils seront stockés dans le même compartiment mais pas de nœud suivant de la liste liée. Et la méthode keys equals () sera utilisée pour identifier la bonne paire clé / valeur dans HashMap.

zengr
la source
3
Les HashMaps sont très intéressants et ils vont en profondeur! :)
Alex
1
Je pense que la question concerne HashTables et non HashMap
Prashant Shubham
10

J'ai entendu dans mes classes de diplôme qu'un HashTable placerait une nouvelle entrée dans le seau «prochaine disponible» si la nouvelle entrée de clé entre en collision avec une autre.

Ceci est en fait pas le cas, au moins pour le JDK Oracle (il est un détail de mise en œuvre qui pourrait varier entre les différentes implémentations de l'API). Au lieu de cela, chaque compartiment contient une liste chaînée d'entrées antérieures à Java 8 et une arborescence équilibrée dans Java 8 ou supérieur.

alors comment le HashTable retournerait-il toujours la valeur correcte si cette collision se produit lors de l'appel d'un retour avec la clé de collision?

Il utilise le equals()pour trouver l'entrée réellement correspondante.

Si j'implémente ma propre fonction de hachage et que je l'utilise dans le cadre d'une table de consultation (c'est-à-dire un HashMap ou un dictionnaire), quelles stratégies existe-t-il pour gérer les collisions?

Il existe différentes stratégies de gestion des collisions avec différents avantages et inconvénients. L'entrée de Wikipedia sur les tables de hachage donne un bon aperçu.

Michael Borgwardt
la source
C'est vrai pour les deux Hashtableet HashMapdans jdk 1.6.0_22 par Sun / Oracle.
Nikita Rybak
@Nikita: pas sûr de Hashtable, et je n'ai pas accès aux sources pour le moment, mais je suis sûr à 100% que HashMap utilise le chaînage et non le sondage linéaire dans chaque version que j'ai jamais vue dans mon débogueur.
Michael Borgwardt
@Michael Eh bien, je regarde la source de HashMap en public V get(Object key)ce moment (même version que ci-dessus). Si vous trouvez une version précise où ces listes liées apparaissent, je serais intéressé de savoir.
Nikita Rybak
@Niki: Je regarde maintenant la même méthode, et je la vois utiliser une boucle for pour parcourir une liste d' Entryobjets liés :localEntry = localEntry.next
Michael Borgwardt
@Michael Désolé, c'est mon erreur. J'ai mal interprété le code. naturellement, e = e.nextn'est pas ++index. +1
Nikita Rybak
7

Mise à jour depuis Java 8: Java 8 utilise un arbre auto-équilibré pour la gestion des collisions, améliorant le pire des cas de O (n) à O (log n) pour la recherche. L'utilisation d'un arbre auto-équilibré a été introduite dans Java 8 comme une amélioration par rapport au chaînage (utilisé jusqu'à java 7), qui utilise une liste chaînée, et a le pire cas de O (n) pour la recherche (car il doit traverser la liste)

Pour répondre à la deuxième partie de votre question, l'insertion se fait en mappant un élément donné à un index donné dans le tableau sous-jacent de la table de hachage, cependant, lorsqu'une collision se produit, tous les éléments doivent encore être préservés (stockés dans une structure de données secondaire , et pas seulement remplacé dans le tableau sous-jacent). Ceci est généralement fait en faisant de chaque composant de tableau (slot) une structure de données secondaire (aka bucket), et l'élément est ajouté au bucket résidant sur l'index de tableau donné (si la clé n'existe pas déjà dans le bucket, dans dans quel cas il est remplacé).

Pendant la recherche, la clé est hachée sur son index de tableau correspondant et la recherche est effectuée pour un élément correspondant à la clé (exacte) dans le compartiment donné. Étant donné que le compartiment n'a pas besoin de gérer les collisions (compare directement les clés), cela résout le problème des collisions, mais le fait au prix de devoir effectuer une insertion et une recherche sur la structure de données secondaire. Le point clé est que dans un hashmap, la clé et la valeur sont stockées, et donc même si le hachage entre en collision, les clés sont comparées directement pour l'égalité (dans le compartiment) et peuvent donc être identifiées de manière unique dans le compartiment.

La gestion de la collission apporte les pires performances d'insertion et de recherche de O (1) dans le cas de l'absence de gestion de collission à O (n) pour le chaînage (une liste liée est utilisée comme structure de données secondaire) et O (log n) pour arbre auto-équilibré.

Références:

Java 8 est livré avec les améliorations / modifications suivantes des objets HashMap en cas de collisions importantes.

  • La fonction alternative de hachage de chaîne ajoutée dans Java 7 a été supprimée.

  • Les compartiments contenant un grand nombre de clés en collision stockeront leurs entrées dans une arborescence équilibrée au lieu d'une liste liée une fois qu'un certain seuil est atteint.

Les modifications ci-dessus garantissent les performances de O (log (n)) dans les pires scénarios ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )

Daniel Valland
la source
Pouvez-vous expliquer comment l'insertion dans le pire des cas pour un HashMap de liste chaînée est uniquement O (1) et non O (N)? Il me semble que si vous avez un taux de collision de 100% pour les clés non dupliquées, vous finissez par devoir traverser tous les objets du HashMap pour trouver la fin de la liste liée, non? Qu'est-ce que je rate?
mbm29414
Dans le cas spécifique de l'implémentation de hashmap, vous avez en fait raison, mais pas parce que vous devez trouver la fin de la liste. Dans une implémentation de liste chaînée de cas général, un pointeur est stocké à la fois sur la tête et la queue, et par conséquent l'insertion peut être faite dans O (1) en attachant le nœud suivant à la queue directement, mais dans le cas de hashmap, la méthode d'insertion doit garantir l'absence de doublons, et doit donc rechercher dans la liste pour vérifier si l'élément existe déjà, et par conséquent, nous nous retrouvons avec O (n). Et c'est donc la propriété set imposée à une liste chaînée qui cause O (N). Je vais apporter une correction à ma réponse :)
Daniel Valland
4

Il utilisera la méthode equals pour voir si la clé est présente paire et surtout s'il y a plus d'un élément dans le même compartiment.

Aéroglisseur plein d'anguilles
la source
4

Comme il existe une certaine confusion sur l'algorithme utilisé par HashMap de Java (dans l'implémentation Sun / Oracle / OpenJDK), voici les extraits de code source pertinents (à partir d'OpenJDK, 1.6.0_20, sur Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : 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 != null && key.equals(k))))
            return e;
    }
    return null;
}

Cette méthode (cite est des lignes 355 à 371) est appelée lors de la recherche d'une entrée dans le tableau, par exemple from get(), containsKey()et quelques autres. La boucle for parcourt ici la liste chaînée formée par les objets d'entrée.

Voici le code des objets d'entrée (lignes 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Juste après cela vient la addEntry()méthode:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Cela ajoute la nouvelle entrée sur le devant du compartiment, avec un lien vers l'ancienne première entrée (ou null, s'il n'y en a pas). De même, la removeEntryForKey()méthode parcourt la liste et se charge de ne supprimer qu'une seule entrée, laissant le reste de la liste intact.

Donc, voici une liste d'entrées liées pour chaque bucket, et je doute fort que cela ait changé de _20à _22, car c'était comme ça à partir de la 1.2.

(Ce code est (c) 1997-2007 Sun Microsystems, et disponible sous GPL, mais pour copier mieux utiliser le fichier original, contenu dans src.zip dans chaque JDK de Sun / Oracle, et aussi dans OpenJDK.)

Paŭlo Ebermann
la source
1
J'ai marqué cela comme un wiki communautaire , car ce n'est pas vraiment une réponse, plus une discussion sur les autres réponses. Dans les commentaires, l'espace n'est tout simplement pas suffisant pour de telles citations de code.
Paŭlo Ebermann
3

voici une implémentation très simple de table de hachage en java. dans uniquement les outils put()et get(), mais vous pouvez facilement ajouter ce que vous voulez. il s'appuie sur la hashCode()méthode de java qui est implémentée par tous les objets. vous pouvez facilement créer votre propre interface,

interface Hashable {
  int getHash();
}

et forcez-le à être implémenté par les touches si vous le souhaitez.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}
Jeffrey Blattman
la source
2

Il existe différentes méthodes de résolution des collisions, parmi lesquelles le chaînage séparé, l'adressage ouvert, le hachage Robin Hood, le hachage de coucou, etc.

Java utilise le chaînage séparé pour résoudre les collisions dans les tables de hachage. Voici un excellent lien pour savoir comment cela se passe: http://javapapers.com/core-java/java-hashtable/

Infusion d'absinthe n Asfodel
la source