fonction de hachage

**franklin626** · 21/04/2009, 00h15

Bonsoir à tous,

Je cherche à réaliser une table de hachage de taille variable qui associe à un caractère ASCII une donnée (dont on ne soucie pas ici).

Le problème, c'est que je souhaite écrire une fonction de hachage qui me renvoie toujours un code hachage unique , pour toute taille de la table, pour tout caractère ASCII.

Pour matérialiser ce que je viens de dire, imaginons qu'après plusieurs insertions et redimensionnements de mon tableau, les indices de mon tableau sont X...Y, comment faire pour que pour chaque caractère ASCII que j'ai ajouté, la fonction de hachage retourne un entier strictement différent?

PS :
- un caractère ASCII est représenté par un entier de 0 à 255
- le but de ma réalisation est de permettre un accès en 0(1) i.e. pas de parcours de sous-liste

D'avance, merci à tous les lecteurs!!!

**pseudocode** · 21/04/2009, 09h34

Envoyé par franklin626

- un caractère ASCII est représenté par un entier de 0 à 255
- le but de ma réalisation est de permettre un accès en 0(1) i.e. pas de parcours de sous-liste

Tu t'es renseigné sur le concept de tableau ?

**franklin626** · 21/04/2009, 14h19

Oui bien sûr mais je ne sais pas avant l'exécution quels caractères indexeront mon tableau.
Je les ajoute ou les supprime un à un. S'il n'y en a que 3 au final, je n'ai pas besoin d'allouer inutilement 255 emplacements en mémoire.

Je peux par exemple allouer au départ 4 emplacements, puis lorsque le redimensionnement est nécessaire, doubler la taille.
Cela impliquerait une fonction de hachage (dépendante ou non de la taille? Je ne sais pas) qui renvoie un code unique pour chaque caractère. De cette façon, je conserve le temps d'accès optimal et je réduis la mémoire nécessaire.

PS : J'ai donné l'exemple des caractères ASCII mais il s'agit d'un tableau générique qui n'est contraint qu'à l'exécution, je pourrait très bien avoir un intervalle d'indexation plus large.

**pseudocode** · 21/04/2009, 15h02

Ca existe... ca s'appelle du "perfect hashing" (et meme du "Dynamic perfect hashing" dans ton cas).

Le problème c'est que pour avoir un temps d'accès constant, on est obligé de consommer beaucoup d'espace mémoire. Toujours ce fameux dilemme d'optimisation Temps/Memoire.

Cela dit, es-tu sur d'avoir tant de collisions que cela pour ne pas utiliser un stockage par hashage traditionnel ?

**franklin626** · 21/04/2009, 20h07

Je ne suis pas un pro du hachage, donc je ne sais pas trop comment je m'y prendrais de façon classique, comme tu le dis.
Si je devais toutefois le faire de cette façon, je procèderais par modulo sur le code ASCII, mais il y aurait effectivement des collisions.

Je comprends le dilemne espace/temps, mais je cherche vraiment à conserver strictement l'accès aux données en O(1)

As-tu des sources intéressantes à proposer pour ce que tu appelles le "dynamic perfect hashing"?

alex_pi · 21/04/2009, 20h12

Une vraiment bonne table de hash ne peut se faire qu'en fonction des données qu'on va y insérer, et surtout de l'usage que l'on veut en faire.

Tu cherches du O(1) temps réel, amorti ? Il faut que l'insertion soit aussi en 0(1) ? Là aussi, temps réel, amorti ?

Tu as quoi comme donnée ? Si ce sont des caractères, arrête de te prendre la tête, un tableau de 256 case, un point c'est tout. Si c'est autre chose, c'est quoi ? Parce que hasher un arbre, un entier, une liste, une structure potentiellement cyclique, etc, c'est pas la même ! Et ton accès en O(1), c'est une fois que tu as le hash, ou la fonction de hashage doit aussi être en O(1) ?

Bref, il faut que tu explicites nettement plus tes contraintes !

**franklin626** · 23/04/2009, 00h30

Effectivement, ta dernière remarque me fait prendre conscience qu'un hachage n'est peut-être pas justifié pour l'application à 256 éléments max. Je vais donc adopter un simple tableau. La mémoire allouée inutilement est négligeable.

Cependant, je reste intéressé par le concept de perfect hashing pour des applications ultérieures.

Il s'agit bien dans ma question de O(1) réel et non amorti.

Admettons que j'ai un type borné d'entiers de 1 à N, avec N très grand, qui sont les clés.
Le hachage à cette fois-ci de l'intérêt, car on ne veut pas nécessairement allouer N emplacements car en utilisation, seule une fraction de ces clés sont ajoutées à la table.

Quant aux données indexées, il s'agit de codes binaires uniques.

Dans quels conditions et avec quelles méthodes puis-je avoir un hachage parfait?