Difference entre table de hachage et index ?
Dernière réponse : dans Programmation
Voila, tout est dans le titre, je tente de definir le terme de "table de hachage" en terme simple, mais google me renvoie vers des reponse un peu trop complexe ...
Si qlqun peut l'exprimer simplement ...
merci !![;)]( ";)")
Si qlqun peut l'exprimer simplement ...
merci !
Autres pages sur : difference table hachage index
Lassé par la pub ? Créez un compte
La caractéristique d'une table de hachage est d'introduire du chaos dans le stockage.
En effet à l'issu du hachage deux éléments proche se retrouve normalement éloignées, et deux éléménets eloignées se retrouvent normalement proche ce qui est la definition d'une transformation chaotique...
L'interet est de facilité des comparaisons d'égalité : deux éléments proches donc difficiles a comparer l'un a l'autre ( ex "ABCDEFGHIJKLMNO" et "ABCDEFGHIJKLMNP" ) vont avoir un code de hash different...
Par contre il plus difficile de faire des compaisons d'ordre...
En effet à l'issu du hachage deux éléments proche se retrouve normalement éloignées, et deux éléménets eloignées se retrouvent normalement proche ce qui est la definition d'une transformation chaotique...
L'interet est de facilité des comparaisons d'égalité : deux éléments proches donc difficiles a comparer l'un a l'autre ( ex "ABCDEFGHIJKLMNO" et "ABCDEFGHIJKLMNP" ) vont avoir un code de hash different...
Par contre il plus difficile de faire des compaisons d'ordre...
Fondamentalement, la technique du hash-coding est une simple variante d'une table avec un indexe. L'interet de cette variante est de pouvoir bénéficier des avantages des tables indexées sans pour autant gaspiller autant de place mémoire quand les indexes ont une grande plage de valeurs.
Le gros avantage des tables a indexe est de permetre de retrouver une donnée quasiment instantanément a l'aide d'une clé.
Le problème d'une table a indexe classique est qu'il faut consacrer une case de tableau a chaque valeur que peut prendre la clé. Et cela même si la table contient peu de données. Si la clé est composée de seulement 8 bits, cela fait 256 cases, ça va. Si la clé fait 32 bits, cela fait plus de 4 milliards de cases : Ca ne va plus.
Le gachis est d'autant plus manifeste si la table en question contient peu de données. 4 milliards de cases de tableau a stocker pour seulement 100 entrées réelles, cela situe le gachis.
Dans la technique de hash-coding, l'idée c'est que plusieurs valeurs de la clé peuvent mener a une même case. On réduit ainsi le nombre de cases nécéssaires.
L'inconvénient évident de la technique, c'est qu'on peut potentiellement se retrouver avec plusieurs données dans la même case. Cela oblige a biaiser en créant soit des listes chainées soit en stockant dans les cases adjacentes.
Le problème de l'implémentation de cette technique, c'est d'arriver a éviter que les données s'aglutinent dans les mêmes endroits du tableau. Mieux les données sont réparties et plus c'est rapide.
Il faut donc trouver une fonction de "dispersion" qui va ventiler au mieux les données dans toute la table le plus uniformément possible.
Comment faire ? Il faut d'abord analyser statistiquement le type de données contenu dans la table. Typiquement, si les valeurs des clés ont tendance a se suivre, la fonction doit disperser ces valeurs.
D'autre part, il faut faire attention a la taille de la table de hash. Trop petite, il y aura perte de performances, trop grande, il y aura perte de mémoire inutile.
Personnellement et bien que j'en ai parfois l'usage, j'ai plutot tendance a utiliser d'autres techniques car potentiellement c'est une technique qui récèle une potentialité de dégénérescence en cas de nombre de données trop importante ou d'un cas particulier de succession de clés qui provoque l'accumulation des données dans un coin de la table.
Le gros avantage des tables a indexe est de permetre de retrouver une donnée quasiment instantanément a l'aide d'une clé.
Le problème d'une table a indexe classique est qu'il faut consacrer une case de tableau a chaque valeur que peut prendre la clé. Et cela même si la table contient peu de données. Si la clé est composée de seulement 8 bits, cela fait 256 cases, ça va. Si la clé fait 32 bits, cela fait plus de 4 milliards de cases : Ca ne va plus.
Le gachis est d'autant plus manifeste si la table en question contient peu de données. 4 milliards de cases de tableau a stocker pour seulement 100 entrées réelles, cela situe le gachis.
Dans la technique de hash-coding, l'idée c'est que plusieurs valeurs de la clé peuvent mener a une même case. On réduit ainsi le nombre de cases nécéssaires.
L'inconvénient évident de la technique, c'est qu'on peut potentiellement se retrouver avec plusieurs données dans la même case. Cela oblige a biaiser en créant soit des listes chainées soit en stockant dans les cases adjacentes.
Le problème de l'implémentation de cette technique, c'est d'arriver a éviter que les données s'aglutinent dans les mêmes endroits du tableau. Mieux les données sont réparties et plus c'est rapide.
Il faut donc trouver une fonction de "dispersion" qui va ventiler au mieux les données dans toute la table le plus uniformément possible.
Comment faire ? Il faut d'abord analyser statistiquement le type de données contenu dans la table. Typiquement, si les valeurs des clés ont tendance a se suivre, la fonction doit disperser ces valeurs.
D'autre part, il faut faire attention a la taille de la table de hash. Trop petite, il y aura perte de performances, trop grande, il y aura perte de mémoire inutile.
Personnellement et bien que j'en ai parfois l'usage, j'ai plutot tendance a utiliser d'autres techniques car potentiellement c'est une technique qui récèle une potentialité de dégénérescence en cas de nombre de données trop importante ou d'un cas particulier de succession de clés qui provoque l'accumulation des données dans un coin de la table.
Lassé par la pub ? Créez un compte
