Hash Code

Hash Code - Stockage/Sauvegarde - Windows & Software

Marsh Posté le 08-04-2003 à 14:25:26    

Bonjour,
 
Je dois faire une présentation sur les tables de hachage. J'ai fais une recherche sur google et trouvé pas mal d'info, mais je comprend pas la différence entre l'utilisation d une table de hachage et un index.  
 
Je comprend pas non plus concrètement comment utilisé une table de hachage.  
 
Si qqun maitrise le sujet est-ce qu'il pourrait m'expliquer comment ca s'utilise ?
 
D'avance merci
 
Shaman
 


---------------
Le Smiley de la mort !! (8÷þ
Reply

Marsh Posté le 08-04-2003 à 14:25:26   

Reply

Marsh Posté le 08-04-2003 à 16:31:49    

up !


---------------
Le Smiley de la mort !! (8÷þ
Reply

Marsh Posté le 08-04-2003 à 16:45:29    

t'auras peut-être plus de chance sur Prog... je déplace le topic ?


---------------
mes programmes ·· les voitures dans les films ·· apprenez à écrire
Reply

Marsh Posté le 08-04-2003 à 16:58:16    

Je prends un exemple concret d'utilisation. Tu as une application ou tu souhaite authentifier des utilisateurs en fonction d'un mot de passe secret (que chaque utilisateur a choisi), tu enregistre ce mots de passe dans une base de données indexées.
 
Supposons que tu stock en clair ce mot de passe ! Le problème : tu te fais pirater ta base de données -> tout tes mots de passes sont accessibles.
 
Bon imagine une fonction de hash, tu passe chaque mot de passe à la moulinette (genre MD5 ou SHA1) tu enregistre ton mot de passe dans ta base de données indexées. Tu te fais pirater ta DB tu t'en fous car ils n'ont que le hash.
 
Pour authentifier tes utilisateurs c'est facile il suffit de prendre le mot de passe en clair (que l'utilisateur entre pour s'authentifier), de la passer dans ta fonction de hachage et de vérifier si une entrée existe dans la base de données.
 
La probablilité que deux utilisateurs choisissent le même mot de passe est faible, mais pour résoudre le problème des collisions on associe généralement un autre champ au mot de passe qui lui reste en clair : le nom d'utilisateur !
 
Bon la tu peux imaginer que tes utilisateurs ne sont pas stocké dans une base de données, mais dans un tableau indexé, le problème est identique. Suppose que je fasse un dump de la mémoire de ton ordi, j'ai tous les mots de passe en clair, si ils sont hashé je peux toujours courrir (avec une fonction de hachage digne de ce nom) pour trouver une autre chaîne en entrée qui donnera le même "hash code" en sortie.


Message édité par Requin le 08-04-2003 à 17:17:37
Reply

Marsh Posté le 08-04-2003 à 17:11:47    

Je prends un deuxième exemple (pas charte compliant du tout) : eDonkey / eMule
 
La problématique c'est de partager des fichiers et de fournir un mécanisme de recherche parmis les fichiers (tu peux voir cela comme un flux de données de taille N).
 
Bon première solution, chaque utilisateur qui veut partager un fichier le transfert sur le serveur qui tient à jour une liste de nom de fichier associées aux données de ce fichier... tu remarque que ce n'est pas viable. Que non seuleemnt il faut une bande passante monumentale, mais aussi un espace de stockage énorme.
 
La solution est d'utiliser une table de hachage ; si le "hash code" est suffisament long et que la fonction de hashage est uniforme il est peu probable d'avoir deux fichiers de même taille qui créent le même hash.
 
Par exemple la fonction de hashage de eDonkey / eMule va créer le hash suivant pour un fichier donné :

Code :
  1. ed2k://|file|CODESW~1.LOG|819|fa9a7a10f7207457ac77d2b0b6934e3a|


 
Tu vois que le nom du fichier CODESW~1.LOG est associé à la taille du fichier "819" octets et au hash des donneés du fichiers "fa9a7a10f7207457ac77d2b0b6934e3a", pour le serveur il suffit de maintenir une liste de utilisateurs qui ont des fichiers de même taillle et avec le même hash, c'est qu'ils ont le même fichier.
 
Donc quand tu te connecte à un serveur edonkey, il suffit d'envoyer le nom de chaque fichier, la taille et son hash. Ce qui fait beaucoup moins de données.


Message édité par Requin le 08-04-2003 à 17:19:53
Reply

Marsh Posté le 09-04-2003 à 08:17:35    

Extra merci beaucoup !
 
Avec les morceau théorique de google, jvais faire une présentation béton !
 
A+
 
Shaman


---------------
Le Smiley de la mort !! (8÷þ
Reply

Marsh Posté le 14-04-2003 à 09:04:18    

Hello,
 
Une dernière question. J'ai vu que après que chaque valeur de la table ai recu son hash code. Il sont indexé en compartiement en fonction de la valeur de hash générée.
 
QUel sont les critère pour les compartiments ??
 
Merci
 

Reply

Marsh Posté le 14-04-2003 à 10:38:15    

Aucune idée ; cela doit dépendre de l'implémentation.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed