La résolution par adressage ouvert commence la recherche à l'adresse fournie par la fonction de hash primaire, celle qu'on applique sur la clef. La première adresse inspectée est donnée par
Si H2 génère effectivement une permutation sur 0...n-1, cette méthode de sondage, ou probing, est garantie de visiter toutes les cases de la table, au plus une fois. L'algorithme d'insertion termine dès qu'on trouve une case inoccupée dans la table.
Fig. 1. Résolution par adressage ouvert. Ici, les cases grises sont occupées par des clefs déjà insérées.
L'avantage de cette méthode est qu'elle est très simple et n'utilise pas de structures de données auxiliaires. Si la table est suffisamment grande et faiblement occupée, le temps d'insertion est garanti constant: la probabilité d'examiner un grand nombre de cases avant d'en trouver une libre est très faible.
Le désavantage principal, c'est qu'elle repose justement sur une fonction de hash secondaire, sur lesquelles nous reviendront ultérieurement. Ces fonctions existent, mais doivent se plier à de nombreuses contraintes, ce qui ne les rends pas nécessairement universellement applicables. Certaines de ces fonctions demandent que la taille de la table soit une puissance de deux, soit de la forme 2k, d'autres encore qu'elle soit un nombre premier. Il existe toutefois des fonctions de hash secondaires qui n'exigent rien de particulier de la taille de la table.