Tabelas de dispersão

Tabelas de dispersão O que é?

Tabela de Dispersão é uma estrutura de dados especial que associa chave de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado.

As Hash Tables são o método mais rápido e eficaz de armazenamento de dados, que permite guardar um maior número e quantidade de informação.
Como funciona? Uma tabela hash é construída através de um vetor de tamanho indeterminado, no qual se armazenam as informações
Nele, a localização de cada informação é dada a partir do cálculo de um índice através de uma função de indexação, a função hash
Como funciona

Para que é utilizado? (cite aplicações práticas) Suas aplicações incluem banco de dados, implementações das tabelas de símbolos dos compiladores, na programação de jogos para acessar rapidamente a posição para qual o personagem irá se mover entre outros.

Funções de dispersão O que é? Métodos (divisão, multiplicação, dobra, análise de dígitos) Para cada um deles aborde, no mínimo: eficiência, algoritmo
.

a - A função de dispersão mapeia uma chave de busca num índice da tabela. Por exemplo adotamos como função de hash a utilização dos dois últimos dígitos do número de matrícula. A implementação dessa função recebe como parâmetro de entrada a chave de busca e retorna um índice da tabela.

Divisão:

A melhor estratégia para desenvolvermos programas é dividirmos um problema grande em diversos problemas menores. Uma aplicação deve ser construída através de módulos independentes. Dentro de cada módulo, a realização da tarefa é dividida entre várias pequenas funções.
É um método particularmente fácil e eficiente, sendo por isso muito empregada.
Temos uma chave x é dividida pela dimensão da tabela m e o resto da divisão é usado com endereço-base: h(x) = x mod m

Dobra:

Suponhamos uma sequência de dígitos escritos num pedaço de papel, este método