Quelle est la différence entre un tableau et une table de hachage dans un langage de programmation?


Réponse 1:

Les tables de hachage utilisent des tableaux. Les tableaux ont une propriété importante pour le hachage: vous pouvez accéder à n'importe quel élément en un temps constant si vous connaissez son index.

Vous pouvez utiliser des tableaux pour des compartiments. Supposons que vous vouliez compter le nombre de chaque lettre dans un texte, par exemple, pour concevoir quelque chose comme du code Morse. Vous créez un tableau avec 26 entrées (pour l'alphabet romain simple sans accent). Chaque fois que vous voyez une lettre, vous calculez l'index et accédez à cette entrée dans le tableau.

Les tables de hachage étendent cela pour des clés arbitrairement longues. Vous calculez un hachage de la clé et accédez à cet index. Le problème est lorsque plusieurs clés ont le même hachage. Il existe différentes façons de résoudre ce problème, dont certaines vont à l'encontre du but du hachage (mais sont faciles à mettre en œuvre). Certains d'entre eux ne le font pas et maintiennent la propriété de temps constant, au moins en moyenne.

Le meilleur que j'ai vu, c'est que le rehash add-the-hash, qui si la mémoire sert d'il y a des décennies, Gonnet et Munroe a prouvé qu'il avait en moyenne un peu plus de 4 accès avec un facteur de charge de 50%, quelle que soit la taille du table de hachage. Cependant, cela nécessite l'utilisation de nombres premiers, ce qui rend sa mise en œuvre délicate. Vous devez trouver les nombres premiers en quelque sorte. Heureusement, les tables de hachage ne deviennent pas si grandes que cela devient ridicule.