Função de hash §

---

Uma função hash é um algoritmo que transforma dados de entrada (chave) em um valor numérico que serve como índice na tabela hash. É como um processador que decide onde cada item deve ser armazenado.

Note

Muitas vezes, a função hash é chamada de função de espalhamento ou de dispersão

Características de uma boa função hash §

1. Determinística §

• Mesma entrada sempre produz mesma saída
• Fundamental para consistência

2. Distribuição Uniforme §

• Espalha os valores uniformemente
• Minimiza colisões

3. Eficiência §

• Rápida de calcular
• Baixo custo computacional

4. Efeito Avalanche §

• Pequenas mudanças na entrada causam grandes mudanças na saída

Métodos Comuns de Hash §

1. Método da Divisão §

public int hashDivisao(int chave) {
    return chave % tamanhoDaTabela;
}

Note

Geralmente tamanhoDaTabela é um número primo para evitar colisões, uma vez que números primos possuem menos divisores.

Exemplo:

• Chave: 234
• Tamanho da tabela: 10
• Índice = 234 % 10 = 4

2. Método da Multiplicação §

public int hashMultiplicacao(int chave) {
    double A = 0.6180339887; // Constante A (0 < A < 1)-> proporção áurea
    double temp = chave * A;
    double parteDecimal = temp - Math.floor(temp);
    // ou double parteDecimal = temp % 1
    return (int)(tamanhoDaTabela * parteDecimal);
}

Note

Geralmente tamanhoDaTabela é potência de 2.

A escolha de “A” pode afetar a qualidade da distribuição. É importante que “A” não seja muito próximo de 0 ou 1 para evitar padrões de distribuição inadequados e aumentando as colisões.

Referências §

---

Aula 7 - Hash Table