Hash duplo resolve um dos problemas da sondagem quadrática, mas também tem uma desvantagem. Qual é a desvantagem?
Passo 1
Bora resumir: a questão é sobre colisões em hashing (endereçamento aberto). Quadratic probing resolve o problema do agrupamento primário mas ainda sofre clustering secundária, e o double hashing entra pra resolver isso usando duas funções de hash. Vamos precisar entender como ele funciona e por que isso traz um custo extra.
Passo 2
A ideia do hash duplo é usar uma função principal h₁(k) pra posicionar e uma secundária h₂(k) como passo de salto entre tentativas: h(k,i) = (h₁(k) + i \cdot h₂(k)) mod m. Assim cada chave tem sua sequência quase aleatória de posições, evitando tanto clustering primário quanto secundário.
Passo 3
O problema é que agora, a cada sondagem, a gente precisa calcular h₂(k) além de h₁(k). Isso dobra (ou quase) o trabalho de hashing em cada tentativa de inserção/consulta, gerando um overhead bem maior do que sondagem quadrática.
Passo 4
Além disso, para garantir que a sequência de sondagens realmente percorra todas as m posições (ou boa parte delas), o tamanho da tabela m e h₂(k) têm que ser coprimos—ou seja, m geralmente precisa ser primo e h₂(k) não pode ter fator em comum com m. Isso impõe restrições de projeto da tabela e da função.
Passo 5
Por isso, apesar de eliminar o clustering secundário, o double hashing traz desvantagem de desempenho (cálculo extra) e exige cuidado na escolha de m e de h₂(k).
Resposta
A desvantagem é o aumento do custo computacional, pois é preciso calcular duas funções de hash a cada tentativa, além de haver a obrigação de escolher o tamanho da tabela (e h₂) de forma a serem coprimos para garantir cobertura completa das posições.