Analyse du hachage avec essais lin\'eaires

Parmi les m\'ethodes efficaces de gestion de donn\'ees ``en place'', l'une des plus anciennes est celle du hachage avec essais lin\'eaires ({\em linear probing hashing\/}). L'algorithme correspondant est particuli\`erement efficace tant que le taux de remplissage reste mod\'er\'e mais s'effondre, en pr\'esentant une violente "transition de phase" lorsque la table devient pleine.

Le hachage avec essais lin\'eaires poss\`ede une tradition d'analyse qui remonte aux travaux de Knuth en 1962 et se relie \`a des fonctions d\'ej\`a \'etudi\'ees par Ramanujan en 1913. La structure combinatoire se relie \'egalement \`a la connectivit\'e dans les graphes al\'eatoires ou aux gains cumul\'es dans les s\'equences de ruines de joueurs. L'expos\'e fera un survol d'une grande diversit\'e de probl\`emes associ\'es \`a l'un des algorithmes les plus fondamentaux de l'informatique tout en pr\'esentant les r\'esultats r\'ecents d'analyse en distribution, lesquels caract\'erisent tr\`es pr\'ecis\'ement les temps de calcul attendus.