Hashing

HASHING (Transformação de Chaves)

1. Introdução
Os algoritmos que realizam a pesquisa linear (O(N)) e a pesquisa binária (O(log2N)) comparam a chave procurada com todas ou com parte das chaves armazenadas na estrutura de dados que contém os registros, logo o tempo médio de resposta dos mesmos aumenta com o aumento do número N de registros.
Existe uma técnica surpreendentemente simples e eficiente chamada hashing, que permite armazenar e localizar um registro através de um cálculo aritmético baseado no valor de sua chave.
Deste modo, o tempo de resposta médio para executar estas operações independe do tamanho da tabela, portanto são feitas a um custo O(1). É aplicada principalmente em compiladores, verificadores de ortografia e em gerenciadores de bancos de dados, mas existem numerosas outras aplicações.
O princípio básico da técnica hashing é simples: em vez de o índice de cada registro ser definido segundo a posição relativa de sua chave em relação às demais, o índice é calculado de forma absoluta através de uma função conveniente, chamada função de hashing, ou função de espalhamento. Em outras palavras, a função de hashing transforma ou converte o valor da chave de cada registro num índice (endereço ou posição) da tabela hash (normalmente um vetor), permitindo armazenar e acessar diretamente cada registro. Estes índices calculados (endereços da tabela onde os registros serão armazenados e pesquisados) parecem ser aleatórios, não havendo uma conexão óbvia entre eles e as chaves que lhe deram origem.
Infelizmente existe um inconveniente: duas ou mais chaves distintas podem ser indexadas com o mesmo índice de entrada na tabela e quando isso ocorre, diz-se que houve uma colisão. Como dois registros não podem ocupar a mesma posição na tabela, é necessária a utilização de algum método para contornar o problema das colisões.

A inserção, pesquisa e exclusão de registros

através de hashing consiste basicamente:
1) Na transformação da chave K