FICHIER DUPLIQUÉ AVEC UNE TABLE DE HACHAGE

WhiteHippo Messages postés 1154 Date d'inscription samedi 14 août 2004 Statut Membre Dernière intervention 5 avril 2012 - 22 mars 2011 à 21:02
Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 - 24 mars 2011 à 03:57

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/52968-fichier-duplique-avec-une-table-de-hachage

Bacterius Messages postés 3792 Date d'inscription samedi 22 décembre 2007 Statut Membre Dernière intervention 3 juin 2016 10
24 mars 2011 à 03:57

Salut,
deux remarques additionnelles:
- pense à nommer tes compos pour que ça soit plus explicite
- il faudra songer à utiliser une fonction de hachage plus efficace dans la procédure clef. En effet, même sans faire exprès, deux fichiers quelconques ont une assez bonne probabilité d'obtenir la même clef. En fait, mathématiquement, et en supposant une fonction idéale, si tu calcules la clef de 65536 fichiers distincts, la probabilité qu'une clef survienne deux fois est de 50% (1/2 - paradoxe des anniversaires). Et ta fonction n'est pas idéale (il n'en existe aucune dans le cas général en fait), ce qui augmente encore plus la probabilité d'un doublon. Tu peux t'inspirer de quelques fonctions simples et rapides qu'on peut trouver sur internet (du type hachage universel, etc..), et une bonne idée serait d'utiliser un Int64 à la place d'un Cardinal. Ca devrait être bon à ce point. Evite bien sûr les fonctions de hachage cryptographiques car elles sont trop lentes (et pas besoin de sécurité ici mais plutôt de vitesse).

Sinon c'est pas mal.

Cordialement, Bacterius !

WhiteHippo Messages postés 1154 Date d'inscription samedi 14 août 2004 Statut Membre Dernière intervention 5 avril 2012 2
22 mars 2011 à 21:02

Bonsoir

Une petite remarque en passant :
Dans UTable tu déclares un type "table = array[0..N] of Liste" hors ta fonction "hachage" renvoie forcément un nombre supérieur à 0 du fait du +1 "result := clef(c) mod N + 1"; donc tu n'utiliseras jamais la cellule indexée par 0.

N.B. Il n'est pas nécessaire de laisser dans ton zip les fichiers inutiles (comme les .dcu).

Cordialement.