Hachage non uniforme: Apparition et taille des composantes geantes
Jean-François Marckert (Universite de Versailles)Le problème du hachage peut se modéliser par un problème de parking où $m$ voitures se garent sur $n$ places numérotées de $1$ à $n$. La voiture $v_i$ choisit la place $k$ avec probabilité $p_k$. Si la place $k$ est déjà occupée, la voiture $v_i$ se garera sur la première place libre parmi les places suivantes $k+1, k+2, …$ (avec la convention $n+1=1$).
Quand les probabilités $p_k$ sont toutes égales, ce problème est le problème de parking uniforme (usuel). Il correspond exactement en informatique au hachage linéaire standard.
Ici, on s’intéresse au cas non uniforme : les probabilités ne sont plus toutes égales, et certaines places sont plus “souvent” choisies que d’autres.
On étudie plus particulièrement la taille des blocs (places successives occupées) dans le parking lorsque les nombres $m$ et $n$ de voitures et de places grandissent tous deux, tout en restant proportionnels $m=\alpha\, n$ avec $0 <\alpha <1$.
On montre alors qu’il existe une fonction de seuil pour l’apparition d’un bloc géant (de l’ordre de $n$). On compare ces résultats à ceux du cas uniforme.
On montre que le déplacement total des voitures pour le remplissage du parking est de l’ordre de $n^2$ (contre $n^{3/2}$ pour le cas uniforme). Ceci fournit donc, entre autres, une analyse en moyenne et dans le pire des cas du problème du hachage lineaire.