A pesquisa seria implementada em uma linguagem procedural, como
lookup(key){
int h1 = hash1(key);
if(table[h1%table.length].key == key){
return table[h1%table.length].value;
int h2 = hash2(key);
if(table[h2%table.length].key == key){
return table[h2%table.length].value;
return null;
}
Sem loops, sem complexidade, nada que faça a pesquisa demorar mais do que um constante pior momento.
A mágica que faz este trabalho está na lógica de inserção e repetição e exige que nenhum elemento de 3 mapeie para o mesmo par de hashes ou, mais geralmente, para cada conjunto de elementos n
, deve haver pelo menos n
hashes exclusivos .
Algumas implementações requerem que a função hash seja sintonizável com um parâmetro para que possa selecionar 2 parâmetros arbitrários para o hash. Então, quando a pré-condição acima for violada, ela selecionará 2 novos parâmetros e refazer a gravação.