Recherche, tri, table

Résumé du document

[...]
Nous avons vu dans ce chapitre que pour gérer des données par exemples des clients on pouvait se servir d'une structure de type clients et ranger ces derniers dans une table ou un tableau.

Il est important à ce niveau de faire quelques remarques

- Si on fait des recherches fréquentes il est intéressant de trier les données de façon à pouvoir y accéder rapidement par dichotomie.
- Par contre, si l'on ajoute souvent des données, il est nécessaire de bien insérer de façon à maintenir le tableau trié (-> implique décalage, très lourd si il y a beaucoup de données)
- Pour un tableau non trié, insertion très rapide. A l'inverse la recherche devient fastidieuse.
-> Il faut donc trouver une solution pour pouvoir trier et rechercher rapidement.

[...] Le rangement dispersé est un rangement où la fonction d'adressage est directement calculée.
Le hachage a la particularité de permettre un temps de recherche constant, c'est-à-dire indépendant du nombre de données.

Ex : on veut gérer une table de personnes indexées par leur prénom. A chaque prénom on associe un entier h(i) de 0 à 12 en procédant comme suit :
- Attribuer aux lettres leur rang dans l'alphabet (A -> 1, B -> 2 etc.)
- Ajouter les valeurs des rangs pour chaque lettre du nom
- Ajouter au nombre obtenu le nombre de lettre de i
- Prendre le reste de la division de ce nombre par 13

On obtient :
h(« serge ») = ((19+5+18+7+5)+5)mod 13=7
h(« odile »)=11
h(« anne »)=12
h(« luc »)=0
h(« basile »)=2

On peut placer les prénoms dans un tableau en utilisant comme position la valeur de h(i). Le problème est que si l'on veut insérer Paule, on constate que h(« paule »)=2. On dit qu'il y a collision primaire entre paule et basile. Toute la difficulté du hachage consiste à trouver une fonction de hachage. Etant quasi impossible de trouver une fonction parfaite, il va donc falloir prendre en compte les collisions et le gérer (...)

Extraits

[...] Recherche, trie, table Dans ce chapitre on utilisera très souvent des tableaux t muni d'un entier n. [...]