Table de hachage

Table de hachage

Je me pose des questions sur l’outil HashMap qui reste pour moi très mystérieux.

HashMap est une classe, dont la documentation est ici. Un objet d’une classe HashMap<K,V> est une table de hachage dont les clés sont des objets de la classe K, et dont les valeurs sont des objets de la classe V. Une table de hachage est une réalisation efficace de la table d’association. Une table d’association est une structure de données abstraite, c’est-à-dire définie par les opérations fournies. Ici, ranger une association k → v, retrouver la valeur v connaissant la clé k etc.

En résumé et dans l’autre sens, une table d’association est une structure abstraite (dit quoi faire), dont la table de hachage est une réalisation efficace (dit comment faire et vite), et dont finalement HashMap est un codage en Java (c’est fait, reste à l’utiliser).

Hachage correct

Dans le TD 4 on nous présente les méthodes hashcode() et equals(object o) comme indispensables au bon fonctionnement de Hashmap, mais à quoi servent-elles concrètement? Sont-elles réellement indispensables? A quoi ressemble une bonnne fonction de hachage? Dans quelle classe doit on la placer? Doit on y faire référence explicitement par la suite ou est-elle automatiquement prise en compte par le compilateur?

Que de questions ! Je répond à tout un peu dans le désordre.

D’abord l’essentiel : Les méthodes hashCode() et equals(Object o) sont à définir comme des méthodes (dynamiques) publiques de la classe des objets employés comme clés dans la table de hachage (pour vous la classes des préfixes). Une fois ceci fait, la prise en compte des nouvelles méthodes par le code de la bibliothèque (c’est-à-dire par HashMap) se fait tout seul. Mais attention, si vous ne redéfinissez pas les deux méthodes, alors vous ne serez pas prévenu par le compilateur.

Quelques précisions.

Il s’agit en fait de redéfinir les deux methodes hashCode() et equals(Object o) héritées de celles de classe Object. Cette redéfinition est indispensable, sinon le programme compilera, mais ne fonctionnera pas de façon satisfaisante. Le TD numéro 4 offre un exemple de ce qu’il faut faire. Dans le TP, la classe des clés est Cell.
Il faut distinguer entre choix correct de la fonction de hachage et choix efficace. Commençons par être correct. La documentation de Java explique les relations qui doivent exister entre les nouvelles définitons de hashCode() et de equals(Object o).
En gros :
1. p.hashCode() est bien une fonction, c’est-a-dire que pour un préfixe donné p, p.hashCode renvoie toujours la même valeur.
2. p1.equals(p2) renvoie true entraîne p1.hashCode() == p2.hashCode().
Enfin, pour comprendre à quoi servent hashCode et equals, il faut savoir comment fonctionne une table de hachage. Ceci est expliqué dans le poly, section 3.2, et plus brièvement dans les transparents de l’amphi 04. On peut dire que pour une clé k donnée, k.hashCode() permet de trouver la bonne liste de collisions; et que k.equals(...) permet de savoir si la clé k est déjà dans la table. Le point 2. ci-dessus limite la recherche d’une une clé égale (selon equals) à k à une seule liste de collisions.

Bon hachage

Pour l’efficacite, je m’appuie sur votre exemple :

Par exemple est-il envisageable de prendre la première lettre de chaque mot du préfixe et de la multiplier par un nombre premier d’un ordre de grandeur différent? Par exemple "il était une fois" renverrait 9(i) + 37 * 5 (e) + 257 * 21 (u) + 65537 * 6 (f).

C’est envisageable (à conditon d’avoir aussi redéfini equals), mais cela risque de conduire à trop de collisions, car seule une petite partie de la clé [les premières lettres de chaque mot] entrent dans le calcul du hashCode. Par exemple, il y aura collision avec « ils étaient uniformément fous »

L’idée me semble valable à condition de remplacer « première lettre » par « hashCode() de la chaîne ».

Il n’est pas facile de définir en quelques mots ce qu’est une bonne fonction de hachage, les quelques principes suivant ne peuvent pas être faux :

Il faut utiliser tout l’espace disponible dans les int (fonction de hachage surjective).
Des clés proches doivent avoir des valeurs de hachage éloignées.
Autant que faire ce peut, deviner une collision ne doit pas être évident.

En pratique, je vous conseille de ne pas vous compliquer la vie et de (bien) mélanger les hashCodes de chacun des mots du préfixe, comme dans les transparents du cours.