Idee et operations
Une map associe une clef a une valeur. Operations: bind (insert/maj) et lookup (recherche).
Map par liste
[(2,8)] -> [(5,3)] -> [(7,1)] -> NULL
lookup(5) => 3
Simple a coder, mais lookup en O(n).
Mini traducteur
On stocke des indices de tableaux de mots. Cela simule un dictionnaire.
Demo: make demo4
Vers le hachage
Une fonction de hachage mappe la clef vers un index. Les collisions se gerent par chainage ou sondage.