Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?

Réponse : A. Après une collision, la position examinée ensuite est l'élément voisin, qui se trouve souvent dans la même ligne de cache ou dans la suivante, si bien qu'il faut moins d'accès mémoire

Sur les CPU modernes, lire la mémoire principale après un défaut de cache prend bien plus de temps que des calculs comme les comparaisons. Le sondage linéaire examine la position voisine après une collision : la plupart des sondages restent dans la même ligne de cache, et le préchargement aide aussi. Avec le chaînage, l'élément suivant d'une liste se trouve souvent ailleurs en mémoire, si bien que chaque pointeur suivi risque de provoquer un défaut de cache. Même à complexité temporelle égale en notation O, la vitesse réelle peut beaucoup varier selon la façon d'accéder à la mémoire. Toutefois, le sondage linéaire ralentit fortement aux facteurs de charge élevés, car les positions occupées se regroupent : on maintient donc le facteur de charge assez bas.