Si la recherche linéaire avec incrément demande un paramètre γ calculé de façon à être relativement premier avec m, la taille de la table, la recherche par résidu quadratique va demander que la taille de la table soit un nombre premier, et, qui plus est, un nombre premier de la forme 4 j + 3.

Soit a₀ = H₁(k), la première adresse à être examinée. Si la clef que nous cherchons se trouve à l'adresse a₀, la fouille se termine avec succès. Si cette adresse ne contient pas la clef recherchée, nous allons procéder à l'examen d'autres adresses.

Avec la fouille par résidus quadratiques on examine, au t ^ième essai, les adresses

pour t = 0,...,¸½( m-1 ). On boucle jusqu'à ce que l'on trouve la clef, auquel cas le sondage termine avec succès, ou jusqu'à ce que nous atteignions deux cases vides, ou encore que nous ayons t = ½( m-1 ), alors le sondage termine avec échec.

Qu'est-ce que cette méthode a de nettement mieux que le sondage linéaire? Premièrement, la séquence des t ² se « délocalise » rapidement parce qu'elle croît très rapidement et, une fois considérée mod m, apparaît assez aléatoire. Deuxièmement, cette séquence est aussi une permutation des entiers 0,...,m-1.

Le seul problème réside dans la génération des nombres premiers de la forme 4 j + 3. Comme nous ne considérons pas les très grands entiers mais seulement de petits entiers de, disons, 32 bits, la tâche ne sera pas très ardue, même en employant un algorithme naïf.