O Hashing Interno

Hashing Interno

Hashing é uma técnica que consiste em receber uma chave hash e aplicar uma função hash a ela para obter determinado valor. Isso pode ser usado, em um sistema de banco de dados, para calcular o endereço de memória de um registro. Geralmente, utiliza-se uma tabela hash, que costuma ser um array, para armazenar os valores de saída. A escolha da posição da tabela a ser acessada é calculada através de um determinado processo aplicado à chave hash.

Alguns exemplos em C, considerando h a função hash que retorna o índice na tabela correspondente à chave k e m o tamanho da tabela:

int h(int k) {

        return k % m;

}

int h(char k[6]) {

        int i, r = 1;

        for(i = 0; i < 6; i++) {

                r = r * k[i];

        }

        return r;

}

Um problema possível é que chaves diferentes correspondam ao mesmo valor de retorno, ou seja, aplicar a função em dois registros diferentes poderia resultar na obtenção do mesmo endereço de memória.

Para solucionar isso, utilizam-se técnicas chamadas resolução de colisão:

• Endereçamento aberto: avança-se na memória até que uma posição livre seja encontrada.
• Encadeamento: Vários locais de overflow são mantidos, além de um campo de ponteiro no local de cada registro. Quando ocorre colisão, o próximo local de overflow é utilizado, e o ponteiro é definido para indicá-lo.
• Hashing múltiplo: Em caso de colisão, outra função de hash é aplicada. Em caso de nova colisão, pode-se repetir o processo ou utilizar o endereçamento aberto.

Cada método requer os algoritmos de inserção, recuperação e exclusão de registros.

Para reduzir as chances de colisão, podemos escolher um número M de locais para armazenar um número r de registros que esperamos armazenar, de modo que (r/M) esteja entre 0,7 e 0,9. Isso significa que serão ocupados entre 70% e 90% dos endereços listados na tabela hash, o que produz chances menores de colisão enquanto não desperdiça muito espaço.

...