Les tables de hachage
|
Par
jipe47
Mise à jour : 25/10/2010
Difficulté :
Intermédiaire
348 visites depuis 7 jours,
classé 301/786
|
).
. Sachez juste que j'utiliserai des exceptions et des interfaces. .
|
|
.
.)
) puisque certains mots peuvent avoir plusieurs significations.1 2 3 4 5 6 7 8 | public interface SymbolTable { public void put(int key, Object value) throws HashTableException; public Object get(int key) throws HashTableException; public void remove(int key) throws HashTableException; public boolean contains(int key); public int size(); } |
). Pour ceux que cela intéresse, voici le code Java de cette exception.1 2 3 4 5 | public class HashTableException extends Exception { public HashTableException() { super() ; } public HashTableException(String s) { super(s); } } |
. .
. Les indices de chaque paire sont déterminés par le hach code de la clé, qui est donné par une fonction de hachage. Oui, je sais, ces mots font peur, mais vous verrez que ce n'est pas si terrible que ça !
dans le reste de ce tutoriel) doit respecter les deux conditions suivantes :
, alors 
;
, alors 
à 
). Il va donc falloir le compresser, c'est-à-dire le borner aux indices du tableau. On utilise pour cela une fonction de compression (que l'on va ici noter 
). Ainsi, l'indice d'un élément i, qui sera donné par la fonction 
, est défini ainsi :
). L'ajout se déroulera selon le schéma ci-dessous.
. Imaginons que l'on dispose des fonctions suivantes :
, 
et 
). En sortant la calculette, on obtient les résultats ci-dessous :| Clé | |  |
|---|---|---|
| 0 | 14 | 4 |
| 4 | 26 | 6 |
| 7 | 35 | 5 |
| 42 | 140 | 0 |
.
et 
, et c'est la cata : l'indice 0 est déjà occupé par 42 ! . la fonction de hachage-compression, et i un indice qui varie de 0 à M :
et 
. La case 4 est occupée, on parcourt alors les indices jusqu'à trouver une case libre. La première case libre est en 7, on y met 30 !
et 
sont des constantes (et où est non nul),
valant 0 et valant 1. Si on insère 22 (dont le hach code est 0), on testera les indices 0 et 1. Pour insérer 30, on ira d'abord voir en 4, puis en 5 et enfin en 8.
, les indices testés auront la forme
définie de cette manière :
qui est occupé ;
qui n'est pas occupé, on doit s'arrêter.
, qui n'est pas occupé, on doit s'arrêter.
. Un dessin sera plus explicite : voici la table de notre exemple.
.
.
), est le rapport entre le nombre d'éléments insérés dans la table et le nombre de cases libres.
. Cela s'applique également pour les tableaux avec des listes (cas du chaînage linéaire).
. Si la table ne contiendra que peu de clés la première solution tombe à l'eau. Pour la seconde, à chaque insertion il faudra reconstruire à chaque fois la table, bref la joie niveau performances ! Quant au chaînage linéaire, il est une bonne alternative, mais il faudra vous décider sur la taille du tableau des listes. Et si beaucoup d'éléments sont insérés, les listes s'allongeront et on aura un temps d'exécution linéaire. . .1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public class Entry { private int key; private Object value; public Entry(int key, Object value) { this.key = key; this.value = value; } // Accesseurs public int getKey() { return key; } public Object getValue() { return value; } // Mutateurs public void setValue(Object value) { this.value = value; } } |
. .1 2 3 4 5 6 7 8 | public interface SymbolTable { public void put(int key, Object value) throws HashTableException; public Object get(int key) throws HashTableException; public void remove(int key) throws HashTableException; public boolean contains(int key); public int size(); } |
1 2 3 4 | private int hash(String s) { // ... } |
. . .1 2 3 4 | private int getBucketIndex(int key) { // ... } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public class Bucket { private Entry slot; private boolean free = true; public Bucket(Entry e) { this.slot = e; this.free = false; } public void clean() { slot.setValue(null); free = true; } // Accesseurs public int getKey() { return slot.getKey(); } public Object getValue() { return slot.getValue(); } public boolean isFree() { return free; } // Mutateur public void setValue(Object value) { slot.setValue(value) ; free = false; } } |
. Elle devra être spécifiée lors de l'instanciation de la table de hachage, et si elle ne l'est pas, on va utiliser une méthode de gestion des collisions par défaut.1 2 3 4 | public interface CollisionManagement { public int nextIndex(int h, int i); } |
. .1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | public class HashTable implements SymbolTable { private Bucket[] bucketArray; // Tableau contenant les paires "clé-valeur" private int nbrObject = 0; // Nombre d'éléments insérés private CollisionManagement manager; // Gestionnaire de collision public HashTable(int size) { // ... } public HashTable(int size, CollisionManagement manager) { // ... } public void put(int key, Object value) throws HashTableException { // ... } public Object get(int key) throws HashTableException { // ... } public void remove(int key) throws HashTableException { // ... } public boolean contains(int key) { // ... } public int size() { // ... } private int hash(String s) { // ... } private int getBucketIndex(int key) { // ... } } |
.1 2 3 4 5 | public HashTable(int size, CollisionManagement manager) { this.manager = manager; bucketArray = new Bucket[size]; } |
. On va par exemple utiliser le sondage linéaire par défaut (que l'on implémentera dans la prochaine sous-partie, rassurez-vous ).1 2 3 4 | public HashTable(int size) { this(size, new LinearProbing()); } |
1 2 3 4 5 6 7 8 9 10 | private int getBucketIndex(int key) { int h = hash(new Integer(key).toString()); // Calcul du hach code int index = h; // index sera l'indice de la clé for(int i = 0 ; bucketArray[index] != null && bucketArray[index].getKey() != key ; i++) index = manager.nextIndex(h, i) % bucketArray.length; // Obtention de la prochaine case return index; } |
. Le reste des fonctions n'est qu'une formalité !1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public void put(int key, Object value) throws HashTableException { if(bucketArray.length == nbrObject) // D'abord vérifier s'il reste de la place throw new HashTableException("Table pleine."); int index = getBucketIndex(key); // L'emplacement de la paire "clé-valeur" boolean inc = true; if(bucketArray[index] == null) // Si l'emplacement est vide... bucketArray[index] = new Bucket(new Entry(key, value)); // ... alors on y place la paire ! else // Si l'emplacement est déjà occupé ou libre... { inc = bucketArray[index].isFree(); // On incrémente que dans le cas où la case est libre bucketArray[index].setValue(value); // On remplace la valeur (choix d'implémentation) } if(inc) nbrObject++; } |
1 2 3 4 5 6 7 8 9 10 11 12 | public Object get(int key) throws HashTableException { if(nbrObject == 0) // Si la table est vide, cela ne sert à rien de continuer. throw new HashTableException("Table vide."); Bucket bucket = bucketArray[getBucketIndex(key)]; // Case dans laquelle devrait se trouver la clé if(bucket != null && !bucket.isFree()) // Si la case est occupée, on a trouvé notre clé ! return bucket.getValue(); else throw new HashTableException("Clé non trouvée"); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 | public void remove(int key) throws HashTableException { if(nbrObject == 0) // Si la table est vide, cela ne sert à rien de continuer throw new HashTableException("Table vide."); Bucket delete = bucketArray[getBucketIndex(key)]; // La case à nettoyer if(delete == null || delete.isFree()) // Si la case est vide ou déjà nettoyée, on peut s'arrêter throw new HashTableException("Clée non trouvée"); delete.clean(); nbrObject--; } |
. Vous devez d'abord récupérer le bucket (toujours avec getBucketIndex), et ensuite renvoyer vrai si elle est occupée, faux sinon.1 2 3 4 5 | public boolean contains(int key) { Bucket bucket = bucketArray[getBucketIndex(key)]; return (bucket != null && !bucket.isFree()); } |
.1 2 3 4 | public int size() { return nbrObject; } |
1 2 3 4 | public interface CollisionManagement { public int nextIndex(int h, int i); } |
.1 2 3 4 5 6 7 | public class LinearProbing implements CollisionManagement { public int nextIndex(int h, int i) { return h + i; } } |
.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public class QuadraticProbing implements CollisionManagement { private int c1, c2; // Si l'utilisateur ne spécifie pas les constantes lors de l'instanciation public QuadraticProbing() { this(0, 1); // Ou les générer aléatoirement } public QuadraticProbing(int c1, int c2) { this.c1 = c1; this.c2 = c2; } public int nextIndex(int h, int i) { return h + c1 * i + c2 * (i * i); } } |
1 2 3 4 5 6 7 8 9 10 11 | public class DoubleHash implements CollisionManagement { public int nextIndex(int h, int i) { return h + hash(i); } private int hash(int i) { // ... } } |
.
), voici une archive avec tout le code complet. Pour utiliser ces classes avec le code de la sous-partie précédente, il suffit d'en instancier une et de passer la référence dans le constructeur de la classe HashTable. Par exemple :1 2 3 4 5 6 7 | // ... CollisionManagement manager = new LinearProbing(); HashTable table = new HashTable(1000, manager); // ... |
.
. Cependant, je ne m'étendrai pas dessus, le but de ce tutoriel est de vous apprendre à utiliser les tables de hachage et non de coder des listes doublement liées. Je ne l'ai pas mis sur le schéma, mais il y aura également une variable membre nbrNode qui sera le nombre de noeuds que contient la liste.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public class Node { private Entry entry; private Node next, prev; public Node(Entry entry) { this(entry, null); } public Node(Entry entry, Node next) { this.entry = entry; this.next = next; this.prev = null; } // Accesseurs public int getKey() { return entry.getKey(); } public Object getValue() { return entry.getValue(); } public Node getNext() { return next; } public Node getPrev() { return prev; } // Mutateurs public void setValue(Object value) { entry.setValue(value); } public void setNext(Node next) { this.next = next; } public void setPrev(Node prev) { this.prev = prev; } } |
.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | public class Bucket { private int nbrNode = 0; // Nombre de noeuds dans la liste private Node list; // Référence vers la tête de la liste public Bucket(Entry e) { // ... } public boolean add(Entry e) { // ... } public void remove(int key) throws HashTableException { // ... } public Node get(int key) { // ... public boolean contains(int key) { // ... } public int getNbrNode() { // ... } } |
1 2 3 4 | public Bucket(Entry e) { this.add(e); } |
1 2 3 4 5 6 7 8 | public Node get(int key) { Node n = list; // Tête de la liste while(n != null && n.getKey() != key) // Tant qu'on n'est pas à la fin ou qu'on n'a pas la clé... n = n.getNext(); // .. on avance dans la liste return n; } |
.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public boolean add(Entry e) { Node n = get(e.getKey()); if(n != null) // Si la clé est déjà dans la liste, on change la valeur { n.setValue(e.getValue()); return false; } // Si la clé n'est pas dans la liste, on ajoute un noeud nbrNode++; Node v = new Node(e, list); // Nouveau noeud, future tête de liste if(list != null) // S'il y a déjà un noeud en tête, on met à jour la référence prev list.setPrev(v); list = v; // Mise à jour de la tête de liste return true; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public void remove(int key) throws HashTableException { Node n = get(key); if(n == null) throw new HashTableException("Clé non trouvée."); nbrNode--; // Opération 1 if(n.getPrev() != null) // Si le noeud est dans la liste n.getPrev().setNext(n.getNext()); else // Si le noeud est le premier de la liste list = n.getNext(); // Opération 2 if(n.getNext() != null) n.getNext().setPrev(n.getPrev()); } |
1 2 3 4 | public boolean contains(int key) { return (get(key) != null); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public void put(int key, Object value) { int index = hash(new Integer(key).toString()); // Calcul de l'indice Entry e = new Entry(key, value); if(bucketArray[index] != null) // Si la liste existe, on ajoute un noeud... { if(bucketArray[index].add(e)) // ... et le nombre d'élément augmente si la clé est nouvelle nbrObject++; } else // Si la liste n'existe pas, on l'instancie { nbrObject++; bucketArray[index] = new Bucket(e); } } |
. Ainsi, on va chercher le noeud qui contiendrait la clé à son indice, et on retourne la valeur si elle existe.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public Object get(int key) throws HashTableException { if(nbrObject == 0) throw new HashTableException("Table vide."); int index = hash(new Integer(key).toString()); // Calcul de l'indice if(bucketArray[index] == null || bucketArray[index].getNbrNode() == 0) // Si la liste n'existe pas ou est vide throw new HashTableException("Clée non trouvée"); Node n = bucketArray[index].get(key); // Récupération du noeud if(n != null) // Si le noeud existe, on retourne la valeur return n.getValue(); else throw new HashTableException("Clée non trouvée"); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 | public void remove(int key) throws HashTableException { if(nbrObject == 0) throw new HashTableException("Table vide."); int index = hash(new Integer(key).toString()); // Calcul de l'indice if(bucketArray[index] == null) throw new HashTableException("Clée non trouvée"); bucketArray[index].remove(key); // Suppression du noeud nbrObject--; } |
1 2 3 4 5 6 7 8 9 10 | public boolean contains(int key) { if(nbrObject == 0) return false; int index = hash(new Integer(key).toString()); // Calcul de l'indice Bucket b = bucketArray[index]; return (b != null && b.contains(key)); // Renvoie vrai si la liste existe et si elle contient la clé } |
. Vous pouvez retrouver tout le code dans cette archive ! . . Une table de hachage sera d'autant plus efficace si les fonctions de hachage et de compression répartissent les indices le plus uniformément possible.1 2 3 4 5 6 7 8 | public int hash(String s) { int h = 0; // Etape 1 - Hachage for(int i = 0 ; i < s.length() ; i++) h += (int) s.charAt(i); } |
1 2 3 4 5 6 7 8 | public int hash(String s) { int h = 0; int c = 42; // Etape 1 - Hachage for(int i = 0 ; i < s.length() ; i++) // On parcourt tous les caractères h += (int) s.charAt(i) * (int)(Math.pow(c, i)); } |
. .1 2 3 4 5 6 7 8 9 10 11 | public int hash(String s) { int h = 0; // Etape 1 - hachage for(int i = 0 ; i < s.length() ; i++) // On parcourt tous les caractères { h = (h << 5) | (h >>> 27); // Décalage cyclique de 5 bits h += (int) s.charAt(i); } } |
).1 2 3 4 5 6 7 8 9 10 | private int hash(String s) { int h = 0; // Etape 1 - Hachage // ... // Etape 2 : compression return Math.abs(h) % bucketArray.length; } |
). .1 2 3 4 5 | private int hash(String s) { // ... return (Math.abs(h) % p) % bucketArray.length; } |
. . Par exemple, ce site en possède pas mal, et était un des premiers résultats ! .
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Indice | 1 | 4 | 7 | 0 | 3 | 6 | 9 | 2 | 5 | 8 |
utiliser une fonction qui renvoie un entier positif toujours inférieur à M, par exemple en prenant les fonctions de hachage suivantes :
renvoit toujours une valeur impaire.
. Ainsi, ils pourraient s'amuser à entrer des clés dans votre table de hachage qui vont complètement détruire les performances !
.1 2 3 4 5 | private int hash(String s) { // ... return (Math.abs(a * h + b) % p) % bucketArray.length; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public class HashTable implements SymbolTable { // ... // Entiers pour le hachage private int a, b; private int p; // ... public HashTable(int size, CollisionManagement manager) { this.manager = manager; bucketArray = new Bucket[size]; Random generator = new Random(); // Générateur de nombres aléatoires p = 1073676287; // Grand nombre premier a = (Math.abs(generator.nextInt()) % p) + 1; b = Math.abs(generator.nextInt()) % p; } // ... } |
), mais peut être très instable et nécessiter de l'espace mémoire supplémentaire.
. C'est moins performant, mais il y a l'assurance de la stabilité des performances, c'est là un des grands avantages des arbres ! ) ; ;
. . Pour toute question ou suggestion (constructive), n'hésitez pas à poster un commentaire. Un grand merci à messages71 pour sa relecture, à Arthurus pour la validation et aux commentaires avisés des Zéros . . Le chapitre sur les tables de hachage commence à partir de la page 372 (dans la 4ème édition) ; . Le chapitre sur les tables de hachage commence à la page 215 (2ème édition).
|
Programmez avec le langage C++ |
|
Introduction : la vérité sur les strings enfin dévoilée |
|
Les tableaux |
|
Les classes (Partie 1/2) |
| Pseudo | Commentaire | ||
|---|---|---|---|
Pole
|
# Posté le 19/09/2010 à 22:46:17 | ||
Chieur professionnel
|
Citation Cela peut dans certains cas durer plus longtemps que le sondage linéaire. Pire : on pourrait ne jamais trouver de case libre, même s'il y en a dans le tableau ! Impossible si la taille du tableau est un nombre premier. Citation De plus, si la fonction de hachage n'est pas optimale, il est possible que de longues files se créent, ce qui inévitablement va flinguer les performances... S'il y a k nombres ayant le même hash alors le chaînage linéaire fera k tests au pire et le sondage au moins k au pire. Considérer cela comme un inconvénient me paraît donc douteux. Citation Il faudra bien évidemment refaire un modulo avec la taille du tableau, histoire de ne pas en sortir .Il faut bien évidemment ne pas refaire de modulo puisqu'il est fait dans la boucle : Code : Java
Note que ce modulo n'est pas présent dans le chaînage linéaire (et c'est une erreur). Citation Pensez à prendre la valeur absolue de h ! En effet, il peut être un nombre très grand et devenir négatif (surtout si vous faites un décalage cyclique). De plus, la fonction modulo de Java renvoie le modulo d'un nombre avec le même signe, donc il peut être négatif (ce qui n'est pas tolérable comme indice d'un tableau ).Certainement pas. D'une part, j'espère que Java a un type unsigned. Et s'il n'en a pas, il faut faire (h%p+p)%p. Citation Plus dangereux encore, imaginez que cette personne crée plusieurs carnets d'adresse avec des énormes clusters et, simultanément, lance plusieurs recherches qui dégénèrent, au point que le serveur web ne puisse plus satisfaire les requêtes... C'est le B-A-ba d'une attaque par déni de service  .Heureusement, il y a moyen de se prémunir et de déjouer ses plans diaboliques en changement très simplement la fonction de compression ! Malheureusement, si l'attaquant a compris quelle est la fonction de hash, il n'y a rien à faire. Quand on utilise des tables de hash, c'est un risque à prendre : la complexité en pire cas est O(N). Citation Bien évidemment, le code que j'ai donné n'est pas excepte de défauts exempte Les caisses sont vides Traité européen de 1965 : Citation : Traité FONCTIONNAIRES ET AGENTS DES COMMUNAUTÉS EUROPÉENNES Article 12 Sur le territoire de chacun des États membres et quelle que soit leur nationalité, les fonctionnaires et autres agents des Communautés: a) jouissent de l'immunité de juridiction pour les actes accomplis par eux, y compris leurs paroles et écrits, en leur qualité officielle, sous réserve de l'application des dispositions des traités relatives, d'une part, aux règles de la responsabilité des fonctionnaires et agents envers les Communautés et, d'autre part, à la compétence de la Cour pour statuer sur les litiges entre les Communautés et leurs fonctionnaires et autres agents. Ils continueront à bénéficier de cette immunité après la cessation de leurs fonctions, |
||
|
jipe47
|
# Posté le 26/09/2010 à 10:37:33 | ||
|
|
Bonjour et désolé pour le retard de cette réponse (rentrée universitaire ). yoch > bonne remarque, j'avoue avoir négligé cet aspect. Une nouvelle sous-partie est en cours d'édition traitant de ce sujet, ainsi que du facteur de charge .Pole > Citation : Pole Impossible si la taille du tableau est un nombre premier. T'aurais une source ou un raisonnement pour justifier ? Sur le moment même, je ne vois pas .Citation : Pole S'il y a k nombres ayant le même hash alors le chaînage linéaire fera k tests au pire et le sondage au moins k au pire. Considérer cela comme un inconvénient me paraît donc douteux. Oui, ça c'est sûr, mais dans les deux cas c'est dégénéré qu'il vaut mieux éviter. Cela reste un inconvénient d'avoir une file, avec un AVL tree ça le serait moins. Citation : Pole Certainement pas. D'une part, j'espère que Java a un type unsigned. Le carré d'un entier valant 46500 est négatif en Java... Et apparament il n'y a pas de nombres non signés en Java (ou pas facilement en tout cas). De toute façon, sur une suggestion d'Arthurus lors de la validation, je vais retirer l'objet Math (un peu trop gros pour ce à quoi il sert). Citation : Pole Malheureusement, si l'attaquant a compris quelle est la fonction de hash, il n'y a rien à faire. D'accord pour la fonction de hachage, mais il ne saura jamais anticiper la fonction de compression vu que les facteurs changent à chaque instanciation. Ou alors il est très fort et parvient à deviner ce que donnera le Random() .Pour le reste, c'est corrigé pour la prochaine validation. Merci pour vos suggestions .
|
||
|
titugo63
|
# Posté le 11/12/2011 à 14:58:10 | ||
Ville : Lavilledieu |
|||
|
Coda
|
# Posté le 03/01/2012 à 22:38:15 | ||
 
Ville : Pouilley-les-vignes |
Bon tutoriel, je trouve l'approche concluante et bien vulgarisée. J'ai détecté une petite erreur : Code : Java
Bonne continuation ! |
||
|
jipe47
|
# Posté le 04/01/2012 à 08:52:37 | ||
|
|
En effet, merci beaucoup pour la faute ! Une validation va être redemandée.
|
Trouvez une formation
Suggestions
Twitter
Facebook
Google+