Pode explicar o princípio do método de duplo hashing para resolver colisões em tabelas de hash?

O método de hashing duplo é uma forma de resolver colisões em tabelas de hash, onde, quando ocorre uma colisão, calcula-se um segundo hash, e o próximo índice para procurar o elemento é determinado com esse segundo hash.

Ideia:

• Existem duas funções de hash: h1(key) e h2(key).

• Ao inserir ou procurar um elemento, primeiro calculamos h1(key) — o índice inicial.

• Se a posição estiver ocupada (colisão), o próximo índice é calculado pela fórmula:

  índice = (h1(key) + i * h2(key)) mod tamanho_da_tabela, onde i é o número de tentativas (0,1,2,...)

Isto permite evitar colisões ao mover-se pela tabela com um passo que depende da chave, o que reduz a aglomeração em comparação com a sondagem linear.

Exemplo em Go:

func doubleHashing(chave int, i int, tamanhoTabela int) int {
    h1 := chave % tamanhoTabela
    h2 := 1 + (chave % (tamanhoTabela - 1))
    return (h1 + i*h2) % tamanhoTabela
}

Aqui, h2 nunca é zero e garante que percorreremos toda a tabela, se necessário.