Tables de hachage VS tableaux associatifs

Question

Récemment, j'ai lu des articles sur tables de hachage dans un livre très célèbre " Introduction aux algorithmes ". Je ne les ai pas encore utilisés dans des applications réelles, mais je veux le faire. Mais je ne sais pas comment commencer.
Quelqu'un peut-il me donner quelques exemples d'utilisation, par exemple, comment réaliser une application de dictionnaire (comme ABBYY Lingvo) en utilisant des tables de hachage ?
Et enfin, j'aimerais savoir quelle est la différence entre les tables de hachage et les tableaux associatifs en PHP, c'est-à-dire quelle technologie dois-je utiliser et dans quelles situations ?
Si je me trompe (je vous prie de m'excuser), corrigez-moi, car en fait je commence avec les tables de hachage et je n'ai que des connaissances (théoriques) de base à leur sujet.
Merci beaucoup.

Answer 1

En PHP, les tableaux associatifs sont implémentés comme des hashtables, avec quelques fonctionnalités supplémentaires.

Cependant, d'un point de vue technique, un tableau associatif n'est pas identique à un tableau de hachage - il s'agit simplement de mis en œuvre en partie avec un hashtable en coulisses. Parce que la plupart de son implémentation est un tableau de hachage, il peut faire tout ce qu'un tableau de hachage peut faire - mais il peut faire plus, aussi.

Par exemple, vous pouvez parcourir un tableau associatif à l'aide d'une boucle for, ce que vous ne pouvez pas faire avec un tableau de hachage.

Donc, bien qu'ils soient similaires, un tableau associatif peut en fait faire un superset de ce que peut faire une table de hachage - ce n'est donc pas exactement la même chose. Considérez-les comme des tables de hachage avec des fonctionnalités supplémentaires.

Exemples de codes :

Utiliser un tableau associatif comme une table de hachage :

$favoriteColor = array();
$favoriteColor['bob']='blue';
$favoriteColor['Peter']='red';
$favoriteColor['Sally']='pink';
echo 'bob likes: '.$favoriteColor['bob']."\n";
echo 'Sally likes: '.$favoriteColor['Sally']."\n";
//output: bob likes blue
//        Sally likes pink

Boucle dans un tableau associatif :

$idTable=array();
$idTable['Tyler']=1;
$idTable['Bill']=20;
$idTable['Marc']=4;
//up until here, we're using the array as a hashtable.

//now we loop through the array - you can't do this with a hashtable:
foreach($idTable as $person=>$id)
    echo 'id: '.$id.' | person: '.$person."\n";

//output: id: 1 | person: Tyler
//        id: 20 | person: Bill
//        id: 4 | person: Marc

Notez en particulier comment, dans le deuxième exemple, l'ordre de chaque élément est maintenu (Tyler, Bill Marc) en fonction de l'ordre dans lequel ils ont été saisis dans le tableau. Il s'agit d'une différence majeure entre les tableaux associatifs et les tables de hachage. Une table de hachage ne maintient aucun lien entre les éléments qu'elle contient, alors qu'un tableau associatif PHP le fait (vous pouvez même trier un tableau associatif PHP).

Answer 2

Les tableaux php sont fondamentalement des tables de hachage

Answer 3

La différence entre un tableau associatif et une table de hachage est qu'un tableau associatif est un type de données, tandis qu'une table de hachage est une implémentation de données. Il est évident que le type de tableau associatif est très important dans de nombreux langages de programmation actuels : Perl, Python, PHP, etc. Une table de hachage est la principale façon d'implémenter un tableau associatif, mais pas vraiment la seule. Et les tableaux associatifs sont la principale utilisation des tables de hachage, mais pas vraiment la seule. Ce n'est donc pas qu'ils sont identiques, mais si vous disposez déjà de tableaux associatifs, vous ne devriez généralement pas vous soucier de la différence.

Pour des raisons de performances, il peut être important de savoir que les tableaux associatifs de votre langage préféré sont implémentés sous forme de hachages. Et il peut être important d'avoir une idée du coût de cette implémentation. Les tables de hachage sont plus lentes et utilisent plus de mémoire que les tableaux linéaires tels que vous les voyez en C.

Perl regroupe les deux concepts en appelant les tableaux associatifs des "hachages". Comme un certain nombre de fonctionnalités de Perl, ce n'est pas tout à fait faux, mais c'est bâclé.

Answer 4

Un tableau en PHP est en fait une carte ordonnée, pas un tableau de hachage. La principale différence entre map et hashtable consiste en l'incapacité de se souvenir de l'ordre dans lequel les éléments ont été ajoutés. D'un autre côté, les hashtables sont beaucoup plus rapides que les maps. La complexité de la récupération d'un élément dans une map est de O(nlogn) et dans une hashtable de O(1).

Answer 5

Un tableau associatif est un tableau dont les éléments ne sont pas accessibles par un index, mais par une clé. La façon dont cela fonctionne en interne est spécifique à l'implémentation (il n'y a pas de règle sur la façon dont cela doit fonctionner). Un tableau associatif peut être implémenté par une table de hachage (la plupart des implémentations le feront), mais il peut aussi être implémenté par une sorte de structure arborescente ou une liste de saut, ou l'algorithme itère simplement sur tous les éléments du tableau et cherche une clé qui correspond (ce serait terriblement lent, mais cela fonctionne).

Une table de hachage est un moyen de stocker des données où les valeurs sont associées à des clés et où vous avez l'intention de trouver des valeurs pour les clés dans un temps (généralement presque) constant. Cela ressemble exactement à ce que vous attendez d'un tableau associatif, c'est pourquoi la plupart du temps les tables de hachage sont utilisées pour implémenter ces tableaux, mais ce n'est pas obligatoire.