Discussion :

[psgkiki]

Bonjour a tous,

J'aimerais savoir quelle est la différence entre l'utilisation de tableaux dynamiques et l'utilisation d'une table de hachage.

Prenez par exemple la réalisation d'un correcteur orthographique.

Les tableaux dynamques, je sais qu'ils permettent d'allouer autant d'espaces que nécessaire et les tables de hachage s'utilisent avec la notion de clés.

Mais y a t-il une réelle différence entre les 2 ? Faut-il utiliser plutot l'un que l'autre ? Niveau temps d'exécution, quelle solution serait la plus rapide ?

Merci pour votre réponse

Cordialement

[Médinoc]

Ce n'est pas du tout la même chose.
La table de hachage, c'est pour fragmenter un ensemble de clés non-triées en plusieurs sous-ensembles (généralement, ces sous-ensembles sont sous la forme de listes chaînées, triées ou non).

Un tableau dynamique n'a pas du tout de notion de clé, c'est juste une zone où l'on met des données...


Par contre, tu peux toujours faire un ensemble de clés qui soit implémenté sous la forme d'un tableau dynamique, trié ou non.
Le fait que le tableau soit trié permet une recherche plus rapide, en O(log(n)), mais l'insertion est beaucoup plus lente, en O(n).

Si tu as besoin d'initialiser ton tableau une fois puis de faire des recherches dedans, il peut être une bonne idée de le remplir puis le trier, pour pouvoir par la suite faire des recherches dichotomiques...