Je révise pour mon interro de structures de données, il y a 2 questions que je me pose.
 
La première, les tables de hachage:
J'ai bien compris que c'était des tableaux de listes mais je ne comprends pas comment fonctionne la recherche dans le tableau si les listes ne sont pas ordonnées.
Dans le cas d'un annuaire par exemple, qu'est ce qui fait que l'on rentre chercher dans telle liste qui correspond à une case X du tableau et pas dans une autre ?
 
La seconde, les listes et la recopie. Je vous copie colle la partie de cours concernée. J'ai quoted ce qui me plus bas.

 
C'est surtout ce passage là que je ne comprends pas, pourquoi on doit forcèment recopier. En quoi ne pas le faire nuit au programme ???
 
Un exemple siouplaît .
 
Merci
 
P.S. Au besoin les modos peuvent déplacer ça dans la cat programmation .

 
Les listes ne sont pas ordonnees donc on fait une recherche sequentielle : pour chercher dedans tu va regarder le premier element, si c'est pas le bon tu passes a l'element suivant et ainsi de suite...
MAIS la fonction de hachage devrait te repartir tes elements correctement eparpilles dans le tableau, si il y a des collisions, on pourra les stocker sous forme de listes (qui seront normalement pas tres grande donc il n'est pas necessaire de les trier ou faire un algo pointu de recherche dessus)
 
Par exemple on pourrait repartir le nom des personnes dans un tableau de 26 elements en fonction de la premiere lettre de leur nom : 1 element = 1 lettre. Mais voila que Patrick, Pierre et Paul commencent par la meme lettre P donc on a une liste de nom commencant par "P".  
Quand on recherche Paul, on va aller a la case "P" du tableau, on trouve d'abord Patrick, c'est pas lui qu'on cherche on regarde le suivant, Pierre, pas lui non plus, Paul ensuite... Bien sur, stocker l'annuaire comme ca c'est pas une bonne idee    
 

 
Bah ca depends si tu veux modifier ton objet ou pas.. Par exemple tu veux connaitre le nombre de chiffres qui constitue un nombre... exemple : 1000 bah dans une fonction qui calcule ca, tu va diviser 1000 par 10 jusqu'a avoir 0 en comptant combien de divisions tu as fait pour en arriver la et tu retournes 4... Mais t'aimerais continuer tes calculs avec ton 1000 du depart donc t'as du donner une copie a ta fonction au lieu de partager le meme nombre 1000 sinon tu va avoir un 0 apres cette fonction, ce qui ppurrait etre embetant... Pareil pour des trucs plus compliques

Merci
 

 
Ok pour le hachage, c'est bien ce que je pensai mais c'était pas très clair dans le sens ou le tableau ne mentionne pas explicitement que la case 0 est la première de l'alphabet ...  
Si tout le monde garde ses petites conventions dans la tête je risque pas de capter ou bien ce sera du "je pense que mais c'est pas sûr à 100% ..."
 
Pour la seconde, je me doute bien que si j'utilise 1000 pour un calcul, ça passe par une variable tampon. Donc à moins de modifier toute la liste pour un calcul, quelques variables buffer suffisent pour la plupart des cas, non  

Bon, soit j'ai pas compris ta question, soit tu connais pas tres bien ton cours
 
C'est seulement pour l'exemple qu'une case du tableau correspond a une lettre (qui est la premiere du nom de celui qu'on cherche ici dans l'exemple ) Ensuite ce n'est pas obligatoire que la case 0 soit la premiere lettre de l'alphabet... Cela depend de ta fonction de hachage qui repartit les elements : tu as une fonction de hachage "f( cle )" qui retourne la case qui lui correspond.  
 
Selon comment elle est definie, elle peut te dire que :
 
- la case 2 corresponde a tout les mots commencant par "b" (b etant la 2eme lettre de l'alphabet ?)
- la case 2 corresponde aux mots constitues de 2 lettres  
- ou plus complique : la case 2 corresponde a la "somme des lettres" d'un mot + la longueur du mot modulo 9 (9 serait la taille du tableau) egal a 2.  
Exemple : Anne = 2 car A = 1, N = 14 et E = 5, longueur du mot "Anne" = 4
f( Anne ) retourne (( 1 + 14 + 14 + 5 ) + 4) mod 9 = 2
 
Bref la fonction de hachage est a definir comme on veux mais  doit respecter quelques criteres... elle doit etre deterministe (tout le temps renvoyer la meme valeur pour une meme cle, pas de random quoi), uniforme ( pour eviter les collisions au maximum et avoir des listes trop longues ) et rapide a calculer ... voila donc y'a pas de conventions personnelles...
 
Sinon pour tes copies de variable, j'ai pas comprit la question !!

 
Merci, c'était le bout de cours qui manquait dans le pdf parceque je me souvient avoir entendu ça en cours mais lu nulle part ailleurs ...

De rien, au moins ca verifie si j'ai assez bien compris pour etre capable de m'exprimer clairement